Day 19

5 files changed, 984 insertions, 2 deletions

diff --git a/day19/input.txt b/day19/input.txt
new file mode 100644
index 0000000..19f59bd
--- /dev/null
+++ b/day19/input.txt
@@ -0,0 +1,716 @@
+--- scanner 0 ---
+-750,-798,564
+651,-651,-450
+545,505,-850
+-869,-573,-721
+-709,660,754
+391,436,558
+-748,-884,535
+585,-474,445
+618,-518,-448
+-359,310,-869
+-738,782,655
+-844,-491,-567
+466,-634,434
+-781,741,779
+-548,281,-819
+-118,-133,20
+333,367,668
+-703,-880,673
+-866,-605,-645
+598,462,-782
+491,-507,297
+661,-570,-430
+320,556,635
+35,-32,-97
+586,635,-867
+-505,429,-858
+
+--- scanner 1 ---
+-688,497,-738
+-736,333,556
+-34,-102,60
+899,266,-847
+-589,-867,-501
+-353,-730,750
+554,-550,827
+-544,513,-875
+412,-618,-555
+601,-554,893
+489,-634,884
+345,548,591
+107,-146,-61
+-817,452,649
+-375,-845,-472
+456,523,560
+497,-582,-712
+497,-726,-621
+371,665,577
+-708,421,573
+-422,-772,728
+-461,-860,-632
+916,452,-758
+903,413,-712
+-578,412,-751
+-320,-679,817
+
+--- scanner 2 ---
+-755,771,-873
+795,-789,-587
+-757,-556,-472
+356,668,762
+-674,544,773
+-774,-631,386
+-871,-524,369
+-764,-495,-587
+356,419,-517
+-542,644,722
+798,-659,-466
+775,-589,-655
+348,409,-473
+-651,766,-763
+-614,509,681
+-809,-411,-477
+433,738,802
+367,670,742
+461,491,-397
+330,-730,416
+371,-602,393
+316,-791,401
+-779,810,-674
+30,20,13
+73,161,-128
+-817,-457,306
+
+--- scanner 3 ---
+475,687,613
+-789,-667,-776
+-408,615,477
+361,626,541
+389,607,551
+-432,671,335
+-624,664,-549
+814,-545,509
+-878,-769,-683
+677,-401,493
+411,-714,-849
+-741,596,-555
+382,577,-853
+-710,-272,448
+-384,786,398
+-153,-20,-38
+446,581,-762
+-617,-353,329
+-634,-381,417
+-811,-736,-734
+440,-500,-871
+571,-628,-864
+690,-511,408
+-12,163,-54
+490,528,-953
+-846,694,-591
+
+--- scanner 4 ---
+-282,-582,-356
+620,620,-378
+-602,-935,444
+-535,724,-357
+619,-737,524
+-788,-918,355
+-641,-922,490
+525,-718,-320
+-642,559,451
+514,-610,-391
+-307,691,-321
+491,-648,480
+892,615,-376
+656,707,781
+728,748,646
+40,-142,83
+596,799,746
+-557,669,464
+515,-847,519
+-532,690,-345
+-310,-792,-390
+-541,525,327
+721,540,-352
+-2,18,-27
+520,-685,-414
+-289,-691,-464
+
+--- scanner 5 ---
+714,-889,-824
+673,784,876
+422,795,-383
+608,-740,-842
+642,-627,917
+-786,356,-453
+741,718,936
+-788,835,535
+-705,-542,-599
+-581,-511,-700
+-727,821,550
+494,690,-263
+-727,-540,727
+671,795,896
+-599,780,527
+781,-723,937
+658,-811,-745
+412,803,-339
+-586,376,-521
+-782,-498,602
+107,-26,-19
+791,-586,835
+-591,-606,-587
+-783,-467,844
+-656,353,-332
+
+--- scanner 6 ---
+592,287,416
+-815,-537,678
+736,790,-603
+722,-611,-576
+384,-756,597
+-488,342,441
+674,-689,-539
+-494,777,-709
+-563,392,360
+612,349,555
+-606,415,457
+-388,-899,-684
+-478,-853,-760
+507,-774,644
+433,-829,496
+-569,754,-703
+621,412,400
+660,-693,-713
+-427,-793,-758
+656,816,-502
+25,-53,-54
+-602,848,-698
+-744,-481,519
+-753,-484,730
+731,792,-331
+
+--- scanner 7 ---
+872,-515,828
+-628,-326,528
+892,-408,757
+-696,628,-912
+-371,571,744
+891,348,446
+-430,501,656
+605,-471,-420
+43,59,-71
+507,383,-741
+759,-389,-445
+769,-473,747
+-263,-483,-572
+-582,-320,643
+-753,560,-860
+681,-503,-423
+-779,615,-946
+812,428,432
+944,446,395
+468,531,-784
+457,412,-930
+-365,-620,-562
+-310,541,741
+-692,-387,629
+-283,-579,-711
+
+--- scanner 8 ---
+-541,410,-414
+-552,-711,698
+-667,379,627
+-547,-479,-470
+887,-817,-628
+431,638,502
+455,563,331
+-559,-860,801
+-702,471,567
+835,673,-400
+-525,-712,723
+813,-382,369
+820,-784,-689
+875,-334,379
+457,558,603
+977,-868,-720
+898,682,-555
+-567,430,495
+-642,-355,-495
+100,32,3
+-543,390,-403
+-473,350,-480
+-634,-524,-450
+760,-295,430
+960,702,-416
+
+--- scanner 9 ---
+-6,-74,-15
+-802,-402,585
+862,483,727
+815,560,866
+811,715,-659
+-487,475,954
+886,-758,900
+-714,-329,502
+-665,486,872
+880,862,-685
+-700,-326,-435
+-446,521,913
+-682,-335,-466
+-446,560,-733
+-570,-418,-388
+-356,603,-641
+524,-582,-585
+124,55,128
+808,854,-624
+860,-608,836
+826,-716,841
+597,-563,-445
+-762,-335,673
+818,502,646
+513,-645,-538
+-407,692,-741
+
+--- scanner 10 ---
+-730,451,629
+509,262,-612
+482,-448,630
+-146,-125,10
+549,596,807
+-887,-578,432
+-467,-694,-643
+-450,-653,-773
+540,331,800
+-841,571,-467
+714,-556,-776
+-869,-621,380
+365,-392,703
+-535,-641,-600
+-867,-588,513
+485,432,754
+40,-59,-55
+563,295,-613
+-764,403,721
+419,355,-665
+607,-393,672
+-746,552,602
+-701,689,-435
+-711,588,-567
+804,-571,-733
+785,-446,-785
+
+--- scanner 11 ---
+573,771,590
+-351,-444,-406
+787,-608,759
+-367,529,-638
+-284,-532,-446
+572,-772,-762
+-641,670,340
+692,760,750
+611,874,-762
+-433,-554,689
+654,782,-852
+-278,-361,-494
+-596,532,344
+-318,-676,638
+816,-696,638
+-643,641,426
+526,-813,-721
+537,-731,-543
+743,882,-801
+782,-582,785
+598,908,717
+-324,-625,653
+-275,576,-508
+-284,607,-526
+50,101,-114
+
+--- scanner 12 ---
+-336,-688,765
+-300,617,665
+37,-100,11
+877,-374,-446
+-678,502,-338
+-748,-607,-379
+-298,612,393
+-242,-721,760
+-274,537,564
+630,825,-418
+597,-850,770
+824,796,689
+698,765,-352
+-675,-725,-395
+724,745,557
+859,704,629
+-741,493,-493
+602,-740,666
+949,-494,-341
+558,-651,794
+137,37,-57
+-698,-682,-298
+959,-450,-333
+-313,-613,771
+-803,473,-354
+700,785,-341
+
+--- scanner 13 ---
+631,604,-454
+-817,-695,-605
+516,482,746
+-578,-506,500
+652,-819,595
+-580,-463,625
+-828,-705,-612
+467,687,714
+-595,730,-755
+-827,289,806
+612,-703,584
+656,630,-550
+773,-738,-514
+477,615,742
+755,-933,-584
+-767,670,-691
+-670,734,-677
+-842,-772,-528
+-849,430,853
+-36,-136,9
+717,-709,626
+-886,388,754
+636,667,-472
+742,-939,-546
+-689,-506,668
+
+--- scanner 14 ---
+-592,-933,767
+482,-632,-548
+765,757,448
+884,-705,475
+145,37,99
+-690,290,-569
+-257,630,542
+-747,342,-501
+-789,-755,-638
+902,-748,527
+-359,640,679
+465,-673,-678
+463,272,-353
+550,-685,-505
+37,-116,-30
+687,779,562
+474,418,-472
+513,461,-324
+-773,256,-556
+-350,-934,798
+611,782,530
+-277,491,638
+-770,-880,-690
+-467,-878,725
+-699,-770,-681
+882,-738,608
+
+--- scanner 15 ---
+692,571,-641
+-550,-318,-456
+606,866,858
+589,-298,607
+764,-624,-331
+-362,855,-565
+795,-642,-322
+-732,-647,718
+-719,-363,-448
+545,938,866
+-386,769,754
+571,869,719
+61,141,120
+-779,-523,636
+-391,836,663
+-377,757,506
+-363,830,-538
+785,655,-559
+645,582,-578
+-214,933,-531
+-803,-494,697
+-595,-338,-543
+497,-388,564
+842,-512,-414
+489,-349,696
+
+--- scanner 16 ---
+-587,-696,-689
+-853,-571,522
+-603,275,-878
+478,-988,-677
+-891,-428,509
+586,-665,400
+-793,-498,587
+-616,358,-844
+495,791,-504
+-489,624,724
+25,-61,-5
+527,-707,492
+-548,301,-792
+407,-891,-627
+399,362,697
+509,-574,467
+338,426,596
+-110,-186,101
+329,-970,-571
+-559,683,812
+-481,-759,-794
+591,771,-643
+-529,744,809
+332,472,711
+-596,-675,-741
+632,689,-494
+
+--- scanner 17 ---
+803,419,503
+-562,-391,649
+-722,622,-299
+-735,-476,637
+-670,478,-359
+695,-637,666
+764,-564,737
+659,-370,-384
+510,-452,-395
+-602,863,567
+-723,568,-266
+831,612,465
+-88,55,58
+-692,-408,690
+801,564,-515
+-868,-782,-575
+-559,773,552
+662,-440,-284
+793,793,-501
+740,703,-551
+-900,-642,-693
+736,-528,733
+-550,844,442
+-768,-652,-592
+816,441,530
+
+--- scanner 18 ---
+-635,-572,-319
+-674,846,447
+781,-415,442
+-637,927,422
+-529,-439,981
+700,-425,462
+126,163,109
+611,715,583
+717,-610,-422
+-429,685,-483
+602,753,-378
+877,-491,-433
+844,-585,-285
+492,566,565
+72,37,-13
+604,886,-481
+-674,-440,-311
+-725,-529,-411
+-666,860,402
+-279,674,-361
+584,614,599
+833,-458,460
+581,734,-546
+-376,-418,910
+-445,754,-355
+-500,-500,957
+
+--- scanner 19 ---
+569,-808,-703
+657,-575,870
+613,626,793
+266,851,-626
+688,-817,871
+549,614,679
+-544,640,-403
+344,772,-570
+-650,577,-508
+415,869,-520
+-659,556,-456
+-171,3,86
+-791,-468,707
+-800,-397,817
+432,-910,-693
+-46,56,-61
+644,727,669
+-611,681,697
+-705,779,692
+-611,-420,-405
+-679,-477,-353
+-679,621,739
+-748,-378,692
+528,-890,-554
+-666,-394,-319
+615,-700,815
+
+--- scanner 20 ---
+-697,750,790
+-899,728,-576
+331,654,-560
+-498,726,751
+321,-757,424
+-784,-824,-809
+381,740,805
+-608,622,746
+459,-619,-371
+-784,735,-515
+-185,-102,156
+-716,-804,-609
+570,-451,-371
+-905,-827,-679
+-894,780,-431
+568,-576,-328
+-974,-490,471
+-898,-377,389
+320,661,-570
+306,577,-637
+553,804,865
+478,726,869
+0,73,29
+-854,-385,399
+299,-804,565
+262,-705,523
+
+--- scanner 21 ---
+309,504,-303
+-837,-519,818
+729,456,594
+753,627,669
+-496,-327,-495
+286,-430,713
+424,555,-264
+727,728,589
+-752,664,651
+-674,701,603
+-62,85,-18
+371,494,-351
+-547,773,-334
+-892,-371,892
+-756,838,665
+207,-595,-837
+-515,-412,-495
+297,-503,-786
+-578,715,-411
+-559,583,-342
+364,-564,-753
+-495,-475,-385
+-819,-472,941
+224,-291,733
+349,-275,704
+
+--- scanner 22 ---
+-633,-466,-382
+138,-81,-97
+742,676,309
+603,580,329
+541,-795,-564
+-636,691,-850
+632,-842,350
+634,-831,370
+-612,-619,-311
+533,-750,-395
+-593,743,-832
+894,688,-559
+-32,91,43
+628,-775,-519
+891,656,-635
+-821,451,644
+752,539,411
+869,770,-713
+-551,-590,-335
+-638,-827,719
+-766,-868,696
+-822,420,402
+702,-765,310
+-626,610,-830
+-827,-882,711
+-766,493,519
+
+--- scanner 23 ---
+-463,775,776
+-454,-491,490
+609,830,-740
+-567,770,666
+-444,-627,-483
+-86,3,-74
+840,939,847
+-439,814,577
+773,-464,-788
+693,804,851
+583,-468,404
+654,-557,-869
+654,850,864
+558,-499,293
+-409,-407,380
+-544,548,-870
+593,967,-596
+-347,-520,-466
+-461,-552,375
+-604,513,-778
+-676,648,-819
+-401,-453,-403
+685,-481,-760
+43,103,67
+694,843,-630
+441,-485,319
+
+--- scanner 24 ---
+-409,-442,377
+-312,-646,-887
+-563,401,-581
+704,445,-842
+-540,492,235
+602,-599,-593
+-263,-707,-927
+-345,356,-599
+712,-636,272
+700,-551,-623
+725,286,-877
+478,347,233
+-526,721,243
+-576,631,296
+708,-600,300
+-458,409,-603
+-309,-512,374
+-394,-666,-894
+59,-8,-107
+701,316,-811
+-420,-524,526
+505,369,220
+440,540,205
+641,-709,341
+670,-384,-586
+
+--- scanner 25 ---
+468,-614,-841
+702,666,417
+426,778,-647
+-552,433,-771
+700,637,331
+-706,-796,-512
+334,731,-517
+-633,547,741
+27,-48,-51
+-595,525,-861
+-514,536,581
+460,-783,-796
+655,775,335
+796,-465,724
+-539,399,708
+821,-619,642
+818,-543,610
+343,700,-535
+-666,-346,697
+-684,425,-810
+-709,-328,645
+-699,-348,564
+555,-659,-821
+-624,-843,-636
+-685,-867,-665
diff --git a/day19/main.hs b/day19/main.hs
new file mode 100644
index 0000000..cf01624
--- /dev/null
+++ b/day19/main.hs
@@ -0,0 +1,121 @@
+{-# LANGUAGE TupleSections #-}
+
+module Main where
+
+import Control.Monad (join)
+import Data.Foldable (find)
+import Data.List (deleteBy, nub)
+import Data.Map.Strict (Map)
+import qualified Data.Map.Strict as M
+import Data.Maybe (isJust)
+import Debug.Trace (trace, traceShow)
+import Utils
+
+type Point = (Int, Int, Int)
+
+type Scanner = (Int, [Point])
+
+cmap :: t -> [t -> b] -> [b]
+cmap x = map ($ x)
+
+dot (a, b, c) (d, e, f) = a * d + b * e + c * f
+
+mmulti (a, b, c) v = (dot a v, dot b v, dot c v)
+
+transforms v =
+  let x = mmulti ((1, 0, 0), (0, 0, -1), (0, 1, 0))
+      y = mmulti ((0, 0, 1), (0, 1, 0), (-1, 0, 0))
+      z = mmulti ((0, -1, 0), (1, 0, 0), (0, 0, 1))
+   in cmap
+        v
+        [ id,
+          x,
+          y,
+          z,
+          x . x,
+          x . y,
+          x . z,
+          y . x,
+          y . y,
+          z . y,
+          z . z,
+          x . x . x,
+          x . x . y,
+          x . x . z,
+          x . y . x,
+          x . y . y,
+          x . z . z,
+          y . x . x,
+          y . y . y,
+          z . z . z,
+          x . x . x . y,
+          x . x . y . x,
+          x . y . x . x,
+          x . y . y . y
+        ]
+
+transformBeacons :: [Point] -> [[Point]]
+transformBeacons beacons =
+  beacons $> map transforms .> transpose
+
+checkAssumedMatch beacons1 beacons2 (b1, b2) =
+  let delta = calculateDelta b1 b2
+      translatedBeacons2 = translateBeacons delta beacons2
+      matchingCommonBeacons = translatedBeacons2 $> filter (`elem` beacons1)
+   in if length matchingCommonBeacons >= 12
+        then Just (translatedBeacons2, delta)
+        else Nothing
+
+checkCompositeAndScannerTf :: Scanner -> Scanner -> Maybe (Int, [Point], Point)
+checkCompositeAndScannerTf (s1, beacons1) (s2, beacons2) =
+  let pairings = [(b1, b2) | b1 <- beacons1, b2 <- beacons2]
+      found = map (checkAssumedMatch beacons1 beacons2) pairings $> find isJust .> join
+      -- if found
+      composite = concat .> nub
+   in case found of
+        Just (newBeacons2, newScannerPos) -> Just (s2, composite [beacons1, newBeacons2], newScannerPos)
+        Nothing -> Nothing
+
+manhattanD (x, y, z) (x', y', z') = abs (x - x') + abs (y - y') + abs (z - z')
+
+calculateDelta :: Point -> Point -> Point
+calculateDelta (x, y, z) (x', y', z') = (x - x', y - y', z - z')
+
+translateBeacons :: Point -> [Point] -> [Point]
+translateBeacons (dx, dy, dz) =
+  map (\(x, y, z) -> (x + dx, y + dy, z + dz))
+
+check2CompositeAndScanner :: Scanner -> Scanner -> Maybe (Int, [Point], Point)
+check2CompositeAndScanner scanner1@(s1, beacons1) scanner2@(s2, beacons2) =
+  let beacons2Tfs = transformBeacons beacons2
+      found = beacons2Tfs $> map (\bs -> checkCompositeAndScannerTf scanner1 (s2, bs)) .> find isJust .> join
+   in found
+
+compute _ [] = error "empty scanners list"
+compute scannerPositions [composite] = Just (composite, scannerPositions)
+compute scannerPositions (scanner@(s, _) : others) =
+  let scannerPairs = others $> map (scanner,)
+      found = scannerPairs $> map (uncurry check2CompositeAndScanner) .> find isJust .> join
+   in case found of
+        Just (droppedS, compositeBeacons, newScannerPos) ->
+          let newOthers = filter (fst .> (/=) droppedS) others
+              newComposite = (s, compositeBeacons)
+              newScannerPositions = newScannerPos : scannerPositions
+           in compute newScannerPositions (newComposite : newOthers)
+        Nothing -> compute scannerPositions others
+
+main :: IO ()
+main = do
+  contents <- getContents
+  let scanners =
+        contents
+          $> lines
+          .> splitOn null
+          .> map (drop 1)
+          .> map (map (splitOn (== ',') .> map read .> \[x, y, z] -> (x, y, z)))
+          .> zip [0 ..]
+
+  let Just ((_, resultBeacons), resultScannerPositions) = compute [] scanners
+  length resultBeacons $> print
+  let scannerPairs = [(s1, s2) | s1 <- resultScannerPositions, s2 <- resultScannerPositions, s1 /= s2]
+  scannerPairs $> map (uncurry manhattanD) .> maximum .> print
diff --git a/day19/simple.txt b/day19/simple.txt
new file mode 100644
index 0000000..08c67b1
--- /dev/null
+++ b/day19/simple.txt
@@ -0,0 +1,9 @@
+--- scanner 0 ---
+0,2,0
+4,1,0
+3,3,0
+
+--- scanner 1 ---
+-1,-1,0
+-5,0,0
+-2,1,0
\ No newline at end of file
diff --git a/day19/test.txt b/day19/test.txt
new file mode 100644
index 0000000..4e496e9
--- /dev/null
+++ b/day19/test.txt
@@ -0,0 +1,136 @@
+--- scanner 0 ---
+404,-588,-901
+528,-643,409
+-838,591,734
+390,-675,-793
+-537,-823,-458
+-485,-357,347
+-345,-311,381
+-661,-816,-575
+-876,649,763
+-618,-824,-621
+553,345,-567
+474,580,667
+-447,-329,318
+-584,868,-557
+544,-627,-890
+564,392,-477
+455,729,728
+-892,524,684
+-689,845,-530
+423,-701,434
+7,-33,-71
+630,319,-379
+443,580,662
+-789,900,-551
+459,-707,401
+
+--- scanner 1 ---
+686,422,578
+605,423,415
+515,917,-361
+-336,658,858
+95,138,22
+-476,619,847
+-340,-569,-846
+567,-361,727
+-460,603,-452
+669,-402,600
+729,430,532
+-500,-761,534
+-322,571,750
+-466,-666,-811
+-429,-592,574
+-355,545,-477
+703,-491,-529
+-328,-685,520
+413,935,-424
+-391,539,-444
+586,-435,557
+-364,-763,-893
+807,-499,-711
+755,-354,-619
+553,889,-390
+
+--- scanner 2 ---
+649,640,665
+682,-795,504
+-784,533,-524
+-644,584,-595
+-588,-843,648
+-30,6,44
+-674,560,763
+500,723,-460
+609,671,-379
+-555,-800,653
+-675,-892,-343
+697,-426,-610
+578,704,681
+493,664,-388
+-671,-858,530
+-667,343,800
+571,-461,-707
+-138,-166,112
+-889,563,-600
+646,-828,498
+640,759,510
+-630,509,768
+-681,-892,-333
+673,-379,-804
+-742,-814,-386
+577,-820,562
+
+--- scanner 3 ---
+-589,542,597
+605,-692,669
+-500,565,-823
+-660,373,557
+-458,-679,-417
+-488,449,543
+-626,468,-788
+338,-750,-386
+528,-832,-391
+562,-778,733
+-938,-730,414
+543,643,-506
+-524,371,-870
+407,773,750
+-104,29,83
+378,-903,-323
+-778,-728,485
+426,699,580
+-438,-605,-362
+-469,-447,-387
+509,732,623
+647,635,-688
+-868,-804,481
+614,-800,639
+595,780,-596
+
+--- scanner 4 ---
+727,592,562
+-293,-554,779
+441,611,-461
+-714,465,-776
+-743,427,-804
+-660,-479,-426
+832,-632,460
+927,-485,-438
+408,393,-506
+466,436,-512
+110,16,151
+-258,-428,682
+-393,719,612
+-211,-452,876
+808,-476,-593
+-575,615,604
+-485,667,467
+-680,325,-822
+-627,-443,-432
+872,-547,-609
+833,512,582
+807,604,487
+839,-516,451
+891,-625,532
+-652,-548,-490
+30,-46,-14
diff --git a/utils.hs b/utils.hs
index fb1ea96..e7e0d4b 100644
--- a/utils.hs
+++ b/utils.hs
@@ -8,9 +8,9 @@ import Control.Applicative (ZipList (ZipList, getZipList))
 
 infixr 6 $>
 
-splitOn :: (Char -> Bool) -> String -> [String]
+splitOn :: (a -> Bool) -> [a] -> [[a]]
 splitOn p s = case dropWhile p s of
-  "" -> []
+  [] -> []
   s' -> w : splitOn p s''
     where
       (w, s'') = break p s'