<!-- livebook:{"persist_outputs":true} --> # Advent of Code 2023 - Day 25 ## Sample ```elixir 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 """ ``` <!-- livebook:{"output":true} --> ``` "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 ```elixir 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 """ ``` <!-- livebook:{"output":true} --> ``` "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 ```elixir 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() ``` <!-- livebook:{"output":true} --> ``` 556467 ```