day18.ps (7291B)
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- day18.ps <day18.txt | display 19 20 % [ item_1 ... item_n ] item_0 -> [ item_0 item_1 ... item_n ] 21 /apush { 22 % array new_item 23 exch aload length 1 add array astore 24 } bind def 25 26 /datafile (%stdin) (r) file def 27 /stderr (%stderr) (w) file def 28 29 /data [ 30 { 31 datafile 300 string readline 32 not { pop exit } if 33 % (X,Y,Z) 34 (,) search 35 not { 1.125 pstack quit } if 36 % (Y,Z) (,) (X) 37 cvi exch pop exch 38 % X (Y,Z) 39 (,) search 40 not { 2.125 pstack quit } if 41 % X (Z) (,) (Y) 42 cvi exch pop exch cvi 43 % X Y Z 44 3 array astore 45 % [X Y Z] 46 } loop 47 ] def 48 49 data 0 get aload pop 3 copy 50 data { 51 aload pop 52 % prev-min-x prev-min-y prev-min-z prev-max-x prev-max-y prev-max-z x y z 53 9 8 roll 3 index 54 % prev-min-y prev-min-z prev-max-x prev-max-y prev-max-z x y z prev-min-x x 55 2 copy gt { exch } if pop 56 % prev-min-y prev-min-z prev-max-x prev-max-y prev-max-z x y z min-x 57 9 8 roll 3 index 58 % prev-min-z prev-max-x prev-max-y prev-max-z x y z min-x prev-min-y y 59 2 copy gt { exch } if pop 60 % prev-min-z prev-max-x prev-max-y prev-max-z x y z min-x min-y 61 9 8 roll 3 index 62 % prev-max-x prev-max-y prev-max-z x y z min-x min-y prev-min-z z 63 2 copy gt { exch } if pop 64 % prev-max-x prev-max-y prev-max-z x y z min-x min-y min-z 65 9 8 roll 6 index 66 % prev-max-y prev-max-z x y z min-x min-y min-z prev-max-x x 67 2 copy lt { exch } if pop 68 % prev-max-y prev-max-z x y z min-x min-y min-z max-x 69 9 8 roll 6 index 70 % prev-max-z x y z min-x min-y min-z max-x prev-max-y y 71 2 copy lt { exch } if pop 72 % prev-max-z x y z min-x min-y min-z max-x max-y 73 9 8 roll 6 index 74 % x y z min-x min-y min-z max-x max-y prev-max-z z 75 2 copy lt { exch } if pop 76 % x y z min-x min-y min-z max-x max-y max-z 77 9 6 roll pop pop pop 78 % min-x min-y min-z max-x max-y max-z 79 } forall 80 % min-x min-y min-z max-x max-y max-z 81 /max-z exch 1 add def 82 /max-y exch 1 add def 83 /max-x exch 1 add def 84 /min-z exch 1 sub def 85 /min-y exch 1 sub def 86 /min-x exch 1 sub def 87 88 /x-width max-x min-x sub 1 add def 89 /y-width max-y min-y sub 1 add def 90 /z-width max-z min-z sub 1 add def 91 92 % x y z -> index 93 /xyz-index { 94 min-z sub 95 y-width mul 96 add min-y sub 97 x-width mul 98 add min-x sub 99 } bind def 100 101 % index -> x y z 102 /split-index { 103 % index 104 dup x-width mod min-x add 105 % index x 106 exch x-width idiv 107 % x yz-part 108 dup y-width mod min-y add 109 % x yz-part y 110 exch y-width idiv 111 % x y z-part 112 min-z add 113 % x y z 114 } bind def 115 116 % [x y z] -> index 117 /arr-index { 118 dup length 3 eq not { 3.125 pstack quit } if 119 aload pop 120 xyz-index 121 } bind def 122 123 /data-dict << 124 data { arr-index 1 } forall 125 >> def 126 127 % x y z -> bool 128 /xyz-in-bounds { 129 true 130 % x y z true 131 1 index min-z ge and 132 1 index max-z le and 133 % x y z z-ok? 134 2 index min-y ge and 135 2 index max-y le and 136 % x y z y-and-z-ok? 137 3 index min-x ge and 138 3 index max-x le and 139 % x y z all-ok? 140 4 1 roll pop pop pop 141 } bind def 142 143 % x y z -> bool 144 /xyz-known { 145 % x y z 146 3 copy xyz-in-bounds 147 { xyz-index data-dict exch known } 148 { pop pop pop false } 149 ifelse 150 } bind def 151 152 % x y z dx dy dz -> x+dx y+dy x+dz 153 /xyz-add { 154 % x y z dx dy dz 155 4 3 roll add 156 % x y dx dy z+dz 157 5 1 roll 158 % z+dz x y dx dy 159 3 2 roll add 160 % z+dz x dx y+dy 161 4 1 roll 162 % y+dy z+dz x dx 163 add 3 1 roll 164 % x+dx y+dy z+dz 165 } bind def 166 167 168 /Helvetica 20 selectfont 169 170 171 (First Puzzle: ) 172 72 700 moveto show 173 174 0 data { 175 % acc [x y z] 176 aload pop 177 % acc x y z 178 3 copy 1 0 0 xyz-add xyz-known not { 4 3 roll 1 add 4 1 roll } if 179 3 copy -1 0 0 xyz-add xyz-known not { 4 3 roll 1 add 4 1 roll } if 180 3 copy 0 1 0 xyz-add xyz-known not { 4 3 roll 1 add 4 1 roll } if 181 3 copy 0 -1 0 xyz-add xyz-known not { 4 3 roll 1 add 4 1 roll } if 182 3 copy 0 0 1 xyz-add xyz-known not { 4 3 roll 1 add 4 1 roll } if 183 3 copy 0 0 -1 xyz-add xyz-known not { 4 3 roll 1 add 4 1 roll } if 184 % acc x y z 185 pop pop pop 186 % acc 187 } forall 188 % side-count 189 15 string cvs show 190 191 192 (Second Puzzle: ) 193 72 664 moveto show 194 195 /exterior-dict x-width y-width z-width mul mul dict def 196 min-x 1 max-x { 197 min-y 1 max-y { 198 % x y 199 2 copy min-z xyz-index exterior-dict exch 1 put 200 2 copy max-z xyz-index exterior-dict exch 1 put 201 % x y 202 pop 203 % x 204 } for 205 % x 206 pop 207 } for 208 min-x 1 max-x { 209 min-z 1 max-y { 210 % x y 211 2 copy min-y exch xyz-index exterior-dict exch 1 put 212 2 copy max-y exch xyz-index exterior-dict exch 1 put 213 % x y 214 pop 215 % x 216 } for 217 % x 218 pop 219 } for 220 min-y 1 max-y { 221 min-z 1 max-z { 222 % y z 223 2 copy min-x 3 1 roll xyz-index exterior-dict exch 1 put 224 2 copy max-x 3 1 roll xyz-index exterior-dict exch 1 put 225 % y z 226 pop 227 % y 228 } for 229 % y 230 pop 231 } for 232 233 234 /boundary-dict data length dict def 235 236 % next-todo x y z -> updated-next-todo 237 /update-dicts { 238 % next-todo x y z 239 3 copy xyz-in-bounds 240 { % next-todo x y z 241 xyz-index 242 % next-todo index 243 data-dict 1 index known 244 % next-todo index is-rock? 245 { boundary-dict 1 index 1 put } 246 { exterior-dict 1 index known 247 % next-todo index is-known? 248 not { 249 % next-todo index 250 exterior-dict 1 index 1 put 251 % next-todo index 252 exch 1 index apush exch 253 % updated-next-todo index 254 } if 255 % next-todo index 256 } 257 ifelse 258 % next-todo index 259 pop 260 } 261 { pop pop pop } 262 ifelse 263 } bind def 264 265 [ exterior-dict { pop } forall ] 266 % inital-todo-list 267 { 268 % todo-list 269 dup length 0 eq { exit } if 270 % todo-list 271 [] exch 272 % next-todo todo-list 273 { 274 % next-todo cur-key 275 split-index 276 % next-todo x y z 277 4 3 roll 278 % x y z next-todo 279 4 copy pop 1 0 0 xyz-add update-dicts 280 4 copy pop -1 0 0 xyz-add update-dicts 281 4 copy pop 0 1 0 xyz-add update-dicts 282 4 copy pop 0 -1 0 xyz-add update-dicts 283 4 copy pop 0 0 1 xyz-add update-dicts 284 4 copy pop 0 0 -1 xyz-add update-dicts 285 % x y z next-todo 286 4 1 roll pop pop pop 287 % next-todo 288 } forall 289 % next-todo 290 } loop 291 292 % x y z -> bool 293 /xyz-is-ext { 294 xyz-index exterior-dict exch known 295 } bind def 296 297 0 data { 298 % acc [x y z] 299 aload pop 300 % acc x y z 301 3 copy 1 0 0 xyz-add xyz-is-ext { 4 3 roll 1 add 4 1 roll } if 302 3 copy -1 0 0 xyz-add xyz-is-ext { 4 3 roll 1 add 4 1 roll } if 303 3 copy 0 1 0 xyz-add xyz-is-ext { 4 3 roll 1 add 4 1 roll } if 304 3 copy 0 -1 0 xyz-add xyz-is-ext { 4 3 roll 1 add 4 1 roll } if 305 3 copy 0 0 1 xyz-add xyz-is-ext { 4 3 roll 1 add 4 1 roll } if 306 3 copy 0 0 -1 xyz-add xyz-is-ext { 4 3 roll 1 add 4 1 roll } if 307 % acc x y z 308 pop pop pop 309 % acc 310 } forall 311 % side-count 312 15 string cvs show 313 314 315 showpage 316 quit