Advent of Code 2023 - Day 25
Sample
sample = """
jqt: rhn xhk nvd
rsh: frs pzl lsr
xhk: hfx
cmg: qnr nvd lhk bvb
rhn: xhk bvb hfx
bvb: xhk hfx
pzl: lsr hfx nvd
qnr: nvd
ntq: jqt hfx bvb xhk
nvd: lhk
lsr: lhk
rzs: qnr cmg lsr rsh
frs: qnr lhk lsr
"""
"jqt: rhn xhk nvd\nrsh: frs pzl lsr\nxhk: hfx\ncmg: qnr nvd lhk bvb\nrhn: xhk bvb hfx\nbvb: xhk hfx\npzl: lsr hfx nvd\nqnr: nvd\nntq: jqt hfx bvb xhk\nnvd: lhk\nlsr: lhk\nrzs: qnr cmg lsr rsh\nfrs: qnr lhk lsr\n"
Input
input = """
bjk: mzl dlz gln
nbx: tsz
rrl: zvd dxn
xln: vbb tst gfr
kth: nrm bkc
krf: ddr crg rtg
zhj: lbj
qsn: tqq grc
dkg: drd cxt hvz jvg qrk pvv
vhx: jfx ffm
bfm: kdl
gpz: nnb
dpr: msg thp tft vpn
zdd: gmv
lhk: qst
psv: bvz dch
zbr: bfm nhk jdf qfk
rtg: zjk mbp
zvg: str qtx
xrt: sgv vjn jxf
cfk: pxr tcb
jbl: xxk qnj hpz jdk vhl
vtf: gmn fjt txg
lnq: tbm
dcx: thf sln vsp
vnr: hrj kss tbm
qlm: bxp
plf: brz
gsb: kdn hbt
qtk: bkr zcz qpp
pmh: mpj lgc
nnf: mlt njq ldv
cbp: nph fvc qsv
jjm: hcf kdn qzv xrb
rhz: kdl klh pvx pnj xdv
ztt: slt lpz jnv qst
vtl: cbx
zcm: jcn dkg pgc zhl
ncn: vvn cbb mkp
fxk: knj pdq ftp jcc
prs: xks
lsg: jjr ghr
qdh: hcv dgb
gfr: bgq ddv
vgn: rdd
tjr: lxb
bzg: ddt drd
nsp: mzl
grh: zql rds
kkx: hbh qqr zdd fvd
gph: gfl nft
dkr: szb nbs rbk flx
pcn: dgn sjf tnq gbx
dcr: vst tbx bpl lnl hqf
mgg: mjc mgd
qkv: fpq ljz svr plf lpg
trs: bfs bmx
plz: xzg
fzj: cbv bsj
fhq: vfj mdb bmh xtx
trt: cpt xql
ccq: tkj xmj zbf rpt
bdc: nhc vkm
ffb: kxn lxs svr qht
qnj: vzd czb
ctq: hhj mlr
qjp: rxn fgf qld kdn
pzv: mnx
tjs: mdl kfb qtn tqs
gdv: chm cms rbk hkh
jdk: xvc zgb
qdd: nhh tgd ccv
svr: kxn
gqs: cfn fhj
rgb: shz rbj sxc
nlj: blv jbg vnt tnf
gtm: dfn xzm cls
gdg: zzk
qhl: mgl flz
hcv: gpp
rvr: mjd qpp grt pmh rrd
pbx: cdl qvx cdv
rqt: fhk nzv
qgd: gqs tpv hbh
dht: snk fxx nsx vbt
xsb: sfj plv
nsv: mxh
gsj: dmb srn jfx cbv
jkx: tsr vvx hmm
ktn: fgs vcn lqx
mdl: qxs rzd
xtn: xdd qgb hsh xjn nbz
xzm: xct
zkf: nxs fvn
kst: lnd
czb: cmb
str: hrj
jfx: ddn pnr
cjx: hvp vlt vbx gsf grr bbs qgb
vkr: prf frr jks
jbp: mjm lqs dks
mmv: qld
bgl: pnr hzj csb zgh jqj qdh xnb
dvp: hrz txd
cpt: sqr
frs: xts rzg
zmj: jjf nsn
bpj: fms ghz xsq bdp
hcr: hvp fjt qrk cfc
kgr: mvr cjr
rkv: xtb mjt zhj
nqb: nhf
dtx: bcz qck
lfp: mvx pkl
lbd: lhg knk cls
chd: zpf mvx
sxr: vvx drp dmj jvz
zph: mpg zfv dpj tjr
kpd: nhf qzn mlx rkz kmp
fng: phh hnr gbx lsg
rzv: bth rgb svm xgv
jqz: bnd jqx qkm
fqx: gjf ddr dcs stq
kbg: xzg
vjl: lht zhv pfc mbs
ljc: sfs xqx mch cmv
xdc: fdb smt njq xrq
qxd: brz rqn
sln: cmb lqs
hgz: zcv vxj rpt
czm: tcj
dml: zrm bdc hdc
dbl: jnv zjk
crf: zff kll ckq pll
vmp: hpm qkm gcv
dbv: rch fdd qxr qbh zrh
qzn: mnm brz
lnb: ljf
rbb: xdv fcj flt nsp
cxs: cpm kbt sgn
dcq: rnf tbh gpz
nnt: gfl txd
slp: pkz
tfd: czf xjj xql vkx
qxx: pmh zpf jbg gbn
vjx: hhn cnf
qdx: fpq jtg
rxk: chg xqx
tvn: gmv
mqg: mzt qzh
sch: kkv bjk
mpg: xmt ndd rnf fng
nfg: ksz nft nqs bqd bxq gtm
pbr: czm ctg vbt zgt
hvz: gdg jxf
pzr: qbb hbt bvf
hpz: qsf xts xxk
ckz: jmd fzv ssl kbg
ljt: xbp btp ncn nhq
rsg: dct vrf
shp: vqh cbr bgj zvr xcs khl cvs
pgc: kcq zdd pkp rnc
vlb: jtg vnt
gzb: jrp
hkd: cdl jmd cfp
rmq: vtf xzv drt sms fvj qct
qjf: zvg lct flh dsn
mxh: dtx cqn gdl
vsg: bfp sln zmq
xdj: dtp rxd sfl lld
xnn: lrk
ttd: qck rnq xfg
kpg: qht fxj xfk drp
vks: hcn mhc jqn flh fjx
rtc: kmh msf lbj fhb
slb: zfb htc stq scx
lrd: plk dct zkf rck
kkv: vqn
gzh: znv lsg dmx hpm mnx
dbx: ftp xdx rlq nsx
znv: mrt zvj
bbv: hkd jmc nqj jrh
phb: sxk jbp
cfn: bqt
svx: pgs cmh lpg jqk
nhk: qzv ctx vxj
pkp: lbb tcp gmp bfp
nvt: gvt zvg zpz
zff: xgv bvk
qmg: zvj tbh
hld: dfs btt dcg tpp
gjp: sxc cst nxm phx
tdx: txh ptl nsh mht lch vsp
qdb: rdh
jjj: sdz zzj xms zhg
jdq: shz zkf pkj
mzt: rvz gzb
tsg: bvk sdz
fjt: plv lmz rrt
tcb: vpm zgh
gpm: bfs ddt bnj ktm
ddv: rxm ghq
xdf: vmt
jmd: vlq vbj fbn cbp
cst: tnx
pkk: svj
mnr: crp sbs fvd
tpp: nsx skj ddv
qlj: vkr gdr xkq pvk
slt: jtb cxb
bcs: flp
dvv: brp xnn dps jtn
plk: gxb pvx
xsp: vlq ttj
kgx: qhl lld nrl lvl ldm xxt
xnj: tvk
bxl: qdx ddg xpx krv
brp: lbb bnm mfl
jlt: dfn mnm jtn ctv qtk
dfx: tzx ppd
jkr: bbs fnd nlq zrm
jhj: pjx tlf fnc crn
ctp: xrp dzg nfz
rvh: mnx
xns: xbr
bmh: llm tmj
kgf: snl
ldh: bbd jdm ghq
kzm: xjh
vpt: hbt xdl ccn
hvp: cgk bdf
jjr: mtv kxn
tks: ztl xlk gmp rxx
zpz: mqt ghq
hrp: tbv ljz qqr lrp
bjh: pjm fcv cbv
klt: lml flx gvn mmn
pjt: zhj fxx pch mmn
zbf: zvd
mnq: xtv xkb vvh vbx
hrl: nhq jks
msd: ppd cdl
kkd: vjs mrv zhs bzh
fvn: snk
gbs: zcp nft
ztl: ddg
blf: bzv kgr mjt
hzq: jjs pnd pnr
qcs: sbx hsb chm xtx
fpf: gqv drp msz jxf
znd: sxh vzd frh cxs slp
zmq: xjn
xrb: tvk rhc
tzc: nbj pcd tjg mnx
gqj: ljc rhc
mjv: fdb kks knj
mlr: qbb chg
gkb: tnf cfn blx
xxg: qtt rpv jrh zmr fpc
kvl: gdr dmx xbp xjh vvs
xqb: tnz xvb
ghr: cfc nhf
kbb: xqb vkx bkc
gbx: ctv ccv
dgb: qfz mbp
xct: jvz krv
fxz: jts dmj
ffx: kgr cdl jjf sxc
tft: xpq zsr mff bxk
nhc: zcs
drd: jjr
mkp: bhh vph
tpx: zhv lkq
hqf: ghq
brr: zqr hdz nft qsq qcm
mgh: cmb bhh
xvc: lst
pdq: tpx dbs qdh
hlf: fnc
zhv: gfp
dbs: xss htz
qsf: dsm dks fvj bnj bxq
ldm: lvd jbx slp
xgq: pkl cnf hdv
lpd: nzv jjs vdf
tkr: nhf vlr sxk hnr
qbh: hcs lxn vjx lvs
mch: nbs
lsq: kpc bfs hhn
hlh: xsq bvf rrq vhx
xdx: svm kbg tnx rxm
vcg: crz pvq lqs xfr dhf
jkk: bgn qtb
xtz: nbx pxr qtx fdq vqn
ssl: qfz mlr
fmk: fjx kll nsv dtx zvr
prb: mjv ckq jnv rmn
gfg: dnj flm
nqd: mnj nkl qxs cjg
rjs: rzg
tkg: fgd kcn krv dpj rjd
zgv: tvn lmz
xmg: zcv qvx xsp
gpf: njq hkx bvk
xzx: tnx
bds: vmn xtd nxs ddr
tst: jhk vpm gfp sxc
sqk: phg bvs
hcn: qpb qlm kgr
nxr: qpk xkb dcq klr
bvt: kss tnx fqj kgc
tlf: qgb
zmh: ddg zmk zsp rpq
jzr: mbj xcs plz
qtp: ffv ntj gkl
ntr: mnl cbp nkl
rnq: rdc sdv
rsb: qzg tjg xmb
gdl: rgc
xtb: brc xnj
mnl: svj
tfc: hrj nsg
tcq: pgv pvq vll qnx
rpq: bqt
vkx: cvs jgc zmt gqj btt
hff: dfb kmb
cdj: gmf nph jqq rzx cdl
pqq: kdl rxs mvr smt
pfd: ccv pbl pvq txz
lxn: qcm bfp jkp
ppp: gkf
kqg: rfx qrh xlk thv
mjj: bqg xfr zgb gfg
jbb: hmm prf qct
jrb: scn hmc jmc
vcn: jgq cpf cgl
bcp: tbj zfb dcs dhn
dmd: phb ccj thp rqn
xvl: cfd lhv kpk
vhc: jtl qdd jsx pvk jgl
plj: msd szr pck zlk
dmn: flp
lst: ffp
dzg: ppm xnj
lct: qtx
hdv: llf
qmt: qst ndh zdh
bmg: hcv rsg gzb
ddn: dch
ljz: blx
jtg: sgn
czh: kpt mbf cfr xts
chj: nlq czb sjf kdg
rnf: bqg fll
gzs: cdv
klv: bvs nkf
hdb: xdx hcc grq qbf
kcl: rxk vqd dtx
rqb: zfb nvd
smr: xvx nsp cbv
pgs: nnq sxk hbh vjx
nnr: hmp qgd
vlv: gkf cxb
qzh: mjt rdc
qpl: kbg qtx zkb
dfn: dvp xvc rps
tbx: dxx jhg
vsq: srn dcl ctq bqj
qhq: dtx hbt hvs gzb
nlv: kzm rlr hlq
ngs: bgj
lvd: gcv
hlq: ffr kcq
grq: dfs kst
vzd: zcz
lcr: zdj krv jks
kkp: xhv bzh
qld: jrh hrj
mbs: vnz
hlp: fvx xxt mnq hff
pjm: fqj xmg zdh djv stz mxs
xdd: sqq nrp
ktm: mvx qsq prs
tcf: lsd xrp flt bnf
ncm: qvg hmf mpj xnn qsn
xsf: thv xxt
zrh: pbl tlf
lks: vqd hlj tnz
jts: blx sgn fkr
vvn: phh
zfv: xns msg cxt fgd
tqs: fhk pxr
bnj: qzc bgn
lqj: hbk xxt crp cfn
nss: rgk hhd jhz kfg npx
jvl: hmc
nrv: zfh
ndd: vkm bbs rrd
zmt: plz
rgf: rnn vhl
ldp: bbc dgn zsp csj crn
hkq: lxb bmx cfc
xms: nxm vzj gzs
cnv: rpt bkc drg cfp
gfn: qsv mvr
qpv: ffv frm bfp
qxs: ddn zfb
ffr: bnd pzv drp
hcs: rtd
bdp: xxg zrt trv xmj
vhj: nxm mmv sqr tsg gzs nbx ljp
qtx: tmj
cdc: trs bls qxr nnb
fdd: kcn lcb xtv
ddr: chg xnb
sxn: phg pzr tqs tsz
zsx: zcs fmm nlv htx xnn xdf
pbl: jfr
nxs: bzv
kqk: jkk mjm lqs
xcx: cbp dfd
cbr: grq hkh lnl
llm: jtb
bbf: klv cmv zhj rmn
vcs: zzx xts tlv qrh
qcc: kdh phg qck ctx
mgt: mkp zfh vkq
mjd: qmg cdr gkb
tfk: rjs zgb xng
qzc: xvc
ftq: krv nnq lxb
vkb: txg jkp rxf bzg
zjt: vvc pmn plf lmz htx tks
xfk: kmm xnn kfg
bld: mgl zdj tsr
xbr: mnb lnb
qvl: kbb zdh ttd srn vdk
flz: sjd
zsr: ffk
dxc: rtd nrv gpz kmf jbg
xts: jgl zjq hdz
zjh: nlq prs
cgh: xbn sfs scx
sjd: rdd gmv
lrj: rbj bfm
vgh: hcf fzj
kfh: tjm cst rrl ztt
gbn: trs xzm zjh
tbj: bvs xzx cqp
vvr: zlt zbf fxg vpm kfh
lnl: mlr qqm
dpx: xkq djx xfr xzm
xdz: xns xbr frr zbb
lrp: lxb
pzd: jtn cbc kpc
rxf: sbs tks zbb
mlq: skh zsz fdq mnl
fgj: ljz ptl jgl
hmq: rrl
xhc: rdh
gfp: jlc bbd
mlx: kcg nnb nhq sfj
fmr: zhg nnt djd
mqt: qfz
jcc: sjr rtk fvc hrd
xqg: nhc cfc
nbc: stz qpl mbp pbx ljb
bvf: trv zql lct tqf
lfz: rvz gvt vqd ppm
nrb: dks rrd mnm nvb
rgl: jxv vqn snv frp bph
hhv: fht ccv kbt tmv pvk mgh
xhv: bdf
sgt: vjs frr hcs
mpd: kss tqf msf cpf
bqt: brz
fpk: djv rxm frz plk
nrz: cgk mnb knk fxj
dtv: jct rgk vkq mfn
zmk: nqb
lgc: nhc gbs
sxh: xjn
bxq: btp tvn
ccj: ggj lhg grc
dtr: vdc vpt ncr rvz khl
xcc: jqz cxt gdg
ddb: gph txd jtl
bhp: hmq
htz: ttl mbp
mjc: ssq czb
zlh: jsx lrp nhh vhl
rks: vkr tbh rjd
jgq: str
drv: shc vdc mzt brc mlt fhk
hxd: zbb sgt mnb
qcm: rch
tqd: nkf psv hnx
qpb: mdf gzb tcb
dgn: ssf ffp
dmj: rtd lhv
bpk: bgj mdf
stj: rch rrd pgx nrh mnr
hkx: zzj
jpz: xzx vcn ctx gjc mkb pzm
bgf: zbs hxd fxz
tqq: jxd
cmh: bpg rzg bls pbl
dfb: sgn crp
vpp: tqd pzm sdz
pck: vmn xbn
hhj: rkr
ncr: mhc jrh czm
mzv: kxb
vsk: cfk ccn lhk cbv nbs
jgc: ffm jrh
xlx: sxt kmp zmq zxx
sgz: rkz xzv fhj blx
dzz: tfc bxp jvl pbp
mbf: tbv mkj
jgr: tmv xjn crz
zrt: lnq jxj mbj
fnx: dmb hvs jqq cmt lbj
bcz: cqp
jdl: djx sgv sfj cvv
jrh: dhn
glc: xjv vgj fzj jsd
pnj: svj frp dmb
rbs: sbs xcc
pvk: xjn
ndh: sbx mlt
hsb: cfp
tqf: nkl zcv hlj bvk cps gsb
dsl: pvv gkl xpx nnb
pxg: jvl jrp jxj rds
jqg: jfr kpk
vql: qpk
cjg: bhp gjc zzj rlj
smh: xmj cdl kmt
mrt: jsx vkm
rkz: fnc
dps: xng fxz hbh
flx: qtn rkr vbj
qlk: ptl nhh hvz
zjs: hvs bsj lsd
zvb: bgn tsr vgb
klh: jrt blf bcj
gmf: fcj qmt tzx
nvz: hqf dxn
rrd: rxx kcq
jgx: kcf kmb rvh jqx
pkj: xnb
dcl: srn qvx
jxv: rzl tsg vgj
lpz: cqq
nkl: dmn kxq gff
gmp: sgv
pld: vkq vmt zcz
jfv: jxj mch frd ljb
blv: hkv
hkj: lxn ggd rsb xlx
mgs: kcq kbt
cqc: pkk qtt cbp zzj
ltj: gcv nqb jkx jct khx fmr
gcv: vkm rlm
lhs: zcp jqg xdj ddb zhs
mfl: mjm
gpv: zsz zkn cms bbd
zhg: bth kgb nvt
ghs: rnc
qfz: dlz
ldd: trt sch
cmc: thv rzg gph
sdv: zkn
kpk: fkr
ctg: zmr
nkf: hhj
pll: vdx vmn
rlr: pcc lnb zsh qxd
rdh: snk
sgk: rnj hdc cdr xrt
vfj: vbb
vgs: lns bmh ljc
xlk: cfn frr
zdt: vbd kmt cgl
zlk: hrj scx
ngf: crc sgt
qtm: fnd hlf jct rpq
ltg: rtd vph rgf xqg mpj
fkd: crc czs fxj
xxk: kcf
vbp: gkf lns pkk
drt: pbl cfr
vrs: vnq fdb
cjv: rjs xqg tnj zqr bqt
grt: txh qkj dgc jbb
xdn: kkp bfr rjd vlr jdl dtc
rdx: qlq bfm shj rlq rxs
jbx: qzc rdd jct
ptl: zdj
ljp: dxn bxp btj
kmf: bld gqv sxh
jxc: ctj txz bsp zzh cmc
ppk: gdv zmj ttd dlz
txg: jrz fnd
lch: jtl mfl
skc: crn nnr zzx grg cdr
kbt: rgk
xjv: ttj
jpm: xmt xvq gsf ggd
kfv: gkf jcs ddn ffm
nsh: xts knb lpg
djx: zvj zfh
jhz: gmn bbc ftq
fjj: hrj ssl drg hcv sqr
vqc: kkv hzq kth srz
hmc: dmn dhn
lpb: hff sms ntj hnr
qrh: ljf
lkr: jfx kgb kgr qsv
vbx: llf
ljb: skh jjs rhc
fll: kxn dhf
cth: rjp rjs vpq zjm mff tck
jml: zmt lfj
jvz: mnx
kpc: xmt rnc
phs: jjf dsn mzl brc
csb: cmv
xvx: ftp vbd
kks: mlr xfg zkb
ghz: fcv ztc vlq
snv: tpx jdq njq
bgb: dxx tjm svm njq
tgb: vbj gth nqd xnj kxb
xss: cqq grh phx
zbd: gjf fxg zql msf
fjb: jqx zdj
tkj: dmb qjf zfb
rnj: ntj
djd: fgd lld
pbz: kmt vqd
vsp: hsh kjf
shz: sxc llm
ldq: qnf sgv thm qhl lfp
szr: jpn pck cpt vnq
nvn: trv xrb xtd
fzf: flh bqj mbp
kjg: jsx
zqr: pkz
gdr: jtl
hjx: bhh fng xsf tjf
gcg: cbb dmx tql kpt
szb: gxb hrd
msz: lbd ntj zvj
qmd: gkl gnx zmk brp
zkm: zsr bmx fll
ldv: hkx xvb nbs
qvg: hmm rnn mgh
slh: tjg jvz mpj
fpc: ctg xrq kst
dcg: hsb xtd zgh fnv
pgx: zjm zvb
zsf: qnj hsh lhl
knj: kgc
xbp: jsx
tcp: cvv dvp
ffv: sjd
mzl: cjr
gth: jrp
qnx: gkb nnt
ggd: vvx
vqh: xcx bpl
cgl: mnl
ffn: qtp mjc vnt rjp
zzx: mgg bmx tvl
xht: vnq mqg jfv xcs lpd cjp
jnd: svc hlj zff frd bcp tvk
vpn: fjb qhl
nsx: ddr
fms: vqc cst fgn mtz
dxx: zbf bjh
njz: sxc jzr ncr xjv
vzj: kmt
dtc: qdx nrv
lxs: bdc cbx prs
btp: mfl
cfp: gnd nph ckp bmh snk
vpq: lhl jzq phh mgh
kcg: tcp dnj fgd
jrt: psv jlc dct
ffz: kdh vxg
txh: ghs ssq msg
fbl: kkv ffm xln ffz bth
pdh: sjr cgh vbb nsn
tnf: hbk
rfx: jvd zfh jzq
zrj: jml dch fzv rnq
sqq: gdg cls
qtb: flm
nqs: tbv jbb fqz hjz
bqp: qlk bpz pjx qsq
djv: jrh mmn
mgc: mml xvb xqd
xpq: pzv sxm ghs
lfj: lhk mzv
bnq: lnq bmg ppp sqk
sfc: hqf hcf rqb xcx
bkr: qsn lvd
hcc: dbs hhp
lhv: rxd sgt ccj
gqv: qzc
nnq: jqg htl
fmm: nqb cbb ztl
vmn: nsp
czs: qzn jxd kmm ghr
cpz: xhc gkn qqm qsc
gxz: sxv rrq jcs ldv
vlt: cml qkm
gpk: drg fcv fzj
hjf: jdk tjf jtg
hhp: xjj gth jvl
sxt: zsr cls
mjt: bqj
lrk: bnd txd bnm fdd
rrb: nqj mpd lkq bvk tnx
chq: hgz cgl nvz qjp
mkb: rvz qtt
bqg: crp
mfn: dpj vkq
pnq: gnd xdv
pkz: kxn mfh
nmt: xqb qlm htz bkc
nfz: ndh ppp nsv gpp qsv
jrp: ckp
bbd: tvk
jqn: bpk stz pnq
jkp: kcg qtb
zbs: bnd kjg pcc
gkn: sqk jvv fvc
qtn: tfc
jzb: kkp jfr lvd
fzv: bph gln
vll: rsb crz jrz
npx: hhv cdr bzg
pbs: rps vvn xsb vkq bqg
nbz: gmv cfn gsf
vhl: xns mnb
rpt: fnv tmj
qbf: nbx tnz vgh
prn: xts lpg
bzv: tnx
bsp: gkl pjx rgk
zmr: zbf
spg: tcj tbx xql btj cqq
jmc: bbd
pch: xfg vlv
lhl: xsf fqz pvq
khx: lgc mvx lld
jpn: lrj nsn ppd mdb tcj
tsh: skj pzm bcz
pqh: skh vdf ghz xnb mdf
sjr: zmt
qzg: kfg pcd pzv
bnr: dmx ztl ggd hkv
fgf: ddr vgj cfp
mtz: bph dcs cvs gzs
xks: vgn zfk
ktd: gvt xcs ftp
jqj: jml nsp szb
nhj: vrs shc xzg rxm
nzq: ddr skj csb
vvh: hdc pkl zsr qpk
pbp: hcf ldh rdc
mzm: lns mqg lnd stz
cjp: lfj fnv smr
hhg: vlb nvb jdk rrt zcs bnm
svz: rxn qlq gvt shc
qxf: fkr lnb nhf gph
pnr: mbj
sfl: fpq
jxj: jdf
thm: fvz nhh sfl
crg: qpp zsh rxd
mzz: hrz nsh qzc gnk
mdx: vkm fvd nnr
hbb: tfk zjq khz cbc
jfz: mjt mgc qfm cmt
zpf: cvv xdf
zgt: gff gqj mxs
hdz: xjn
fvj: grc
gmn: fvj czb
qtt: pfl
fcj: lbj xtb
kss: kdh tbm
srt: gjc kll dch
sxv: dxn dzg dfd
vbj: vxj
fgn: xqd mnp pkk
lbb: fnd
npb: qvt hcc jgc rrb
bkl: rbj cps qxs mkb
khl: drg
btr: dml htl sxt kzm
nlr: frm csj dhf gtm gdr kmm ldm
lzz: mlt cmv
hfm: rqn
vbt: vdx
vbd: dsn
vrf: cqp
vqf: pcc zrh
qxb: cqq dgb ddv scn
rjp: gkb nrl
gmb: ddr gpk gdv rbk qdb
fbn: gff mbj
vtg: pdq xtd ktd skj stm
knb: zsh cmb vjx
tjm: ctg vzj
ccn: xrp
lqs: qxr
jbs: gjf pcs kgr xgv
zvr: lct nrm
pgv: pzd vql jqg
tzk: klv jgc vnd lks
jgl: zcz mtv
crj: vrf lfj xhc
jzq: vqf kgf
nvf: pcs fgs lzz
rzl: jgq tzx bpk
kgb: qbb
fgs: mzv gln
rzt: mgt vlr hrz jct
cjz: blv svr flz vmt
jjn: qrk vtl crc
thf: cml plf pgx
sfk: flh rds jdm cpt
nvb: gbs jgr
zpm: hbk jzb sfl btp qpv
pjx: hdv
fsh: xmt rxx zsf
vvx: xvq
tlt: znj fkb rzx qtn
grg: gqv crc sxr
bbc: fxj fll
qpp: hlf
kmb: fht
phx: llm zdh
dvl: dlz xgh jjf dct
mdb: kgr rxm
vmt: dpj
lhf: nvf ctp zfb knj jss
xmb: rnc rrd
mgd: qpk hrl cfd
qgb: fvj
njg: pkl xdb cml qrh ljf qnx vnt
qnz: txz fgd nrz
rzx: xsq cms dfs
dtp: nqb phh
sdh: tck hfm chd vql
vlz: hmc pnj msf fbn gvt hnx zjk
tnq: lvs qsn zvj
qht: bnm dfb
ftj: jqx hmm vjs gnx
bkv: cxb nbs bgq gfn
pvv: vjn lvs
rlj: kxb kgb vrf
htx: bqt rnc
gnk: drd bdf txd
sgd: szz ngf hpm cml
qzv: lpz knn
htl: flm tsr tmv
llj: rpv hcv flp
mht: tgd qnz tlf
bqd: zjq lhg llf
bgn: bfs zhs
tgd: mgl
grz: pbp rsg xdv
gcc: dnj lxs lfp drt tql
vcr: lsd vhx sdv vxg
sgf: grr tbv lbb qrk
cpf: tbm
ksz: vgb sgv tck
zlx: jcn znv qxr jjn
flt: frd jrp vnq
lxj: qrh rgf lch sqq
qrs: fkd vjn hlq jks
kmp: vgn zlh
rnx: sfs smt ttj
rxx: xhv chd
stm: tsh rds mdf qbb
qnf: hhn kmb dtp
kfb: ttl kst vxj
cxb: mhc znp
fxx: cvs
bfr: ngf dks tjf qqr bhh
bpz: hsh sqq hfm
hkl: vlt mcf xhv lsq zsx
pcd: rkz fht
zbb: ctv
vph: flm hsh
bth: fkb
ctj: cxs pmn ffb
jcn: dks fgj
vvc: lgc kpk xsb
rgh: ztc hhj jqq hmc
gbq: pbl kjf kbt tlv
rrq: pfc czf qcs mnp
pzm: frp
xjj: hmq tnz
lcb: lmz qgb kcq
tvl: pcd plv vlr
hmf: grc lcr ssf
dln: fnc frs crc qxd jtl
dgc: zgv vtl xks
ggg: gqs hff mkj ljt fjb
tlv: mnm mcf
xdl: kdl fvc dct
tcj: nsg
lpg: rjd
rbk: cmt kgc
hhl: pkl tbh kpt tvn
fcv: zlk pvx xfc jmc
jhk: nsn
lgn: frd zvd fzf rqt ndh pfl
ljf: prf
vxc: rmx nzv gff vnd slt
klx: qvx nph xsp dcl
vnz: nsg pkj
cfc: gfl
mnp: xrp
bcj: zdv qdb mtz
mfb: nrp cmh fsh xdj
ggm: gfp qst nkf
btt: ggm csb qlm kgc fkb
qmb: pbz scn nxm
gnx: fqz fpq kpt
xgh: mmv chm rgb pnq kdh
cnf: hnr
jnv: kth
hpm: mrv
jsd: vfj zgh qfm
mcf: rdd pkl fvd cpm bbs
qrk: rqn
xqc: fjx khl xht bsk
fvz: ffp hkv kjg
qct: thp rxd
tnj: jxd lld qtb
tpv: mrt vtl xpx
vvq: gfn gjc vfj jzr mmn
dsm: vtl prn
hcf: chg
jdf: hsk
xrq: bvk
jcs: vlv mhc
nmq: zvg mnp pbz
kbq: nqj xtd hmq phg
bhc: nmq mdl vdx bnf
ddc: bcs xsq lnl jdm grh
znp: tcb
vrc: hrl bqg jbg hfm rvr
svc: phs ktn jvv
frm: nlq gph
cdn: frh crg qpp dnj ntj frs sjf
zjq: jfr hlf
hnx: mbp
gpp: znp fhb
fxg: tzx jqq
zps: fnd vgn xgq
rtk: sbx xql hhj
zkb: trt
lht: bpl hhj dxn
rxs: kdn fhk
vpm: bpl
skf: bgf xfr tkr tcm
txz: jxf knk
qfk: gsb nkf dht
znj: nrm xzg rhc xqx
mxs: btj xzx
jct: mtv
nrh: tjr zzk hrp qhl txd
tkh: sdv cjr dbl csg hkx
xgv: rxs
tqh: zpm hrk kmb ggj
dhn: bsj
crn: vmp nnr rks bls
bvz: gth xll xsp bbd
bpg: rnj cvv xvq
jpx: jdq fhb ngs dfs tmj kxq
qfm: bgj
zdk: zmd lzz scx vqd
tsf: bmx cfr zmk rtd xng
tck: tjg
pcs: plz gkf rdh
rbj: mjt
zsp: zdd vjs
sbs: vzd lnb
rlm: cbx plv
szz: rnj cxr jxd vql
cxt: xbr kfg
xfg: hcf
ckh: ffv zps tzc nrp
mgl: rvh
drq: qmb bhp jlc sch vst
jss: zvg mqt pxr
jps: jtb dfs vzj lqx
zzh: kzm ffn hdz
mff: slh rpq
qqr: xbp
hkh: bcz
jqq: hsk
dcs: nqj
jqx: tqq
rgv: jct qdb xtx cms
cbc: jkk mgs
gmd: dgb msd hsk mlr
pbm: znv gmv gkb rfx
fjx: rzd nxs zvd
zdv: xtx bcs
dzp: lcr msg snl tqq
tql: pld sxm
lkq: hsk gdl
zhl: lsg xgq gph
mjm: rvh
ppm: gfr vqn svm zkb
klr: lsg vpn snl
rfm: pll crj cps vgh rzd
kmh: zhv ldd smh
rmf: lvs zcp hcs vbx zmq
xkb: srj
sxk: cfr
vvs: tnf qkm rps
kmt: bsj
hdj: zjt ssf npx hjf
ffk: nrl rjd rnj
phh: snl
ddt: gfl kdg
cps: cbv
xxm: jfx zql fbl zjs
qlq: kmh lpz ttl zdh
zmd: klv bqj dbl vbd
sjf: tjf lvd
kcn: nhq
hdc: xdb fhj
fzq: zfk kgf thv kpk
llf: xdf
jhg: lfj hnx brc zkn
dxh: xks zrm fgd prf
thr: ttj fgs pfl fqj
dxd: nsv ngs ddv fdb
vgj: rtg
qfj: hkv nsh vgb pld
pfc: pkk nvd
sfs: jgq
bvd: xnj sbx rgv plz
jsx: vkm
knn: dsn lhk xqx ttl
lqf: llj frp qtn vnz vpp
zsj: hlj ctq kgr tsz xvx
pjz: mzv fkb nvg jcs
xqd: mvr mbs
cfd: qmg kjg
lbh: fpq nrl sxh rrt
srj: rps rch
bnd: cgk
fhj: pcc
rgc: xmj jjs bgj
xpx: jvz mfh tcp
xkq: vlr mpj
vst: zkn nzq plz
rkr: gxb
qtd: mqt mlq nrm gdl
hjj: bsj fzv znp lnq
sdz: str qpb
rct: czb gfg zzk ggd
czf: xcs lnd cfk
ztc: cmt dfx
vjn: ffp
cqn: nvn ftp zmr
kjf: kmm bkr
rpv: fdq vdf hkh
khz: jtn vsp tjr
stq: xtb trv qzh
frh: djd nnt vvn
ckp: cdl
nlq: mrv
dfd: nvd
mjx: zjh zsh zfk slp
qvz: pbr pdq mbj glc fvn
lns: vnq
bxk: tgd xtv bls
mnj: ljc hmq ppp
pjs: zfv kqk gpz mdx nrv flz
csg: grz srz zcv bxp
vnd: pnd rxm
qsc: ctx nrm xhc
rng: xdd dcx xvl qtb
qvt: bvs gpf srt
xzv: vlb vgb xmb
chm: lnd
xjh: cpm ssq
vxg: ppd qqm
frz: shc ldd vgs
xfc: qfm vbt
rdc: hrd
lqx: rgv
xtv: gsf
shj: xqx bhp jhk rnx
bph: xfc rdc
vdk: nvz stz zdv
hbt: ftp
tnz: pkk xrb
rnn: dhf sxm
mkj: qsq lrp
nbj: fht mfh thv
zlt: zjk mch smt
cxr: hrz sxk ssq nbj
lvl: xzm slh
vjv: xmt xkb thp cnf
qcn: kll dmn vqh htz
kxq: nbs jdf
kdg: qct cbx
jvg: tmv vqf rlm
gvn: xjv nnf pch
rmx: dfx dcs pll
jvd: hbk cfd ctv
fqj: nrm
rck: jdm nvd qqm xrq
grr: fkr zjm
dqv: fqz szz lst gmp rbs dsm gpm drp qcm
sxm: kgf ggj
bfs: zcp lst
rmn: fxx kmh lrj rzd
xft: fdq lqx jvv pfl
xmt: ggj
cvj: ckq rqt fnv lml
jnm: jvv psv cpt sjr
hsh: hhn
hrk: sgt hdv vsg thf ddg
fvx: zkm hkv sxm
bsk: mjv jtb qck nsg mbs
plm: zmj rzd gnd vqd nhk ccn
tsz: ckp
gbz: vdf hsb trt zdt rxk
bgq: nsn
jqk: xxk cjx hlf
hrj: flp
zfk: mnx
hhd: jct mfh zcz
stz: ffz fnx
hjz: sxm tlf zgb
gqc: jrb qhq dfd fnx
knz: dtc hkq lst jzb pcc
scn: skj cdv cqp
csj: phb kcf lvl cpm
ckq: hzj dcs
jrz: ssf hrl
mml: bzv llm
xbn: bmh hvs
gnd: bvs
pnd: hrd xrb vnr
rxn: jlc kcl rkr mml
hmp: mgs plv fgj
zxx: vjn cgk knk
xdb: rjs mbf
fhb: kxb
cbb: mtv
rvz: cdv
xvb: xmj ntr cqp
mrv: crz
pvp: rrt zdj zgv xvq
lvr: pch lsd jrh czm
bzh: kcn kcf
vdc: xln rqb
zsz: vrs jcs
nvg: sqr svj zfb
qkj: lhg ghs qhl
fdb: gxb
gkf: vdx
sms: zrm zjm
zcs: zrm
bnf: zdh nzv
rqv: bdf srj brp kmb bqd
rlq: jrb ngs
xll: bcs tcb llm
htc: fvn bmh pll bgq
lml: gjf vbb
tcm: mfn zqr pmn
srz: krf qpl
vlq: zdh
fjp: frz nkl fxx rkv vbp
pmn: blv
nfc: ppm bjh znj gln
ndq: nnb xct jgx prn
zhs: hsh
cnn: mmv skh zpz flp
ssf: sfj
pvx: btj
kbd: mgg fxz rrt rbs zzk
rkj: pkj fhb rqb jhk
hzj: hrj cpf cjr
xng: nrp xvq
"""
"bjk: mzl dlz gln\nnbx: tsz\nrrl: zvd dxn\nxln: vbb tst gfr\nkth: nrm bkc\nkrf: ddr crg rtg\nzhj: lbj\nqsn: tqq grc\ndkg: drd cxt hvz jvg qrk pvv\nvhx: jfx ffm\nbfm: kdl\ngpz: nnb\ndpr: msg thp tft vpn\nzdd: gmv\nlhk: qst\npsv: bvz dch\nzbr: bfm nhk jdf qfk\nrtg: zjk mbp\nzvg: str qtx\nxrt: sgv vjn jxf\ncfk: pxr tcb\njbl: xxk qnj hpz jdk vhl\nvtf: gmn fjt txg\nlnq: tbm\ndcx: thf sln vsp\nvnr: hrj kss tbm\nqlm: bxp\nplf: brz\ngsb: kdn hbt\nqtk: bkr zcz qpp\npmh: mpj lgc\nnnf: mlt njq ldv\ncbp: nph fvc qsv\njjm: hcf kdn qzv xrb\nrhz: kdl klh pvx pnj xdv\nztt: slt lpz jnv qst\nvtl: cbx\nzcm: jcn dkg pgc zhl\nncn: vvn cbb mkp\nfxk: knj pdq ftp jcc\nprs: xks\nlsg: jjr ghr\nqdh: hcv dgb\ngfr: bgq ddv\nvgn: rdd\ntjr: lxb\nbzg: ddt drd\nnsp: mzl\ngrh: zql rds\nkkx: hbh qqr zdd fvd\ngph: gfl nft\ndkr: szb nbs rbk flx\npcn: dgn sjf tnq gbx\ndcr: vst tbx bpl lnl hqf\nmgg: mjc mgd\nqkv: fpq ljz svr plf lpg\ntrs: bfs bmx\nplz: xzg\nfzj: cbv bsj\nfhq: vfj mdb bmh xtx\ntrt: cpt xql\nccq: tkj xmj zbf rpt\nbdc: nhc vkm\nffb: kxn lxs svr qht\nqnj: vzd czb\nctq: hhj mlr\nqjp: rxn fgf qld kdn\npzv: mnx\ntjs: mdl kfb qtn tqs\ngdv: chm cms rbk hkh\njdk: xvc zgb\nqdd: nhh tgd ccv\nsvr: kxn\ngqs: cfn fhj\nrgb: shz rbj sxc\nnlj: blv jbg vnt tnf\ngtm: dfn xzm cls\ngdg: zzk\nqhl: mgl flz\nhcv: gpp\nrvr: mjd qpp grt pmh rrd\npbx: cdl qvx cdv\nrqt: fhk nzv\nqgd: gqs tpv hbh\ndht: snk fxx nsx vbt\nxsb: sfj plv\nnsv: mxh\ngsj: dmb srn jfx cbv\njkx: tsr vvx hmm\nktn: fgs vcn lqx\nmdl: qxs rzd\nxtn: xdd qgb hsh xjn nbz\nxzm: xct\nzkf: nxs fvn\nkst: lnd\nczb: cmb\nstr: hrj\njfx: ddn pnr\ncjx: hvp vlt vbx gsf grr bbs qgb\nvkr: prf frr jks\njbp: mjm lqs dks\nmmv: qld\nbgl: pnr hzj csb zgh jqj qdh xnb\ndvp: hrz txd\ncpt: sqr\nfrs: xts rzg\nzmj: jjf nsn\nbpj: fms ghz xsq bdp\nhcr: hvp fjt qrk cfc\nkgr: mvr cjr\nrkv: xtb mjt zhj\nnqb: nhf\ndtx: bcz qck\nlfp: mvx pkl\nlbd: lhg knk cls\nchd: zpf mvx\nsxr: vvx drp dmj jvz\nzph: mpg zfv dpj tjr\nkpd: nhf qzn mlx rkz kmp\nfng: phh hnr gbx lsg\nrzv: bth rgb svm xgv\njqz: bnd jqx qkm\nfqx: gjf ddr dcs stq\nkbg: xzg\nvjl: lht zhv pfc mbs\nljc: sfs xqx mch cmv\nxdc: fdb smt njq xrq\nqxd: brz rqn\nsln: cmb lqs\nhgz: zcv vxj rpt\nczm: tcj\ndml: zrm bdc hdc\ndbl: jnv zjk\ncrf: zff kll ckq pll\nvmp: hpm qkm gcv\ndbv: rch fdd qxr qbh zrh\nqzn: mnm brz\nlnb: ljf\nrbb: xdv fcj flt nsp\ncxs: cpm kbt sgn\ndcq: rnf tbh gpz\nnnt: gfl txd\nslp: pkz\ntfd: czf xjj xql vkx\nqxx: pmh zpf jbg gbn\nvjx: hhn cnf\nqdx: fpq jtg\nrxk: chg xqx\ntvn: gmv\nmqg: mzt qzh\nsch: kkv bjk\nmpg: xmt ndd rnf fng\nnfg: ksz nft nqs bqd bxq gtm\npbr: czm ctg vbt zgt\nhvz: gdg jxf\npzr: qbb hbt bvf\nhpz: qsf xts xxk\nckz: jmd fzv ssl kbg\nljt: xbp btp ncn nhq\nrsg: dct vrf\nshp: vqh cbr bgj zvr xcs khl cvs\npgc: kcq zdd pkp rnc\nvlb: jtg vnt\ngzb: jrp\nhkd: cdl jmd cfp\nrmq: vtf xzv drt sms fvj qct\nqjf: zvg lct flh dsn\nmxh: dtx cqn gdl\nvsg: bfp sln zmq\nxdj: dtp rxd sfl lld\nxnn: lrk\nttd: qck rnq xfg\nkpg: qht fxj xfk drp\nvks: hcn mhc jqn flh fjx\nrtc: kmh msf lbj fhb\nslb: zfb htc stq scx\nlrd: plk dct zkf rck\nkkv: vqn\ngzh: znv lsg dmx hpm mnx\ndbx: ftp xdx rlq nsx\nznv: mrt zvj\nbbv: hkd jmc nqj jrh\nphb: sxk jbp\ncfn: bqt\nsvx: pgs cmh lpg jqk\nnhk: qzv ctx vxj\npkp: lbb tcp gmp bfp\nnvt: gvt zvg zpz\nzff: xgv bvk\nqmg: zvj tbh\nhld: dfs btt dcg tpp\ngjp: sxc cst nxm phx\ntdx: txh ptl nsh mht lch vsp\nqdb: rdh\njjj: sdz zzj xms zhg\njdq: shz zkf pkj\nmzt: rvz gzb\ntsg: bvk sdz\nfjt: plv lmz rrt\ntcb: vpm zgh\ngpm: bfs ddt bnj ktm\nddv: rxm ghq\nxdf: vmt\njmd: vlq vbj fbn cbp\ncst: tnx\npkk: svj\nmnr: crp sbs fvd\ntpp: nsx skj ddv\nqlj: vkr gdr xkq pvk\nslt: jtb cxb\nbcs: flp\ndvv: brp xnn dps jtn\nplk: gxb pvx\nxsp: vlq ttj\nkgx: qhl lld nrl lvl ldm xxt\nxnj: tvk\nbxl: qdx ddg xpx krv\nbrp: lbb bnm mfl\njlt: dfn mnm jtn ctv qtk\ndfx: tzx ppd\njkr: bbs fnd nlq zrm\njhj: pjx tlf fnc crn\nctp: xrp dzg nfz\nrvh: mnx\nxns: xbr\nbmh: llm tmj\nkgf: snl\nldh: bbd jdm ghq\nkzm: xjh\nvpt: hbt xdl ccn\nhvp: cgk bdf\njjr: mtv kxn\ntks: ztl xlk gmp rxx\nzpz: mqt ghq\nhrp: tbv ljz qqr lrp\nbjh: pjm fcv cbv\nklt: lml flx gvn mmn\npjt: zhj fxx pch mmn\nzbf: zvd\nmnq: xtv xkb vvh vbx\nhrl: nhq jks\nmsd: ppd cdl\nkkd: vjs mrv zhs bzh\nfvn: snk\ngbs: zcp nft\nztl: ddg\nblf: bzv kgr mjt\nhzq: jjs pnd pnr\nqcs: sbx hsb chm xtx\nfpf: gqv drp msz jxf\nznd: sxh vzd frh cxs slp\nzmq: xjn\nxrb: tvk rhc\ntzc: nbj pcd tj" <> ...
Part 1
defmodule Part1 do
def parse(input) do
input
|> String.split("\n", trim: true)
|> Enum.flat_map(fn line ->
[from, tos] = String.split(line, ": ")
tos = String.split(tos, " ")
tos
|> Enum.map(fn to ->
Enum.sort([from, to]) |> List.to_tuple()
end)
end)
end
def contract(edges, sizes) do
[{from, to}] = Enum.take_random(edges, 1)
sizes =
Map.put(
sizes,
from,
Map.get(sizes, from, 1) +
Map.get(sizes, to, 1)
)
sizes = Map.delete(sizes, to)
edges =
edges
|> Enum.filter(fn {f, t} -> {f, t} != {from, to} end)
|> Enum.map(fn {f, t} ->
cond do
t == to -> Enum.sort([f, from]) |> List.to_tuple()
f == to -> Enum.sort([from, t]) |> List.to_tuple()
true -> {f, t}
end
end)
{edges, sizes}
end
defp try_min_cut(edges, sizes \\ nil)
defp try_min_cut(edges, nil) do
try_min_cut(
edges,
nodes(edges)
|> Enum.map(fn n ->
{n, 1}
end)
|> Map.new()
)
end
defp try_min_cut([], _sizes), do: nil
defp try_min_cut(edges, sizes) do
if length(edges) == 3 do
{edges, sizes}
else
{edges, sizes} = contract(edges, sizes)
try_min_cut(edges, sizes)
end
end
def min_cut(edges) do
reduced = try_min_cut(edges)
if reduced == nil do
min_cut(edges)
else
reduced
end
end
def nodes(edges) do
edges
|> Enum.flat_map(fn {k, v} -> [k, v] end)
|> MapSet.new()
end
end
edges = Part1.parse(input)
{_, sizes} = Part1.min_cut(edges)
sizes |> Map.values() |> Enum.product()
556467
