commit 651137afb4b61d305cf3383e273feffef9cc079f (patch)
parent d069807a20826ca4f0382468d2a8ac78b0f5e195
Author: Alex Karle <alex@alexkarle.com>
Date: Mon, 9 Dec 2024 08:40:09 -0500
2024 Add day 9
Diffstat:
| A | 2024/09/1.py | | | 56 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2024/09/2.py | | | 83 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 139 insertions(+), 0 deletions(-)
diff --git a/2024/09/1.py b/2024/09/1.py
@@ -0,0 +1,56 @@
+#!/usr/bin/env python3
+import sys
+
+def expand(dense):
+ fs = []
+ for i in range(len(dense)):
+ if i % 2 == 0:
+ for j in range(int(dense[i])):
+ fs.append(i // 2)
+ else:
+ for j in range(int(dense[i])):
+ fs.append(None)
+ return fs
+
+def pprint(fs):
+ for c in fs:
+ if c is not None:
+ print(c, end="")
+ else:
+ print(".", end="")
+ print("")
+
+def compact(fs):
+ comp = [c for c in fs]
+ l = 0
+ r = len(fs) - 1
+ while l < r:
+ while comp[l] is not None:
+ l += 1
+ while comp[r] is None:
+ r -= 1
+ if l < r:
+ comp[l] = comp[r]
+ comp[r] = None
+ l += 1
+ r -= 1
+
+ return comp
+
+def chksum(fs):
+ tot = 0
+ for i in range(len(fs)):
+ if fs[i] is None:
+ break
+ tot += fs[i] * i
+
+ return tot
+
+if __name__ == '__main__':
+ dense = next(sys.stdin).strip()
+ fs = expand(dense)
+ comp = compact(fs)
+ #pprint(fs)
+ #pprint(compact(fs))
+ print(chksum(comp))
+
diff --git a/2024/09/2.py b/2024/09/2.py
@@ -0,0 +1,83 @@
+#!/usr/bin/env python3
+import sys
+
+def expand(dense):
+ fs = []
+ for i in range(len(dense)):
+ if i % 2 == 0:
+ for j in range(int(dense[i])):
+ fs.append(i // 2)
+ else:
+ for j in range(int(dense[i])):
+ fs.append(None)
+ return fs
+
+def pprint(fs):
+ for c in fs:
+ if c is not None:
+ print(c, end="")
+ else:
+ print(".", end="")
+ print("")
+
+def compact(fs):
+ comp = [c for c in fs]
+
+ # First store the free space to avoid rescanning every time
+ free = {}
+ start = None
+ size = 0
+ for i in range(len(comp)):
+ if comp[i] is not None:
+ if start is not None:
+ free[start] = size
+ start = None
+ size = 0
+ else:
+ if start is None:
+ start = i
+ size += 1
+
+ # work backwards
+ id = comp[-1]
+ end = len(comp) - 1
+ for i in range(len(comp) - 1, -1, -1):
+ if comp[i] == id:
+ # still in file block
+ continue
+ else:
+ if id is not None:
+ # span from i + 1 -> end needs moving
+ start = i + 1
+ size = end - start + 1
+ for f in sorted(free.keys()):
+ if f < start and free[f] >= size:
+ # copy the block
+ for j in range(size):
+ comp[f + j] = comp[start + j]
+ comp[start + j] = None
+ # update our space
+ free[f + size] = free[f] - size
+ del(free[f])
+ break
+ # reset state
+ id = comp[i]
+ end = i
+ return comp
+
+def chksum(fs):
+ tot = 0
+ for i in range(len(fs)):
+ if fs[i] is None:
+ continue
+ tot += fs[i] * i
+
+ return tot
+
+if __name__ == '__main__':
+ dense = next(sys.stdin).strip()
+ fs = expand(dense)
+ comp = compact(fs)
+ # pprint(comp)
+ print(chksum(comp))
+
