adventofcode

git clone https://git.ce9e.org/adventofcode.git

commit
94b425b0aefa818580ca92ac7e13b5782a147bc8
parent
2494a9301f12add6a20594d3841e7fd76daf513c
Author
Tobias Bengfort <tobias.bengfort@posteo.de>
Date
2024-03-02 14:06
2023-12-25

I used force-based layout and clustering to identify the two groups.
It took some fiddeling with the exact formulas for forces, but worked
out pretty well.

I originally thought I would only use this as an optimization to find
likely candidated, but that wasn't even necessary.

Other solutions I read about used Karger's algorithm. Another idea was
to check which edges most often appear in the paths between random
nodes.

Diffstat

A 2023/25/dot.py 11 +++++++++++
A 2023/25/input.txt 1250 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A 2023/25/solution.rs 123 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A 2023/25/test.txt 13 +++++++++++++

4 files changed, 1397 insertions, 0 deletions


diff --git a/2023/25/dot.py b/2023/25/dot.py

@@ -0,0 +1,11 @@
   -1     1 import sys
   -1     2 
   -1     3 print('graph g {')
   -1     4 
   -1     5 with open(sys.argv[1]) as fh:
   -1     6     for line in fh:
   -1     7         line = line.rstrip()
   -1     8         left, tail = line.split(': ', 1)
   -1     9         for right in tail.split():
   -1    10             print(f'  {left} -- {right};')
   -1    11 print('}')

diff --git a/2023/25/input.txt b/2023/25/input.txt

@@ -0,0 +1,1250 @@
   -1     1 jtq: nrr nqb
   -1     2 jql: rxs rgl nsb
   -1     3 gmj: fhr cvd rdb fbz jcc
   -1     4 rdb: llj jzl
   -1     5 fmc: brd rkv dds
   -1     6 qmf: nhf xrh xxd nxl kvv
   -1     7 jqp: dtk fmj
   -1     8 jqk: fxp llf
   -1     9 ccz: kmx pcr vdx dbh rxd
   -1    10 hzx: mnf
   -1    11 tvv: ncq tdq
   -1    12 fpx: mgp tbx drv std
   -1    13 xhj: xxd nnk brj tgq jqq
   -1    14 hzl: dkz
   -1    15 xll: vqn tdv tch
   -1    16 vqn: kjt
   -1    17 sdp: qgr hxg vtj vpf
   -1    18 hks: cgx dmc
   -1    19 fzm: hbk tvb rnj
   -1    20 ppf: brd gdn jcc
   -1    21 mfq: kvl fbd mrx
   -1    22 kvs: gsm glq pkq vjh
   -1    23 crm: bmh qpg nsl gkq
   -1    24 vfx: zfx qvl zfr tml
   -1    25 qxc: ddj
   -1    26 qmd: glt zjb
   -1    27 gcj: lhr
   -1    28 jrg: zdk pcb bzv zjv
   -1    29 blx: nqd drv ttm pqx
   -1    30 jln: brp bxq
   -1    31 knf: jzj
   -1    32 pvn: zpp zvl qbx nnt
   -1    33 ksk: qks qmd lvf kkt ksg
   -1    34 bmf: skh mcl
   -1    35 kcj: fth qhf tdd cvb lbm rff
   -1    36 qbm: vkf ctx tzm pgl
   -1    37 bds: gzn slt
   -1    38 kjc: mtd xrt jnq tgb kxb
   -1    39 jct: hvh kvf jfx fkq cgz
   -1    40 xgp: nxl qkr sxn csh
   -1    41 bgg: ltv pnr
   -1    42 frp: hqp pvv bmf
   -1    43 nnx: hzk dpv nbs
   -1    44 hsn: jsm
   -1    45 rbd: thx cgf dbr cqx
   -1    46 lsj: vbr nfm mdd
   -1    47 sjc: zdf lnf
   -1    48 jdt: tpm ccv zpp
   -1    49 ktl: ntf bms tgl txf nrf
   -1    50 lsl: vrn cnb lgp
   -1    51 kpz: pxj nrr tns
   -1    52 ftd: zds jlt
   -1    53 hvm: cxz kfc pkm rqh qvl
   -1    54 gjz: jlt jds grh dth
   -1    55 tch: srh zqb
   -1    56 sgs: dgr pnx hcz
   -1    57 qhf: tbp
   -1    58 kfp: qtf vzg kfm lrd
   -1    59 tsr: grn tkd
   -1    60 fnp: kpg tbq vpv vxd
   -1    61 xfl: ssl ttz npx
   -1    62 srt: cnc rdx rdf
   -1    63 zsc: pcp tdm knz tgc ztl
   -1    64 tbx: nkq dbl qjl pth
   -1    65 stk: bhm cxq
   -1    66 qtl: jdv
   -1    67 hqg: rbj bng zpj lfv ksq hdk
   -1    68 tpb: nqd
   -1    69 tdv: zsl xcd
   -1    70 sbg: sss dnp lfd llb
   -1    71 lxp: pbk xcq
   -1    72 qps: dls mtr
   -1    73 lnd: dtk rzp vpn
   -1    74 pcc: vjh csh bmh tbp
   -1    75 svc: sdz fpr kpq
   -1    76 sjx: hlv qmh kzk grd
   -1    77 rgf: vcn jkm
   -1    78 kxh: nds hnl mhj nfs
   -1    79 jmh: tct hjq rxn qcg
   -1    80 hzg: ltz
   -1    81 jlf: xtt hzx gvg gjl chm dlt
   -1    82 cnk: ddb fvb lbs tnd
   -1    83 bzj: qzr pnk
   -1    84 hnf: mkd
   -1    85 plv: ttn xkh
   -1    86 rgt: dmj mdk ndz drv
   -1    87 pnk: ppf
   -1    88 vfh: fps pkm ssj pdl
   -1    89 zfj: hng
   -1    90 gnk: lpt shm pvn
   -1    91 ndz: knq
   -1    92 xcb: bgg qgj jkl
   -1    93 jkc: ndz jzj cng lzq
   -1    94 rrm: kfm tth
   -1    95 krj: nsb tbh bbp
   -1    96 qvl: zhx zqc
   -1    97 fkg: nvk
   -1    98 hfk: dxz pqj rhn
   -1    99 lft: vmz vdj jth dbj
   -1   100 tdq: nxl jth
   -1   101 vrg: hzg
   -1   102 fkj: bxc phk
   -1   103 lfv: hmc qdm
   -1   104 lgp: rsk krt
   -1   105 nqp: mbd lng
   -1   106 qhj: tkd
   -1   107 jjs: dgr lxp bnx dgj
   -1   108 ggp: nmm tlc gzn hgd fnh tth
   -1   109 cff: fjk pxj nvt
   -1   110 ttj: qfm sts qdr gbz
   -1   111 djh: gkb hjg
   -1   112 ftr: vmz rqf nzq pqm nxr mpg
   -1   113 nbh: lmq cng lpt
   -1   114 ssl: gdl
   -1   115 zvm: sjc tgn dhg qmh gvt
   -1   116 ggj: vls zbv
   -1   117 cch: mlz dlr
   -1   118 cmd: vsj kjt xlb rpm
   -1   119 skx: rbr ssd
   -1   120 bsr: mpl kmx ktr fjb ksq
   -1   121 rcn: njb
   -1   122 lkv: fkl rhl zvg nkc
   -1   123 lgd: frc rbr spx jlj bzj
   -1   124 nrf: vqs
   -1   125 sgc: ssv dhh fzm vmz fzl
   -1   126 gqq: vtk tnd
   -1   127 nlx: cgx
   -1   128 xct: tsr rzk lqj lgm
   -1   129 sqp: cmk qfx
   -1   130 bjg: nnz lhr
   -1   131 hmb: xfb tsr qtf qnx
   -1   132 gqn: xgx hxg glt fhr gqc
   -1   133 mmh: fps
   -1   134 lgh: ltg tgq zds bbd
   -1   135 zgv: qdm qjl cjb lpv
   -1   136 frk: sgk
   -1   137 mdf: pgr ccv phk
   -1   138 gxn: cgf nvk
   -1   139 sdf: dkr mnq
   -1   140 sxt: bmk kdj
   -1   141 dng: tbh rpm fbk
   -1   142 sjr: nfm tfv mjc
   -1   143 xxp: vfm xhp
   -1   144 kzr: fzb
   -1   145 dvt: hks fqg lgh
   -1   146 lpl: kng tth fnj cfz
   -1   147 cxk: szb bhp vkf zrz
   -1   148 rzl: nft hqg glm
   -1   149 xlx: zfr nmd ddk mpp fqb
   -1   150 ksx: phl tmr rpm jbz pxr fgc tfv
   -1   151 ghd: mgq xhp fnx
   -1   152 xbf: znf
   -1   153 qzn: rsf
   -1   154 lkx: hhf hnx tlx hbj
   -1   155 rpz: npm nts htk
   -1   156 zps: djb skq mxh
   -1   157 zmn: jmq hqp
   -1   158 lts: pxj xmj ppz nfq
   -1   159 jlk: pqt nbh nlk tnr rdp
   -1   160 bms: xcd lqt
   -1   161 brm: dxt xxn qxc nkj
   -1   162 lxg: zxm tpm
   -1   163 jxd: vgr cds gsm zxj
   -1   164 mlz: clk
   -1   165 pth: cnb
   -1   166 hlc: dqr jhg hnf
   -1   167 nns: rgc bds hch kkk
   -1   168 tvk: sss zxj krs
   -1   169 phl: rgf zrn
   -1   170 hjm: qfl vtk hsc
   -1   171 mgj: lfb mlx nnz cxb
   -1   172 dmj: djb fmn
   -1   173 npx: ktq ltg
   -1   174 qmh: dfx
   -1   175 pgk: jqq rdh dsj qnn hxj
   -1   176 lnr: gbl cjg gfz jqk
   -1   177 zsj: zfj fqt
   -1   178 brz: bpf qbd ftd qmf bmf
   -1   179 zhx: pds tnd dmm
   -1   180 qhg: xll cmk ppz srx
   -1   181 vfd: zln cdn
   -1   182 jmx: mnf bsq
   -1   183 dqh: nms fpr nkj
   -1   184 smg: glp ngt pnk
   -1   185 ztl: vcv mbc
   -1   186 pvk: rzk
   -1   187 jhm: gqq qtl ztl xml
   -1   188 rzr: rxk mdh
   -1   189 nzp: dpv mqg mjb pdf
   -1   190 ngb: fkl ctx dcq czx
   -1   191 tdc: dlt tbd
   -1   192 nqs: mps qlv ssx xbp hcn
   -1   193 pmd: fvr vmf gcd vvt
   -1   194 shq: rtm bpm bqc dkm
   -1   195 tgr: rbs txf ftx mcx rtm
   -1   196 grn: rjm nms
   -1   197 psq: fmj
   -1   198 ksg: kdk qzn hzx glt
   -1   199 bnq: ckl
   -1   200 jnq: hzx qpd hjl dcl xbk
   -1   201 zqb: frl
   -1   202 vlq: snh rpm
   -1   203 pkm: jkm
   -1   204 jpd: ltl drn gck bxc bkh
   -1   205 smd: dvt mbc hrz czx
   -1   206 slg: pds
   -1   207 dcs: dnh
   -1   208 gfz: zdj
   -1   209 kcb: dxz mfg jln
   -1   210 dxk: sgf bjf nzq fps scq
   -1   211 rzq: llh
   -1   212 xmx: kdt xbf kgb jjf
   -1   213 jds: rjh rgl jqq
   -1   214 zdx: npt
   -1   215 dqz: thx dqr
   -1   216 jpn: qhj jjf
   -1   217 rtf: hsn cjb vvt ghd
   -1   218 xcc: sdz xtt
   -1   219 jtx: qlm crb qxz
   -1   220 cct: dlv xgg dmp gsd
   -1   221 cbz: zvc dtv dkm qbd
   -1   222 jtk: qgr vnx xbp
   -1   223 vhz: fts tvx krj njb
   -1   224 hhq: nxb bsq fjn
   -1   225 qbx: qpd cxg
   -1   226 jfr: qzb vdf fzm frk
   -1   227 jzp: tvd rls lfb fqg lhs
   -1   228 cvd: qnx
   -1   229 pkz: fbk qnz
   -1   230 njs: fzl
   -1   231 mqb: gdl
   -1   232 mhs: vdx
   -1   233 bvd: fsg ldf
   -1   234 xmk: hzg mbd fpg fhr
   -1   235 dpv: lrk
   -1   236 szb: qpt bxt
   -1   237 fnj: qkl
   -1   238 mgx: ktr zll hvt
   -1   239 bpf: jmq htd
   -1   240 zst: sfh lxz zfl mgp
   -1   241 chl: gxn dcs
   -1   242 ddj: znl
   -1   243 bbd: pnx tfv
   -1   244 bph: ftx dxp dqq vfl mmd
   -1   245 blt: hjb djf rbl bmf
   -1   246 cvb: kft
   -1   247 bsh: qpm snm vqn njb
   -1   248 cmk: bcd
   -1   249 hdl: kfz dsf
   -1   250 jmm: qpm ttk
   -1   251 cqx: lxj tcf djh
   -1   252 ptp: kzv qgj rxk
   -1   253 rmt: vft ttk
   -1   254 bdk: mjl nfc xnd tll
   -1   255 jzj: rjq
   -1   256 fvp: vtk gqq rbl bst
   -1   257 hjl: jnx
   -1   258 xqk: qhd cbv
   -1   259 mpg: dth nnz sgp
   -1   260 lxj: vmh
   -1   261 rtb: slt
   -1   262 cfd: cdl
   -1   263 kbz: vmf njc lqn rgc
   -1   264 kmc: znx hbn
   -1   265 snf: fks kfz
   -1   266 bqt: qnz bmh pxr fth
   -1   267 qlm: dmm tvd
   -1   268 ptc: tzm
   -1   269 qmn: tvd
   -1   270 gmr: sfh rll psd cfz
   -1   271 jmq: kzr
   -1   272 rjh: pcx nxx
   -1   273 gdg: hjg zfl hqk dqh
   -1   274 fdn: jbt
   -1   275 vpd: rhn hng tcs
   -1   276 xzh: skh dnp
   -1   277 npp: qzn vxd kfv
   -1   278 tbh: vcn mdd
   -1   279 tpj: fnj mgq
   -1   280 pzb: xlz lvz ncq qfh
   -1   281 nft: bzv clk vpn
   -1   282 sqm: bbp zds
   -1   283 czv: dxp cdl nhf czt
   -1   284 zvv: mqv thm vsh
   -1   285 zrn: dmv fbk qfh
   -1   286 jtz: rvn vsh ldf
   -1   287 lnj: kzk zhj dzd grn
   -1   288 nmd: mnq nql bkc
   -1   289 nnt: mqv xbk blx
   -1   290 fzz: pkm fkc qkr fbd
   -1   291 xjb: dfh qcg dmj
   -1   292 qcf: dhq fqr lzq
   -1   293 ljg: mkk zvf xmj
   -1   294 qcd: kvl zqb cxz nsf
   -1   295 ntq: rxn lvf
   -1   296 grh: lfb
   -1   297 cds: kpz srh qgj
   -1   298 pdl: ppk dpj xcd
   -1   299 pxn: plv
   -1   300 zll: bng ddc pth
   -1   301 njc: rll hzx
   -1   302 pbm: mmd kks gmt ghj
   -1   303 dnp: mzp
   -1   304 grq: csq dqz tpb ckl
   -1   305 hsd: lmq xdv
   -1   306 sxs: pch ssv qfm lls kht
   -1   307 mqs: xcc vtj mhg qhj nlt
   -1   308 cbv: vdx thm
   -1   309 mhj: nvr mgq
   -1   310 pdf: xgx
   -1   311 cjz: cnz dkz lqt dmv
   -1   312 zfb: nzh lls mpp bgr
   -1   313 lfd: zsl ssj zds
   -1   314 dvg: hhv jhl
   -1   315 hnh: nxq vst lzq
   -1   316 kdk: dtn glm
   -1   317 dcr: tvx
   -1   318 hvh: vlh rmt svd
   -1   319 kxk: sbc sdp hsn shn dfx zvv hjj
   -1   320 kgb: glp gvk
   -1   321 fkq: jlt pxn
   -1   322 mdk: xrt ldb
   -1   323 nrm: mgp njc xdv gfz
   -1   324 fjb: rsf mxm
   -1   325 tbq: ktd jjf
   -1   326 fvr: bpk
   -1   327 dsd: vql sss
   -1   328 sgk: rxk lsz pcp
   -1   329 qzs: ksz mdd
   -1   330 fld: mfm mjc rff qhf
   -1   331 trb: zll trk
   -1   332 ltz: znf
   -1   333 jxv: hbs bbp ptc qkb
   -1   334 flk: ddc hrp rfr mbg
   -1   335 fjk: cxq hzn fbd
   -1   336 ljb: vpn nlk gkb cng
   -1   337 mgq: ltz
   -1   338 cxb: sxn
   -1   339 btp: lrk pxb snf mrv
   -1   340 gvt: rxn
   -1   341 drc: hcn mxm stg kkk npp pxs zfv rpf
   -1   342 msm: hlx trx xjp jrc
   -1   343 dkr: mcl
   -1   344 nxl: vzh
   -1   345 bxt: bql
   -1   346 kpg: htn
   -1   347 hrz: lbz mcx ljx
   -1   348 mcf: cfz dhq lhm glp
   -1   349 gft: bng qhd
   -1   350 bzc: lhb mfn dgx xcd
   -1   351 tmr: ddk dxz srr
   -1   352 xlk: shl chm tlc tpj
   -1   353 nfg: fvb xml vtk
   -1   354 zvc: qfx jkl
   -1   355 vvg: kks jhl
   -1   356 gdn: knf glp
   -1   357 rqk: kfv djh tkd bsd
   -1   358 qnn: rgf
   -1   359 fhq: dcr ftd rdf pnx
   -1   360 tmz: ttk
   -1   361 pcx: glb pnr
   -1   362 llr: jjn nfg gsd
   -1   363 ftv: ppz xvz vvv
   -1   364 jfs: kjh lxz krt zll
   -1   365 fkc: ftv krj xmc
   -1   366 rmr: qgf fts
   -1   367 lzq: hrd
   -1   368 fsg: thm
   -1   369 vqg: vfr xtt mpl
   -1   370 gqc: nvr shn
   -1   371 kct: lnf hpt frc dbh
   -1   372 ngx: pvk pgr
   -1   373 rkl: vrn hnf
   -1   374 ttn: mdh
   -1   375 zdm: fzm pnt kjm mcg qlg sfz
   -1   376 nhx: rbr
   -1   377 jmd: lkd bzj ggj mdf
   -1   378 hcr: gsd sqp kjd vtk
   -1   379 scq: ckz nrr nxp
   -1   380 hds: pxr mjc
   -1   381 dzj: mcl
   -1   382 ssj: stk zmr qzs lvn
   -1   383 jjp: lxp fqt tgq npt
   -1   384 qkr: zqc
   -1   385 nxp: dxr
   -1   386 bcx: bbm lpv zrx
   -1   387 rbl: vbc hzl
   -1   388 phm: tpm vdx nrt
   -1   389 jnk: vcn zfj ltj
   -1   390 zlc: dcs clf cvd
   -1   391 mrf: rjq
   -1   392 nlk: mqv kpq kgf dxt
   -1   393 zdj: hrd
   -1   394 cpb: gft glt lsl psq
   -1   395 rln: ffv vqs fqg sxm
   -1   396 xkp: mkh knk kcz vfr mjb
   -1   397 dqr: rsf
   -1   398 blz: zrv jdd bzx php
   -1   399 svd: vmt xrh
   -1   400 tnb: bgp hpv jrc bst
   -1   401 dch: qjl rzp lnj rpz
   -1   402 crr: nfs hjg hch
   -1   403 xfb: ltz bdb
   -1   404 kkz: lvn jmm lbs
   -1   405 pct: qfx mcb fsn
   -1   406 xgg: fqt
   -1   407 hbz: grd kng lvf
   -1   408 xdx: spg vtq zvc rcn
   -1   409 lhm: gvk tdl jtm
   -1   410 lkd: lct jnq rgt tkd kdt
   -1   411 dkm: pdl czv ltj
   -1   412 zpl: bdl rjm
   -1   413 dzd: xbf dfx rdp
   -1   414 cvs: mcg ppg nfq tml
   -1   415 mjm: hvl zzj qxc zgn
   -1   416 jzl: jtm jrh tpj
   -1   417 rqf: dgj tdd mfq
   -1   418 xjn: fth czh pft tbk
   -1   419 rls: vjh snh
   -1   420 sdv: dfh kfm
   -1   421 vbn: qkl kpq bkh lxz
   -1   422 ngm: mdd gjq nfm vmt
   -1   423 nvt: dvg bhm
   -1   424 fsl: tgn xsl vfm
   -1   425 dzr: fvr dsp
   -1   426 cdn: rtb
   -1   427 dmv: ltg
   -1   428 ckm: sqm bdt xcd rgl
   -1   429 phk: drv ltl
   -1   430 tkm: fsr
   -1   431 hcn: hrp
   -1   432 hdf: smh trk hkn lgp
   -1   433 fcr: pgk nxh mgv bxt trq
   -1   434 ktt: qkk hmj tbq xxn cgf
   -1   435 czr: lhs bvh nvt sxv gpm bbd
   -1   436 bst: jsj
   -1   437 hbn: mrv cxg
   -1   438 bht: vtv
   -1   439 tbk: gdl lbm mgr lfb
   -1   440 dhb: rtb grn hjl dcs knq
   -1   441 ccn: dxr
   -1   442 czx: tvd
   -1   443 brp: nkc tmc
   -1   444 zcj: jhg nnx phx
   -1   445 pcr: jsm
   -1   446 dmc: tkm jsj
   -1   447 kjh: smg jjd
   -1   448 mdp: rgf ztx zgf
   -1   449 ngv: sql xtj ttk qzv kvf grc
   -1   450 bhp: crq
   -1   451 gsb: fkc hgp dmv gkj
   -1   452 hjx: fzx rjq kkv
   -1   453 lcb: vhp vlm dpj rmr
   -1   454 qfg: rkl qks hnl zmd drv
   -1   455 mdh: vqs
   -1   456 rpf: gcd
   -1   457 qsj: bff grc dcj ckz
   -1   458 xzp: dtn vfm tvn
   -1   459 dxl: svc qpd gqn qxr
   -1   460 tpr: qkb
   -1   461 srr: nkc npz jnt
   -1   462 ngt: vbx vqz lmq
   -1   463 sql: tdv msr mfl
   -1   464 tlx: gqf xnz
   -1   465 zzp: mdp smt frk cgx
   -1   466 pdz: qlc nds vqz
   -1   467 nrz: xcb zfj gmt pch
   -1   468 jkl: pbk
   -1   469 dds: pxs nxb dkq
   -1   470 vrk: fkj kps jqk
   -1   471 cdq: bnq grd rrm dsf
   -1   472 mvd: gqd vkf qmn
   -1   473 xmc: gjd qfh
   -1   474 nxq: fks dsp
   -1   475 mcg: zdx
   -1   476 kjp: tdm pcp ljx srl mhz mmh
   -1   477 lng: fsg
   -1   478 lkm: qgj sxj ktq lsz
   -1   479 xgc: vjn pdz nlt qjn tfj
   -1   480 xlb: gkq czh
   -1   481 mmd: vvv rgl xvz
   -1   482 pzf: gsd dgr qhh xvz mjl
   -1   483 zgb: xjp
   -1   484 nzq: qzv rmt lcj ttn ktq
   -1   485 nds: gcd xjv bzr
   -1   486 dlz: rdf ntf ddk fvb
   -1   487 kdj: lvf jmx
   -1   488 hch: ktd hbt
   -1   489 sss: lbs qfh xgg
   -1   490 glq: rcj xnz vjh
   -1   491 mlx: trf sgs xkh gjj
   -1   492 fhk: zvg xlt mhz gcj
   -1   493 pgt: mbb czd hqt qgs std
   -1   494 bzx: hdl dnh fss
   -1   495 pqx: znl zrx
   -1   496 qfx: dpl
   -1   497 hsr: cdn fxp pcr jls
   -1   498 bbm: nbs skx
   -1   499 mfg: tzm spg
   -1   500 tml: qfm
   -1   501 sbd: dsd ksz bsh gqd
   -1   502 gsm: cmk cdj
   -1   503 zfx: jvr dvg pbk xgm
   -1   504 vnc: slg rxs
   -1   505 qlv: jjf hkn
   -1   506 mgr: vvg zxj pcp
   -1   507 pqt: gdn csq hfd
   -1   508 fpp: qhd kpm
   -1   509 ncq: kfc qkb
   -1   510 vft: dcr xlz
   -1   511 rvr: gqf dnp lhs rtm
   -1   512 bsx: ssd ptk tlj
   -1   513 ddc: pvk zdf qmh vss
   -1   514 clf: llj hbn
   -1   515 ttl: nkq hrd
   -1   516 jkm: npz
   -1   517 hzb: bht smh rpq vnh
   -1   518 bnt: pch dmc rxs sxm nfc
   -1   519 xbk: xgx gck
   -1   520 hxg: lpl
   -1   521 vdf: kcb bcn ltv mfg
   -1   522 hbd: rdb jmx gvg knq zmd
   -1   523 fbd: pqj
   -1   524 vdd: fvr znx
   -1   525 jzn: bgr rdh bql bgg
   -1   526 sbc: dlt
   -1   527 mnz: rjq
   -1   528 dsj: lhr krj
   -1   529 zcx: rgr vtk xlb jkm
   -1   530 dnr: sbg hng tcs ftj
   -1   531 hbj: npt ffv gmt ssl
   -1   532 blp: dsp zpk zmb pdk
   -1   533 sfl: fbk tgc clm pch bks
   -1   534 bgn: qfm rgf lqt
   -1   535 mld: kpg mbb fbz jnx
   -1   536 znz: gzz lnj nvk cnb
   -1   537 sjd: hrk kcd nqs
   -1   538 mbg: rtj bvd jtm rsk
   -1   539 bmh: npt
   -1   540 vlh: vcv
   -1   541 trx: rzb
   -1   542 dxt: vpv nvr
   -1   543 npm: xhp drf tkd
   -1   544 slt: rtj
   -1   545 rpv: zvg dmm skh
   -1   546 dmp: rgz nqb pzh
   -1   547 hpv: mfm
   -1   548 fdk: dsj xrr zjz
   -1   549 bqc: mcl kgs gmt
   -1   550 jdh: pkq frk jqq
   -1   551 rll: drn sfh mps
   -1   552 mfh: vsq csn qpd ltz
   -1   553 ztx: vql pkz
   -1   554 pqg: cmv xpz dxr sxs jlt
   -1   555 qzr: rbj
   -1   556 kjl: xrn nxb kzk ktd vdx cdn
   -1   557 lgs: hxg dzr kdt dhq
   -1   558 ssx: cxg
   -1   559 pcb: zxg dhb
   -1   560 mfb: lbv mqk mhs dhn php
   -1   561 bzr: tbd ltl
   -1   562 zmm: gfj gfz lxz qgs gzz
   -1   563 mgv: kzv tzm
   -1   564 ffv: mfn
   -1   565 rdp: mxm
   -1   566 mrx: vmn lqt
   -1   567 lcd: xzh ssl cff frp rjh
   -1   568 vbc: snm
   -1   569 cgz: ltv jll bpm nhf llb
   -1   570 rgr: sql csh qgf mpp
   -1   571 php: qkk lcg cnb
   -1   572 mpl: ngx hmc mnf
   -1   573 fpc: hvt qps kmx lxg
   -1   574 ctx: dth ssj
   -1   575 nlf: dmm sxm ddk hsc
   -1   576 gjq: cmk nrr vzh
   -1   577 jjm: kkk chl qps xzp
   -1   578 qxz: kjd fdn
   -1   579 xxj: vst drv
   -1   580 nrt: gzn fnj
   -1   581 qtz: gft gvt bzv
   -1   582 xxt: mfr nsv hfk gjj bff
   -1   583 hjb: gkj ddb mcg
   -1   584 gpr: ctx rdh jmm bhm
   -1   585 zgn: kmx
   -1   586 dkq: qzf jqp nnt
   -1   587 mpv: gfj flk nxq
   -1   588 lxz: rjm
   -1   589 mbd: dsp fss
   -1   590 zrz: qtl phl rzq fkq
   -1   591 rkb: vmf hnh fzx zrx
   -1   592 kfc: cvb
   -1   593 kjt: fbk
   -1   594 mqg: pvk
   -1   595 bdc: dhc grh jrc cgs bjp
   -1   596 lrd: lrk qtz hbz tvn dtp
   -1   597 fbv: hmc ttr hrk
   -1   598 hfg: brj vdj xvz sfz
   -1   599 gfl: fjb xsl vnh pdk
   -1   600 mjr: bgp
   -1   601 tgb: vpn mkd nff
   -1   602 rmv: gcd fmc lpl mps rzl
   -1   603 rdx: pds
   -1   604 shm: ptk rzk mnz
   -1   605 tks: hds xvz vlq jlb knc jnk
   -1   606 ckl: tjf jsm cxg fgx
   -1   607 nzc: xxp xqk hjx gns
   -1   608 kgf: fsl fpp sxt
   -1   609 zfl: kkh mxj
   -1   610 tvn: vrg cgf
   -1   611 zfr: nrr qbd
   -1   612 jhg: qnx
   -1   613 qxl: ttz cgc hlx mfl
   -1   614 rxm: mdh tmc cvb
   -1   615 mxg: qth ksb ztl
   -1   616 chk: svz qzr zxg
   -1   617 fsn: qmn dhh
   -1   618 fpg: rbr csq dlr
   -1   619 svj: rhz lhr smt mfl
   -1   620 htp: fks mkd xdv
   -1   621 hhf: jkl
   -1   622 rbs: srr xxd
   -1   623 qgf: pxn hng
   -1   624 nfc: pkq
   -1   625 ppj: spx mgp fmj kgb
   -1   626 vfl: bhp
   -1   627 lfb: npz
   -1   628 pdt: dtk pqt zdj cbl
   -1   629 jgz: xnq dbr bht rbb
   -1   630 drf: bds qjn
   -1   631 bdz: qnn gsd fzb bgr
   -1   632 tdl: nvr
   -1   633 rlb: kfc czx mqb tgs
   -1   634 zvl: qnx hjl
   -1   635 dgf: vbf htd
   -1   636 qlh: tjk jfx zmn cfd nsl
   -1   637 qlg: srl mkk xkh
   -1   638 dbj: zvg dxp bpm jkg
   -1   639 npg: mcg ftj zpq mgr
   -1   640 thm: chd
   -1   641 ksb: pvv stk khj
   -1   642 lnb: dng knd scc cgx hbk
   -1   643 nfs: jvs
   -1   644 sxj: czt
   -1   645 bzs: nxb nms kcz
   -1   646 lpv: lnf
   -1   647 zpq: kft srh
   -1   648 gbl: hsk rgc rtv
   -1   649 pkp: jjm fvg rpf
   -1   650 xqx: lrg pnf qcf smh
   -1   651 tfj: djb nlt bzm ntq rpj
   -1   652 djf: zrk slg pnr
   -1   653 kvf: txl
   -1   654 ppk: crb jvr
   -1   655 zkg: lng vnx
   -1   656 tvb: ssj sch fdn
   -1   657 vnh: nlt jdt
   -1   658 kpj: qxz zgb hzl fdn
   -1   659 gdl: llh
   -1   660 srx: qzv frl trf
   -1   661 mdz: mmh kft snm
   -1   662 xbl: hpv cnk ktp sbt
   -1   663 jsm: nhv rbf
   -1   664 vqz: kpm
   -1   665 ppg: scc smt ftv
   -1   666 xhp: ddj
   -1   667 knk: clk
   -1   668 qpv: jjd vjn kdt
   -1   669 hlv: lnd bnq cjn
   -1   670 cxn: dhq dsf sgb svz
   -1   671 rqb: bxt dvt vcv dcq
   -1   672 xgq: rtp vsq vkb vqz
   -1   673 csq: fjn
   -1   674 mjl: pzh
   -1   675 vzh: xlz
   -1   676 mlq: zxj jsj rjh ztx
   -1   677 dqt: cfd
   -1   678 fxp: tbd fmn
   -1   679 tbj: vns zpl qzn vfd
   -1   680 khj: xrh plv skz
   -1   681 qbd: pds
   -1   682 cdl: pbk lhb
   -1   683 bkc: dtv jhl hhf
   -1   684 hps: xnq htp bmk ssx
   -1   685 htk: ptk drv
   -1   686 qjc: qkb dgr tcs
   -1   687 gmd: mdk qdm vst
   -1   688 zjx: nsv zpq hpv
   -1   689 kvl: qpg nsl lhb
   -1   690 cfp: cjn sjc skq
   -1   691 xlt: rdf dgj mzp qnn
   -1   692 mnr: csq jqp
   -1   693 trk: fkt kzk lqj
   -1   694 ghx: fkg lqn xqk pdk zhj
   -1   695 nts: qkl kmc jgn
   -1   696 vrn: nhv mjb
   -1   697 dth: nqb dpj vhp
   -1   698 sgf: jpg sxj vbc
   -1   699 jvr: jfx
   -1   700 hxj: mdh
   -1   701 dgx: cmk ssv rls
   -1   702 rgd: pnh qmd qcf bxc
   -1   703 nsv: nfq
   -1   704 ljt: tkm cfd jql qhf
   -1   705 bzf: mms bgr
   -1   706 qgr: bzv
   -1   707 gpb: nqp blx ssx zfv
   -1   708 rxf: rpq hrp vmh knk pcb pmd nfs
   -1   709 fnx: vrf skx
   -1   710 dtn: nkj
   -1   711 rtv: xdb cvd kpg
   -1   712 fzl: rgz
   -1   713 dbl: lbv mxh
   -1   714 kbx: zbv
   -1   715 tcf: gfj
   -1   716 mcb: tmc knd nxp
   -1   717 bks: tnd sxn
   -1   718 rxd: sbc jvt
   -1   719 hbt: fnj szl
   -1   720 jcz: dqt tgc gbz pgl
   -1   721 lvk: lnf nmm xdd
   -1   722 spg: cxb clm tpr
   -1   723 ndl: knz mqb tkf
   -1   724 nkl: cbv
   -1   725 rhl: ndl vnc fgb zvf
   -1   726 xxn: csq bht
   -1   727 glm: mxm
   -1   728 vlk: dzr jcc pxm znx
   -1   729 ctn: nbs ksq tcf zkg
   -1   730 grv: vbx llj jnx
   -1   731 bzm: hzk fnx tjf
   -1   732 hhd: rbs hxj lkm
   -1   733 bxm: hgv dhc kjm fmf
   -1   734 hvt: cjn
   -1   735 cnp: kht lsj snh msr
   -1   736 zqc: pnr
   -1   737 xlz: nhf
   -1   738 fxl: vqs txl tgz tmz rzr
   -1   739 zjv: chd pvk
   -1   740 lrg: ltz mrv
   -1   741 bhs: hdl nqp hjl hll
   -1   742 dxz: hhv
   -1   743 cmj: fps qld rgz qhd
   -1   744 rbb: qjn kkv rtp
   -1   745 ddb: mdd
   -1   746 gdj: qdr pdl hnx gpm
   -1   747 gzz: dnh ntq bsq
   -1   748 gng: sdp ttl vrg bzv
   -1   749 tkf: hzl dkr sqm
   -1   750 gjh: hlc phs fgx zmb xgq ggc
   -1   751 gvg: rdp djb
   -1   752 pgl: pkz
   -1   753 snv: npz dkz mbc
   -1   754 mqq: jnr tfj dxl qpv
   -1   755 lhl: zpp svc
   -1   756 dlv: rxs
   -1   757 hll: qxs lpv vls
   -1   758 mcr: hds hbs dgx jtx hzt
   -1   759 qct: dst kcz bmk rsk mhg
   -1   760 zvg: xml
   -1   761 gfp: vqf
   -1   762 qdz: qbd ssj sbt
   -1   763 txv: lhl mrf cdn ckl
   -1   764 gqd: cmk
   -1   765 kfv: qdm
   -1   766 fgx: tgn vdx
   -1   767 glp: vpj std
   -1   768 tll: gjd npz fmf
   -1   769 llz: kvl blg bbp lcb
   -1   770 kcd: dsp jvs jlj
   -1   771 vmf: mtr
   -1   772 drv: cvd
   -1   773 frx: sdv jrh psq bvd
   -1   774 qbh: vqf gsv htk
   -1   775 lvz: jmm kvf nvs
   -1   776 mtd: mlk gkb qks jtz kjh
   -1   777 qks: ssx
   -1   778 knz: sxj
   -1   779 nnz: gkf
   -1   780 scc: kht
   -1   781 bsc: ttn mvd dzj dng qtl
   -1   782 qpg: nxp
   -1   783 blg: brj pzf kvs kjk sqm
   -1   784 hgv: nlx hhf
   -1   785 tgs: fvb gdl
   -1   786 xgm: qss jln kgs
   -1   787 zfs: qxc spx htc spm
   -1   788 chm: hrk tlc rvn
   -1   789 ddp: srt vvg
   -1   790 kkh: rbr vrf shn
   -1   791 zvf: xjp vlm
   -1   792 mfr: rdx mpp vlh xmc
   -1   793 cmv: zgf
   -1   794 pvv: fll njb
   -1   795 qdr: dkz xtj
   -1   796 ttr: vrf vpv kfm
   -1   797 mms: srh jtq jsj
   -1   798 jbz: bhp srl
   -1   799 fvg: jgn dcl
   -1   800 pxs: htn gxn
   -1   801 sxv: gqd srh hgf
   -1   802 vgr: dth glb zqb phj
   -1   803 glt: mlz
   -1   804 znx: zxm
   -1   805 pxj: kgs tgs
   -1   806 jnd: xrh nnz
   -1   807 fmf: fbk
   -1   808 nff: lbv
   -1   809 sts: jnd slg jtq rgl dcr
   -1   810 ldf: vqf zmd
   -1   811 cvj: cng fnx
   -1   812 fjd: pss
   -1   813 bvh: jnd dqt nzq
   -1   814 jtm: tjf nvr
   -1   815 qgj: gcj
   -1   816 skz: vhp sxm npx
   -1   817 phs: llf fvr tbx
   -1   818 zrp: lcg tdc rxf zrv
   -1   819 cnd: vmf ddj xbp
   -1   820 pxm: cnd tsr bpk qgs
   -1   821 qzx: xnz fdk pmr bxt
   -1   822 hdk: fvr vqg xjb
   -1   823 ltv: vkf rcn dxr
   -1   824 vss: svz kdj
   -1   825 cvp: llr nxr dqt vlm ktq
   -1   826 phb: vmn vfx qfl rxm
   -1   827 fqr: hrp kbx
   -1   828 xrt: vkb tpm
   -1   829 phh: ghj fzl tvx mkk sjr zgf
   -1   830 phx: drn djb knk
   -1   831 nxb: fpp tlj
   -1   832 dgl: vdd fpr vqf
   -1   833 mfl: kjm
   -1   834 vtj: cfz rzk vrg
   -1   835 fgc: bql nfc ktp
   -1   836 jsk: trb hnh zps zlc
   -1   837 vbf: bjg rcn nzh pcx
   -1   838 drn: znf
   -1   839 jhq: vft jbt
   -1   840 msp: psd vfr zdj xvh rbj
   -1   841 glh: bdb grv fpc sdz chk
   -1   842 dls: fkg tdl
   -1   843 bzb: mfm vcg nlx nfq clm tvv
   -1   844 mzf: tvx cct cnc fkl jth
   -1   845 vvt: bds
   -1   846 ckj: pcr nvk dfh grf
   -1   847 rbf: vpv
   -1   848 nsl: qhf
   -1   849 kdt: qlv
   -1   850 dtp: hrp
   -1   851 mhg: rtb
   -1   852 ljf: qth vrs szb lcj
   -1   853 gsv: hrd lmq rpf
   -1   854 cql: clk
   -1   855 gnf: vss gmd lvk mgx xvh
   -1   856 skh: mzp nxr
   -1   857 hpt: sxt cng bnq
   -1   858 rnj: txl pvv kht
   -1   859 jll: lnf gkf
   -1   860 qpt: sfz
   -1   861 hgp: xzh knd tvb
   -1   862 msv: zdk ckl hsd jdt
   -1   863 vxd: smg pdf gqc
   -1   864 cfq: zmr hjb ckz cmv
   -1   865 fkl: qzs vfl
   -1   866 crb: rzq
   -1   867 knc: csh nsb tlx
   -1   868 ftl: qfh hsc bcd hzt xcq
   -1   869 czd: brd
   -1   870 trf: vjh hks sxm
   -1   871 rkv: zpl zpj dtp
   -1   872 ljx: dkr
   -1   873 qtf: lqj skq
   -1   874 xmm: vmh mhs skq thx
   -1   875 kcz: cnb
   -1   876 lbv: vjn
   -1   877 ztm: vjn gfp gkb mnr
   -1   878 lsr: vvv lhn vmn xgs
   -1   879 nvs: ttz pvv bhm
   -1   880 pcz: vqg qhj chd hnl fmn htc gfp
   -1   881 sxn: qpm
   -1   882 ccv: fss jzj
   -1   883 kjm: vqs
   -1   884 fnh: lvf vqz zmd rsf
   -1   885 xpz: nzh nxp krs vvv
   -1   886 fbz: ldb szl tbd
   -1   887 trq: dlv plv pgl
   -1   888 nmm: kfz hfd
   -1   889 vcg: rjh fqg
   -1   890 znl: zrx
   -1   891 nss: tzm sdf gkj qhf
   -1   892 dtv: ngz
   -1   893 vsh: lxz zgn zbd rkl
   -1   894 kzv: rxs
   -1   895 nqj: zsj qgf qjc jkg lsz
   -1   896 krt: xcc cfp bpk
   -1   897 rlv: hvl knf bcx cgj
   -1   898 vpn: xxp cql
   -1   899 smt: kft nsv pnx
   -1   900 bxb: xfb lgm snf zjv
   -1   901 cnc: fqb
   -1   902 tgx: jdh sqp bzb fkl
   -1   903 xmj: czt jhl
   -1   904 fks: fss lmq
   -1   905 xzv: dkz tns
   -1   906 ghj: pnr tvd
   -1   907 lfc: lxp tvk hvm bzf
   -1   908 kqr: npt
   -1   909 nql: dvf vlq tdd
   -1   910 lsv: frl jvr kjd mrx pct dlv
   -1   911 rff: njs ljx pqj bxq
   -1   912 zxj: xkh
   -1   913 cqc: lqt pzf bjg ksz
   -1   914 qxr: vpj pxb
   -1   915 kpq: fbv
   -1   916 nhv: dbr
   -1   917 cdj: vkf gqd mnq
   -1   918 pgr: std
   -1   919 zsl: pbk dnp
   -1   920 rqh: pkz bxt zgb
   -1   921 qjn: lgm
   -1   922 vls: kng
   -1   923 jkg: rzr
   -1   924 kdp: mfn xml dkm nsf
   -1   925 xjp: clm
   -1   926 grd: rkl zkg
   -1   927 ktr: dlt
   -1   928 tcs: xcq
   -1   929 cbl: chd
   -1   930 dcj: tfv bck gjj
   -1   931 lbz: bnx bms
   -1   932 jfx: cxb
   -1   933 pfx: nff vrk dgl vdd
   -1   934 nxx: vmz ngz mcx vql
   -1   935 bjp: dgx bql zmn
   -1   936 xdd: fsg bdb qxs
   -1   937 tgz: vbr rzb fts
   -1   938 zzj: kmc rcb ttr
   -1   939 ntf: lls bkc
   -1   940 zdk: rrm lxj
   -1   941 dss: dqz fkt mnz cjg shn
   -1   942 zjz: hzn lbs knd
   -1   943 xsk: cql qcf qqf bzr
   -1   944 tlm: ltj ccn dsd glb
   -1   945 hnx: snm npx nrf
   -1   946 hjj: hzg
   -1   947 xgs: dvf ddv tgz
   -1   948 rnr: slt hsd zxz ktd
   -1   949 dhg: vzg hjj zzj
   -1   950 lvn: lcj qpt
   -1   951 dqq: rmr bck crq xcq
   -1   952 pmr: kzr ljg vtq qkr
   -1   953 bdt: vhp fts trx
   -1   954 cgj: drn cch
   -1   955 skd: kkh nzp hkn dfh
   -1   956 grc: xrh rqf
   -1   957 lhc: vfr ngt bxc kdb
   -1   958 fhc: zxz fcd drf xhr knf trb gvk
   -1   959 gkq: mfm kht
   -1   960 sgp: gkj qfl dkz
   -1   961 bdl: jzj hrk
   -1   962 jlj: llj sjc rgc
   -1   963 zmb: rfr sfh
   -1   964 mcn: hhq fzx fjn kkh
   -1   965 qzb: npx tch grh
   -1   966 zln: ttl vkb mnf
   -1   967 pgn: hbk lls kjd gqd sdf
   -1   968 lhs: lsz zdx
   -1   969 kxb: bdl ssd kbx
   -1   970 dcl: frc dbl rjm mhg
   -1   971 qss: pcx ttz
   -1   972 stg: cqx ngx cbl
   -1   973 xsl: lvf dxt
   -1   974 mtr: tpb
   -1   975 gnm: hnx tdd xxd pxr hcz
   -1   976 ttm: rtb tpb sdv
   -1   977 bgp: nnz mqb
   -1   978 dhz: vft cxz lhz
   -1   979 kkt: kkv hsd tbx
   -1   980 rhz: xnd czt bjf
   -1   981 hqp: zqc
   -1   982 pss: qfl gkf
   -1   983 zkh: vzh ktp skh nfc zmr
   -1   984 jjd: qcg
   -1   985 zrs: tgc bxq dkz khj
   -1   986 lbm: bxq
   -1   987 jdv: hhv nqb
   -1   988 gsk: zvc dvf glb xzv
   -1   989 nsf: jnt kgs tdq hbs
   -1   990 grf: llj vpv mgp
   -1   991 tnr: hjg kbx cfz
   -1   992 sjn: hgv nxp lhz ngb
   -1   993 bcf: zxm xbf dls ttl
   -1   994 vzd: bql dmc bjf njs cnp
   -1   995 bff: tzm qzv
   -1   996 vrs: tpr tjd
   -1   997 rcj: nnk cxq hsc
   -1   998 rtp: dtp zdf bmc
   -1   999 xdb: xxj zfl vnx
   -1  1000 jjn: bmh vpd crq
   -1  1001 dtk: mjb
   -1  1002 kks: pzh
   -1  1003 rdh: dhh
   -1  1004 svq: ltv hbj dvf fkc
   -1  1005 dph: bst qth jth ztl
   -1  1006 xrn: jnr xjv xxj
   -1  1007 cgp: gmq kps dch nrm
   -1  1008 hqr: mqb rbs ddp jfx
   -1  1009 bsf: lxj sjd dfx jtk
   -1  1010 jvt: lxg xbp rxn frc
   -1  1011 nkq: jhg mtr
   -1  1012 psd: kng
   -1  1013 hvl: bhs brd ckl vfd
   -1  1014 vfj: tcf gzn mps vfm
   -1  1015 vsj: txl snh fmf sts gpl
   -1  1016 rvn: szl rfr
   -1  1017 cfj: hsn brd jvs rtj
   -1  1018 rpj: lfv vss mnf
   -1  1019 dcv: pqm xll tvv bpf
   -1  1020 sgb: nqs hbn jnr
   -1  1021 mxj: nkq cjn nhv
   -1  1022 jdq: bbm qbh kkh mkd crr
   -1  1023 gmq: kdk hnf svz
   -1  1024 zhn: jbz fdf qld cmv
   -1  1025 tjg: mrv csq qkl
   -1  1026 pft: pzh jsj
   -1  1027 htd: hxj dpl
   -1  1028 tdm: cnc dpl
   -1  1029 hqk: qcg
   -1  1030 tct: sxt nms lnf
   -1  1031 jzr: hbk gpl rzb kzv
   -1  1032 pnf: nqd
   -1  1033 shl: zzj bkh xdv bng zxz
   -1  1034 dxp: vlh
   -1  1035 ncn: fcd lpt fbz cgj
   -1  1036 hgf: pss ckz xfl tml mcx llh
   -1  1037 ptk: lbv
   -1  1038 vcr: lbv znx zgn hjg
   -1  1039 csn: gck hbt xtt ttl hcn nkl
   -1  1040 lhz: gqf qnz
   -1  1041 mhz: mjl
   -1  1042 hzk: cjb
   -1  1043 fkt: vjn htc
   -1  1044 qjl: hcj
   -1  1045 jrh: vmh
   -1  1046 ltl: lpv
   -1  1047 ftj: zgf npx
   -1  1048 jfj: mpv mhj jnx mqg
   -1  1049 hqt: pqx vzg sbc
   -1  1050 xlr: mgv fjd ppk
   -1  1051 rgn: hqp rpv knz gdx
   -1  1052 vsq: vbx htc
   -1  1053 vsp: hhv nsb crq kzr
   -1  1054 gpm: fzb jlt kvv tns
   -1  1055 fll: smt sdn jll
   -1  1056 ttz: rhn scc tgq
   -1  1057 pxb: lmq gck
   -1  1058 nkv: fqt lvn tpr zjx
   -1  1059 ntt: cvj lld vnx lng
   -1  1060 cgs: bcn ccn pvv ksz
   -1  1061 bkh: czd cbl
   -1  1062 pll: mmh pds brj
   -1  1063 hmj: cbv bpk vvt qgs zxg hvt
   -1  1064 ccr: pkp qqf pgr cvj
   -1  1065 mkh: mnf xxj
   -1  1066 lms: sdz vrf hgd hjq
   -1  1067 jrc: vmn
   -1  1068 ssd: nfs
   -1  1069 kvv: kgs
   -1  1070 qhh: brp qkb
   -1  1071 zrf: ltz tdl ptk jzl
   -1  1072 rcl: xjb rxd vns fqr nqd pkp sjc
   -1  1073 nxh: zmr kzv sfz
   -1  1074 cnz: kjd mnq vsp
   -1  1075 dhc: lvn gjd nkc
   -1  1076 bvq: slt vdx clf lng
   -1  1077 xtj: sdn tjd
   -1  1078 kmx: psd
   -1  1079 hjq: zkg fmj
   -1  1080 bvg: fkj zzj pdf pnh bmk
   -1  1081 gns: sbc xhr qlv
   -1  1082 vtv: xnq
   -1  1083 pnh: sbc ktr
   -1  1084 pnt: ltj qlm frl
   -1  1085 lcg: hvt zbv
   -1  1086 vzg: mqg dxt
   -1  1087 tlr: csn rcb jjd gbg
   -1  1088 hcj: kbx gvk
   -1  1089 vtq: ltg kqr
   -1  1090 nlt: xnq zjv
   -1  1091 hcz: bcn kqr
   -1  1092 frm: lpv tkd mnz kpq
   -1  1093 smh: kkk skq spx
   -1  1094 dlr: gfp
   -1  1095 jpg: pnr zrk hpv kzv
   -1  1096 jqq: cxq
   -1  1097 srh: scc bhp
   -1  1098 sbt: fqb
   -1  1099 dst: dls htn knq
   -1  1100 rtm: sch dgj
   -1  1101 jnr: mxh
   -1  1102 fpr: lpt
   -1  1103 hgd: zll zdk
   -1  1104 ffh: pll sbt ccn jnt
   -1  1105 xcq: xgg
   -1  1106 hzt: fsr dgx
   -1  1107 bck: bcd qmn
   -1  1108 jls: fhr qxs
   -1  1109 qzf: kpg mrf hqk
   -1  1110 bnx: vcv tkm
   -1  1111 nfm: npt
   -1  1112 hhk: qdz tjk bgn llb vcg
   -1  1113 ngz: bbp
   -1  1114 fgr: dgf jkg jnl gjd xzv
   -1  1115 lld: lbv kpm zpp
   -1  1116 mbl: xlr snv dpl vfl dtv ffv zpq sch tbp
   -1  1117 rhn: vbc
   -1  1118 jtt: zsj mms krs sdf
   -1  1119 qlc: qhd bzs hmc
   -1  1120 dnq: ddp vlq zgb tbp
   -1  1121 vjh: nsb
   -1  1122 zxs: fnx thx zvl
   -1  1123 ddv: vrs qmv ppz
   -1  1124 vst: mbd
   -1  1125 hsk: kbx vqf knf
   -1  1126 mmz: pth zxg lgm mnr
   -1  1127 mqk: pxs dhq xhr
   -1  1128 gjj: mbc tns
   -1  1129 tjd: vql
   -1  1130 jpc: fqx qhd hch kmx
   -1  1131 nln: fnx ggc vpj fmn
   -1  1132 qld: tjk zdx
   -1  1133 bjf: qpm srt lls
   -1  1134 bjz: fjb mxh bdb rfr
   -1  1135 kps: dbr rbr
   -1  1136 kxm: szl mbb znl xhr vqg
   -1  1137 qgs: qxr vkb
   -1  1138 mlk: glm rfr htk
   -1  1139 zrv: bmc tjf
   -1  1140 phj: tvd krs mqb
   -1  1141 lqj: gvt
   -1  1142 gbg: nkl dsf pnf
   -1  1143 qqf: ltz qgr tlj rpq
   -1  1144 nzh: tmc cxb
   -1  1145 kgd: ctx trx dhz vsp
   -1  1146 rbj: qhd
   -1  1147 lct: zrx cql
   -1  1148 fcd: htp jls
   -1  1149 cxz: fth ssv
   -1  1150 zdn: gqf bcn tmz tdv
   -1  1151 kkp: dkr dpj lcj mjr vtv
   -1  1152 dgr: llb
   -1  1153 cdc: qdr kbj ngz zrk svd ptp
   -1  1154 rpq: dtn
   -1  1155 vpf: bdl vsq mgq
   -1  1156 zbd: lct nff fkg tdc
   -1  1157 mkd: bsq
   -1  1158 gbz: kjt jll
   -1  1159 rgz: mjc
   -1  1160 jgn: rfr kfv
   -1  1161 cjg: pnf nbs
   -1  1162 lrk: nhx
   -1  1163 xnd: bcd ptc
   -1  1164 fgb: tgr hsc lbz
   -1  1165 lqt: kks xcb
   -1  1166 mbc: txf
   -1  1167 xvh: pnk hvt
   -1  1168 cgc: dzj npz njs
   -1  1169 fdx: vnc cdc gqf jhq
   -1  1170 nnk: mdz tjd
   -1  1171 dhn: bbm phx hcj pmd
   -1  1172 zpj: dnh cgf rcb fss
   -1  1173 hzn: bks ftx
   -1  1174 bmc: htn
   -1  1175 tcb: sgk xnz fjd dzj
   -1  1176 fxs: nhx mqv mbb jpn
   -1  1177 dbh: nkl thx glt
   -1  1178 zsv: mzp vmn bzf bgr
   -1  1179 gjl: hpt ztm fvg
   -1  1180 zfv: ksq zxm xjv
   -1  1181 nxf: rzp kkv nbh gjl
   -1  1182 bsd: hzk bmc hjj
   -1  1183 snj: hqk tjg lpt xgx zbv
   -1  1184 qmv: dmv vqn mjr fqb
   -1  1185 tcj: kks njb svd mxg
   -1  1186 bpm: ddb
   -1  1187 msr: txf
   -1  1188 hlx: nlx fsn
   -1  1189 vdj: nxr qnz
   -1  1190 xjv: nrt
   -1  1191 kjk: zqc nrf qpt
   -1  1192 hmc: kfz sbc
   -1  1193 xcd: hqp
   -1  1194 sdn: vcn
   -1  1195 skq: rbf
   -1  1196 rzp: tgn
   -1  1197 sch: cnc
   -1  1198 zjb: qkl vls ndz
   -1  1199 gdx: pkq rzb gkf
   -1  1200 spm: rlv mkh zcj
   -1  1201 qkk: svc rrm fjn
   -1  1202 jlb: dgf cnk nvt
   -1  1203 llf: zdf vpj
   -1  1204 tth: znf vbx
   -1  1205 vbr: tnd nhf
   -1  1206 jcc: cjb
   -1  1207 dzk: mkk msr jdv hhd
   -1  1208 vns: czd cch
   -1  1209 zxk: cdl rzq tmz
   -1  1210 lfl: fkj qzr bsx chl gnk
   -1  1211 cms: rcb dqr phm lhl
   -1  1212 rsk: jvs
   -1  1213 hfd: hkn nhx
   -1  1214 vck: xgq jpn fzx mhs
   -1  1215 ktp: cdl
   -1  1216 bgf: cqx dlr lrg rtj
   -1  1217 vlm: rxs
   -1  1218 czh: kkz vcn
   -1  1219 jdd: dpv zxs ggj
   -1  1220 jbt: bcn tbp
   -1  1221 lhn: jhq bxt sbg
   -1  1222 vvm: cgx dhh fxl sdn
   -1  1223 jnl: tch rhz zrk ptc
   -1  1224 gkf: mdd
   -1  1225 pdk: rbf cch
   -1  1226 ldb: kpm nkj hbn
   -1  1227 tjk: qgj
   -1  1228 pqm: qkb vvg
   -1  1229 zpk: zjv jrh zxz hnl
   -1  1230 vmt: txl jmq
   -1  1231 xbp: nvr ldf mrf tlc qxs
   -1  1232 zhj: pxs ndz
   -1  1233 fdf: jnd pft hfk
   -1  1234 lqn: gfj vtv
   -1  1235 fqx: rpf crr psq tlj
   -1  1236 kfg: dcq xcd qpg xml
   -1  1237 tgl: mhz bpf mjr
   -1  1238 xrr: jnt jhm tlx
   -1  1239 ftx: lhb kqr llh
   -1  1240 ggc: jls mlz
   -1  1241 hvn: fsr qss gjd crb mfn
   -1  1242 qth: nhf
   -1  1243 kbj: mcl hcz rxk
   -1  1244 dcq: hjm
   -1  1245 srl: mdz
   -1  1246 pqj: gcj
   -1  1247 zfg: zxk fsr fzb pxn rdx
   -1  1248 hbs: fjd
   -1  1249 kdb: fss bsd qbx
   -1  1250 gpl: lbm kvv qhh

diff --git a/2023/25/solution.rs b/2023/25/solution.rs

@@ -0,0 +1,123 @@
   -1     1 #[path = "../lib.rs"]
   -1     2 mod lib;
   -1     3 
   -1     4 fn len(x: f32, y: f32) -> f32 {
   -1     5     return (x * x + y * y).sqrt();
   -1     6 }
   -1     7 
   -1     8 fn d(a: (f32, f32), b: (f32, f32)) -> f32 {
   -1     9     return len(a.0 - b.0, a.1 - b.1);
   -1    10 }
   -1    11 
   -1    12 fn parse_input() -> Vec<Vec<bool>> {
   -1    13     let mut names = vec![];
   -1    14     for line in lib::iter_input() {
   -1    15         let (left, right) = line.split_once(": ").unwrap();
   -1    16         names.push(left.to_string());
   -1    17         for r in right.split(" ") {
   -1    18             names.push(r.to_string());
   -1    19         }
   -1    20     }
   -1    21     names.sort();
   -1    22     names.dedup();
   -1    23 
   -1    24     let mut graph = vec![vec![false; names.len()]; names.len()];
   -1    25 
   -1    26     for line in lib::iter_input() {
   -1    27         let (left, right) = line.split_once(": ").unwrap();
   -1    28         let i = names.iter().position(|x| x == left).unwrap();
   -1    29         for r in right.split(" ") {
   -1    30             let j = names.iter().position(|x| x == r).unwrap();
   -1    31             graph[i][j] = true;
   -1    32             graph[j][i] = true;
   -1    33         }
   -1    34     }
   -1    35 
   -1    36     return graph;
   -1    37 }
   -1    38 
   -1    39 fn force(graph: &Vec<Vec<bool>>, rounds: usize) -> Vec<(f32, f32)> {
   -1    40     let n = graph.len();
   -1    41     let mut pos = vec![(0.0, 0.0); n];
   -1    42 
   -1    43     for i in 0..n {
   -1    44         // random start positions would be nice, but I just use mod13 here
   -1    45         pos[i] = (i as f32, (i % 13) as f32);
   -1    46     }
   -1    47 
   -1    48     for r in 0..rounds {
   -1    49         let step = (n as f32) * ((rounds - r) as f32) / 2.0;
   -1    50         for i in 0..n {
   -1    51             let mut x = 0.0;
   -1    52             let mut y = 0.0;
   -1    53             for j in 0..n {
   -1    54                 if i == j {
   -1    55                     continue;
   -1    56                 }
   -1    57                 let dx = pos[i].0 - pos[j].0;
   -1    58                 let dy = pos[i].1 - pos[j].1;
   -1    59                 let d = len(dx, dy);
   -1    60                 if graph[i][j] {
   -1    61                     x -= dx * d;
   -1    62                     y -= dy * d;
   -1    63                 } else {
   -1    64                     x += dx / d / d;
   -1    65                     y += dy / d / d;
   -1    66                 }
   -1    67             }
   -1    68 
   -1    69             let s = step / len(x, y);
   -1    70             pos[i] = (
   -1    71                 pos[i].0 + x * s,
   -1    72                 pos[i].1 + y * s,
   -1    73             );
   -1    74         }
   -1    75     }
   -1    76     return pos;
   -1    77 }
   -1    78 
   -1    79 fn cluster(pos: &Vec<(f32, f32)>, rounds: usize) -> usize {
   -1    80     let x_center = pos.iter().map(|(x, _)| *x).sum::<f32>() / (pos.len() as f32);
   -1    81     let y_center = pos.iter().map(|(_, y)| *y).sum::<f32>() / (pos.len() as f32);
   -1    82 
   -1    83     let mut c1 = (x_center - 1.0, y_center);
   -1    84     let mut c2 = (x_center + 1.0, y_center);
   -1    85     let mut n = 0;
   -1    86 
   -1    87     for _ in 0..rounds {
   -1    88         let mut x1 = 0.0;
   -1    89         let mut y1 = 0.0;
   -1    90         let mut n1 = 0;
   -1    91 
   -1    92         let mut x2 = 0.0;
   -1    93         let mut y2 = 0.0;
   -1    94         let mut n2 = 0;
   -1    95 
   -1    96         for i in 0..pos.len() {
   -1    97             if d(pos[i], c1) < d(pos[i], c2) {
   -1    98                 x1 += pos[i].0;
   -1    99                 y1 += pos[i].1;
   -1   100                 n1 += 1;
   -1   101             } else {
   -1   102                 x2 += pos[i].0;
   -1   103                 y2 += pos[i].1;
   -1   104                 n2 += 1;
   -1   105             }
   -1   106         }
   -1   107 
   -1   108         c1 = (x1 / n1 as f32, y1 / n1 as f32);
   -1   109         c2 = (x2 / n2 as f32, y2 / n2 as f32);
   -1   110         n = n1;
   -1   111     }
   -1   112 
   -1   113     return n;
   -1   114 }
   -1   115 
   -1   116 fn main() {
   -1   117     let graph = parse_input();
   -1   118 
   -1   119     let pos = force(&graph, 20);
   -1   120     let a = cluster(&pos, 4);
   -1   121 
   -1   122     println!("part1: {}", a * (graph.len() - a));
   -1   123 }

diff --git a/2023/25/test.txt b/2023/25/test.txt

@@ -0,0 +1,13 @@
   -1     1 jqt: rhn xhk nvd
   -1     2 rsh: frs pzl lsr
   -1     3 xhk: hfx
   -1     4 cmg: qnr nvd lhk bvb
   -1     5 rhn: xhk bvb hfx
   -1     6 bvb: xhk hfx
   -1     7 pzl: lsr hfx nvd
   -1     8 qnr: nvd
   -1     9 ntq: jqt hfx bvb xhk
   -1    10 nvd: lhk
   -1    11 lsr: lhk
   -1    12 rzs: qnr cmg lsr rsh
   -1    13 frs: qnr lhk lsr