2019/notes

   1 Use 'm4 -H $large_prime' (like 65521 or 1048573) for better speed.
   2 Baselines here shown with default hash sizing.
   3
   4
   5 jam
   6 loom
   7 mug
   8 spool of cat6
   9 prime number
  10 food ration
  11 fuel cell
  12 manifold
  13
  14 baselines as of Jan 7:
  15 $ time cat intcode.m4 day2.input day2.m4 | m4
  16 4484226
  17 5696
  18 real    0m9.513s
  19 $ time cat intcode.m4 day5.input day5.m4 | m4
  20 7988899
  21 13758663
  22 real    0m0.012s
  23 $ time cat intcode.m4 day7.input day7.m4 | m4
  24 17790
  25 19384820
  26 real    0m2.567s
  27 $ time cat intcode.m4 day9.input day9.m4 | m4
  28 3340912345
  29 51754
  30 real    0m6.207s
  31 $ time cat intcode.m4 day11.input day11.m4 | m4
  32 2093
  33  XXX    XX XXX  X  X X      XX X  X XXX
  34  X  X    X X  X X X  X       X X  X X  X
  35  XXX     X X  X XX   X       X X  X X  X
  36  X  X    X XXX  X X  X       X X  X XXX
  37  X  X X  X X X  X X  X    X  X X  X X
  38  XXX   XX  X  X X  X XXXX  XX   XX  X
  39 real    0m2.497s
  40 $ time cat intcode.m4 day13.input day13.m4 | m4
  41 180
  42 8777
  43 real    0m8.910s
  44 $ time cat intcode.m4 day15.input day15.m4 | m4
  45 280
  46 400
  47 real    0m2.321s
  48 $ time cat intcode.m4 day17.input day17.m4 | m4
  49 6448
  50 914900
  51 real    0m2.755s
  52 $ time cat intcode.m4 day19.input day19.m4 | m4
  53 220 (90 / 200)
  54 10010825 (134 / 497)
  55 real    0m3.770s
  56 $ time cat intcode.m4 day21.input day21.m4 | m4
  57 19354173
  58 1145849660
  59 real    0m9.052s
  60 $ time cat intcode.m4 day23.input day23.m4 | m4
  61 22151
  62 17001
  63 real    0m32.670s
  64 $ time cat intcode.m4 day25.input day25.m4 | m4
  65 537002052
  66 real    1m1.344s
  67
  68
  69 !jam=28 !spool=1073741856 !manifold=41 !loom=157
  70 mug=35 prime=536870945 food=131106 fuel=102
  71
  72 jam: 28-27                   ->          1
  73 molten lava: 28-28 -> 0
  74 loom: 157-29                 ->       0x80
  75 escape pod: 30-30 -> 0
  76 mug: 35-31                   ->          4
  77 spool of cat6: 1073741856-32 -> 0x40000000
  78 prime number: 536870945-33   -> 0x20000000
  79 food ration: 131106-34       ->    0x20000
  80 giant electromagnet: 35-35 -> 0
  81 photons: 36-36 -> 0
  82 infinite loop: 37-37 -> 0
  83 fuel cell: 102-38            ->       0x40
  84 manifold: 41-39              ->          2
  85
  86 mem2721 starts 0
  87 f2722: called with Addr[1550]537002052, 33, f1702, scratch:1664
  88 2722: 109,5,            save
  89 2724: 1202,-2,1,2721,   mem2721=[sp-2:f1702]
  90 2728: 21207,-4,0,-1,    [sp-1]=[sp-4:Addr]<0
  91 2732: 1206,-1,2739,     if ([sp-1]==0) goto 2739   # Addr=max(0,Addr)
  92 2735: 21102,0,1,-4,     [sp-4]=0*1=0
  93 2739: 22101,0,-4,1,     [sp+1]=0+[sp-4]
  94 2743: 21201,-3,0,2,     [sp+2]=[sp-3:33]+0
  95 2747: 21102,1,1,3,      [sp+3]=1*1=1
  96 2751: 21101,2758,0,0,   [sp]=2758
  97 2755: 1105,1,2763,      call 2763 ([Addr], 33, 1)
  98 2758: 109,-5            pop
  99 2760: 2105,1,0          return
 100
 101 mem1308 starts 0
 102 mem1309 starts 0
 103 f1310: called with [1128:Room]
 104 1310: 109,2,             save
 105 1312: 1201,-1,0,1309,    [1309]=[SP-1:Room]
 106 1316: 1101,0,0,1308,     [1308]=0
 107 1320: 21102,4601,1,1,    [SP+1]=4601:Items
 108 1324: 21101,0,13,2,      [SP+2]=13
 109 1328: 21101,0,4,3,       [SP+3]=4
 110 1332: 21102,1353,1,4,    [SP+4]=1353
 111 1336: 21101,0,1343,0,    [SP]=1343
 112 1340: 1105,1,1130,       call f1130 (Items, 13, 4, f1353)
 113 1343: 21001,1308,0,-1,   [SP-1:Ret]=[1308]
 114 1347: 109,-2,            pop
 115 1349: 2106,0,0,          return
 116
 117 mem1550: CurrentWeight (starts 109)
 118 mem1551: starts 0
 119 mem1552: Delta (starts 99)
 120 f1553: called with scratch:0
 121 1553: 109,2,              save
 122 1555: 1101,0,0,1550,      [1550]=0
 123 1559: 21101,4601,0,1,     [SP+1]=4601:Items
 124 1563: 21101,13,0,2,       [SP+2]=13
 125 1567: 21101,4,0,3,        [SP+3]=4
 126 1571: 21101,0,1664,4,     [SP+4]=f1664
 127 1575: 21102,1582,1,0,     [SP]=1582
 128 1579: 1106,0,1130,        call f1130 (Items, 13, 4, f1664)
 129 1582: 2,2486,1352,1551,   [1551]=[2486]*[1352]
 130 1586: 1101,0,0,1552,      [1552]=0
 131 1590: 21002,1550,1,1,     [SP+1]=[1550]
 132 1594: 21101,0,33,2,       [SP+2]=33
 133 1598: 21102,1,1702,3,     [SP+3]=f1702
 134 1602: 21102,1,1609,0,     [SP]=1609
 135 1606: 1106,0,2722,        call f2722 (CurrentWeight, 33, 1)
 136 1609: 21007,1552,0,-1,    [SP-1]=[1552]<0
 137 1613: 1205,-1,1630,       if (![SP-1]) goto 1630
 138 1616: 20107,0,1552,-1,    [SP-1]=0<[1552]
 139 1620: 1205,-1,1637,       if (![SP-1]) goto 1637
 140 1623: 21102,1,1630,0,     [SP]=f1630
 141 1627: 1106,0,1752,        call f1752 ()
 142 1630: 21101,548,0,1,      [SP+1]=548    # "...heavier"
 143 1634: 1105,1,1641,        goto 1641
 144 1637: 21102,687,1,1,      [SP+1]=687    # "...lighter"
 145 1641: 21101,1648,0,0,     [SP]=1648
 146 1645: 1106,0,1234,        call f1234 (rejection string)
 147 1648: 21101,4457,0,1,     [SP+1]=4457:Checkpoint
 148 1652: 21101,1659,0,0,     [SP]=1659
 149 1656: 1106,0,1424,        call f1424 (Checkpoint)
 150 1659: 109,-2,             pop
 151 1661: 2105,1,0,           return
 152
 153 f1752: called without args
 154 1752: 109,1,              save
 155 1754: 21101,826,0,1,      [SP+1]=826  # "...typing"
 156 1758: 21101,0,1765,0,     [SP]=1765
 157 1762: 1105,1,1234,        call f1234 (str1)
 158 1765: 20101,0,1550,1,     [SP+1]=[1550]
 159 1769: 21102,1776,1,0,     [SP]=1776
 160 1773: 1106,0,2863,        call f2863 (output code)
 161 1776: 21101,0,1090,1,     [SP+1]=1090  # "...keypad"
 162 1780: 21101,0,1787,0,     [SP]=1787
 163 1784: 1106,0,1234,        call f1234 (str2)
 164 1787: 99,                 halt
 165 1788: 1106,0,1787,        goto halt [unreached]
 166 1791: 109,-1,             pop [unreached]
 167 1793: 2106,0,0,           return [unreached]
 168
 169 f1130: called with Addr, Len, Size, Fn, scratch x2
 170
 171 f1664: called with Addr, Index, scratch
 172 1664: 109,4,             save
 173 1666: 21202,-2,-1,-2,    [SP-2:Index]=-[SP-2]
 174 1670: 2101,0,-3,1675,    [1675]=[SP-3:Addr]
 175 1674: 21008,0,-1,-1,     [SP-1]=([1675]==-1)
 176 1678: 1206,-1,1697,      if (![SP-1]) goto 1697  # if not carrying, end
 177 1681: 1201,-3,2,1687,    [1687]=[SP-3]+2
 178 1685: 20101,-27,0,-3,    [SP-3:Ret]=[1687]-27
 179 1689: 22201,-3,-2,-3,    [SP-3:Ret]+=[SP-2]
 180 1693: 2001,1550,-3,1550, [1550]+=[SP-3]          # [1550]+=weight-27-index
 181 1697: 109,-4,            pop
 182 1699: 2105,1,0,          return
 183
 184 f1702:
 185 109,5,21008,1552,0,-1,1206,-1,1747,1201,-3,1901,1717,20102,1,0,-2,1205,-4,1736,20207,-2,1551,-1,1205,-1,1747,1102,-1,1,1552,1106,0,1747,22007,1551,-2,-1,1205,-1,1747,1102,1,1,1552,109,-5,2106,0,0,
 186
 187 Idea for day 18 priority queue:
 188
 189 store open set as string containing " prio prio ... ", plus a set of
 190 macro stacks, one per prio. Adding in sorted order involves pushing
 191 work to head of correct macro stack, then ensuring prio is in string
 192 (index(" prio "), use substr splicing to add if not, perhaps with
 193 binary search to find index to add at for O(log n)). Removing current
 194 is O(1) (first prio from string, first macro from that stack, shrink
 195 string if stack empties). Leave duplicate work in - when visiting
 196 current, check if prio stack popped from still matches node's current
 197 f value (if not, node was revisited through another shorter path in
 198 meantime).  With puzzle input, never use more than 1863 priorities, so
 199 5 chars/prio, and never more than 10k prio string.
 200
 201 Updated baselines Dec 2020
 202 day 2: 7.131
 203 day 5: 0.012
 204 day 7: 2.215
 205 day 9: 5.348
 206 day11: 2.051
 207 day13: 7.521
 208 day15: 2.012
 209 day17: 2.282
 210 day19: 2.473
 211 day21: 7.505
 212 day23:16.689
 213 day25: 1.131
 214 total 56.37