day15.ps (7706B)
1 %!PS 2 % 3 % Copyright (c) 2022, Natacha Porté 4 % 5 % Permission to use, copy, modify, and distribute this software for any 6 % purpose with or without fee is hereby granted, provided that the above 7 % copyright notice and this permission notice appear in all copies. 8 % 9 % THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10 % WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11 % MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12 % ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13 % WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14 % ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15 % OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 % 17 % Usage: 18 % gs -q- -sDEVICE=png16m -o- day15.ps <day15.txt | display 19 20 /datafile (%stdin) (r) file def 21 /stderr (%stderr) (w) file def 22 23 % [ item_1 ... item_n ] item_0 -> [ item_0 item_1 ... item_n ] 24 /apush { 25 % array new_item 26 exch aload length 1 add array astore 27 } bind def 28 29 % [ item_0 ... item_n-1 ] item_n -> [ item_0 item_1 ... item_n ] 30 /aappend { 31 exch aload length 32 % new-item item-0 item-1 ... item-n-1 n 33 dup dup 2 add exch 1 add roll 34 % item-0 item-1 ... item-n-1 n new-item 35 exch 36 % item-0 item-1 ... item-n-1 new-item n 37 1 add array astore 38 } bind def 39 40 % [ item_0 item_1 ... item_n ] -> [ item_1 ... item_n ] item_0 41 /apop { 42 aload length 1 sub array astore exch 43 } bind def 44 45 % min any max any num -> updated-min any updated-max any 46 /update-min-max { 47 % min any max any num 48 4 index 1 index gt 49 % min any max any num min>num? 50 { 5 4 roll pop dup 5 1 roll } if 51 % updated-min any max any num 52 2 index 1 index lt 53 % updated-min any max any num max<num? 54 { 3 2 roll pop dup 3 1 roll } if 55 % updated-min any updated-max any num 56 pop 57 % updated-min any updated-max any 58 } bind def 59 60 % [[S1x S1y B1x B1y] [S2x S2y B2x B2y] ... [Snx Sny Bnx Bny]] 61 /data [ 62 { 63 datafile 200 string readline 64 not { pop exit } if 65 % (Sensor at x=Sx, y=Sy: closest beacon is at x=Bx, y=By) 66 (Sensor at x=) anchorsearch 67 not { pstack quit } if 68 pop 69 % (Sx, y=Sy: closest beacon is at x=Bx, y=By) 70 (, y=) search 71 not { pstack quit } if 72 cvi exch pop exch 73 % Sx (Sy: closest beacon is at x=Bx, y=By) 74 (: closest beacon is at x=) search 75 not { pstack quit } if 76 cvi exch pop exch 77 % Sx Sy (Bx, y=By) 78 (, y=) search 79 not { pstack quit } if 80 cvi exch pop exch cvi 81 % Sx Sy Bx By 82 4 array astore 83 % [Sx Sy Bx By] 84 } loop 85 ] def 86 87 data 0 get 0 get 88 data 0 get 1 get 89 2 copy 90 data { 91 % min-x min-y max-x max-y [Sx Sy Bx By] 92 dup length 4 eq not { 1.125 pstack quit } if 93 aload pop 94 % min-x min-y max-x max-y Sx Sy Bx By 95 8 2 roll 96 % Bx By min-x min-y max-x max-y Sx Sy 97 update-min-max 98 % Bx By min-x min-y max-x max-y Sx 99 update-min-max 100 % Bx By min-x min-y max-x max-y 101 6 4 roll 102 % min-x min-y max-x max-y Bx By 103 update-min-max 104 % min-x min-y max-x max-y Bx 105 update-min-max 106 % min-x min-y max-x max-y 107 } forall 108 /max-y exch def 109 /max-x exch def 110 /min-y exch def 111 /min-x exch def 112 113 % interval-list min-x max-x -> updated-interval-list 114 /add-interval { 115 false 116 [ 117 % interval-list min-x max-x inserted? mark 118 4 1 roll 5 4 roll 119 % mark min-x max-x inserted? interval-list 120 { 121 dup length 2 eq not { 4.125 pstack quit } if 122 aload pop 123 % mark prev-items new-min new-max inserted? cur-min cur-max 124 { %%% 1-iteration loop to use `exit` as a short circuit 125 4 index 1 index 1 add gt 126 % mark prev-items new-min new-max inserted? cur-min cur-max fully-before? 127 { 2 array astore 4 1 roll exit 128 % mark items new-min new-max inserted? 129 } if 130 % mark prev-items new-min new-max inserted? cur-min cur-max 131 3 index 1 add 2 index lt 132 % mark prev-items new-min new-max inserted? cur-min cur-max fully-after? 133 { 2 array astore 134 % mark prev-items new-min new-max inserted? cur-item 135 1 index 136 { 4 1 roll 137 % mark prev-items cur-item new-min new-max inserted? 138 } 139 { 140 3 index 3 index 2 array astore 141 % mark prev-items new-min new-max inserted? cur-item new-item 142 exch 5 2 roll pop true 143 % mark prev-items cur-item new-item new-min new-max inserted? 144 } 145 ifelse 146 exit 147 } if 148 % mark prev-items new-min new-max inserted? cur-min cur-max 149 4 index 2 index gt 150 % mark prev-items new-min new-max inserted? cur-min cur-max new-min>cur-min? 151 { 5 4 roll pop 1 index 5 1 roll } if 152 % mark prev-items merged-min new-max inserted? cur-min cur-max 153 3 index 1 index lt 154 % mark prev-items merged-min new-max inserted? cur-min cur-max new-max<cur-max? 155 { 4 3 roll pop dup 4 1 roll } if 156 % mark prev-items merged-min merged-max inserted? cur-min cur-max 157 pop pop 158 % mark prev-items merged-min merged-max inserted? 159 exit 160 } loop 161 % mark items-so-far new-min new-max inserted? 162 } forall 163 % mark items new-min new-max inserted? 164 { pop pop } 165 { 2 array astore } 166 ifelse 167 % mark items 168 ] 169 } bind def 170 171 172 % data y -> interval-array 173 /interval-list { 174 % data y 175 [] 3 2 roll 176 { 177 % y interval-list [Sx Sy Bx By] 178 dup length 4 eq not { 2.125 pstack quit } if 179 aload pop 180 % y interval-list Sx Sy Bx By 181 2 index 1 index sub abs 182 % y interval-list Sx Sy Bx By delta-y 183 4 index 3 index sub abs add 184 % y interval-list Sx Sy Bx By dist 185 6 index 4 index sub abs 186 % y interval-list Sx Sy Bx By dist abs(Sy-y) 187 2 copy ge 188 { 189 % y interval-list Sx Sy Bx By dist abs(Sy-y) 190 sub 191 % y interval-list Sx Sy Bx By h-dist 192 4 index 1 index 2 copy sub 3 1 roll add 193 % y interval-list Sx Sy Bx By h-dist min-x max-x 194 % 8 index 4 index eq 195 % % y interval-list Sx Sy Bx By h-dist min-x max-x y=By? 196 % { 197 % % y interval-list Sx Sy Bx By h-dist min-x max-x 198 % 2 index 0 eq 199 % { pop pop pop pop pop pop pop } 200 % { % y interval-list Sx Sy Bx By h-dist min-x max-x 201 % 4 index 1 index eq 202 % { 1 sub } 203 % { 4 index 2 index eq 204 % { exch 1 add exch } 205 % { 3.125 pstack quit } 206 % ifelse 207 % } ifelse 208 % % y interval-list Sx Sy Bx By h-dist fixed-min-x fixed-max-x 209 % 7 2 roll pop pop pop pop pop 210 % % y interval-list fixed-min-x fixed-max-x 211 % add-interval 212 % % y updated-interval-list 213 % } ifelse 214 % } 215 % { 216 % y interval-list Sx Sy Bx By h-dist min-x max-x 217 7 2 roll pop pop pop pop pop 218 % y interval-list fixed-min-x fixed-max-x 219 add-interval 220 % y updated-interval-list 221 % } 222 % ifelse 223 % y updated-interval-list 224 } 225 { pop pop pop pop pop pop } 226 ifelse 227 % y updated-interval-list 228 } forall 229 % y final-interval-list 230 exch pop 231 % final-interval-list 232 } bind def 233 234 % data y -> count 235 /position-count { 236 % data y 237 interval-list 238 % interval-array 239 0 exch 240 { 241 % accumulator interval 242 aload pop 243 % accumulator min max 244 exch sub 1 add 245 % accumulator interval-size 246 add 247 } forall 248 % total 249 } bind def 250 251 252 /Helvetica 20 selectfont 253 254 255 (First Puzzle: ) 256 72 700 moveto show 257 data 10 position-count 258 % for my input: data 2000000 position-count 259 15 string cvs show 260 261 262 (Second Puzzle:) 263 72 664 moveto show 264 265 0 1 20 266 % for my input: 0 1 4000000 267 { 268 % y 269 dup data exch 270 % y data y 271 interval-list 272 % y interval-list 273 dup length 2 ge 274 { 0 get 1 get 1 add 275 % y x 276 4000000 mul add 277 % result 278 ( ) show 279 15 string cvs show 280 } 281 { pop pop } 282 ifelse 283 } for 284 285 286 showpage 287 quit