From 4f3ce462021b6f55b225e44b144b07090e8b8183 Mon Sep 17 00:00:00 2001 From: Laurent MAZET Date: Fri, 12 Dec 2025 16:44:37 +0100 Subject: [PATCH] day 9 --- day-9.awk | 29 +++ day-9.txt | 496 +++++++++++++++++++++++++++++++++++++++++++++++++ day-9_test.txt | 8 + day-9b.awk | 185 ++++++++++++++++++ 4 files changed, 718 insertions(+) create mode 100644 day-9.awk create mode 100644 day-9.txt create mode 100644 day-9_test.txt create mode 100644 day-9b.awk diff --git a/day-9.awk b/day-9.awk new file mode 100644 index 0000000..b5e154e --- /dev/null +++ b/day-9.awk @@ -0,0 +1,29 @@ +#!/usr/bin/awk -f + +BEGIN { + FS = "," + n = 0 +} + +!/^[0-9,]*$/ { + print "error line", NR, $0 +} + +NF == 2 { + n++ + x[n] = $1 + y[n] = $2 +} + +END { + m = 0 + for (i = 1; i < n; i++) { + for (j = i + 1; j <= n; j++) { + w = (x[i] > x[j]) ? x[i] - x[j] + 1 : x[j] - x[i] + 1 + h = (y[i] > y[j]) ? y[i] - y[j] + 1 : y[j] - y[i] + 1 + a = w * h + if (a > m) m = a + } + } + print m +} diff --git a/day-9.txt b/day-9.txt new file mode 100644 index 0000000..66a39b4 --- /dev/null +++ b/day-9.txt @@ -0,0 +1,496 @@ +97615,50359 +97615,51574 +97880,51574 +97880,52787 +97832,52787 +97832,54045 +98308,54045 +98308,55187 +97455,55187 +97455,56428 +97608,56428 +97608,57577 +97086,57577 +97086,58800 +97054,58800 +97054,60056 +97128,60056 +97128,61283 +97011,61283 +97011,62360 +96295,62360 +96295,63474 +95780,63474 +95780,64718 +95702,64718 +95702,65758 +94990,65758 +94990,67104 +95133,67104 +95133,68247 +94699,68247 +94699,69240 +93917,69240 +93917,70385 +93499,70385 +93499,71581 +93170,71581 +93170,72717 +92702,72717 +92702,73502 +91601,73502 +91601,74745 +91319,74745 +91319,75801 +90706,75801 +90706,76627 +89745,76627 +89745,77961 +89534,77961 +89534,78812 +88622,78812 +88622,79459 +87470,79459 +87470,80349 +86652,80349 +86652,81297 +85905,81297 +85905,82410 +85333,82410 +85333,83641 +84859,83641 +84859,84224 +83712,84224 +83712,85182 +82941,85182 +82941,85489 +81580,85489 +81580,86273 +80667,86273 +80667,87660 +80237,87660 +80237,87896 +78879,87896 +78879,88858 +78085,88858 +78085,89421 +76998,89421 +76998,90264 +76103,90264 +76103,90831 +75024,90831 +75024,91515 +74018,91515 +74018,92447 +73143,92447 +73143,92488 +71787,92488 +71787,93692 +71024,93692 +71024,93312 +69506,93312 +69506,94350 +68637,94350 +68637,94479 +67379,94479 +67379,95144 +66333,95144 +66333,95471 +65160,95471 +65160,96293 +64141,96293 +64141,96243 +62855,96243 +62855,96580 +61686,96580 +61686,97010 +60535,97010 +60535,97390 +59366,97390 +59366,96985 +58055,96985 +58055,97125 +56855,97125 +56855,97277 +55659,97277 +55659,97593 +54477,97593 +54477,97412 +53250,97412 +53250,98188 +52079,98188 +52079,97850 +50851,97850 +50851,97591 +49640,97591 +49640,97613 +48433,97613 +48433,97478 +47232,97478 +47232,97959 +45983,97959 +45983,98122 +44739,98122 +44739,97901 +43531,97901 +43531,97758 +42314,97758 +42314,96719 +41262,96719 +41262,97232 +39921,97232 +39921,96719 +38786,96719 +38786,96225 +37658,96225 +37658,96045 +36448,96045 +36448,95750 +35265,95750 +35265,95184 +34173,95184 +34173,95280 +32840,95280 +32840,94440 +31858,94440 +31858,93838 +30794,93838 +30794,93113 +29795,93113 +29795,93299 +28353,93299 +28353,92192 +27553,92192 +27553,91710 +26435,91710 +26435,91165 +25347,91165 +25347,90253 +24485,90253 +24485,89978 +23217,89978 +23217,88985 +22426,88985 +22426,88304 +21425,88304 +21425,87446 +20559,87446 +20559,87114 +19267,87114 +19267,86006 +18614,86006 +18614,85364 +17561,85364 +17561,84365 +16835,84365 +16835,83879 +15605,83879 +15605,82741 +15031,82741 +15031,81877 +14176,81877 +14176,81139 +13168,81139 +13168,80122 +12482,80122 +12482,79364 +11466,79364 +11466,77950 +11328,77950 +11328,77269 +10183,77269 +10183,75850 +10124,75850 +10124,75271 +8765,75271 +8765,73896 +8695,73896 +8695,72983 +7845,72983 +7845,72127 +6848,72127 +6848,70848 +6673,70848 +6673,69631 +6410,69631 +6410,68724 +5442,68724 +5442,67546 +5091,67546 +5091,66231 +5138,66231 +5138,65210 +4378,65210 +4378,63906 +4476,63906 +4476,62782 +4019,62782 +4019,61592 +3793,61592 +3793,60572 +2824,60572 +2824,59258 +3156,59258 +3156,58109 +2702,58109 +2702,56905 +2535,56905 +2535,55719 +2221,55719 +2221,54475 +2427,54475 +2427,53302 +1837,53302 +1837,52073 +1940,52073 +1940,50856 +1855,50856 +1855,50338 +94918,50338 +94918,48430 +2294,48430 +2294,47210 +2136,47210 +2136,45974 +1928,45974 +1928,44816 +2583,44816 +2583,43602 +2623,43602 +2623,42452 +3100,42452 +3100,41261 +3276,41261 +3276,39997 +3124,39997 +3124,38711 +2970,38711 +2970,37675 +3839,37675 +3839,36558 +4329,36558 +4329,35324 +4431,35324 +4431,34177 +4825,34177 +4825,32887 +4842,32887 +4842,31903 +5669,31903 +5669,30777 +6123,30777 +6123,29546 +6355,29546 +6355,28756 +7505,28756 +7505,27268 +7271,27268 +7271,26599 +8579,26599 +8579,25471 +9042,25471 +9042,24432 +9662,24432 +9662,23524 +10480,23524 +10480,22341 +10894,22341 +10894,21323 +11559,21323 +11559,20292 +12213,20292 +12213,19289 +12911,19289 +12911,18288 +13619,18288 +13619,17248 +14294,17248 +14294,16628 +15419,16628 +15419,16039 +16548,16039 +16548,15220 +17435,15220 +17435,14383 +18306,14383 +18306,13672 +19286,13672 +19286,12373 +19789,12373 +19789,12150 +21156,12150 +21156,11025 +21831,11025 +21831,10536 +22972,10536 +22972,10037 +24092,10037 +24092,9428 +25134,9428 +25134,8698 +26104,8698 +26104,8188 +27203,8188 +27203,7023 +27961,7023 +27961,6535 +29085,6535 +29085,6343 +30338,6343 +30338,5846 +31445,5846 +31445,5498 +32612,5498 +32612,4868 +33671,4868 +33671,4752 +34914,4752 +34914,4301 +36039,4301 +36039,4224 +37274,4224 +37274,3841 +38419,3841 +38419,2952 +39455,2952 +39455,3029 +40716,3029 +40716,2858 +41917,2858 +41917,2054 +43024,2054 +43024,1940 +44247,1940 +44247,2483 +45530,2483 +45530,1888 +46701,1888 +46701,2338 +47943,2338 +47943,1574 +49138,1574 +49138,2240 +50360,2240 +50360,2185 +51572,2185 +51572,1632 +52818,1632 +52818,1686 +54046,1686 +54046,2670 +55174,2670 +55174,2098 +56468,2098 +56468,3008 +57562,3008 +57562,2737 +58839,2737 +58839,2624 +60108,2624 +60108,3047 +61269,3047 +61269,3156 +62506,3156 +62506,3773 +63605,3773 +63605,3923 +64839,3923 +64839,4634 +65889,4634 +65889,5550 +66844,5550 +66844,5123 +68319,5123 +68319,6288 +69150,6288 +69150,6269 +70494,6269 +70494,7268 +71362,7268 +71362,7673 +72517,7673 +72517,8042 +73704,8042 +73704,8701 +74732,8701 +74732,9408 +75727,9408 +75727,10095 +76733,10095 +76733,10720 +77781,10720 +77781,11483 +78733,11483 +78733,12191 +79725,12191 +79725,13168 +80497,13168 +80497,13986 +81391,13986 +81391,14395 +82658,14395 +82658,15550 +83245,15550 +83245,15992 +84524,15992 +84524,17041 +85200,17041 +85200,18048 +85906,18048 +85906,19035 +86624,19035 +86624,19949 +87426,19949 +87426,21071 +87960,21071 +87960,21864 +88927,21864 +88927,22634 +89956,22634 +89956,24072 +89994,24072 +89994,24882 +90983,24882 +90983,25922 +91617,25922 +91617,26848 +92462,26848 +92462,28215 +92481,28215 +92481,29352 +92908,29352 +92908,30328 +93678,30328 +93678,31384 +94298,31384 +94298,32580 +94581,32580 +94581,33691 +95074,33691 +95074,34845 +95453,34845 +95453,35942 +96018,35942 +96018,37096 +96418,37096 +96418,38437 +96085,38437 +96085,39507 +96817,39507 +96817,40609 +97511,40609 +97511,41939 +97013,41939 +97013,43093 +97474,43093 +97474,44316 +97482,44316 +97482,45474 +98107,45474 +98107,46742 +97503,46742 +97503,47930 +97950,47930 +97950,49140 +98289,49140 +98289,50359 diff --git a/day-9_test.txt b/day-9_test.txt new file mode 100644 index 0000000..c8563ea --- /dev/null +++ b/day-9_test.txt @@ -0,0 +1,8 @@ +7,1 +11,1 +11,7 +9,7 +9,5 +2,5 +2,3 +7,3 diff --git a/day-9b.awk b/day-9b.awk new file mode 100644 index 0000000..e21d3eb --- /dev/null +++ b/day-9b.awk @@ -0,0 +1,185 @@ +#!/usr/bin/awk -f + +BEGIN { + FS = "," + n = 0 + mx = my = 0 +} + +!/^[0-9,]*$/ { + print "error line", NR, $0 +} + +NF == 2 { + n++ + x[n] = $1 + if (mx < $1) mx = $1 + y[n] = $2 + if (my < $2) my = $2 +} + +function nsort(t, r, i, j, k, l) { + l = 0 + delete r + for (i in t) { + m = -1 + for (j = 1; j <= l; j++) { + if (r[j] < t[i]) continue + m = (r[j] > t[i]) ? j : 0 + break + } + if (m == -1) { + r[++l] = t[i] + } else if (m > 0) { + for (j = l; j >= m; j--) r[j + 1] = r[j] + r[m] = t[i] + l++ + } + } + return l +} + +function adisp(n, a) { + if (n) printf "%s", n + for (i in a) printf " %s", a[i] + printf "\n" +} + +function shrink(x, xx, rx, i, j, m) { + m = 0 + for (i in x) { + for (j in xx) { + if (x[i] == xx[j]) { + rx[i] = j * 2 + if (m < rx[i]) m = rx[i] + } + } + } + return m +} + +function draw(b, x, y, i, k, k0, ke, l, lx, ly) { + l = length(x) + lx = x[l] + ly = y[l] + for (i = 1; i <= l; i++) { + if (lx == x[i]) { + if (ly < y[i]) { + k0 = ly + ke = y[i] + } else { + k0 = y[i] + ke = ly + } + for (k = k0; k <= ke; k++) { + b[x[i] "," k] = "X" + } + } else if (ly == y[i]) { + if (lx < x[i]) { + k0 = lx + ke = x[i] + } else { + k0 = x[i] + ke = lx + } + for (k = k0; k <= ke; k++) { + b[k "," y[i]] = "X" + } + } else print "error" + lx = x[i] + ly = y[i] + } +} + +function push(x, v, i) { + for (i in x) if (x[i] == v) return + x[length(x) + 1] = v +} + +function _fill(b, v, c, i, t, x, y) { + while (length(v) > 0) { + delete t + for (i in v) { + if (b[v[i]]) continue + b[v[i]] = "O" + split(v[i], c, ",") + for (x = -1; x <= 1; x++) { + for (y = -1; y <= 1; y++) { + if ((x == 0) && (y == 0)) continue + j = (c[1] + x) "," (c[2] + y) + if (!b[j]) push(t, j) + } + } + } + delete v + for (i in t) v[i] = t[i] + } +} + +function fill (b, n, i, v) { + for (i = 1; i <= n; i++) { + if (b[i "," 3]) break + } + i++ + b[i "," 3] = "O" + v[1] = i+1 "," 3 + v[3] = i "," 4 + v[4] = i+1 "," 4 + _fill(b, v) +} + + +function bdisp(b, n, i, j) { + for (i = 1; i <= n; i++) { + for (j = 1; j <= n; j++) { + printf "%s", (b[i "," j]) ? b[i "," j] : "." + } + printf "\n" + } +} + +END { + print n, mx, my + lx = nsort(x, xx) + ly = nsort(y, yy) + mrx = shrink(x, xx, rx) + mry = shrink(y, yy, ry) + #adisp("rx:", rx) + #adisp("ry:", ry) + draw(b, rx, ry) + bl = (mrx > mry) ? mrx + 1: mry + 1 + fill(b, bl) + #bdisp(b, bl) + a = 0 + for (i = 1; i < n; i++) { + for (j = i + 1; j <= n; j++) { + v = 1 + if (rx[i] < rx[j]) { + rx0 = rx[i] + rxe = rx[j] + } else { + rx0 = rx[j] + rxe = rx[i] + } + if (ry[i] < ry[j]) { + ry0 = ry[i] + rye = ry[j] + } else { + ry0 = ry[j] + rye = ry[i] + } + for (k = rx0; (k <= rxe) && v; k++) { + for (l = ry0; (l <= rye) && v; l++) { + if (!b[k "," l]) v = 0 + } + } + if (!v) continue + w = (x[i] > x[j]) ? x[i] - x[j] + 1 : x[j] - x[i] + 1 + h = (y[i] > y[j]) ? y[i] - y[j] + 1 : y[j] - y[i] + 1 + s = w * h + if (a < s) a = s + } + } + print "max:", a + +} -- 2.30.2