One Elf has the important job of loading all of the rucksacks with supplies for the jungle journey. Unfortunately, that Elf didn't quite follow the packing instructions, and so a few items now need to be rearranged.
Each rucksack has two large compartments. All items of a given type are meant to go into exactly one of the two compartments. The Elf that did the packing failed to follow this rule for exactly one item type per rucksack.
The Elves have made a list of all of the items currently in each rucksack (your puzzle input), but they need your help finding the errors. Every item type is identified by a single lowercase or uppercase letter (that is, a and A refer to different types of items).
The list of items for each rucksack is given as characters all on a single line. A given rucksack always has the same number of items in each of its two compartments, so the first half of the characters represent items in the first compartment, while the second half of the characters represent items in the second compartment.
For example, suppose you have the following list of contents from six rucksacks:
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw
The first rucksack contains the items vJrwpWtwJgWrhcsFMMfFFhFp, which means its first compartment contains the items vJrwpWtwJgWr, while the second compartment contains the items hcsFMMfFFhFp. The only item type that appears in both compartments is lowercase p.
The second rucksack's compartments contain jqHRNqRjqzjGDLGL and rsFMfFZSrLrFZsSL. The only item type that appears in both compartments is uppercase L.
The third rucksack's compartments contain PmmdzqPrV and vPwwTWBwg; the only common item type is uppercase P.
The fourth rucksack's compartments only share item type v. The fifth rucksack's compartments only share item type t. The sixth rucksack's compartments only share item type s. To help prioritize item rearrangement, every item type can be converted to a priority:
Lowercase item types a through z have priorities 1 through 26. Uppercase item types A through Z have priorities 27 through 52. In the above example, the priority of the item type that appears in both compartments of each rucksack is 16 (p), 38 (L), 42 (P), 22 (v), 20 (t), and 19 (s); the sum of these is 157.
Find the item type that appears in both compartments of each rucksack. What is the sum of the priorities of those item types?
test_input =
"""
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw
"""
|> String.trim()
"vJrwpWtwJgWrhcsFMMfFFhFp\njqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL\nPmmdzqPrVvPwwTWBwg\nwMqvLMZHhHMvwLHjbvcjnnSBnvTQFn\nttgJtRGJQctTZtZT\nCrZsJsPPZsGzwwsLwLmpwMDw"
input =
"""
QtGHnGlcwQGvHwMHGnnGfRFCJnRBfVVJRVBfCFBh
qsDjzNWhmspNNqVrfjVfjJCbBVfB
DLhPTmNDTzTqzpmzLpswGMHtMgwglcPQMQvSGM
ctwDjvgtltgglHrSHCsQWBBDfS
ZJZdVnmhmfCprnBTfS
dNddhhdPRRdbdNcvwCPCgCctjPlF
MNNDGMWrQsfhtrTnrm
jcvRPRPJdvccRNFNCjLdcwJCSHtHPmzhsSzPHmfhnftnTffH
RddRcjRvZgZNWNgQQb
fPrvhqhRPSfCCfhrqtbtLcmZmtHCtpCFcc
WFQJlTdzgGJVQGWQTzdJcHbQZtLtHmbbZMZHsZQm
JFNlzTBNJGlNPSRhfqRRrN
tdVVgttdDtJJsNPmzdQmjcPP
CBTMmmmbTBHqHMwQcZPWWsWnzbbnzW
CGlLFCTMGvqBGvGvGSRSRfmtRRtgVgrSLS
LHSGJLWZLqHQHpRHRz
bpBPVtpCwPgBCtqqvzfzMQvjbbjz
lhVsTgPlBNThpBNwBtVThPnrGGWJZnLZFnFrGWsFrWZr
nQbbbjpnsdsGCSlmHtJmvljHMjWt
cDcgThLVcPTHVlVlHllvWp
cwpgghTcRRczDhnQGGCSdfszdSbS
vTMFDNTlDhjTDNMNJDwmWWWfGPfLnnzLGfMmmL
bVQgbpqqtctzLflltnCz
VSqlVSHRFvNwJSDj
RfZfjljffssWLWPTGPjhzT
FDCvMDMJJpBJpBFJCMBDMtPbWbLVPGztWPVTtPmLWGhQ
DpgHggpwBJwzJMrFFvrCrHsffnRScNsdclSnnRnSNs
wTvfHSvSwssPGCLCPhgSCn
QNpMRqRJQMZlBBbRRRMfbZlBhPChghhlChGCtnthctjPhchh
rrrNBbMZqRbqDsFHTwfWTFFwrF
fVgfQhhgfTLHSLNZZHfZ
CDtsqrqlDtqDddsqjsstHrSlNLWLcSZScFWWcNBFcBcc
jrCJrHjDCMMDsJjJMstThppgwvGzVGQzhJvvng
DGlTlSzbSnzmwbmblTBBPgffpNjFHppZBH
WqQdWqqJdCrtvQtJLQjtdcBNfPsNZfHZZsHNNZHsBBHL
cCJcjdRvqrQhqvWMzlbDGVGbSMSnbR
BfQmpfpmsRCRPDSZVSjjSg
MhNJGMTMHGGTbnGMJrbJHTzzdPgSwSqqPjPdZddSqNSwPZDw
TWbWbhnHWBFBFBDD
FrlJbTcBTcrlTlqwZTwWdhWLChLtVhdfLhmwWC
pppSpzBGMMMjSSMSzMNzHRSDVWGWDWVCDtGdtdhLhftthd
RNNgpMPRNgzggFJcBPqFZJZrbc
SdvnnvvntnbDDqtz
wRpFRRspZhgZgFggFMgtczcGGDzQcGlGDMqcDG
CLLCFNZhsppRvvttBPCjStdT
JJDMhSwmMwBnnJPJmQcFtfQtfgQhQQfcgH
ZvCvTGqGVWTZZWptQggGtHfDgcpz
dsVCvDTZWWbZqqCZqVsqsqmNlPNnSJmbNNmlmMSnJLBl
MGnMBMBJFpBcNpdwRWRvRNdblmwW
LSgtPCChgjCPgSSzCSqWLLbrdWlmwmwmFvml
QhHPVSHghCtQFgCzgQhVnDGMGffnpcZMcMfJDf
QwrJqMLRLtBQRtWLJLvQLMrMgNNzPDngNHlHnbbbggHlgZNt
GdfThGcmShTGSfppmFfTHDNNblSZDbbzlBzZZHHg
TffmGBBFcCFFmTGFhBwjJQJMQWqWQCrrvQMR
mRbrjZzRLchHqqdLDllh
mCGCsJSggCmgSGShlhhDVVVwhqSltV
PsfsGNGJvGPfspvcmrTRBrjTZzvT
NRNqFFtqqFrDDQRcJJJNrWDswHwWwbDVTgTwLbVlVD
ZpdHHGPmgwTwldbw
HnnnMPMzChPmnpnmfFJCRqcJqJRRrrtSBc
LnNNLBmTNBNTwNZZjZmRMHJwMHvbWrvPMMWdcP
GtSFDFpzsGVvMJdJsrMbvr
SqQQGGtqqSVtDpGtplVDpVJClmnhnTZNjNfmnmBChCZL
CHltTDsjHNHHdpDRmqdPQpzd
fMMbbZwLJgMVVFmcRqRpzdqbRm
MJJWfnVhMzTNGlNTsh
WtWbtWvrrQGrbcSWHHfSHfgdWJ
zpnPhLPhPnTMMnzMzpMnDzLPjTVjccSgdmjdvSJdHSgdjScj
qqvMMCnDCCCzqqCzhPlLsRsGtrsNlRbZtBRtbrrQ
mPTmlGQnjNTPQQNljnlQnmmCtgRPhghqgqgzqLRPtMqqMzhq
pDsVSZcdVspbdBpcBHBcHhqLWzMbfhMMrMgMgzLRft
pFZpJJFSBFRllvlFNC
pbMVjJbwbbLqlZlstRhjstsN
FSTnfCBcnBSBvSmmCFCCRQhZBZNsRGlsQQNsqZlG
dvcdfFcqmfcmdMdJgwJJHMbH
QSRlWDhQQqDqlTCjTRCSljSmVsPmmGmzsgvppzPVVzdPSP
HHwtMNMZvfPGbdwdggwG
ZFcNMFFvHLMjlCWrqhqchh
jccDSGVVlRLVSVVScWZZwLvbphgwdpLwZv
BQHBtfQQHBfmMtmFznrHzmDwghWphvZZFpDhZvgvpZhh
DmQrPQnBtTnzrrfHrtfMrmTCGqPNjSPCRRGjRCRRqCNjVN
bRDbbtVgPFFbDfgVCtPcGsNNsHccqcGGWCNNzW
ZwlmJwwRSmlJdQRhqGNTqzGTwzqGhc
ZQdZjpljldrSMjmjdRLdmdbVvvtDVFFffvBFPVBgMnBg
rzwGrwPGppqzPMzrdqsssSsvgtQgTTTJsH
LCNNHLmHWvCJstsJss
cfVLLNBmZBVMVDHGwrhM
FCGFrJltMGdFdGtlFtCgFzQfQnZfVVVMDcQDVzVjfD
PSPSPZPRbPRsbBRbHBTPvfVzQcDQqWWnDjnnHDjzcz
RmSTPwSTRpvSlZglgZprZtNp
njtLGLbcNTbbLnLmNTtqnFzVPwJFFzPVFPwMVmfMmV
srpZlSpsSVqgSPJJ
HZsHsrZhrBQpqQvpdprnTnnHTbGLbHnjHGbjbT
vFFnJjvnVSjgCqSCDZ
lswrrcsQrHTHwdrDdhmqqsRhzmggghgsGC
QPrWQWcDNDHdddNrQPfDMLMLtvvMbnBpPFvpFFvL
LgltlRMtcccgMdlzqTVwwrdsqm
FpvfSDNzSpnvGSnNpmsmVqVVrHwvTqVmmw
pGjDFFDpffnWQbnzjLJhhLchPPJMPBLt
lJqBqPvtvVPnttnJjJBjVMzMrFhdQrQFbGbQnrbzGG
msRgTgmTLLmsTDRfQRllMdGzdRbMHQFF
msfDWglWTpSLCgTpSCDsfPjvjtwVjJZqqSSvPVZSqB
VZZWGZGlZZZMZrGMlQBQGWltFzqvzzcVcgzvmgzddccgvqFc
rLjNrDRLDRLTqdCqFCNzFgqg
TJSSbHfDDfSnbpHpJnGhWPtrZWnPhBwWPWBt
ssvsDDjNwhjNhGGgDDRZllltLCLvCWbMffLCfWzb
qVRmJFSQqqVcqSMWMWLMlllbtbVM
PqQBPcFJFcmdrJPJrFrQpsNjnTGgwTwGssRNRnRBsG
sHsJJfSsrpBLHCLJmdqgdZgRNZQlgRNC
VtnFbhFhwjwVPPjhbccQDQqgRlWDQmdWZZDd
hFhFvbhGwzvFbtbPnttGbtjsLBfspSrMvJLrpJTrMsLZrH
nzJDJvvZznnqnZrpTgTpzzTNjlmtsglBjjttQQCgCCtlBj
SRLRfdVfSVcfHdVVdSLdMHQjPtClsmcwNQltjwjCQQwm
RShVLWWfWWGvsTZz
vcdptvndNzrndjctrvcnvtTdbwwRTgwbHDFDTWgqWlWqwqbl
ffVBmQPhshhfPmSfBPfChmmCWFWbDWFbWwwqRDbsgwWMbWFb
SJJCBLZBhfvnJnpGtvRc
HLMMHHpNqWHqFqppPWnshtsLhBnVDtthLLms
JgmSRgCRGbgwGSbgJJjRRDntztrVhnsDrllllwhhzt
bRRCCjgRvJQQdcdjjvRcQdgbZPZpqfqpHHMfNFqNTPWqQWmq
PPwQTlFrLqrLQrPfPJrHtcjtSvdCNNctLCjNdc
DGZMhmVRMGqVmVDnGMbBZhsjHNvjdstddjdjccSBSjds
mqzVnWDmmGzRhqRbbWQQFwPQQTlzPFpTlPJJ
RMmnMrZMlQQpGrQt
gPPgcDBcjdgjBCBcQtNDNzzthltGphhz
FSvPSSjFWFScSWdjWvbTwWJQZQVRsMTQVwTmVR
PwlbMTDQDvMwttThPthhvhvvZzNLzNZjQCNNLWLCRZWQRzNW
VpJHFpgfqdFqqHFGHVSdGmZZRnSsnLjNZCWmmszLSz
drrJRGJVrcMBDwhDbcMh
hghHTgbwHbDqHrgbbbSLzzFNnsVqNVBnLnfs
jMlcMRRmGcRlZQMMJRJSPPmCFzBBzpfBfLfpFLszLNNFVCfz
JlmGlZmvRMgvrgbrrSTw
ZtTTHpprHtQtHtpqPmjVSScjVSjjSNqw
nRvGWhRbnRGzvWCBGPjNdwcSwcnlJdmmSj
vCbsmbWfRsRWWzsMWBQFFrDZpgpFHLgQLMgQ
QlJBfZssjgZsQsDNbScdDZdNcvvF
zrGrVVpVMWMwMVLMwqVWpRdNFSDcFNDFbSddqHldDdqd
VLVtrWpMRCRLWGWMRwVGCVPfCPJnBTQsJlmjsfsPBQjC
GQqpnnFWFcnWpBMhhSZRhQCCCfRQRD
HsbcczlrjzflffLVfDlt
jssvwsHPsjzWdMcgBnvqMB
JMJdMptTbbtpJZhtTMZwJdNWQBPNBlwNBNQWHBCHHPlg
rVqsvVmjrcCqCPsPNQgnsnQglW
rVvzfqvLjFVDVcLjCqLmJFGbpJpRJTGMtbRpdGRG
LrmwdZHlSlcVlSrrDWCzbtpjpgzjtD
gBGgPTTBqPQTqnnPJhMTTCzzppnCvptpnCtzNpDntz
qQPTTPshRRQqcgsflHZcsSLV
smvdTvlPzslmVjMhJlbjrblJ
cqFffFffcwFfpcDSjcnZwZWrQVDrQBhNbrrNBbWVbNhr
nSpRZRjpcHqpCpqnqFRGmvPLtLGmCdCsGLLdtC
PJPLPPHDdPvdnbctfcpt
NRrGNjNzLjltppvpRSRS
LzVWLjTWGLQqBgZWJWBBFg
znzccGnswWrWNCpvvdTCzddC
RfZlRDDDZflSBMhhhPSMMZpmpHHGNCGTmCJTmvmCvJGR
GbBMhhbSMhMffDMZPggSGfhVWLwjsLttWtrjWscVLWnQWswn
jwRzdZZhwhwHSQqpStJHhp
GVGPBvNPvffpvtvp
nsGGDVtFNGgGWjWlTwrwTmjwTR
MQtmmMMmnHGGTmhw
llqvqvvpqdvvrSfrpSfdfnhFSTMNDHFMNFFSGFwMHT
JqvvRgpCfrzCpqqzdfRpRllWZZBQJbVVtMttsVWJbjPbcc
zgqBczqBbBGjdHVgdDFd
lNVhNNnLtZZZGWjdWrSW
PCQhNflCtCwtJwhClMmVcRmpbPqTcmBqpm
wWbqbTwVrQLqlMtrZtZffNfMfP
vhjqqRpRvZsfssZN
ccBjJBqGpRhDGbJldHlgLwddLd
hVScjtgcchVhSgZJSchVwLbNLWnLNwwnwrbWNLgr
BzMdBqzBQzZQPpfrsrbrNdNLsrRR
zPMzmmGpmzGlFQPPmlZPzSVTSVJJcSlcDhTlvSCtjJ
hzdwlqngZQvDfmzF
vcRrcsVNpVQsFfBfPPQB
HCHVWVcCpNMHWRjLwhvhggdjvggM
LBHCTPzHHBcClwppwjjNNl
JddZMRmmssVmvDvJddSJWVWBwpQvwfpwvwwfrrFNQfwjpl
BsVMVZDVZssZhMhJqLzhzzHzPTPnLGqb
bcnNQnBTvvvWTQTJhdHJzhSjpJJjStjd
mMwqwVMMRwhBtjdSVBVl
GfsrwCRmZBcZTvBf
bBjQmmmqWdLqvLbWLtNJccNZZgCBCZgCTg
phfpfzpHPDwfMwvVzlhlJJlggcZgZcRFFlCgZg
zfhpMMDpVVzzhHhzzMMwfnMfSmQmbQvvWqWjmLSqdQmrqjjn
ZzdcbGTwLZwPPwpMPWpjWPpWChBC
nmznNRFHQrqQvqqmmMfWWWpMFjspWFMWjB
zqRDSmDrmvnvntGccGdcTVtLTlVG
nfnVscTcDzsZqmRtjtsqjJ
wnnhWPWLBNwPLHdQdWdHPHLdJjqRRqrvjrmqFtvRqtQRqFjm
bWhHdBBLdLnShWHcTVzCfCpVDTblpT
WSjVFSVTSWvgvFwpgTTFsfdVclhNCfsHnHlHsCfV
zRqLqZqZZQcdNltfHzsd
ZqBqGLLRcjWWBvTT
wwBqgZfbgbZsvWmfJrtFrdDttqdFdLct
SNSSVTnnThnCSPPnzVztQJJQdLPtFcGLdFGDsD
lSlszRVsRjmmfjfRRf
NGzGWSLzMdQtcctbgWjt
vqTnfVVHBffnCmHgMtrrrHrgtcrt
vqCDVlFnnCnnBSzlspSzLSNMLL
rwVlfVMRSTqTgRhT
pppjLtpZjHFHNhsctSqDDVtnns
HNjJLFBFHZZzWbVBZGfwdGrMfCCfGvmzlM
zFzztqWnJttqqzJtdqbtqbPVMGcGZwgPGVwGQjwCCggMZQ
hssLlrsSrBmBrZGSfgwgSwQCcj
BmBBDBHLrlNhLNHrpsDvLJNtddczdRzzcTqJzzdWnc
pLWcpGSscLQPDzLBgdbmdZHBHmZB
lntfCfVMvtttqVqnZHHbbBZmwwwCdHhc
qqRJFfRFRNlTzSSWWzSJpc
DrphDfFrdGGjTTgTgCSV
vbsMZPnPvqHMQvtZZPWBBVVBJjWSVTPjJC
nMbnsRSQvvLRMsssQhdFrcwczLlDrrDzhz
LLlDQlcLDqLSlCDRlRDCqTTzzgNzShSBdZGBFBBgNG
nHnMwPPbrWwpmztdMtzFZZFtTN
PJfbZmHrpJfZDRLlDlLcVsVJ
wZwQsrrzQFQSrRSFbzDglcdCcdljjdlljcvslLhv
VPqGJtqqfnJcCLFllFMGcd
fNHPJWpmHfffqJHmwzgbrBDZrDbFRQ
HggtSJtzrgltshlTsrzbzsgbFddfffDZwZRZZZGfGDRTNNZZ
LnjWccmQBPWqmWPqMfFNdGBRCDFFSfDfRd
WpMjWpMcWSjqqPjQLmvmjMgllsbgbtvsrrtvJgJHhrHl
PMcMcBpztMztzPPhbSgGSvgfHD
nsmsVQVZVQmTRmddrLgfFhfLgLDzgvffDhbF
dwsjrQQrVwTmZRTzsTdBcjqlqWpcCCppcllltC
DbVjbjwNMDTCVbhbTNDrVTTmzFGLFLHcLHzmcWFczLHwmH
PPWsfBZngtZqZZnPgZnPqvmFmczgRHGmGSRRSSLGFF
sntBlWPdnspnnPQZtnNNNMjhMNrVMjMThjpr
rCrCWVvvWDnBWvDnWDMCMZTpThhGGhGRGqGqZmhZqV
NNjQMzNzQjjwNmJNmZddpdTG
QwtwLPcjPtQlHSSslzwHSlPQDfDWsggsvvBvDvnvgngCnvFM
ZDCbvbDvvHbCGTWpZTtWWQnn
hLqzLVhVwNwVfMnJrfqMzWrQddgmQQGdgpgQGmgjTj
wlVNwJJfVRLPRnHRbFHRsP
lLmvLGRCrmDwVPVsjmtBBQmt
NSHWNbzSHWpSpfChqqJPnzBJsBPPJnQJ
pWcHbNfWpgZcWbhbZSgchWpRdCZMMdGDFFrLwlwMRRZFdd
PnNrFVZQHNDrmNQPflbhbfqbvhwbVfvq
TCdTtpCtCWTBMtjTJMWtBMCLSfvbqqzqbljflwDLvLjLLf
MCCGcpCJRWTTMGmPnDFNQQnDns
FhSmttZmgLjJVMlVGllGjcrj
NRNvNWNCdnNrBvWvwRdWvvvRCGcbVVQbMQGcGcVcMclzVVlG
qwBsBWwnvdtHJJSrtHsr
wnwPrnBBPgqRPjhgCRGCLvvbRZcJvCbb
dWVdVdlMHtsTslMtzztFGGczvvGJzL
fMflHpddJfNNVfNWWmDqQpwBgwnjPBQDjqBh
WttGctsNCNrfwTMlBtlr
HJLzLJJVnFjHbnbVjDHDdFqwwffTTfTGwrqwBBTT
jgVgJSbnHjNWsWCSWWGG
ssLfHLvrrfMMlBMRMfpd
qbbhmGCCVDQhQQVzDDbqmhMBtDZdBZHlddpltpBpdlJd
QhQbzqCGzVzSbqzLHjLgrcjvPSnnSL
NGGZGsGFCGvCcnCcgnZWrPHjsJjHjTDjJHfrjHDP
RzzQmwwmdRRwMqRQmZwtfrDPfTfrbjHqrDPTHr
MBLphmLpSzdRlnWZCNcGLgLG
LwPPHZLLWRMWMsHqTCjmTTjSTn
lFpNNpzplbfphzNcQzVcpvzsnqTsggmnjfgqCDsnCDqsgS
vFJJhQVhbcVddLtmWZJdmm
GwMNMGBMRMGjdSGsDntglDrDGQ
WTmPPzfmlQrsnQmg
ZPTJVvllhBwvLvwRwj
nlSvqqFqzfnbnvFwwsGHTBHgPfWsTrRPgG
dMdjphVhhgdLVJhNRBGPRWWBBGPTTGHV
thJgLpghLNLhNQMCtdMhSmFlQnzzwnbzlbqqSQFb
ZJJLBWhJBNwJwLvgRgGRgbZqbHTbGT
cCrfFFnzjmdrdrmmzsgSPSHSbHWPRgrgGR
dmCFntnFctjfdVtttjtDVncfBDlNJJppwQMwNBNvvplppWNh
GGNNNbNbqmsmTVbCDQQhDJQT
rgPvdgMdPdBddvMcrMnvgcSwhClTTJCwClDTvLJJthTlth
zBdWpnDBDmfFGRffzH
WNNNWcDcdVHNQTNT
lLvLctvrvvvPCpHLQQTZVQLTTHBV
zltgpbPCrrmtlmrlhhbqcWMqDDMDFMfbGScc
dzSHRCGZGdRQWQWtllWB
mNmbLbbmwjsmsNjDmcPvpVHBVPQvWDWBBpvB
jnmNNrLcnnjjHhSCdGMSfrfd
mgGvfvJSmSSrbvScmGccTPCqNnRjlpNNfNjqwqlpNpfw
zZLLQFFFtsFwWjjRqbbCsW
hBBLBdFHddVrGbVc
bJGchsCcHwbHfgvg
qdlSSNqLPqlPQZDffgfZRZMghvZr
PLtqtFTPNLlWlqtQqqQzBBmcnschGtjtnChmzC
llNLDLzjDtCTVtClCDMHSlmwdmmdSmddwZSS
gPJszvsBPbwSHZRQSJQJ
bgFssFPcWhDjCzLcnNDD
ZTGMwdhMwMJphZMJlNdVBCnncNPLBCCRPnCncn
fWsqmfSsqvfFFFvmWjfSSsPLCwVPRnPRCmRnRRCVzRCV
FQfQfvStwjtqsjvvQWFfWqWtlMDdGTJJGdMdhJtDMbllDZ
DzZLpBDptpVPrrrFPqRmBj
WsfCTTgMllCWJMlhslNsCFJrGqvmRPqmqZjGFjvmvm
HfghcNghHhgNNfbDDZdcdpndDzpt
RRBRdJfccVRdDJqdDrvwShwvztWJlWwSJn
mPtCHPPmHbmHNZjjjQHbMSgrSWhWzWnnQwvzzrlrll
tpFmjpmjFMCmppmVTVLFVfBqTqVDLd
jtljZcTcVVtdggVmdczzzDPzvCsvRbDsDmvm
MHHnnJMFMNpwSNprpMJrfsbPRRbWDGLbHLDRvzzssR
rJFNvQfBSwQBwNwldZTqTtctQchthc
WsWTWsfjgTJGSnTz
RHNmvRLCpJclcNcvHpNcPBzgQgMnnGFnLFgPgnPF
mHlcdbbccZcCCCNZZNcCWtthWbWqwwJsbDfthfwW
vFFzppnHFrjmpljQhg
JPGfPWVdwfPgQzVQlTrQrZ
PwRJfGDBfCHMzRHNHMNR
"""
|> String.trim()
"QtGHnGlcwQGvHwMHGnnGfRFCJnRBfVVJRVBfCFBh\nqsDjzNWhmspNNqVrfjVfjJCbBVfB\nDLhPTmNDTzTqzpmzLpswGMHtMgwglcPQMQvSGM\nctwDjvgtltgglHrSHCsQWBBDfS\nZJZdVnmhmfCprnBTfS\ndNddhhdPRRdbdNcvwCPCgCctjPlF\nMNNDGMWrQsfhtrTnrm\njcvRPRPJdvccRNFNCjLdcwJCSHtHPmzhsSzPHmfhnftnTffH\nRddRcjRvZgZNWNgQQb\nfPrvhqhRPSfCCfhrqtbtLcmZmtHCtpCFcc\nWFQJlTdzgGJVQGWQTzdJcHbQZtLtHmbbZMZHsZQm\nJFNlzTBNJGlNPSRhfqRRrN\ntdVVgttdDtJJsNPmzdQmjcPP\nCBTMmmmbTBHqHMwQcZPWWsWnzbbnzW\nCGlLFCTMGvqBGvGvGSRSRfmtRRtgVgrSLS\nLHSGJLWZLqHQHpRHRz\nbpBPVtpCwPgBCtqqvzfzMQvjbbjz\nlhVsTgPlBNThpBNwBtVThPnrGGWJZnLZFnFrGWsFrWZr\nnQbbbjpnsdsGCSlmHtJmvljHMjWt\ncDcgThLVcPTHVlVlHllvWp\ncwpgghTcRRczDhnQGGCSdfszdSbS\nvTMFDNTlDhjTDNMNJDwmWWWfGPfLnnzLGfMmmL\nbVQgbpqqtctzLflltnCz\nVSqlVSHRFvNwJSDj\nRfZfjljffssWLWPTGPjhzT\nFDCvMDMJJpBJpBFJCMBDMtPbWbLVPGztWPVTtPmLWGhQ\nDpgHggpwBJwzJMrFFvrCrHsffnRScNsdclSnnRnSNs\nwTvfHSvSwssPGCLCPhgSCn\nQNpMRqRJQMZlBBbRRRMfbZlBhPChghhlChGCtnthctjPhchh\nrrrNBbMZqRbqDsFHTwfWTFFwrF\nfVgfQhhgfTLHSLNZZHfZ\nCDtsqrqlDtqDddsqjsstHrSlNLWLcSZScFWWcNBFcBcc\njrCJrHjDCMMDsJjJMstThppgwvGzVGQzhJvvng\nDGlTlSzbSnzmwbmblTBBPgffpNjFHppZBH\nWqQdWqqJdCrtvQtJLQjtdcBNfPsNZfHZZsHNNZHsBBHL\ncCJcjdRvqrQhqvWMzlbDGVGbSMSnbR\nBfQmpfpmsRCRPDSZVSjjSg\nMhNJGMTMHGGTbnGMJrbJHTzzdPgSwSqqPjPdZddSqNSwPZDw\nTWbWbhnHWBFBFBDD\nFrlJbTcBTcrlTlqwZTwWdhWLChLtVhdfLhmwWC\npppSpzBGMMMjSSMSzMNzHRSDVWGWDWVCDtGdtdhLhftthd\nRNNgpMPRNgzggFJcBPqFZJZrbc\nSdvnnvvntnbDDqtz\nwRpFRRspZhgZgFggFMgtczcGGDzQcGlGDMqcDG\nCLLCFNZhsppRvvttBPCjStdT\nJJDMhSwmMwBnnJPJmQcFtfQtfgQhQQfcgH\nZvCvTGqGVWTZZWptQggGtHfDgcpz\ndsVCvDTZWWbZqqCZqVsqsqmNlPNnSJmbNNmlmMSnJLBl\nMGnMBMBJFpBcNpdwRWRvRNdblmwW\nLSgtPCChgjCPgSSzCSqWLLbrdWlmwmwmFvml\nQhHPVSHghCtQFgCzgQhVnDGMGffnpcZMcMfJDf\nQwrJqMLRLtBQRtWLJLvQLMrMgNNzPDngNHlHnbbbggHlgZNt\nGdfThGcmShTGSfppmFfTHDNNblSZDbbzlBzZZHHg\nTffmGBBFcCFFmTGFhBwjJQJMQWqWQCrrvQMR\nmRbrjZzRLchHqqdLDllh\nmCGCsJSggCmgSGShlhhDVVVwhqSltV\nPsfsGNGJvGPfspvcmrTRBrjTZzvT\nNRNqFFtqqFrDDQRcJJJNrWDswHwWwbDVTgTwLbVlVD\nZpdHHGPmgwTwldbw\nHnnnMPMzChPmnpnmfFJCRqcJqJRRrrtSBc\nLnNNLBmTNBNTwNZZjZmRMHJwMHvbWrvPMMWdcP\nGtSFDFpzsGVvMJdJsrMbvr\nSqQQGGtqqSVtDpGtplVDpVJClmnhnTZNjNfmnmBChCZL\nCHltTDsjHNHHdpDRmqdPQpzd\nfMMbbZwLJgMVVFmcRqRpzdqbRm\nMJJWfnVhMzTNGlNTsh\nWtWbtWvrrQGrbcSWHHfSHfgdWJ\nzpnPhLPhPnTMMnzMzpMnDzLPjTVjccSgdmjdvSJdHSgdjScj\nqqvMMCnDCCCzqqCzhPlLsRsGtrsNlRbZtBRtbrrQ\nmPTmlGQnjNTPQQNljnlQnmmCtgRPhghqgqgzqLRPtMqqMzhq\npDsVSZcdVspbdBpcBHBcHhqLWzMbfhMMrMgMgzLRft\npFZpJJFSBFRllvlFNC\npbMVjJbwbbLqlZlstRhjstsN\nFSTnfCBcnBSBvSmmCFCCRQhZBZNsRGlsQQNsqZlG\ndvcdfFcqmfcmdMdJgwJJHMbH\nQSRlWDhQQqDqlTCjTRCSljSmVsPmmGmzsgvppzPVVzdPSP\nHHwtMNMZvfPGbdwdggwG\nZFcNMFFvHLMjlCWrqhqchh\njccDSGVVlRLVSVVScWZZwLvbphgwdpLwZv\nBQHBtfQQHBfmMtmFznrHzmDwghWphvZZFpDhZvgvpZhh\nDmQrPQnBtTnzrrfHrtfMrmTCGqPNjSPCRRGjRCRRqCNjVN\nbRDbbtVgPFFbDfgVCtPcGsNNsHccqcGGWCNNzW\nZwlmJwwRSmlJdQRhqGNTqzGTwzqGhc\nZQdZjpljldrSMjmjdRLdmdbVvvtDVFFffvBFPVBgMnBg\nrzwGrwPGppqzPMzrdqsssSsvgtQgTTTJsH\nLCNNHLmHWvCJstsJss\ncfVLLNBmZBVMVDHGwrhM\nFCGFrJltMGdFdGtlFtCgFzQfQnZfVVVMDcQDVzVjfD\nPSPSPZPRbPRsbBRbHBTPvfVzQcDQqWWnDjnnHDjzcz\nRmSTPwSTRpvSlZglgZprZtNp\nnjtLGLbcNTbbLnLmNTtqnFzVPwJFFzPVFPwMVmfMmV\nsrpZlSpsSVqgSPJJ\nHZsHsrZhrBQpqQvpdprnTnnHTbGLbHnjHGbjbT\nvFFnJjvnVSjgCqSCDZ\nlswrrcsQrHTHwdrDdhmqqsRhzmggghgsGC\nQPrWQWcDNDHdddNrQPfDMLMLtvvMbnBpPFvpFFvL\nLgltlRMtcccgMdlzqTVwwrdsqm\nFpvfSDNzSpnvGSnNpmsmVqVVrHwvTqVmmw\npGjDFFDpffnWQbnzjLJhhLchPPJMPBLt\nlJqBqPvtvVPnttnJjJBjVMzMrFhdQrQFbGbQnrbzGG\nmsRgTgmTLLmsTDRfQRllMdGzdRbMHQFF\nmsfDWglWTpSLCgTpSCDsfPjvjtwVjJZqqSSvPVZSqB\nVZZWGZGlZZZMZrGMlQBQGWltFzqvzzcVcgzvmgzddccgvqFc\nrLjNrDRLDRLTqdCqFCNzFgqg\nTJSSbHfDDfSnbpHpJnGhWPtrZWnPhBwWPWBt\nssvsDDjNwhjNhGGgDDRZllltLCLvCWbMffLCfWzb\nqVRmJFSQqqVcqSMWMWLMlllbtbVM\nPqQBPcFJFcmdrJPJrFrQpsNjnTGgwTwGssRNRnRBsG\nsHsJJfSsrpBLHCLJmdqgdZgRNZQlgRNC\nVtnFbhFhwjwVPPjhbccQDQqgRlWDQmdWZZDd\nhFhFvbhGwzvFbtbPnttGbtjsLBfspSrMvJLrpJTrMsLZrH\nnzJDJvvZznnqnZrpTgTpzzTNjlmtsglBjjttQQCgCCtlBj\nSRLRfdVfSVcfHdVVdSLdMHQjPtClsmcwNQltjwjCQQwm\nRShVLWWfWWGvsTZz\nvcdptvndNzrndjctrvcnvtTdbwwRTgwbHDFDTWgqWlWqwqbl\nffVBmQPhshhfPmSfBPfChmmCWFWbDWFbWwwqRDbsgwWMbWFb\nSJJCBLZBhfvnJnpGtvRc\nHLMMHHpNqWHqFqppPWnshtsLhBnVDtthLLms\nJgmSRgCRGbgwGSbgJJjRRDntztrVhnsDrllllwhhzt\nbRRCCjgRvJQQdcdjjvRcQdgbZPZpqfqpHHMfNFqNTPWqQWmq\nPPwQTlFrLqrLQrPfPJrHtcjtSvdCNNctLCjN" <> ...
defmodule Solution do
def run_part1(input) do
input
|> String.split("\n")
|> Enum.map(&split/1)
|> Enum.map(&find_similar/1)
|> Enum.join("")
|> String.to_charlist()
|> Enum.map(&score/1)
|> Enum.sum()
end
def run_part2(input) do
input
|> String.split("\n")
|> Enum.map(&String.to_charlist/1)
|> Enum.chunk_every(3)
|> Enum.map(&find_similar/1)
|> Enum.map(&score/1)
|> Enum.sum()
end
def split(str) do
half_way = round(String.length(str) / 2)
str
|> String.graphemes()
|> Enum.split(half_way)
end
def find_similar({l, r}) do
lset = MapSet.new(l)
rset = MapSet.new(r)
MapSet.intersection(lset, rset)
|> MapSet.to_list()
|> List.first()
end
def find_similar([elf1, elf2, elf3]) do
elf1_set = MapSet.new(elf1)
elf2_set = MapSet.new(elf2)
elf3_set = MapSet.new(elf3)
MapSet.intersection(elf1_set, elf2_set)
|> MapSet.intersection(elf3_set)
|> MapSet.to_list()
|> List.first()
end
def score(letter) when letter in ?a..?z do
letter - 96
end
def score(letter) when letter in ?A..?Z do
letter - 38
end
end
{:module, Solution, <<70, 79, 82, 49, 0, 0, 15, ...>>, {:score, 1}}
Solution.run_part1(test_input)
157
Solution.run_part1(input)
8349
As you finish identifying the misplaced items, the Elves come to you with another issue.
For safety, the Elves are divided into groups of three. Every Elf carries a badge that identifies their group. For efficiency, within each group of three Elves, the badge is the only item type carried by all three Elves. That is, if a group's badge is item type B, then all three Elves will have item type B somewhere in their rucksack, and at most two of the Elves will be carrying any other item type.
The problem is that someone forgot to put this year's updated authenticity sticker on the badges. All of the badges need to be pulled out of the rucksacks so the new authenticity stickers can be attached.
Additionally, nobody wrote down which item type corresponds to each group's badges. The only way to tell which item type is the right one is by finding the one item type that is common between all three Elves in each group.
Every set of three lines in your list corresponds to a single group, but each group can have a different badge item type. So, in the above example, the first group's rucksacks are the first three lines:
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
And the second group's rucksacks are the next three lines:
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw
In the first group, the only item type that appears in all three rucksacks is lowercase r; this must be their badges. In the second group, their badge item type must be Z.
Priorities for these items must still be found to organize the sticker attachment efforts: here, they are 18 (r) for the first group and 52 (Z) for the second group. The sum of these is 70.
Find the item type that corresponds to the badges of each three-Elf group. What is the sum of the priorities of those item types?
input_part2 =
"""
QtGHnGlcwQGvHwMHGnnGfRFCJnRBfVVJRVBfCFBh
qsDjzNWhmspNNqVrfjVfjJCbBVfB
DLhPTmNDTzTqzpmzLpswGMHtMgwglcPQMQvSGM
ctwDjvgtltgglHrSHCsQWBBDfS
ZJZdVnmhmfCprnBTfS
dNddhhdPRRdbdNcvwCPCgCctjPlF
MNNDGMWrQsfhtrTnrm
jcvRPRPJdvccRNFNCjLdcwJCSHtHPmzhsSzPHmfhnftnTffH
RddRcjRvZgZNWNgQQb
fPrvhqhRPSfCCfhrqtbtLcmZmtHCtpCFcc
WFQJlTdzgGJVQGWQTzdJcHbQZtLtHmbbZMZHsZQm
JFNlzTBNJGlNPSRhfqRRrN
tdVVgttdDtJJsNPmzdQmjcPP
CBTMmmmbTBHqHMwQcZPWWsWnzbbnzW
CGlLFCTMGvqBGvGvGSRSRfmtRRtgVgrSLS
LHSGJLWZLqHQHpRHRz
bpBPVtpCwPgBCtqqvzfzMQvjbbjz
lhVsTgPlBNThpBNwBtVThPnrGGWJZnLZFnFrGWsFrWZr
nQbbbjpnsdsGCSlmHtJmvljHMjWt
cDcgThLVcPTHVlVlHllvWp
cwpgghTcRRczDhnQGGCSdfszdSbS
vTMFDNTlDhjTDNMNJDwmWWWfGPfLnnzLGfMmmL
bVQgbpqqtctzLflltnCz
VSqlVSHRFvNwJSDj
RfZfjljffssWLWPTGPjhzT
FDCvMDMJJpBJpBFJCMBDMtPbWbLVPGztWPVTtPmLWGhQ
DpgHggpwBJwzJMrFFvrCrHsffnRScNsdclSnnRnSNs
wTvfHSvSwssPGCLCPhgSCn
QNpMRqRJQMZlBBbRRRMfbZlBhPChghhlChGCtnthctjPhchh
rrrNBbMZqRbqDsFHTwfWTFFwrF
fVgfQhhgfTLHSLNZZHfZ
CDtsqrqlDtqDddsqjsstHrSlNLWLcSZScFWWcNBFcBcc
jrCJrHjDCMMDsJjJMstThppgwvGzVGQzhJvvng
DGlTlSzbSnzmwbmblTBBPgffpNjFHppZBH
WqQdWqqJdCrtvQtJLQjtdcBNfPsNZfHZZsHNNZHsBBHL
cCJcjdRvqrQhqvWMzlbDGVGbSMSnbR
BfQmpfpmsRCRPDSZVSjjSg
MhNJGMTMHGGTbnGMJrbJHTzzdPgSwSqqPjPdZddSqNSwPZDw
TWbWbhnHWBFBFBDD
FrlJbTcBTcrlTlqwZTwWdhWLChLtVhdfLhmwWC
pppSpzBGMMMjSSMSzMNzHRSDVWGWDWVCDtGdtdhLhftthd
RNNgpMPRNgzggFJcBPqFZJZrbc
SdvnnvvntnbDDqtz
wRpFRRspZhgZgFggFMgtczcGGDzQcGlGDMqcDG
CLLCFNZhsppRvvttBPCjStdT
JJDMhSwmMwBnnJPJmQcFtfQtfgQhQQfcgH
ZvCvTGqGVWTZZWptQggGtHfDgcpz
dsVCvDTZWWbZqqCZqVsqsqmNlPNnSJmbNNmlmMSnJLBl
MGnMBMBJFpBcNpdwRWRvRNdblmwW
LSgtPCChgjCPgSSzCSqWLLbrdWlmwmwmFvml
QhHPVSHghCtQFgCzgQhVnDGMGffnpcZMcMfJDf
QwrJqMLRLtBQRtWLJLvQLMrMgNNzPDngNHlHnbbbggHlgZNt
GdfThGcmShTGSfppmFfTHDNNblSZDbbzlBzZZHHg
TffmGBBFcCFFmTGFhBwjJQJMQWqWQCrrvQMR
mRbrjZzRLchHqqdLDllh
mCGCsJSggCmgSGShlhhDVVVwhqSltV
PsfsGNGJvGPfspvcmrTRBrjTZzvT
NRNqFFtqqFrDDQRcJJJNrWDswHwWwbDVTgTwLbVlVD
ZpdHHGPmgwTwldbw
HnnnMPMzChPmnpnmfFJCRqcJqJRRrrtSBc
LnNNLBmTNBNTwNZZjZmRMHJwMHvbWrvPMMWdcP
GtSFDFpzsGVvMJdJsrMbvr
SqQQGGtqqSVtDpGtplVDpVJClmnhnTZNjNfmnmBChCZL
CHltTDsjHNHHdpDRmqdPQpzd
fMMbbZwLJgMVVFmcRqRpzdqbRm
MJJWfnVhMzTNGlNTsh
WtWbtWvrrQGrbcSWHHfSHfgdWJ
zpnPhLPhPnTMMnzMzpMnDzLPjTVjccSgdmjdvSJdHSgdjScj
qqvMMCnDCCCzqqCzhPlLsRsGtrsNlRbZtBRtbrrQ
mPTmlGQnjNTPQQNljnlQnmmCtgRPhghqgqgzqLRPtMqqMzhq
pDsVSZcdVspbdBpcBHBcHhqLWzMbfhMMrMgMgzLRft
pFZpJJFSBFRllvlFNC
pbMVjJbwbbLqlZlstRhjstsN
FSTnfCBcnBSBvSmmCFCCRQhZBZNsRGlsQQNsqZlG
dvcdfFcqmfcmdMdJgwJJHMbH
QSRlWDhQQqDqlTCjTRCSljSmVsPmmGmzsgvppzPVVzdPSP
HHwtMNMZvfPGbdwdggwG
ZFcNMFFvHLMjlCWrqhqchh
jccDSGVVlRLVSVVScWZZwLvbphgwdpLwZv
BQHBtfQQHBfmMtmFznrHzmDwghWphvZZFpDhZvgvpZhh
DmQrPQnBtTnzrrfHrtfMrmTCGqPNjSPCRRGjRCRRqCNjVN
bRDbbtVgPFFbDfgVCtPcGsNNsHccqcGGWCNNzW
ZwlmJwwRSmlJdQRhqGNTqzGTwzqGhc
ZQdZjpljldrSMjmjdRLdmdbVvvtDVFFffvBFPVBgMnBg
rzwGrwPGppqzPMzrdqsssSsvgtQgTTTJsH
LCNNHLmHWvCJstsJss
cfVLLNBmZBVMVDHGwrhM
FCGFrJltMGdFdGtlFtCgFzQfQnZfVVVMDcQDVzVjfD
PSPSPZPRbPRsbBRbHBTPvfVzQcDQqWWnDjnnHDjzcz
RmSTPwSTRpvSlZglgZprZtNp
njtLGLbcNTbbLnLmNTtqnFzVPwJFFzPVFPwMVmfMmV
srpZlSpsSVqgSPJJ
HZsHsrZhrBQpqQvpdprnTnnHTbGLbHnjHGbjbT
vFFnJjvnVSjgCqSCDZ
lswrrcsQrHTHwdrDdhmqqsRhzmggghgsGC
QPrWQWcDNDHdddNrQPfDMLMLtvvMbnBpPFvpFFvL
LgltlRMtcccgMdlzqTVwwrdsqm
FpvfSDNzSpnvGSnNpmsmVqVVrHwvTqVmmw
pGjDFFDpffnWQbnzjLJhhLchPPJMPBLt
lJqBqPvtvVPnttnJjJBjVMzMrFhdQrQFbGbQnrbzGG
msRgTgmTLLmsTDRfQRllMdGzdRbMHQFF
msfDWglWTpSLCgTpSCDsfPjvjtwVjJZqqSSvPVZSqB
VZZWGZGlZZZMZrGMlQBQGWltFzqvzzcVcgzvmgzddccgvqFc
rLjNrDRLDRLTqdCqFCNzFgqg
TJSSbHfDDfSnbpHpJnGhWPtrZWnPhBwWPWBt
ssvsDDjNwhjNhGGgDDRZllltLCLvCWbMffLCfWzb
qVRmJFSQqqVcqSMWMWLMlllbtbVM
PqQBPcFJFcmdrJPJrFrQpsNjnTGgwTwGssRNRnRBsG
sHsJJfSsrpBLHCLJmdqgdZgRNZQlgRNC
VtnFbhFhwjwVPPjhbccQDQqgRlWDQmdWZZDd
hFhFvbhGwzvFbtbPnttGbtjsLBfspSrMvJLrpJTrMsLZrH
nzJDJvvZznnqnZrpTgTpzzTNjlmtsglBjjttQQCgCCtlBj
SRLRfdVfSVcfHdVVdSLdMHQjPtClsmcwNQltjwjCQQwm
RShVLWWfWWGvsTZz
vcdptvndNzrndjctrvcnvtTdbwwRTgwbHDFDTWgqWlWqwqbl
ffVBmQPhshhfPmSfBPfChmmCWFWbDWFbWwwqRDbsgwWMbWFb
SJJCBLZBhfvnJnpGtvRc
HLMMHHpNqWHqFqppPWnshtsLhBnVDtthLLms
JgmSRgCRGbgwGSbgJJjRRDntztrVhnsDrllllwhhzt
bRRCCjgRvJQQdcdjjvRcQdgbZPZpqfqpHHMfNFqNTPWqQWmq
PPwQTlFrLqrLQrPfPJrHtcjtSvdCNNctLCjNdc
DGZMhmVRMGqVmVDnGMbBZhsjHNvjdstddjdjccSBSjds
mqzVnWDmmGzRhqRbbWQQFwPQQTlzPFpTlPJJ
RMmnMrZMlQQpGrQt
gPPgcDBcjdgjBCBcQtNDNzzthltGphhz
FSvPSSjFWFScSWdjWvbTwWJQZQVRsMTQVwTmVR
PwlbMTDQDvMwttThPthhvhvvZzNLzNZjQCNNLWLCRZWQRzNW
VpJHFpgfqdFqqHFGHVSdGmZZRnSsnLjNZCWmmszLSz
drrJRGJVrcMBDwhDbcMh
hghHTgbwHbDqHrgbbbSLzzFNnsVqNVBnLnfs
jMlcMRRmGcRlZQMMJRJSPPmCFzBBzpfBfLfpFLszLNNFVCfz
JlmGlZmvRMgvrgbrrSTw
ZtTTHpprHtQtHtpqPmjVSScjVSjjSNqw
nRvGWhRbnRGzvWCBGPjNdwcSwcnlJdmmSj
vCbsmbWfRsRWWzsMWBQFFrDZpgpFHLgQLMgQ
QlJBfZssjgZsQsDNbScdDZdNcvvF
zrGrVVpVMWMwMVLMwqVWpRdNFSDcFNDFbSddqHldDdqd
VLVtrWpMRCRLWGWMRwVGCVPfCPJnBTQsJlmjsfsPBQjC
GQqpnnFWFcnWpBMhhSZRhQCCCfRQRD
HsbcczlrjzflffLVfDlt
jssvwsHPsjzWdMcgBnvqMB
JMJdMptTbbtpJZhtTMZwJdNWQBPNBlwNBNQWHBCHHPlg
rVqsvVmjrcCqCPsPNQgnsnQglW
rVvzfqvLjFVDVcLjCqLmJFGbpJpRJTGMtbRpdGRG
LrmwdZHlSlcVlSrrDWCzbtpjpgzjtD
gBGgPTTBqPQTqnnPJhMTTCzzppnCvptpnCtzNpDntz
qQPTTPshRRQqcgsflHZcsSLV
smvdTvlPzslmVjMhJlbjrblJ
cqFffFffcwFfpcDSjcnZwZWrQVDrQBhNbrrNBbWVbNhr
nSpRZRjpcHqpCpqnqFRGmvPLtLGmCdCsGLLdtC
PJPLPPHDdPvdnbctfcpt
NRrGNjNzLjltppvpRSRS
LzVWLjTWGLQqBgZWJWBBFg
znzccGnswWrWNCpvvdTCzddC
RfZlRDDDZflSBMhhhPSMMZpmpHHGNCGTmCJTmvmCvJGR
GbBMhhbSMhMffDMZPggSGfhVWLwjsLttWtrjWscVLWnQWswn
jwRzdZZhwhwHSQqpStJHhp
GVGPBvNPvffpvtvp
nsGGDVtFNGgGWjWlTwrwTmjwTR
MQtmmMMmnHGGTmhw
llqvqvvpqdvvrSfrpSfdfnhFSTMNDHFMNFFSGFwMHT
JqvvRgpCfrzCpqqzdfRpRllWZZBQJbVVtMttsVWJbjPbcc
zgqBczqBbBGjdHVgdDFd
lNVhNNnLtZZZGWjdWrSW
PCQhNflCtCwtJwhClMmVcRmpbPqTcmBqpm
wWbqbTwVrQLqlMtrZtZffNfMfP
vhjqqRpRvZsfssZN
ccBjJBqGpRhDGbJldHlgLwddLd
hVScjtgcchVhSgZJSchVwLbNLWnLNwwnwrbWNLgr
BzMdBqzBQzZQPpfrsrbrNdNLsrRR
zPMzmmGpmzGlFQPPmlZPzSVTSVJJcSlcDhTlvSCtjJ
hzdwlqngZQvDfmzF
vcRrcsVNpVQsFfBfPPQB
HCHVWVcCpNMHWRjLwhvhggdjvggM
LBHCTPzHHBcClwppwjjNNl
JddZMRmmssVmvDvJddSJWVWBwpQvwfpwvwwfrrFNQfwjpl
BsVMVZDVZssZhMhJqLzhzzHzPTPnLGqb
bcnNQnBTvvvWTQTJhdHJzhSjpJJjStjd
mMwqwVMMRwhBtjdSVBVl
GfsrwCRmZBcZTvBf
bBjQmmmqWdLqvLbWLtNJccNZZgCBCZgCTg
phfpfzpHPDwfMwvVzlhlJJlggcZgZcRFFlCgZg
zfhpMMDpVVzzhHhzzMMwfnMfSmQmbQvvWqWjmLSqdQmrqjjn
ZzdcbGTwLZwPPwpMPWpjWPpWChBC
nmznNRFHQrqQvqqmmMfWWWpMFjspWFMWjB
zqRDSmDrmvnvntGccGdcTVtLTlVG
nfnVscTcDzsZqmRtjtsqjJ
wnnhWPWLBNwPLHdQdWdHPHLdJjqRRqrvjrmqFtvRqtQRqFjm
bWhHdBBLdLnShWHcTVzCfCpVDTblpT
WSjVFSVTSWvgvFwpgTTFsfdVclhNCfsHnHlHsCfV
zRqLqZqZZQcdNltfHzsd
ZqBqGLLRcjWWBvTT
wwBqgZfbgbZsvWmfJrtFrdDttqdFdLct
SNSSVTnnThnCSPPnzVztQJJQdLPtFcGLdFGDsD
lSlszRVsRjmmfjfRRf
NGzGWSLzMdQtcctbgWjt
vqTnfVVHBffnCmHgMtrrrHrgtcrt
vqCDVlFnnCnnBSzlspSzLSNMLL
rwVlfVMRSTqTgRhT
pppjLtpZjHFHNhsctSqDDVtnns
HNjJLFBFHZZzWbVBZGfwdGrMfCCfGvmzlM
zFzztqWnJttqqzJtdqbtqbPVMGcGZwgPGVwGQjwCCggMZQ
hssLlrsSrBmBrZGSfgwgSwQCcj
BmBBDBHLrlNhLNHrpsDvLJNtddczdRzzcTqJzzdWnc
pLWcpGSscLQPDzLBgdbmdZHBHmZB
lntfCfVMvtttqVqnZHHbbBZmwwwCdHhc
qqRJFfRFRNlTzSSWWzSJpc
DrphDfFrdGGjTTgTgCSV
vbsMZPnPvqHMQvtZZPWBBVVBJjWSVTPjJC
nMbnsRSQvvLRMsssQhdFrcwczLlDrrDzhz
LLlDQlcLDqLSlCDRlRDCqTTzzgNzShSBdZGBFBBgNG
nHnMwPPbrWwpmztdMtzFZZFtTN
PJfbZmHrpJfZDRLlDlLcVsVJ
wZwQsrrzQFQSrRSFbzDglcdCcdljjdlljcvslLhv
VPqGJtqqfnJcCLFllFMGcd
fNHPJWpmHfffqJHmwzgbrBDZrDbFRQ
HggtSJtzrgltshlTsrzbzsgbFddfffDZwZRZZZGfGDRTNNZZ
LnjWccmQBPWqmWPqMfFNdGBRCDFFSfDfRd
WpMjWpMcWSjqqPjQLmvmjMgllsbgbtvsrrtvJgJHhrHl
PMcMcBpztMztzPPhbSgGSvgfHD
nsmsVQVZVQmTRmddrLgfFhfLgLDzgvffDhbF
dwsjrQQrVwTmZRTzsTdBcjqlqWpcCCppcllltC
DbVjbjwNMDTCVbhbTNDrVTTmzFGLFLHcLHzmcWFczLHwmH
PPWsfBZngtZqZZnPgZnPqvmFmczgRHGmGSRRSSLGFF
sntBlWPdnspnnPQZtnNNNMjhMNrVMjMThjpr
rCrCWVvvWDnBWvDnWDMCMZTpThhGGhGRGqGqZmhZqV
NNjQMzNzQjjwNmJNmZddpdTG
QwtwLPcjPtQlHSSslzwHSlPQDfDWsggsvvBvDvnvgngCnvFM
ZDCbvbDvvHbCGTWpZTtWWQnn
hLqzLVhVwNwVfMnJrfqMzWrQddgmQQGdgpgQGmgjTj
wlVNwJJfVRLPRnHRbFHRsP
lLmvLGRCrmDwVPVsjmtBBQmt
NSHWNbzSHWpSpfChqqJPnzBJsBPPJnQJ
pWcHbNfWpgZcWbhbZSgchWpRdCZMMdGDFFrLwlwMRRZFdd
PnNrFVZQHNDrmNQPflbhbfqbvhwbVfvq
TCdTtpCtCWTBMtjTJMWtBMCLSfvbqqzqbljflwDLvLjLLf
MCCGcpCJRWTTMGmPnDFNQQnDns
FhSmttZmgLjJVMlVGllGjcrj
NRNvNWNCdnNrBvWvwRdWvvvRCGcbVVQbMQGcGcVcMclzVVlG
qwBsBWwnvdtHJJSrtHsr
wnwPrnBBPgqRPjhgCRGCLvvbRZcJvCbb
dWVdVdlMHtsTslMtzztFGGczvvGJzL
fMflHpddJfNNVfNWWmDqQpwBgwnjPBQDjqBh
WttGctsNCNrfwTMlBtlr
HJLzLJJVnFjHbnbVjDHDdFqwwffTTfTGwrqwBBTT
jgVgJSbnHjNWsWCSWWGG
ssLfHLvrrfMMlBMRMfpd
qbbhmGCCVDQhQQVzDDbqmhMBtDZdBZHlddpltpBpdlJd
QhQbzqCGzVzSbqzLHjLgrcjvPSnnSL
NGGZGsGFCGvCcnCcgnZWrPHjsJjHjTDjJHfrjHDP
RzzQmwwmdRRwMqRQmZwtfrDPfTfrbjHqrDPTHr
MBLphmLpSzdRlnWZCNcGLgLG
LwPPHZLLWRMWMsHqTCjmTTjSTn
lFpNNpzplbfphzNcQzVcpvzsnqTsggmnjfgqCDsnCDqsgS
vFJJhQVhbcVddLtmWZJdmm
GwMNMGBMRMGjdSGsDntglDrDGQ
WTmPPzfmlQrsnQmg
ZPTJVvllhBwvLvwRwj
nlSvqqFqzfnbnvFwwsGHTBHgPfWsTrRPgG
dMdjphVhhgdLVJhNRBGPRWWBBGPTTGHV
thJgLpghLNLhNQMCtdMhSmFlQnzzwnbzlbqqSQFb
ZJJLBWhJBNwJwLvgRgGRgbZqbHTbGT
cCrfFFnzjmdrdrmmzsgSPSHSbHWPRgrgGR
dmCFntnFctjfdVtttjtDVncfBDlNJJppwQMwNBNvvplppWNh
GGNNNbNbqmsmTVbCDQQhDJQT
rgPvdgMdPdBddvMcrMnvgcSwhClTTJCwClDTvLJJthTlth
zBdWpnDBDmfFGRffzH
WNNNWcDcdVHNQTNT
lLvLctvrvvvPCpHLQQTZVQLTTHBV
zltgpbPCrrmtlmrlhhbqcWMqDDMDFMfbGScc
dzSHRCGZGdRQWQWtllWB
mNmbLbbmwjsmsNjDmcPvpVHBVPQvWDWBBpvB
jnmNNrLcnnjjHhSCdGMSfrfd
mgGvfvJSmSSrbvScmGccTPCqNnRjlpNNfNjqwqlpNpfw
zZLLQFFFtsFwWjjRqbbCsW
hBBLBdFHddVrGbVc
bJGchsCcHwbHfgvg
qdlSSNqLPqlPQZDffgfZRZMghvZr
PLtqtFTPNLlWlqtQqqQzBBmcnschGtjtnChmzC
llNLDLzjDtCTVtClCDMHSlmwdmmdSmddwZSS
gPJszvsBPbwSHZRQSJQJ
bgFssFPcWhDjCzLcnNDD
ZTGMwdhMwMJphZMJlNdVBCnncNPLBCCRPnCncn
fWsqmfSsqvfFFFvmWjfSSsPLCwVPRnPRCmRnRRCVzRCV
FQfQfvStwjtqsjvvQWFfWqWtlMDdGTJJGdMdhJtDMbllDZ
DzZLpBDptpVPrrrFPqRmBj
WsfCTTgMllCWJMlhslNsCFJrGqvmRPqmqZjGFjvmvm
HfghcNghHhgNNfbDDZdcdpndDzpt
RRBRdJfccVRdDJqdDrvwShwvztWJlWwSJn
mPtCHPPmHbmHNZjjjQHbMSgrSWhWzWnnQwvzzrlrll
tpFmjpmjFMCmppmVTVLFVfBqTqVDLd
jtljZcTcVVtdggVmdczzzDPzvCsvRbDsDmvm
MHHnnJMFMNpwSNprpMJrfsbPRRbWDGLbHLDRvzzssR
rJFNvQfBSwQBwNwldZTqTtctQchthc
WsWTWsfjgTJGSnTz
RHNmvRLCpJclcNcvHpNcPBzgQgMnnGFnLFgPgnPF
mHlcdbbccZcCCCNZZNcCWtthWbWqwwJsbDfthfwW
vFFzppnHFrjmpljQhg
JPGfPWVdwfPgQzVQlTrQrZ
PwRJfGDBfCHMzRHNHMNR
"""
|> String.trim()
"QtGHnGlcwQGvHwMHGnnGfRFCJnRBfVVJRVBfCFBh\nqsDjzNWhmspNNqVrfjVfjJCbBVfB\nDLhPTmNDTzTqzpmzLpswGMHtMgwglcPQMQvSGM\nctwDjvgtltgglHrSHCsQWBBDfS\nZJZdVnmhmfCprnBTfS\ndNddhhdPRRdbdNcvwCPCgCctjPlF\nMNNDGMWrQsfhtrTnrm\njcvRPRPJdvccRNFNCjLdcwJCSHtHPmzhsSzPHmfhnftnTffH\nRddRcjRvZgZNWNgQQb\nfPrvhqhRPSfCCfhrqtbtLcmZmtHCtpCFcc\nWFQJlTdzgGJVQGWQTzdJcHbQZtLtHmbbZMZHsZQm\nJFNlzTBNJGlNPSRhfqRRrN\ntdVVgttdDtJJsNPmzdQmjcPP\nCBTMmmmbTBHqHMwQcZPWWsWnzbbnzW\nCGlLFCTMGvqBGvGvGSRSRfmtRRtgVgrSLS\nLHSGJLWZLqHQHpRHRz\nbpBPVtpCwPgBCtqqvzfzMQvjbbjz\nlhVsTgPlBNThpBNwBtVThPnrGGWJZnLZFnFrGWsFrWZr\nnQbbbjpnsdsGCSlmHtJmvljHMjWt\ncDcgThLVcPTHVlVlHllvWp\ncwpgghTcRRczDhnQGGCSdfszdSbS\nvTMFDNTlDhjTDNMNJDwmWWWfGPfLnnzLGfMmmL\nbVQgbpqqtctzLflltnCz\nVSqlVSHRFvNwJSDj\nRfZfjljffssWLWPTGPjhzT\nFDCvMDMJJpBJpBFJCMBDMtPbWbLVPGztWPVTtPmLWGhQ\nDpgHggpwBJwzJMrFFvrCrHsffnRScNsdclSnnRnSNs\nwTvfHSvSwssPGCLCPhgSCn\nQNpMRqRJQMZlBBbRRRMfbZlBhPChghhlChGCtnthctjPhchh\nrrrNBbMZqRbqDsFHTwfWTFFwrF\nfVgfQhhgfTLHSLNZZHfZ\nCDtsqrqlDtqDddsqjsstHrSlNLWLcSZScFWWcNBFcBcc\njrCJrHjDCMMDsJjJMstThppgwvGzVGQzhJvvng\nDGlTlSzbSnzmwbmblTBBPgffpNjFHppZBH\nWqQdWqqJdCrtvQtJLQjtdcBNfPsNZfHZZsHNNZHsBBHL\ncCJcjdRvqrQhqvWMzlbDGVGbSMSnbR\nBfQmpfpmsRCRPDSZVSjjSg\nMhNJGMTMHGGTbnGMJrbJHTzzdPgSwSqqPjPdZddSqNSwPZDw\nTWbWbhnHWBFBFBDD\nFrlJbTcBTcrlTlqwZTwWdhWLChLtVhdfLhmwWC\npppSpzBGMMMjSSMSzMNzHRSDVWGWDWVCDtGdtdhLhftthd\nRNNgpMPRNgzggFJcBPqFZJZrbc\nSdvnnvvntnbDDqtz\nwRpFRRspZhgZgFggFMgtczcGGDzQcGlGDMqcDG\nCLLCFNZhsppRvvttBPCjStdT\nJJDMhSwmMwBnnJPJmQcFtfQtfgQhQQfcgH\nZvCvTGqGVWTZZWptQggGtHfDgcpz\ndsVCvDTZWWbZqqCZqVsqsqmNlPNnSJmbNNmlmMSnJLBl\nMGnMBMBJFpBcNpdwRWRvRNdblmwW\nLSgtPCChgjCPgSSzCSqWLLbrdWlmwmwmFvml\nQhHPVSHghCtQFgCzgQhVnDGMGffnpcZMcMfJDf\nQwrJqMLRLtBQRtWLJLvQLMrMgNNzPDngNHlHnbbbggHlgZNt\nGdfThGcmShTGSfppmFfTHDNNblSZDbbzlBzZZHHg\nTffmGBBFcCFFmTGFhBwjJQJMQWqWQCrrvQMR\nmRbrjZzRLchHqqdLDllh\nmCGCsJSggCmgSGShlhhDVVVwhqSltV\nPsfsGNGJvGPfspvcmrTRBrjTZzvT\nNRNqFFtqqFrDDQRcJJJNrWDswHwWwbDVTgTwLbVlVD\nZpdHHGPmgwTwldbw\nHnnnMPMzChPmnpnmfFJCRqcJqJRRrrtSBc\nLnNNLBmTNBNTwNZZjZmRMHJwMHvbWrvPMMWdcP\nGtSFDFpzsGVvMJdJsrMbvr\nSqQQGGtqqSVtDpGtplVDpVJClmnhnTZNjNfmnmBChCZL\nCHltTDsjHNHHdpDRmqdPQpzd\nfMMbbZwLJgMVVFmcRqRpzdqbRm\nMJJWfnVhMzTNGlNTsh\nWtWbtWvrrQGrbcSWHHfSHfgdWJ\nzpnPhLPhPnTMMnzMzpMnDzLPjTVjccSgdmjdvSJdHSgdjScj\nqqvMMCnDCCCzqqCzhPlLsRsGtrsNlRbZtBRtbrrQ\nmPTmlGQnjNTPQQNljnlQnmmCtgRPhghqgqgzqLRPtMqqMzhq\npDsVSZcdVspbdBpcBHBcHhqLWzMbfhMMrMgMgzLRft\npFZpJJFSBFRllvlFNC\npbMVjJbwbbLqlZlstRhjstsN\nFSTnfCBcnBSBvSmmCFCCRQhZBZNsRGlsQQNsqZlG\ndvcdfFcqmfcmdMdJgwJJHMbH\nQSRlWDhQQqDqlTCjTRCSljSmVsPmmGmzsgvppzPVVzdPSP\nHHwtMNMZvfPGbdwdggwG\nZFcNMFFvHLMjlCWrqhqchh\njccDSGVVlRLVSVVScWZZwLvbphgwdpLwZv\nBQHBtfQQHBfmMtmFznrHzmDwghWphvZZFpDhZvgvpZhh\nDmQrPQnBtTnzrrfHrtfMrmTCGqPNjSPCRRGjRCRRqCNjVN\nbRDbbtVgPFFbDfgVCtPcGsNNsHccqcGGWCNNzW\nZwlmJwwRSmlJdQRhqGNTqzGTwzqGhc\nZQdZjpljldrSMjmjdRLdmdbVvvtDVFFffvBFPVBgMnBg\nrzwGrwPGppqzPMzrdqsssSsvgtQgTTTJsH\nLCNNHLmHWvCJstsJss\ncfVLLNBmZBVMVDHGwrhM\nFCGFrJltMGdFdGtlFtCgFzQfQnZfVVVMDcQDVzVjfD\nPSPSPZPRbPRsbBRbHBTPvfVzQcDQqWWnDjnnHDjzcz\nRmSTPwSTRpvSlZglgZprZtNp\nnjtLGLbcNTbbLnLmNTtqnFzVPwJFFzPVFPwMVmfMmV\nsrpZlSpsSVqgSPJJ\nHZsHsrZhrBQpqQvpdprnTnnHTbGLbHnjHGbjbT\nvFFnJjvnVSjgCqSCDZ\nlswrrcsQrHTHwdrDdhmqqsRhzmggghgsGC\nQPrWQWcDNDHdddNrQPfDMLMLtvvMbnBpPFvpFFvL\nLgltlRMtcccgMdlzqTVwwrdsqm\nFpvfSDNzSpnvGSnNpmsmVqVVrHwvTqVmmw\npGjDFFDpffnWQbnzjLJhhLchPPJMPBLt\nlJqBqPvtvVPnttnJjJBjVMzMrFhdQrQFbGbQnrbzGG\nmsRgTgmTLLmsTDRfQRllMdGzdRbMHQFF\nmsfDWglWTpSLCgTpSCDsfPjvjtwVjJZqqSSvPVZSqB\nVZZWGZGlZZZMZrGMlQBQGWltFzqvzzcVcgzvmgzddccgvqFc\nrLjNrDRLDRLTqdCqFCNzFgqg\nTJSSbHfDDfSnbpHpJnGhWPtrZWnPhBwWPWBt\nssvsDDjNwhjNhGGgDDRZllltLCLvCWbMffLCfWzb\nqVRmJFSQqqVcqSMWMWLMlllbtbVM\nPqQBPcFJFcmdrJPJrFrQpsNjnTGgwTwGssRNRnRBsG\nsHsJJfSsrpBLHCLJmdqgdZgRNZQlgRNC\nVtnFbhFhwjwVPPjhbccQDQqgRlWDQmdWZZDd\nhFhFvbhGwzvFbtbPnttGbtjsLBfspSrMvJLrpJTrMsLZrH\nnzJDJvvZznnqnZrpTgTpzzTNjlmtsglBjjttQQCgCCtlBj\nSRLRfdVfSVcfHdVVdSLdMHQjPtClsmcwNQltjwjCQQwm\nRShVLWWfWWGvsTZz\nvcdptvndNzrndjctrvcnvtTdbwwRTgwbHDFDTWgqWlWqwqbl\nffVBmQPhshhfPmSfBPfChmmCWFWbDWFbWwwqRDbsgwWMbWFb\nSJJCBLZBhfvnJnpGtvRc\nHLMMHHpNqWHqFqppPWnshtsLhBnVDtthLLms\nJgmSRgCRGbgwGSbgJJjRRDntztrVhnsDrllllwhhzt\nbRRCCjgRvJQQdcdjjvRcQdgbZPZpqfqpHHMfNFqNTPWqQWmq\nPPwQTlFrLqrLQrPfPJrHtcjtSvdCNNctLCjN" <> ...
test_input_part2 =
"""
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw
"""
|> String.trim()
"vJrwpWtwJgWrhcsFMMfFFhFp\njqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL\nPmmdzqPrVvPwwTWBwg\nwMqvLMZHhHMvwLHjbvcjnnSBnvTQFn\nttgJtRGJQctTZtZT\nCrZsJsPPZsGzwwsLwLmpwMDw"
Solution.run_part2(test_input_part2)
70
Solution.run_part2(input_part2)
2681