09
https://adventofcode.com/2024/day/9
Prob1
python
import sys
line = sys.stdin.readline().strip()
arr = []
for idx, cnt_str in enumerate(line):
cnt = int(cnt_str)
if idx % 2 == 0:
arr.extend([idx//2]*cnt)
else:
arr.extend([-1]*cnt)
print(arr)
lptr = 0
rptr = len(arr) - 1
while lptr < rptr:
while lptr < rptr and arr[lptr] != -1:
lptr += 1
if lptr >= rptr:
break
while lptr < rptr and arr[rptr] == -1:
rptr -= 1
if lptr >= rptr:
break
arr[lptr] = arr[rptr]
lptr += 1
rptr -= 1
arr = arr[:rptr + 1]
print(arr)
checksum = 0
for idx, x in enumerate(arr):
if x == -1:
continue
checksum += idx*x
print(checksum)Prob2
python
import sys
from typing import List, Tuple
line = sys.stdin.readline().strip()
files: List[Tuple[int, int]] = []
# (l, r)
holes: List[Tuple[int, int]] = []
ptr = 0
for idx, cnt_str in enumerate(line):
cnt = int(cnt_str)
if cnt == 0:
continue
if idx % 2 == 0:
files.append((ptr, ptr + cnt))
else:
#if holes and holes[-1][1] == ptr:
# holes[-1][1] += cnt
#else:
holes.append((ptr, ptr + cnt))
ptr += cnt
for fidx in range(len(files) - 1, -1, -1):
fl, fr = files[fidx]
flen = fr - fl
for hidx, hole in enumerate(holes):
l, r = hole
if l > fl:
continue
if flen > r - l:
continue
holes[hidx] = (l + flen, r)
files[fidx] = (l, l + flen)
break
check_sum = 0
for fidx, file in enumerate(files):
l, r = file
check_sum += fidx*((r-1)*r - (l-1)*l)//2
print(check_sum)