day09.nim (4833B)
1 # Copyright (c) 2024, Natacha Porté 2 # 3 # Permission to use, copy, modify, and distribute this software for any 4 # purpose with or without fee is hereby granted, provided that the above 5 # copyright notice and this permission notice appear in all copies. 6 # 7 # THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 8 # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 9 # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 10 # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 11 # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 12 # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 13 # OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 14 15 from std/algorithm import sorted 16 from std/sequtils import concat, filterIt, mapIt 17 18 # Read input file 19 20 let data = stdin.readLine().mapIt(ord(it) - ord('0')) 21 22 # Puzzle 1 23 24 func part(offset, times, id: int): int = 25 (offset * times + (times * (times - 1) div 2)) * id 26 27 func checksum1(d: seq[int]): int = 28 var 29 left = 0 30 right = (len(d) - 1) div 2 31 todo = d[2*right] 32 offset = 0 33 gap = 0 34 result = 0 35 while left < right: 36 if gap == 0: 37 result += part(offset, d[2*left], left) 38 offset += d[2*left] 39 gap = d[2*left+1] 40 left += 1 41 elif todo == 0: 42 right -= 1 43 todo = d[2*right] 44 else: 45 let chunk = min(todo, gap) 46 result += part(offset, chunk, right) 47 offset += chunk 48 gap -= chunk 49 todo -= chunk 50 result += part(offset, todo, right) 51 52 echo "Puzzle 1: ", checksum1(data) 53 54 # Puzzle 2 55 # 5135326805366 is too low 56 # 5105400512454 is too low 57 # 5396427849295 is too low 58 59 type F = tuple 60 id, offset, size: int 61 type G = tuple 62 offset, size: int 63 64 func make_files(d: seq[int]): seq[F] = 65 var acc = d[0] 66 result.add((id: 0, offset: 0, size: d[0])) 67 for i in 1 .. (len(d) - 1) div 2: 68 acc += d[2*i-1] 69 result.add((id: i, offset: acc, size: d[2*i])) 70 acc += d[2*i] 71 72 func make_gaps(d: seq[int]): seq[G] = 73 var acc = 0 74 for i in 0 ..< len(d): 75 if i mod 2 == 1: 76 result.add((offset: acc, size: d[i])) 77 acc += d[i] 78 79 proc add_gap(gaps: seq[G], new_gap: G): seq[G] = 80 for i in 0 ..< len(gaps): 81 if gaps[i].size == 0: 82 continue 83 elif gaps[i].offset + gaps[i].size < new_gap.offset: 84 result.add(gaps[i]) 85 elif gaps[i].offset + gaps[i].size == new_gap.offset: 86 if i+1 < len(gaps) and gaps[i+1].offset == new_gap.offset + new_gap.size: 87 # echo "Double-sided merge" 88 result.add((offset: gaps[i].offset, size: gaps[i].size + new_gap.size + gaps[i+1].size)) 89 return concat(result, gaps[i+2 .. ^1].filterIt(it.size > 0)) 90 else: 91 # echo "Left merge of ", gaps[i], " and ", new_gap 92 result.add((offset: gaps[i].offset, size: gaps[i].size + new_gap.size)) 93 return concat(result, gaps[i+1 .. ^1].filterIt(it.size > 0)) 94 elif gaps[i].offset == new_gap.offset + new_gap.size: 95 # echo "Right merge" 96 result.add((offset: new_gap.offset, size: gaps[i].size + new_gap.size)) 97 return concat(result, gaps[i+1 .. ^1].filterIt(it.size > 0)) 98 else: 99 # echo "Insertion" 100 result.add(gaps[i]) 101 result.add(new_gap) 102 return concat(result, gaps[i+1 .. ^1].filterIt(it.size > 0)) 103 104 proc check_gaps(files: seq[F], gaps: seq[G]): bool = 105 for i in 1 ..< len(gaps): 106 if gaps[i].size < 0: 107 # echo "Negative gap at ", i 108 return false 109 if gaps[i-1].offset + gaps[i-1].size >= gaps[i].offset: 110 # echo "Overlapping gaps ", i-1, " and ", i 111 return false 112 113 for i in 0 ..< len(files): 114 for j in 0 ..< len(gaps): 115 if not (files[i].offset >= gaps[j].offset + gaps[j].size or gaps[j].offset >= files[i].offset + files[i].size): 116 # echo "Overlapping file ", i, " and gap ", j 117 # echo files[i] 118 # echo gaps[j] 119 return false 120 121 return true 122 123 proc checksum2(d: seq[int]): int = 124 var 125 files = make_files(d) 126 gaps = make_gaps(d) 127 # assert check_gaps(files, gaps) 128 for fi in countdown(len(files) - 1, 0): 129 stdout.write "Processing file ", fi, " / ", len(files), " \r" 130 for gi in 0 ..< len(gaps): 131 if gaps[gi].offset > files[fi].offset: 132 break 133 if files[fi].size <= gaps[gi].size: 134 # echo "moving file ", files[fi], " into gap ", gi, ": ", gaps[gi] 135 let freed_offset = files[fi].offset 136 files[fi].offset = gaps[gi].offset 137 gaps[gi].offset += files[fi].size 138 gaps[gi].size -= files[fi].size 139 # echo " updated file:", files[fi] 140 # echo " updated gap:", gaps[gi] 141 gaps = add_gap(gaps, (offset: freed_offset, size: files[fi].size)) 142 # assert check_gaps(files, gaps) 143 break 144 result = 0 145 for f in files: 146 result += part(f.offset, f.size, f.id) 147 148 echo "Puzzle 2: ", checksum2(data), " "