Day 5 found me tired but awake at midnight at my desk, where I sloppily and groggily wrote a slow, inefficient solution that ran long enough for part 2 that I decided to go to bed rather than wait; luckily the right answer was waiting for me this morning!

I’m going to quickly, quietly do a little clean up here and call it a day.

(ns aoc.2021.day.05
  (:require [clojure.string :as str]
            [hyperfiddle.rcf :as rcf]))

(rcf/enable!)

The problem is straightforward: given a list of line segments which are horizontal, vertical or exactly diagonal, count the number of integer points that are occupied by more than one segment.

(def input "309,347 -> 309,464\n425,687 -> 300,687\n226,766 -> 885,107\n681,618 -> 921,378\n968,54 -> 38,984\n35,341 -> 321,627\n493,485 -> 632,485\n908,183 -> 110,981\n677,378 -> 677,231\n703,378 -> 703,536\n179,581 -> 429,331\n339,133 -> 664,458\n212,680 -> 212,136\n251,699 -> 858,699\n163,725 -> 163,22\n70,226 -> 97,226\n968,119 -> 954,119\n551,551 -> 415,551\n768,167 -> 546,167\n125,302 -> 155,332\n640,201 -> 341,201\n757,791 -> 757,736\n406,570 -> 418,558\n250,919 -> 976,193\n570,362 -> 304,96\n463,973 -> 463,337\n322,199 -> 322,73\n141,186 -> 141,906\n964,940 -> 964,743\n99,461 -> 15,461\n255,856 -> 255,194\n650,293 -> 650,136\n89,98 -> 969,978\n974,977 -> 37,40\n641,795 -> 985,795\n441,972 -> 441,427\n18,942 -> 943,17\n166,167 -> 617,167\n182,146 -> 790,146\n88,854 -> 928,14\n537,38 -> 233,38\n786,562 -> 867,562\n251,102 -> 147,102\n551,373 -> 672,252\n915,713 -> 791,589\n28,373 -> 28,651\n463,365 -> 396,365\n349,948 -> 737,948\n246,860 -> 84,860\n334,817 -> 866,285\n880,958 -> 641,719\n229,203 -> 740,714\n39,220 -> 575,756\n899,383 -> 275,383\n49,952 -> 774,952\n384,42 -> 581,42\n11,731 -> 522,731\n194,638 -> 679,153\n922,279 -> 922,398\n589,579 -> 709,579\n97,716 -> 244,716\n769,923 -> 769,189\n636,567 -> 866,337\n413,925 -> 729,925\n581,524 -> 89,32\n970,217 -> 851,217\n716,373 -> 122,967\n606,785 -> 191,785\n322,432 -> 706,432\n788,911 -> 788,889\n904,917 -> 904,862\n889,351 -> 796,351\n508,18 -> 508,165\n859,187 -> 879,187\n531,409 -> 562,378\n914,97 -> 233,778\n194,191 -> 194,592\n620,674 -> 55,109\n194,973 -> 863,973\n679,940 -> 679,296\n836,108 -> 700,108\n861,376 -> 585,376\n166,299 -> 166,141\n847,377 -> 847,217\n872,972 -> 872,413\n28,872 -> 28,695\n876,152 -> 108,920\n487,536 -> 697,536\n30,28 -> 982,980\n834,503 -> 834,586\n927,459 -> 339,459\n87,809 -> 770,126\n24,973 -> 981,16\n185,383 -> 185,13\n850,328 -> 541,19\n399,111 -> 742,111\n703,305 -> 458,305\n571,889 -> 803,657\n356,697 -> 364,697\n847,160 -> 108,899\n170,954 -> 137,954\n927,120 -> 897,150\n687,662 -> 507,662\n762,259 -> 762,951\n90,612 -> 647,55\n114,437 -> 483,68\n138,269 -> 638,269\n720,947 -> 29,947\n563,52 -> 360,52\n665,953 -> 187,475\n283,855 -> 283,744\n120,284 -> 120,319\n935,422 -> 349,422\n372,858 -> 372,779\n68,768 -> 814,22\n206,400 -> 22,400\n72,954 -> 977,49\n861,557 -> 794,557\n893,654 -> 893,132\n306,364 -> 697,364\n828,165 -> 695,165\n122,57 -> 986,921\n509,470 -> 608,470\n794,730 -> 520,456\n291,305 -> 525,71\n648,530 -> 92,530\n329,173 -> 329,343\n960,941 -> 133,114\n256,523 -> 369,523\n433,379 -> 195,379\n199,783 -> 821,783\n974,205 -> 299,205\n200,400 -> 27,573\n294,175 -> 294,493\n320,20 -> 320,393\n274,85 -> 969,780\n112,73 -> 112,969\n371,381 -> 121,631\n942,906 -> 46,906\n663,742 -> 208,287\n422,258 -> 422,356\n884,283 -> 859,283\n750,142 -> 710,142\n823,454 -> 642,273\n296,366 -> 296,245\n518,615 -> 852,949\n74,513 -> 655,513\n850,77 -> 850,950\n985,980 -> 33,28\n16,982 -> 979,19\n265,234 -> 849,234\n303,408 -> 229,334\n344,63 -> 932,651\n417,597 -> 548,597\n729,361 -> 245,845\n888,156 -> 80,964\n215,29 -> 411,225\n762,108 -> 115,108\n63,855 -> 875,43\n398,382 -> 874,858\n419,78 -> 419,417\n263,553 -> 131,553\n766,399 -> 584,399\n778,126 -> 226,678\n580,781 -> 580,401\n623,506 -> 966,506\n364,723 -> 364,349\n834,667 -> 177,10\n402,515 -> 402,493\n924,50 -> 22,952\n64,826 -> 64,470\n199,694 -> 145,694\n893,900 -> 20,27\n850,834 -> 725,959\n47,573 -> 575,45\n71,287 -> 71,296\n796,728 -> 796,442\n88,700 -> 726,700\n230,332 -> 412,514\n618,284 -> 618,661\n221,738 -> 817,142\n149,38 -> 474,38\n563,331 -> 441,331\n219,187 -> 522,187\n300,341 -> 300,633\n228,305 -> 70,463\n396,875 -> 22,875\n533,116 -> 519,116\n257,781 -> 257,443\n181,236 -> 181,822\n10,13 -> 986,989\n59,290 -> 753,984\n121,89 -> 121,827\n958,233 -> 653,233\n685,641 -> 685,322\n167,124 -> 446,403\n246,170 -> 77,339\n503,189 -> 503,72\n666,182 -> 824,340\n825,675 -> 629,479\n967,915 -> 967,785\n749,403 -> 92,403\n950,217 -> 950,391\n356,872 -> 514,872\n279,900 -> 138,900\n114,284 -> 502,672\n700,792 -> 32,124\n252,783 -> 806,229\n557,215 -> 557,103\n35,29 -> 963,957\n650,285 -> 23,912\n669,191 -> 446,414\n66,283 -> 66,37\n564,250 -> 175,250\n425,611 -> 425,964\n662,224 -> 707,224\n599,979 -> 599,873\n402,886 -> 402,979\n329,181 -> 329,964\n120,891 -> 685,326\n788,438 -> 788,460\n140,939 -> 338,939\n496,343 -> 327,343\n749,151 -> 749,339\n181,527 -> 181,455\n61,949 -> 966,44\n138,262 -> 894,262\n192,146 -> 801,146\n301,405 -> 765,405\n938,235 -> 938,55\n543,958 -> 320,958\n54,982 -> 867,169\n66,147 -> 702,783\n839,419 -> 97,419\n519,879 -> 519,707\n159,255 -> 159,787\n258,897 -> 968,897\n427,10 -> 427,62\n782,750 -> 782,960\n878,742 -> 785,649\n171,74 -> 883,74\n220,184 -> 910,874\n696,984 -> 696,512\n175,753 -> 303,753\n666,515 -> 45,515\n886,101 -> 14,973\n121,823 -> 154,823\n63,976 -> 987,52\n480,478 -> 167,791\n757,338 -> 757,719\n593,286 -> 542,286\n989,602 -> 989,135\n793,857 -> 712,857\n65,976 -> 843,198\n729,334 -> 106,957\n102,234 -> 42,294\n830,223 -> 267,223\n800,590 -> 921,590\n526,38 -> 863,38\n770,719 -> 65,14\n317,267 -> 541,267\n653,697 -> 653,720\n506,532 -> 483,555\n564,387 -> 205,387\n971,669 -> 971,966\n421,905 -> 421,264\n506,85 -> 407,85\n435,863 -> 230,863\n945,133 -> 694,133\n604,921 -> 604,168\n66,677 -> 499,244\n300,551 -> 893,551\n836,228 -> 836,631\n29,208 -> 443,208\n546,584 -> 148,584\n855,904 -> 855,315\n636,694 -> 852,478\n399,252 -> 399,170\n46,596 -> 46,789\n919,211 -> 201,929\n662,983 -> 545,866\n22,913 -> 908,27\n441,605 -> 94,952\n190,257 -> 769,836\n700,395 -> 861,556\n562,620 -> 562,687\n34,165 -> 603,734\n372,302 -> 585,302\n71,857 -> 588,340\n956,566 -> 738,784\n778,610 -> 74,610\n331,640 -> 346,655\n274,473 -> 274,691\n646,142 -> 144,142\n911,971 -> 618,971\n233,341 -> 233,505\n467,990 -> 41,990\n633,739 -> 57,163\n585,405 -> 905,405\n320,449 -> 320,628\n44,738 -> 44,293\n67,267 -> 770,970\n933,155 -> 765,323\n383,879 -> 896,366\n130,986 -> 435,986\n264,863 -> 979,148\n114,721 -> 725,110\n546,949 -> 546,790\n762,42 -> 67,42\n443,985 -> 245,985\n689,803 -> 126,803\n496,702 -> 943,255\n955,963 -> 117,125\n686,411 -> 979,704\n226,256 -> 226,352\n889,683 -> 889,437\n47,161 -> 545,161\n450,283 -> 450,469\n461,338 -> 461,695\n808,777 -> 808,962\n902,459 -> 902,744\n793,703 -> 158,68\n100,919 -> 69,919\n912,785 -> 331,204\n712,609 -> 712,512\n268,762 -> 268,355\n972,667 -> 974,667\n647,647 -> 164,647\n589,180 -> 589,644\n836,258 -> 376,718\n676,977 -> 211,977\n626,608 -> 874,360\n271,911 -> 324,858\n182,374 -> 182,347\n14,989 -> 985,18\n461,462 -> 956,957\n82,79 -> 974,971\n607,478 -> 607,147\n898,76 -> 582,392\n326,31 -> 683,31\n768,47 -> 768,348\n35,386 -> 185,386\n803,391 -> 803,932\n879,486 -> 879,658\n183,39 -> 183,855\n431,467 -> 499,399\n434,306 -> 304,436\n774,618 -> 521,618\n364,426 -> 364,457\n44,849 -> 791,102\n70,850 -> 276,850\n181,838 -> 181,736\n574,18 -> 574,784\n103,613 -> 537,179\n34,218 -> 115,299\n808,777 -> 636,777\n483,112 -> 483,939\n15,790 -> 15,253\n433,427 -> 742,427\n829,947 -> 895,947\n361,180 -> 860,180\n124,499 -> 124,615\n879,712 -> 745,712\n16,12 -> 16,149\n36,981 -> 36,561\n929,52 -> 30,951\n845,85 -> 318,612\n114,731 -> 794,51\n434,280 -> 406,308\n530,513 -> 114,513\n417,715 -> 417,273\n44,845 -> 44,225\n951,122 -> 450,623\n32,707 -> 32,832\n51,58 -> 51,806\n165,305 -> 49,189\n517,221 -> 942,221\n125,233 -> 193,233\n903,180 -> 101,982\n123,303 -> 247,179\n199,174 -> 546,521\n185,860 -> 538,860\n825,751 -> 825,784\n454,720 -> 64,720\n28,10 -> 974,956\n626,760 -> 586,760\n91,234 -> 10,234\n973,939 -> 65,31\n589,308 -> 255,308\n547,945 -> 239,945\n909,914 -> 111,116\n484,182 -> 253,182\n145,575 -> 339,575\n215,143 -> 611,143\n963,983 -> 20,40\n220,733 -> 333,846\n126,860 -> 940,46\n715,823 -> 715,284\n832,65 -> 436,65\n923,496 -> 530,889\n708,517 -> 708,764\n154,681 -> 22,549\n909,135 -> 57,987\n225,966 -> 225,941\n629,491 -> 629,17\n927,349 -> 72,349\n15,987 -> 983,19\n265,912 -> 74,912\n14,985 -> 988,11\n986,64 -> 129,921\n697,831 -> 943,831\n379,143 -> 853,617\n232,887 -> 623,887\n947,473 -> 947,453\n898,762 -> 218,762\n599,386 -> 870,386\n757,137 -> 757,496\n437,285 -> 437,326\n515,311 -> 515,63\n305,703 -> 720,703\n321,770 -> 88,537\n75,48 -> 457,430\n38,499 -> 38,544\n481,896 -> 481,944\n614,483 -> 437,483\n647,430 -> 368,430\n641,669 -> 641,691\n849,626 -> 427,204\n805,688 -> 805,536\n102,315 -> 102,108\n729,525 -> 770,525\n234,702 -> 38,702\n17,457 -> 526,457\n369,155 -> 369,647\n216,118 -> 216,43\n342,384 -> 342,905\n470,832 -> 314,676\n179,318 -> 179,315\n40,707 -> 547,707\n771,236 -> 453,236\n113,823 -> 826,110\n731,642 -> 707,642\n36,398 -> 810,398\n233,447 -> 979,447\n74,286 -> 907,286\n939,223 -> 939,10\n866,57 -> 866,656\n978,20 -> 10,988\n816,176 -> 50,942\n293,868 -> 293,350\n900,159 -> 148,911\n58,84 -> 644,84\n720,416 -> 720,906\n935,31 -> 13,953\n41,727 -> 221,727\n633,112 -> 633,695\n418,947 -> 418,574\n632,711 -> 791,711\n73,228 -> 73,861\n59,447 -> 83,447\n418,938 -> 418,638\n922,352 -> 636,352\n66,773 -> 66,868\n69,678 -> 600,147\n333,251 -> 298,251\n371,803 -> 740,434\n976,972 -> 976,165\n896,415 -> 240,415\n672,476 -> 860,476\n202,291 -> 195,291\n99,971 -> 518,552\n284,858 -> 910,232\n187,282 -> 187,627\n157,445 -> 157,665\n421,879 -> 38,496\n155,431 -> 405,431\n772,472 -> 315,929\n69,818 -> 132,818\n70,328 -> 70,800\n471,788 -> 646,788\n960,900 -> 97,37\n258,566 -> 186,494\n345,413 -> 306,413\n897,173 -> 897,896\n74,740 -> 74,795\n679,238 -> 679,811\n870,64 -> 64,870\n30,869 -> 288,869\n539,380 -> 539,862\n452,692 -> 748,692\n527,712 -> 527,139\n725,504 -> 717,504\n201,338 -> 636,338\n626,719 -> 626,302\n580,153 -> 274,459\n654,215 -> 246,215\n363,738 -> 363,192\n335,502 -> 970,502\n266,52 -> 266,442\n125,127 -> 281,127\n")

(defn parse-line-segments [input]
  (let [parse-line (fn [line]
                     (->> (str/split line #" -> ")
                          (map #(str/split % #","))
                          (map #(map parse-long %))))]
    (map parse-line (str/split-lines input))))

(def line-segs (parse-line-segments input))

(defn horz-or-vert [[[x1 y1] [x2 y2]]]
  (or (= x1 x2) (= y1 y2)))

(defn line-points [[[x1 y1 :as a] [x2 y2 :as b]]]
  "Assumes that the given segment is horizontal, vertical
  or exactly diagonal."
  (let [delta-f (fn [a b] (cond
                            (< a b) inc
                            (> a b) dec
                            :else identity))
        xf (delta-f x1 x2)
        yf (delta-f y1 y2)
        len (fn [a b] (Math/abs (- a b)))
        len (->> (map len a b)
                 (sort)
                 (last))]
    (take (inc len) (map vector (iterate xf x1)
                                (iterate yf y1)))))

(Last night I was generating all points in the square defined by points a and b, and then filtering out those not on the line connecting the points; today I’ve found an algorithm that’s at least sane.)

(defn num-doubly-occupied-points [segs]
  (->> segs
       (mapcat line-points)
       (frequencies)
       (filter (fn [[_ v]] (> v 1)))
       (count)))

(defn part-1 []
  (num-doubly-occupied-points (filter horz-or-vert line-segs)))

(defn part-2 []
  (num-doubly-occupied-points line-segs))


(rcf/tests
  (time (part-1)) := 6113
  (time (part-2)) := 20373)