- commit
- 9257b3fec2a284f608f65bac3a154a95aa4353cb
- parent
- f58867f6b92fd1af57ef316b25f34976966e6d6d
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2025-12-17 12:34
2025-12-10
Diffstat
| A | 2025/10/part1.zig | 116 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2025/10/part2.py | 158 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2025/10/test.txt | 3 | +++ |
3 files changed, 277 insertions, 0 deletions
diff --git a/2025/10/part1.zig b/2025/10/part1.zig
@@ -0,0 +1,116 @@
-1 1 const std = @import("std");
-1 2
-1 3 const Error = error{IndexError};
-1 4
-1 5 const T = u16;
-1 6 const S = 16;
-1 7
-1 8 fn takeBlock(reader: *std.io.Reader) ![]u8 {
-1 9 const line = try reader.peekDelimiterExclusive('\n');
-1 10 if (std.mem.indexOfScalar(u8, line, ' ')) |len| {
-1 11 reader.toss(len + 1);
-1 12 return line[0..len];
-1 13 } else {
-1 14 reader.toss(line.len + 1);
-1 15 return line;
-1 16 }
-1 17 }
-1 18
-1 19 fn nth(t: type, n: usize) t {
-1 20 return @as(t, 1) << @intCast(n);
-1 21 }
-1 22
-1 23 fn parseIndicator(s: []u8) T {
-1 24 var value: T = 0;
-1 25 for (s[1..s.len - 1], 0..) |c, i| {
-1 26 if (c == '#') {
-1 27 value |= nth(T, i);
-1 28 }
-1 29 }
-1 30 return value;
-1 31 }
-1 32
-1 33 fn parseButton(s: []u8) !T {
-1 34 var i: usize = 1;
-1 35 var button: T = 0;
-1 36 while (std.mem.indexOfScalar(u8, s[i..], ',')) |j| {
-1 37 const v = try std.fmt.parseInt(usize, s[i..i+j], 10);
-1 38 button |= nth(T, v);
-1 39 i += j + 1;
-1 40 } else {
-1 41 const v = try std.fmt.parseInt(usize, s[i..s.len-1], 10);
-1 42 button |= nth(T, v);
-1 43 }
-1 44 return button;
-1 45 }
-1 46
-1 47 fn increment(stack: *[S]usize, i: usize, n: usize) bool {
-1 48 if (stack[i] + 1 < n) {
-1 49 stack[i] += 1;
-1 50 return false;
-1 51 } else if (i > 0) {
-1 52 const inc = increment(stack, i - 1, n - 1);
-1 53 stack[i] = stack[i - 1] + 1;
-1 54 return inc;
-1 55 } else {
-1 56 stack[i] = 0;
-1 57 return true;
-1 58 }
-1 59 }
-1 60
-1 61 fn foo(target: T, buttons: []T) usize {
-1 62 var count: usize = 1;
-1 63 var stack = [_]usize{0} ** S;
-1 64 std.debug.assert(buttons.len <= stack.len);
-1 65
-1 66 while (count <= buttons.len) {
-1 67 var v: T = 0;
-1 68 for (0..count) |i| {
-1 69 v ^= buttons[stack[i]];
-1 70 }
-1 71 if (v == target) {
-1 72 return count;
-1 73 }
-1 74
-1 75 if (increment(&stack, count - 1, buttons.len)) {
-1 76 stack[count] = stack[count - 1] + 1;
-1 77 count += 1;
-1 78 }
-1 79 }
-1 80
-1 81 unreachable;
-1 82 }
-1 83
-1 84 pub fn main() !void {
-1 85 const allocator = std.heap.smp_allocator;
-1 86
-1 87 const path: [:0]const u8 = std.mem.span(std.os.argv[1]);
-1 88 var file = try std.fs.cwd().openFile(path, .{});
-1 89 defer file.close();
-1 90
-1 91 var buffer: [1024]u8 = undefined;
-1 92 var reader = file.reader(&buffer);
-1 93
-1 94 var part1: usize = 0;
-1 95
-1 96 var target: T = 0;
-1 97 var buttons = std.ArrayList(T).empty;
-1 98 defer buttons.deinit(allocator);
-1 99
-1 100 while (takeBlock(&reader.interface)) |s| {
-1 101 if (s[0] == '[') {
-1 102 target = parseIndicator(s);
-1 103 buttons.clearRetainingCapacity();
-1 104 } else if (s[0] == '(') {
-1 105 try buttons.append(allocator, try parseButton(s));
-1 106 } else {
-1 107 const count = foo(target, buttons.items);
-1 108 part1 += count;
-1 109 }
-1 110 } else |err| switch (err) {
-1 111 error.EndOfStream => {},
-1 112 else => |e| return e,
-1 113 }
-1 114
-1 115 std.debug.print("part1: {}\n", .{part1});
-1 116 }
diff --git a/2025/10/part2.py b/2025/10/part2.py
@@ -0,0 +1,158 @@
-1 1 import math
-1 2 import sys
-1 3 from fractions import Fraction
-1 4
-1 5
-1 6 def parse_list(s):
-1 7 return [Fraction(int(p, 10)) for p in s[1:-1].split(',')]
-1 8
-1 9
-1 10 def parse_line(line):
-1 11 parts = line.rstrip().split()
-1 12 buttons = [parse_list(part) for part in parts[1:]]
-1 13 target = buttons.pop()
-1 14 return buttons, target
-1 15
-1 16
-1 17 def build_equations(buttons, target):
-1 18 a = []
-1 19 for i in range(len(target)):
-1 20 row = []
-1 21 for j in range(len(buttons)):
-1 22 row.append(Fraction(1 if i in buttons[j] else 0))
-1 23 row.append(target[i])
-1 24 a.append(row)
-1 25 return a
-1 26
-1 27
-1 28 def solve_equations(a):
-1 29 i = 0
-1 30 used = set()
-1 31 fixed = set()
-1 32 while len(used) < len(a) and i + 1 < len(a[0]):
-1 33 # find first non-empty row
-1 34 k = None
-1 35 for j in range(len(a)):
-1 36 if j not in used and a[j][i] != 0:
-1 37 k = j
-1 38 used.add(k)
-1 39 fixed.add(i)
-1 40 break
-1 41
-1 42 if k is not None:
-1 43 for ii in range(i + 1, len(a[0])):
-1 44 a[k][ii] /= a[k][i]
-1 45 a[k][i] = Fraction(1)
-1 46
-1 47 # iterate rows and remove k
-1 48 for j in range(len(a)):
-1 49 if j != k and a[j][i] != 0:
-1 50 for ii in range(i + 1, len(a[0])):
-1 51 a[j][ii] -= a[k][ii] * a[j][i] / a[k][i]
-1 52 a[j][i] = Fraction(0)
-1 53
-1 54 i += 1
-1 55
-1 56 conditions = []
-1 57 not_fixed = sorted(set(range(len(a[0]) - 1)) - fixed)
-1 58 for i in range(len(a[0]) - 1):
-1 59 if i in fixed:
-1 60 for row in a:
-1 61 if row[i] == 1:
-1 62 conditions.append([*[-row[j] for j in not_fixed], row[-1]])
-1 63 break
-1 64 else:
-1 65 conditions.append([
-1 66 *[Fraction(1 if i == j else 0) for j in not_fixed],
-1 67 Fraction(0),
-1 68 ])
-1 69 return conditions
-1 70
-1 71
-1 72 def _get_lower_bound(c, i, lower, upper):
-1 73 bound = -c[-1]
-1 74 for j in range(len(c) - 1):
-1 75 if i == j:
-1 76 continue
-1 77 elif c[j] == 0:
-1 78 continue
-1 79 elif c[j] > 0:
-1 80 bound -= c[j] * upper[j]
-1 81 elif c[j] < 0:
-1 82 bound -= c[j] * lower[j]
-1 83 else:
-1 84 return None
-1 85 return bound / c[i]
-1 86
-1 87
-1 88 def get_bounds(conditions, total):
-1 89 n = len(conditions[0]) - 1
-1 90 lower = [0 for _ in range(n)]
-1 91 upper = [total for _ in range(n)]
-1 92 dirty = True
-1 93 while dirty:
-1 94 dirty = False
-1 95 for c in conditions:
-1 96 for i in range(n):
-1 97 if c[i] > 0:
-1 98 bound = _get_lower_bound(c, i, lower, upper)
-1 99 if bound is not None and bound > lower[i]:
-1 100 lower[i] = math.ceil(bound)
-1 101 dirty = True
-1 102 elif c[i] < 0:
-1 103 bound = _get_lower_bound([-x for x in c], i, upper, lower)
-1 104 if bound is not None and bound < upper[i]:
-1 105 upper[i] = math.floor(bound)
-1 106 dirty = True
-1 107 return lower, upper
-1 108
-1 109
-1 110 def evaluate(c, x):
-1 111 return sum(c[i] * x[i] for i in range(len(x))) + c[-1]
-1 112
-1 113
-1 114 def test(conditions, x):
-1 115 for c in conditions:
-1 116 y = evaluate(c, x)
-1 117 if y.denominator != 1 or y < 0:
-1 118 return False
-1 119 return True
-1 120
-1 121
-1 122 def resolve_conditions(conditions, total):
-1 123 s = [sum(c[i] for c in conditions) for i in range(len(conditions[0]))]
-1 124
-1 125 if all(x == 0 for x in s[:-1]):
-1 126 return s[-1]
-1 127
-1 128 lower, upper = get_bounds(conditions, total)
-1 129
-1 130 best = None
-1 131 x = [v for v in lower]
-1 132 while True:
-1 133 if test(conditions, x):
-1 134 y = evaluate(s, x)
-1 135 if best is None or y < best:
-1 136 best = y
-1 137 upper = [min(y, v) for v in upper]
-1 138
-1 139 for i in reversed(range(len(x))):
-1 140 x[i] += 1
-1 141 if x[i] <= upper[i]:
-1 142 break
-1 143 x[i] = lower[i]
-1 144 else:
-1 145 break
-1 146
-1 147 return best
-1 148
-1 149
-1 150 if __name__ == '__main__':
-1 151 result = 0
-1 152 with open(sys.argv[1]) as fh:
-1 153 for line in fh:
-1 154 buttons, target = parse_line(line)
-1 155 a = build_equations(buttons, target)
-1 156 conditions = solve_equations(a)
-1 157 result += resolve_conditions(conditions, sum(target))
-1 158 print(result)
diff --git a/2025/10/test.txt b/2025/10/test.txt
@@ -0,0 +1,3 @@
-1 1 [.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
-1 2 [...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
-1 3 [.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}