Day 08

Setup

short_sample = """
acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf
"""

long_sample = """
be cfbegad cbdgef fgaecd cgeb fdcge agebfd fecdb fabcd edb | fdgacbe cefdb cefbgd gcbe
edbfga begcd cbg gc gcadebf fbgde acbgfd abcde gfcbed gfec | fcgedb cgb dgebacf gc
fgaebd cg bdaec gdafb agbcfd gdcbef bgcad gfac gcb cdgabef | cg cg fdcagb cbg
fbegcd cbd adcefb dageb afcb bc aefdc ecdab fgdeca fcdbega | efabcd cedba gadfec cb
aecbfdg fbg gf bafeg dbefa fcge gcbea fcaegb dgceab fcbdga | gecf egdcabf bgf bfgea
fgeab ca afcebg bdacfeg cfaedg gcfdb baec bfadeg bafgc acf | gebdcfa ecba ca fadegcb
dbcfg fgd bdegcaf fgec aegbdf ecdfab fbedc dacgb gdcebf gf | cefg dcbef fcge gbcadfe
bdfegc cbegaf gecbf dfcage bdacg ed bedf ced adcbefg gebcd | ed bcgafe cdgba cbgef
egadfb cdbfeg cegd fecab cgb gbdefca cg fgcdab egfdb bfceg | gbdfcae bgc cg cgb
gcafb gcf dcaebfg ecagb gf abcdeg gaef cafbge fdbac fegbdc | fgae cfgab fg bagce
"""

input = """
cbgefad agc fdega cgdf ecdgfa efgca gaefbd edagbc cg ecafb | cdgafbe cfdg cg gac
gcbdfe cgefb bgadcfe de cfabeg cbgade dbfe ced acfdg egdcf | de bedf ecdgf ecd
dcafgb eagdfb bagdefc abg ba afbc bdgec cdgab gaedfc gadfc | abg ba agfdc gab
agfbe fc fgbadec bdgcef gcdbe fbcead ebgcf cfe gdfc dcbega | edfabc efgab cdfg ecf
fcdeg cfbedg dcfeba fge fcdga ebdg cfebd edgcabf efbagc ge | cbdgef begcaf ge dbcfe
fceadbg ecbg cab cb bdfcea agfce cfaedg gadbf bfagc gceabf | cba cab bc bgce
ecadb dcgea baeg dge fcdga gbdefc abfdgce bcfaed debcga ge | dge egd fdbeac bage
dfc fbgde dgefcb bgfade gbfc cf afecgbd cadge fdegc abcfed | cf cfgb dagec bdegf
edaf bagcdf bafegd efacdbg fbaecg gcbde ad gda bfaeg edbag | dgbafe fcbgae adg dag
fbgdca efacdb faegcbd egbfd acebf feagb ga ecga bgefca gaf | geca gaf gdefacb egac
dcfeab adcfb eac dbgace agdefbc ae decfg caefd feab agfdcb | fgecbad cae bfae eca
befg bcafe begacd ebgfac eba fgeadbc dabgcf bgcaf eb feacd | eafcb agcfb gcbfa facde
acefgdb cbadeg gbcde cde dfbgae eagc dfbeac ec bgade dgcbf | cagfdeb ce gafcbed dgcfb
dafbg cdebg ca cabfge cead fcagbed abcgd febcgd agc egbdac | agc cdebg gac bdgaf
cfbged bfc egfc eadbc fbacgd gfbde dbfce efabdg efdgacb fc | bfegd fbc fcagdb dcefbg
bg fedbcg eadgf edagb dbg fgba dgfeab gafcde aecdb dgfaebc | degfa bdg egabd gbade
cedb fedgbc aedgfb efdgb dagcf cfe ec fdceg caefbg gaebcfd | ec fcgebda dbec dgbfe
bdgeac fbgedca cg bcedg gcb bcefga gacd dfegb adebc ecbdfa | edcagb cgeafbd agcd dgca
fa bfa abcfeg bfgea gdabe defcgb cbgef efca cbedagf fcdgab | fa cegdfb bfecg ecaf
cabfd egbafc bdae dcaef ba gcdfb gcdfae abc bfgdeca daefbc | cfeda eabd gdbcf gcedfa
gbcdafe cfgdab becf bdf edcbaf bf cebagd bdeaf efdag cdaeb | afdeb febc bf fb
gebad caed gcbfde befacg dfgacbe dbcaeg gea ea gbafd dcegb | gbecaf gafceb cbagef caedfgb
adebgf cgafbe agbdc cafbedg dg dcaebg gdb bcadf egabc cgde | ebdgacf cbeadfg fdaegcb bcgdefa
fcbgae gce bgdfec acgf daefbc eacbg bcaef gaebcfd gc aegdb | eafdcb gbaec cgfa fcag
bdfgce ca dcfbae ceafgd dgfca abefcgd dgabf acd aceg gecdf | fabgd cda gacfed dac
gdbfea agcbde abdec dbaefgc fbcae dgeac cdgfae bcdg bd ebd | gcebad adgbef db bd
adcb acgde cde cd baegc edbcgf edacbg gfdea gfabce edgfbac | defbcg dce bfeagdc gbacef
afe agcbfe dgbeac af fcebd afgc aebfc gbadefc egbac gabfed | af ebgcfa af fea
fea cgafbed debga bfgdae fa dgefc aegfd gafb cdafbe dacbeg | af afgde af bcadefg
fcegdab dabcg gdbaec becd de afcdgb abged eabfg fecdag aed | bacdg aed de ade
bd gbd gbecf fbcgd egfdab fagdc bdec fegbdac dfgecb facegb | cedb bdfegc gbdface egcbf
cfagd bdcf bcdgea gcabfe dc cagfbd fdgecba cad bacgf afegd | geacbfd cbdgaf dgbfac cd
gace fdbeca gba cbfae bgdfca efbag dbefacg bcagfe ga fbgde | adcgfbe ga ag cdbafe
fb fgecbda dabecg bfedgc gcfbe ebgdc ecfdab fagce fbe dfbg | fb bfcdeg cdfegb bf
cdge afedbc bgc fdcbg dgfbec ebdfc becdgfa ecfgba cg dgfab | decg bfaedcg fbdag cbfgd
bdafgc gacdf cafgdeb fcdega dfabge edacf fde ed cged bfeac | abdcfeg de abfce bgdeacf
cgfbe de cfebag faedbc gbdfe gbcdfe ecgd def dgbfa dfaegcb | decg ebgfdc ed gbceaf
gfd fcgbd fdgeba df ecdf cdfebg efbcag fbgaecd cgbfe bgdac | gfd efcd gfd dcef
dafe bcaed dbf gfdceb fd agcfb aefbdc beacdg ebfacdg cfbad | fead bdf abefdc defa
bgdce facg fgebad efcda gefcd dcfaeg dabfegc cabfed gfe gf | ecadf dgcaebf gdfabec fg
bcfaed cgeafb cgfedb gcdabef fbecg gacdf facgb abge baf ab | bgae bdgceaf dfcga eagb
degcbf bec aecgdf acdegfb fcbd dgaecb fegab fgdec cb cbefg | gbeaf dfcb gbfdec adcfgeb
cgef cbeafd bgafed ec gefdabc cae deagf caedg cgbda feadgc | ce feabgd ecgad efcg
fgdbae geabcdf ega fdecg ea acbe cbagf cegfa fbagdc aebfcg | ae gea acbe ceab
gabe dcfbae ae dgefc dea cbafgd gebdaf dbgfeca gbadf gefad | ade aed ead adefgb
fabdc cgbdef gdec aecgfb bgfde ebcfd afbdceg ce cef egbafd | cdfbge dgce cabgef ce
ebfacg gdce gbefcd befgd cdabf cfdgb cg efbadg bcg aebgdfc | gbfdc gcb dcge bdcfa
efagc geadfb ca fegcad fca defabc fbgec egfda dgac cbedafg | cdag caf caf dgac
dbaec bd efcda dagcfeb adb cgbea cdgb dacgeb aegcfb baegfd | bda efbcgad cdbg gacbe
ge acbge bedg aeg agfdec cabgd bcdgfa edgcafb egbcad befac | gecba ge fcgdae cdbefag
fdbae gacfde fecbd cgdfeb af gaebcdf aef bfca gaebd cafdbe | aef fea edcgbaf fcbed
dcfg bfagd cdebaf cbaeg fcagdb bdgaef gfacb dfcgbea fac cf | cfbgeda debfga gaecb cf
fbdaec bdfca gd bfgcd gbd bedgca gbefc abdgcf gadf gcdbfae | cdefagb bdg fcabgd dg
ecbgafd ecdgab abedfc eafbgc cabef abd da fcad baedf fgbed | cbeagf dba faecbdg ad
bdefg ecfbd ec cfe aebc fdgeca cbadf cagfedb fbcagd efbcda | ecf ec ec efc
eadfcgb gebdfa afcdb agefd adgbf bgea gb adfecg gfbdce fgb | gbea gbf gcfdeba ageb
cb fegba dfcbgae gefdc gebfc fadbec cbe agfbec adgfbe cbga | daebfc abgc egcdf ebc
dgfec dg bfadcg gacfde eafgcdb agde agcfeb cebdf cafge cgd | bcedf dg dg abdecfg
gbf cagedbf gadf gcbea ebcfda afbcg afdbgc bfgdec adfbc fg | gfb gdfa fdacb fg
bd bfd degaf bedaf gbacfd cfaeb ebdfga fecgda acdgebf bdge | eafcb bd eafdgcb bd
gefba dcagefb gebfad baecf cegbaf fc dacbe fcb egdcbf gcaf | efbga fgca cgadefb dcbefag
edgaf eagfb bfeagc ed cagfbde gdafc egadbc edfb dge gfbead | gabdcef fdage agbfec dfbe
agdbfe gd dbeag acgbedf cdbfag gda cfgeab edfg beacd bgafe | gd efdg gbefa agd
dfgbac efgabd edg afcde bgfda eg abecgfd deagf eagb dbfecg | bedcfg dcbfaeg egd ged
cdfaegb bdcg bcafde deabg dcagef dg badce gfaeb agd edbagc | geabd abced dga dg
faedc bgaec gf cagfe daecbf egcfda fcgd efg cfdbeag bgefad | fecabd afcde gcdf eagdbfc
bcdgfa eabfd cfbde gcbed cbf efbadc gfdabe gbfdeca faec fc | cfb dbgec dbgec feac
fgacb abgefdc feacd bdef dbc db bcedag adecgf acebfd fbdca | cbd cbd bd dfbe
acfdbe daeg gaebfc fga gdcfb dcagbef bfagd ag gdefba badef | ga fadbg agdfb gaf
gbefdc bfegad feag dae gfebd ae dafgbec dfabe daegcb cadfb | daegfb bdagec ea egaf
bcage gefadb cfga fbdecga gdbcef bga aegcbf bdeca gfbec ag | ebacg bedcgfa ebgcdf agb
bdegf dbaegf efabg ag gade fga cedbfg ebfac afcbgd bceafgd | aegfcbd gfdeb bgefdca gaf
efcadgb dfb bgcad fd fdcbg gefcb gfaecb fdec edbgfc aefbgd | df bcdag fbaceg fd
febgcd fgbdcae fdegab cgabf gbfcd gecaf bdcagf cdab bga ba | ba gafdbc gba ab
gefba dafgb gfcae bfde gdceab badgef be afgbced ebg cfgbda | eb eb fcega deabcg
cbfdae egabdfc eacbdg ecdab gce agfbc gaed eg gcfbed egabc | gead dbfgace dgebcfa gade
bacgfd dgfe fdagecb cgebdf fbedc edb eabfc bacdeg fdcgb ed | de ebd dfge debfcga
dcgae ef bgefda dfabec ecdbgfa acdfb efa fadec cbef bacfgd | cfabged acfgebd dfcba eagcdfb
gbfde fcd agcedf cdea edgcf gefbac begdcaf gafec gabdcf dc | dc agfec bgedf bfegac
debgfa cfgba bag fcdgb bcad ba fedcbg afdgbc eafcg cgfdbea | dcagfeb ba ba bfdcgae
bfdgae bdfcage edagbc eagbd febac fgbcad cdeab adc cedg dc | gebdfa edcg ebacf ecgd
cbfdea fcbgade egabd gface bfecga deafcg acegd dc cgdf dca | fcdg fgcd cgfea cgdf
eafcdg cb bedca cdgabfe aefbd gdcea facegb edcabg bac dcbg | cdgb decba gfceda bac
gbdecfa ceabfd edfgb gfba bgdcfe af dgfeba dgaef fae eacgd | dgabfe fa fadeg gbaf
dcaegb gdcfea eadcfb dafcg daecg afd gafe bedcgaf bfcdg af | acdfgbe dfa afd fgea
cfgbdea bfade afecbd faedg bdac aeb fedcb faecbg ba bcgfed | cfdeb egcfdab abe ba
fgcabd geadbcf cdbe ebgdf feacgb cgfeb db gdebcf dgaef bdg | efbgcd gbadfc ebgdfca dgabcf
gebfda ge cbfdega cgde gacfe afecb gef bcgdfa cadegf fdgca | ecdg cedg fcgedba abecf
adebc dbgc abefcd agfde egc gcaebf agecd cg ebafdcg degcab | fgade ceg bgdc gbcd
gacedbf ebgf afegcd beadf cdeba aebfgd fab bgafcd edagf bf | fbge fgcead debac fegb
fcgdeb bgdeca gfeacdb edbga gfea fadbg fg aegfbd fgb fbdac | gf gafe caegdb afcgdbe
cdfeg bd dbfe acdfeg dbfcg dbg afbgc dbgace gdcebf ebcagdf | fcgdb dgb bfcgaed febd
becagf dagefc cdebf gefab dgf gfbde bdegfa dabg gd ecfbgda | gd bfadeg gdf fdg
fcaebg fbadec edgbc fc fagc fec egafb efcbgda fegadb bgecf | fc eabdfg acfg deafbcg
be fbgca fbgade fdgace bcde edbgcf cfgeadb degfc ebf bfceg | cbfdgea bcgaf fcegd gfdeba
cdgba edbgc geca bge gbadce gdfbae dcefb dcfabg gecadfb eg | eg fdbaeg ge geb
cdbfg ad afegcdb ecfba cdfab adec geafbd cfedab dab bgaefc | cbgdafe faebc da ad
edbcf cbgedfa gceb eg gfbad egf gdfbec fabcde bfged gefdac | ebgcdaf ge dgcfeb dbfce
fde fegcba ecdfb acfebd beacf fcdbaeg df afdb bcegd gedfac | gecfba eacfb df cafegbd
edbafgc gd adecb dfga bgdfae bedcfg geafb aegbd gde cebafg | deg gefbcda dgaf edg
gfb eagf cdbfae fg gadbf gdcba dabgef fecgdb dfcaebg afdbe | cabegfd cbdefa gfb bgf
gfa edgfa caefgb gf gbcaed gdcf egcda eabfd edgfac fbecgad | fg fag fg fdcg
gf ebgda cabedgf gcfb cdfbae gef efcab decgfa ecbgfa abfeg | bcgf gf egf gfe
gdae ecfbag badgc ebcfda cbgfd gaefdcb ebgdca ceabg adc da | eacgfb bgadc dca cda
acgbf ceagf cbgafe bfc gbdcfea fdecab bf befg eadcfg dabcg | fdaceb cbf bcf bfge
cedgb bfe efbcg ef acfe fdbacg cdbgeaf gdbaef gebacf cfbga | bagfdc fbceg cafdbg cagebf
dbcgae gfbda ca cbdeg dcgba abfgdec acb efdbgc daec bafegc | agecbd dagcfeb ac ac
bgcfeda gfcba gfe ef degafb eadgb bedf afgbe bdecga gfdace | fe bfde gebaf dceabg
defcba facgeb de cbdea ecfba ebdgaf fecd ade bgfcaed cdbga | dea de acebd ed
bad cgbadfe ecadf ebdcg aedgfb ba aecbd decabg bacg gbfecd | bagc cbag agbc eafdc
cfgde afgeb aec bcfdae gbac abcdegf agdfeb ca gaebfc aegfc | dafgbe eac bgac facegb
gecda eb cbdea cdbfa egadbfc fdecag deabgf bde acdebg gbce | cedagfb gceda facdegb ebd
bgd db fbed fabdg eacdfg dgbecaf cafgb edgfa aebdfg gdaebc | db dfgaec ebdf agdbf
fgecadb abe cagfbd bcdage eb eadgbf dcfea deafb bfeg agdfb | daecgb agfbdec be gbfe
deabg bef caebgfd fdaeb gdebfc fe fcbgda ceaf bacedf bfacd | fe afcgedb eadbf gacbdef
ac gcae aebcd bedcg eadfb bfcged gadcbe acegbfd bac fbacdg | fbgcead cdgbefa dbgcaf bfdcge
egcfa cef cgeab abfc gfedabc abcefg agbdce cf eafgd dbfegc | abcf dafeg fcgbde gaebc
afdceg dgbec egdca bc cedfab ebdfg bacg ebcfagd egacdb bdc | abgc ecgadb abgc dbcaefg
cgefab efcd fcg dfcbge dabgc egbfd bgfcd fc dabegf bedafcg | dgfeb fecd fc cf
dea abcdfge abfecg de edfc ebfac gbcda eagfbd fdaceb daceb | cdgba dbacg badcegf edcf
abgfd fbaegd bfdcga fgbea agcdebf ge gbde cafgde fge ceafb | ebdg gedb cafegd cbdgfa
adbg fecbg caegd bcgead ba aecgdf deabfc cbaeg ceafgbd eba | efgdac becfad fcadbe febcad
cefbag eca cdbeaf dbcefga fbdca dgbcfa efdag decb dfeac ce | cgbaefd ec aefdg cea
bdgfae acgeb cegfd egdca efcdbg dcfa ad gda cgafed cdgabef | ad acedg ad fgdecba
gdfa dcg bcegad gd bfaecg afdcge cedbf cgfae gfedbca fcdeg | gcebda gcd fbedcga cdg
ebafgc da fbdag fgbca bagdfec gdfeb cgfabd dabc egfdca gad | ad badc dagcebf fecdgab
abd bdagfce adfceb adbcf egbfda febgdc da cead acgbf cbedf | bgadef efbcdg da fagbed
bae dfagbe fecba edacfbg baecdf bdec gbdcaf be bdacf agcef | ecfadbg be abegcdf bdec
bcd fegadb gcafebd badgec eadc abdfcg aegbd dc gcedb fcegb | dbc cd abdgcf acgedb
fg bfdeg dfeab dfg cbegfd ceadbg efadgcb cdbge fgce dfgcab | gbafecd gfcbda gfd bdgaec
agcf acb edfgcb fabdcge begad ac dfgcab dgcbf abdgc cebfad | gfedabc badge gacf ebgda
dfgabe fge dbfagc edfca gebc ge badgecf fagec fbgac baecfg | cegfa gfbca fcdbga eg
dagb ebgdf fgbaed ab ecbfadg befga fabcde baf fcega begdcf | gbfcaed afb adbg bgda
dfgec efabcg ebfag cga agbdef beac dgfacb cagdbef ca fgaec | ecbgaf fagce cag bace
ae fgbdea dbcfag cbea begdcaf gea gdecf decga cgdabe bagdc | ae ega bcfagde ae
bgaec efgbadc cgeafb becdga cadbfe bafgc afeg fa bfa fgcbd | fdabegc afb feag gbace
cfbdgea egfabd ed afecg fdaec cdafb cgdafe dae gfebca cged | cagfe cgfbade ed dceagfb
bfegad ecdb acbfg gdb fdcgeb db bdgfc acebdfg cdgef dcfgae | gbd bd cdeb gcefd
dcba cb decfga bagfe gdabecf bdgafc gcdfa bgc ecdfbg abgcf | bc gdaefc fcdeabg fbage
cf efdc cdfgba dcgaef dbegacf fgbea ecgfa ceagbd cfg decag | gedcab cf fedc cf
cg gadcef edabcgf dgfea abefgd ebgdcf acfge cge baefc cdag | gc begfda gc gedaf
bc fcageb cbg cfagd cfgdb agcfed fdebgca dcfbag efgbd bcda | abcfge fgdeac bc bcda
cgabf cf efdacgb cgaeb cefadg bcefga fgc ceagdb ebfc badfg | dbfga gcf gacbf cbegaf
dbg cfbgae dbceg cagd gd gbfdeac cgaeb bfecd agfebd decabg | eacbgfd eadgbf dg agecbd
gebfdc gcabf bdcgfea gcdba fcdgea afbe cafeg bf fbc beagcf | fbae agfbc cbgefad afgcb
fcae baefdgc feadcb cedba fbe fe bagfd bdefcg edafb abedgc | faec dcegba dagceb fgdba
egfbcda ecbfg ebdcgf fcadbg cd ebdc edcgf gafed efbcga gdc | bced bdgcfae dgfec efabgc
geb gfdeac feagc egbfc dbcfgea cebfd fdeagb bcfega bacg bg | abcg cbag bge dacbefg
bcdef afe ecab bcefdg edfca febcad ea cfagd dfbegca dagbef | ea fgdeab afe eaf
acdbegf gbcfda bfge dcefb bgd febadc dcaeg gb degbc gfdecb | fabcdeg aecgd gbd gb
fba cdaefb cbgefd ba afebdg afegb bgacfed fbdeg gbda caegf | ab efdgb bgad dfebg
eaf bcegda fe gacef gefb agcbe cedfbag dagcf defbac afecbg | ef aecfg ebgf gbedafc
fgedb ad fcage dcae cedbafg aegdf dagefc afd gafcdb geacbf | gcaef befagc da dfbgaec
cbdga ecb bcade dgaceb dbeg cbdfag eb fcagbe gebcdfa dface | edbg begd dcbea beadcfg
badfeg af egcdbf deacbf dbacf abgdc dfbagec fba cdfeb afce | cgbad dbgfae fcbad acdefb
ed ced cfaebdg deaf bcgfe bgadec dbafgc dacbf defacb dbfce | afed bgcaefd cgbef gafedcb
gcfba cbdgea aecgdf cdgebf be bec gcbea dbae gacde egbcdfa | agcbf dcgabfe fagbdec ebda
fedbag fagcd dagfe efgc faebgcd egabcd cag badcf fagcde gc | agdfc caedgb gca cg
gbfecad bdafge fgb bfdae eabfdc fgbeac gcdfa bg debg bgdaf | febad fgceab dfcaeb bgf
eb ebd dgcabf gcabde fcedgab aebg cgadb abfdec ebgcd cfdeg | ebgcd cbfgead bfedgca deafbc
ed acdgfb aed gefabd fegcabd gfed bdaegc edbfa bfeca gdfab | aed ade fdgbace fgadb
bg bfecad fbg bedgcf agfdc efdcb cgbdf bceg fgebcad beadgf | bfg bcgfd dcegabf febdac
cd bgfadc befcga bfcga gacd ecfgdb dfabe dfc bfdca fcgbdae | cbagfd cfd cabfdge dcbfga
gae cbfega adbef acebfd geadb dagbc adgefb ge egfd fcgbead | eg fbegacd edgf eg
fdgbaec abfc gebdfc fa afgbe bfceg dbage cebfag gaf egcafd | cfba dageb afebg fcagbed
acfeb ab bdae afb cbfdga fcdae aefcdg ecfgb cdeabf dfgcbea | abf gdabfc dbefac bafdcg
gcadf febgac gfcbed bcgdf gfa dacfe ga ecfagdb cfbgda abdg | agf edfca egcdafb fag
gef cbfeag cafg gcbae edabcg dfaecgb fg dafgeb ecfbg fdceb | cafg fg ebfcag ebcfg
faedbc fb egcdf cagedb bcdfg eacbgfd bdgac bfc gcadbf afgb | fcedbga bdcag fb aebcgfd
afdeb cafeb becgdfa fgce gcabfe fgcab bgcfda ec bdegca bce | gdcfaeb dgbecfa adfgbc bce
dcega fdgaec aegb bdgca gafdecb fcdab cefdgb egbdac bg gbc | bg bcg gbae bage
cabedg aedbf dba gbdeaf gfba decgbf ab gadfbec edcaf egbdf | eafbd gabf fgba ba
gbcda daegfcb efadb fg cgeadb fcbeag agbfd fbg dfgc bfacdg | dabcgfe gcdfba gbcade acgfbed
bgcda gd fagd bdacfge abgec acbfd agdfbc acefbd gdc gbdefc | dg adbcfg beadfcg gbcda
fgbd cbf bcdfag bfgca fb cfgaed abcge cgafd cdfbae bdgceaf | aegcb fcb bcf bf
daebgf cbefdg cdegfa adce ad fdecbag dgcfe gcbaf gda gdacf | cfgba gad da da
cagdfb egcbfda fbadc gdc efcabd cbfgd efgcb dgeabc adfg dg | cgd dbefgac fdgabce agfd
fedcag gadfceb abecfg cgdbe fcedg gafedb fc deagf dcaf cgf | fc fgc cfda fdac
dgcafe befg fec bcgdf ecdba afgbcd ef cefbd aedfgcb bdcgef | cbead gbfe agdcbfe ecf
cedbaf dcbfa cfgedba gdcbf fecbga daec ad fgedab faceb bda | dgaefb cead fecdgba bafdec
bcdef fgebac fdgb fb edcbgf fbc fagdec fcgde abfgcde cebad | bdfaceg fbcdgea fb bdfegc
dcbea fegdba gaedb cbgdef bg egb fagb feagcd dgafe fdabcge | dcaefbg bfga gafb gfdeab
aecgfd debagc dbgfa dab edabgfc cdafg fbca ba gfbde dcbgfa | ab abdegcf ecabgfd ba
cdefbg fcabd cega bdafeg ag begdca bdagc egbcd dgecfba abg | gbfeadc aceg ag egca
gbfcade gecfa fdceag bdefa bcag gb gfb eafbcg dbgfce faegb | gcab gb bfade cefbdg
fe acdbf gbeafd dafgcb afbce dgfbeca dcef efa gcbae dfcbae | afe cgeba ecdf fbeadc
eacd gdc acfdeg begdfac cfdga agefd bcgfa bgefdc fegadb dc | cd cd dabegcf ecfgabd
cde dabfc eagbd abfcdg bedca afdcbe cfeb daegfc cfegdab ec | ce ecd adcfb gaedb
bedacf fc gfedb fecgadb gcdafe degac dfgce cfga cdf cgdeab | gcfed bgfed ebdfg cdf
afdbce gcfadb fg dgcae bagedfc fegca ebfg eafgbc fag abefc | cafbgde gf efadcb fgbe
fgbedac agcbe cegbf cbfdg bcgaed fgebda ef acfe bfe gceafb | egacfdb ef cabfeg ef
adegb bcaedfg deaf fa afb gcefb edbcag efbgad afgbe bagcdf | edbag fba af dgabefc
edgabf aedc fbagc da ecbgdf bdcga agefdcb gad ecdgb cbdega | cbdag ad fgbdcae dbceg
ec gecbfa cagedf fadge fbgeda cbdga cfde eacdg ceg cfgaebd | ecg ec ecfd ec
gcafeb egbdc bdac daceg dbfge bc cdafge ebc cgdeba fabdgce | dgcbea dfcabeg gdfeca cbdaegf
aeb edbgcf ba dbcge adbg cbgeaf bceadg faced cbaegfd deacb | dfeac bea cebgfa ab
fgacb gdeafb fegabdc bfagec cgf dcbaf ecgfad cbeg cg afebg | gfc fagceb cdfgae fcg
gb gdb gbca ecfgbad cdfgbe afcdgb dfbga bfead gcafd feacgd | beafd bdg dgb aefdb
gb caebgd gfcb aegdfcb acfbe edgaf abg bgfea beagcf dcefab | bga dafge agbdefc efabgc
febcga bfgcda afc cbagefd agcd bfecgd ac dfbca cbfgd befad | ac fca afc cdfab
"""

digits = %{
  0 => "abcefg",
  1 => "cf",
  2 => "acdeg",
  3 => "acdfg",
  4 => "bcdf",
  5 => "abdfg",
  6 => "abdefg",
  7 => "acf",
  8 => "abcdefg",
  9 => "abcdfg"
}

segment_frequency =
  digits
  |> Map.values()
  |> Enum.map_join(&String.graphemes/1)
  |> String.graphemes()
  |> Enum.frequencies()

# %{"a" => 8, "b" => 6, "c" => 8, "d" => 7, "e" => 4, "f" => 9, "g" => 7}

digits_length =
  digits
  |> Enum.map(fn {key, val} -> {key, String.length(val)} end)
  |> Enum.into(%{})

# %{0 => 6, 1 => 2, 2 => 5, 3 => 5, 4 => 4, 5 => 5, 6 => 6, 7 => 3, 8 => 7, 9 => 6}

digits_by_length =
  digits
  |> Enum.map(fn {key, val} -> {key, String.length(val)} end)
  |> Enum.into(%{})
  |> Enum.map(fn {key, val} -> {val, key} end)
  |> Enum.reduce(%{}, fn {key, value}, acc ->
    Map.update(acc, key, [value], fn existing_value -> existing_value ++ [value] end)
  end)
  |> inspect(charlists: :as_lists)

# %{2 => [1], 3 => [7], 4 => [4], 5 => [2, 3, 5], 6 => [0, 6, 9], 7 => [8]}

Part a

defmodule Day08 do
  # Part A
  def order_segments(pattern) do
    pattern |> String.graphemes() |> Enum.sort() |> Enum.join()
  end

  def solve_a_signal_pattern(signal_pattern) do
    case String.length(signal_pattern) do
      2 -> {signal_pattern, 1}
      3 -> {signal_pattern, 7}
      4 -> {signal_pattern, 4}
      7 -> {signal_pattern, 8}
      # -1 = unknown signal_pattern
      _ -> {signal_pattern, -1}
    end
  end

  def solve_signal_patterns(patterns) do
    patterns
    |> Enum.map(fn signal_pattern ->
      solve_a_signal_pattern(signal_pattern)
    end)
    |> Enum.reduce(%{}, fn {key, value}, acc ->
      Map.put(acc, order_segments(key), value)
    end)
  end

  def decode_output_values(output_values, dictionary) do
    output_values
    |> Enum.map(fn output_value ->
      Map.get(dictionary, order_segments(output_value), -1)
    end)
  end

  # Part B
  def search_pattern_in_dictionary(dictionary, digit) do
    dictionary
    |> Map.to_list()
    |> Enum.filter(fn {_key, value} -> value == digit end)
    |> Enum.at(0)
    |> elem(0)
  end

  def solve_remaining_signal_patterns(dictionary) do
    #   0
    # 1   2
    #   3
    # 4   5
    #   6
    segments = %{}

    one = dictionary |> search_pattern_in_dictionary(1)
    four = dictionary |> search_pattern_in_dictionary(4)
    seven = dictionary |> search_pattern_in_dictionary(7)
    eight = dictionary |> search_pattern_in_dictionary(8)

    # Digits 7 and 1 have a single segment difference
    segments =
      %{}
      |> Map.put(
        0,
        ((seven |> String.graphemes()) -- (one |> String.graphemes())) |> Enum.at(0)
      )

    # Only one number misses segment 5
    segments =
      segments
      |> Map.put(
        5,
        dictionary
        |> Map.keys()
        |> Enum.map_join(&String.graphemes/1)
        |> String.graphemes()
        |> Enum.frequencies()
        |> Map.to_list()
        |> Enum.filter(fn {_key, value} -> value == 9 end)
        |> Enum.at(0)
        |> elem(0)
      )

    # Number 1 has only 2 segments, #2 and #5, and now we know #5
    segments =
      segments
      |> Map.put(
        2,
        ((one |> String.graphemes()) -- (segments |> Map.get(5) |> String.graphemes()))
        |> Enum.at(0)
      )

    # Number 6 has the segments from 8 minus segment #2
    six =
      ((eight |> String.graphemes()) -- (segments |> Map.get(2) |> String.graphemes()))
      |> Enum.join()

    # Only 5 and 6 miss segment #2 and 6 is known
    five =
      dictionary
      |> Map.keys()
      |> then(&(&1 -- [six]))
      |> Enum.reject(fn x ->
        x
        |> String.graphemes()
        |> Enum.member?(segments |> Map.get(2))
      end)
      |> Enum.at(0)

    # Segment #1 is the only one to show up in 6 digits
    segments =
      segments
      |> Map.put(
        1,
        dictionary
        |> Map.keys()
        |> Enum.map_join(&String.graphemes/1)
        |> String.graphemes()
        |> Enum.frequencies()
        |> Map.to_list()
        |> Enum.filter(fn {_key, value} -> value == 6 end)
        |> Enum.at(0)
        |> elem(0)
      )

    # Segment #4 is the only one to show up in 4 digits
    segments =
      segments
      |> Map.put(
        4,
        dictionary
        |> Map.keys()
        |> Enum.map_join(&String.graphemes/1)
        |> String.graphemes()
        |> Enum.frequencies()
        |> Map.to_list()
        |> Enum.filter(fn {_key, value} -> value == 4 end)
        |> Enum.at(0)
        |> elem(0)
      )

    # 9 is 8 minus segment #4
    nine =
      ((eight |> String.graphemes()) -- (segments |> Map.get(4) |> String.graphemes()))
      |> Enum.join()

    # 3 is 9 minus segment #1
    three =
      ((nine |> String.graphemes()) -- (segments |> Map.get(1) |> String.graphemes()))
      |> Enum.join()

    # 0: [0, 6, 9] have 6 segments, and 6 and 9 are both known
    zero =
      dictionary
      |> Map.keys()
      |> Enum.filter(fn key -> String.length(key) == 6 end)
      |> then(&(&1 -- [six, nine]))
      |> Enum.at(0)

    # 2 is the only unknown digit so far
    two =
      dictionary
      |> Map.keys()
      |> then(&(&1 -- [zero, one, three, four, five, six, seven, eight, nine]))
      |> Enum.at(0)

    dictionary =
      dictionary
      |> Map.put(zero, 0)
      |> Map.put(two, 2)
      |> Map.put(three, 3)
      |> Map.put(five, 5)
      |> Map.put(six, 6)
      |> Map.put(nine, 9)
  end
end

input
|> String.split(["\n", " | "], trim: true)
|> Enum.map(&String.split/1)
|> Enum.chunk_every(2)
|> Enum.map(fn line ->
  [unique_signal_patterns | output_values] = line
  {Day08.solve_signal_patterns(unique_signal_patterns), output_values |> Enum.at(0)}
end)
|> Enum.map(fn line ->
  {dictionary, output_values} = line
  Day08.decode_output_values(output_values, dictionary)
end)
|> Enum.concat()
|> Enum.count(fn x -> x == 1 or x == 4 or x == 7 or x == 8 end)

Part b

input
|> String.split(["\n", " | "], trim: true)
|> Enum.map(&String.split/1)
|> Enum.chunk_every(2)
|> Enum.map(fn line ->
  [unique_signal_patterns | output_values] = line

  {
    unique_signal_patterns |> Day08.solve_signal_patterns(),
    output_values |> Enum.at(0)
  }
end)
|> Enum.map(fn line ->
  {dictionary, output_values} = line
  {Day08.solve_remaining_signal_patterns(dictionary), output_values}
end)
|> Enum.map(fn line ->
  {dictionary, output_values} = line
  Day08.decode_output_values(output_values, dictionary)
end)
|> Enum.map(&Enum.join/1)
|> Enum.map(&String.to_integer/1)
|> Enum.sum()