Day 13: Claw Contraption

Class {
	#name : 'Day13Solver',
	#superclass : 'AoCSolver',
	#instVars : [
		'machines'
	],
	#category : 'AoCDay13',
	#package : 'AoCDay13'
}

Day13Solver >> parseRawData [
	machines := ('<n><n>' expandMacros split: rawData) collect: [ :machineString | Day13Machine newFromString: machineString ]
]

Day13Solver >> solvePart1 [
	^ (machines collect: [ :machine | machine tokensToWin]) sum
]

Day13Solver >> solvePart2 [
	^ (machines collect: [ :machine | machine tokensToWinAlt]) sum
]

Class {
	#name : 'Day13Machine',
	#superclass : 'Object',
	#instVars : [
		'aButton',
		'bButton',
		'prizeLocation',
		'prizeLocationAlt'
	],
	#category : 'AoCDay13',
	#package : 'AoCDay13'
}

Day13Machine class >> newFromString: aString [
	| machine re nums |
	machine := self new.
	re := '\d+' asRegex.
	nums := (re matchesIn: aString) collect: #asInteger.
	machine aButton: nums first @ nums second.
	machine bButton: nums third @ nums fourth.
	machine prizeLocation: nums fifth @ nums sixth.
	machine prizeLocationAlt: machine prizeLocation + 10000000000000.
	^ machine
]

Day13Machine >> tokensToWin [
	0 to: 100 do: [ :aPresses |
		0 to: 100 do: [ :bPresses |
			aPresses * aButton + (bPresses * bButton) = prizeLocation ifTrue: [
				^ 3 * aPresses + bPresses ] ] ].
	^ 0
]

Day13Machine >> tokensToWinAlt [
	| l1 l2 result |
	l1 := GLine a: aButton x b: bButton x c: prizeLocationAlt x negated.
	l2 := GLine a: aButton y b: bButton y c: prizeLocationAlt y negated.
	result := (l1 intersectionsWith: l2) first asPoint.
	^ result isIntegerPoint
		  ifTrue: [ 3 * result x + result y ]
		  ifFalse: [ 0 ]
]

import re
from z3 import *

with open('input/13.txt', 'r') as f:
    input = f.read()

machines = [m.split("\n") for m in input.split('\n\n')]
for i, (a, b, prize) in enumerate(machines):
    ax, ay = re.search(r'Button A: X\+(\d+), Y\+(\d+)', a).groups()
    bx, by = re.search(r'Button B: X\+(\d+), Y\+(\d+)', b).groups()
    px, py = re.search(r'Prize: X=(\d+), Y=(\d+)', prize).groups()
    machines[i] = (int(ax), int(ay), int(bx), int(by), int(px), int(py))

def solve(machine, offset=0):
    ax, ay, bx, by, px, py = machine
    a = Int('a')
    b = Int('b')
    o = Optimize()
    o.add(a >= 0, b >= 0)
    o.add(a * ax + b * bx == px + offset)
    o.add(a * ay + b * by == py + offset)
    o.minimize(3 * a + b)
    if o.check() == sat:
        return o.model().eval(3 * a + b).as_long()
    return 0

part_1 = 0
part_2 = 0
for machine in machines:
    part_1 += solve(machine)
    part_2 += solve(machine, 10000000000000)

print("Part 1:", part_1)
print("Part 2:", part_2)

def parse_13(filename='./data/13.in'):
    with open(filename) as file:
        ret = []
        for line in file:
            ret.append(line.strip())
    return ret
parse_13()

import re
def solution_13a(data=None, filename=None):
    if not data:
        lines = parse_13(filename)
    else:
        lines = data
    def get_test_case(a, b, p):
        coords = []
        matches = re.match(r"Button A: X\+([0-9]+), Y\+([0-9]+)", a)
        x = int(matches[1])
        y = int(matches[2])
        coords.append((x, y))
        matches = re.match(r"Button B: X\+([0-9]+), Y\+([0-9]+)", b)
        x = int(matches[1])
        y = int(matches[2])
        coords.append((x, y))
        matches = re.match(r"Prize: X=([0-9]+), Y=([0-9]+)", p)
        x = int(matches[1])
        y = int(matches[2])
        coords.append((x, y))
        return tuple(coords)
    def get_test_cases(lines):
        return [get_test_case(a, b, p) for a, b, p in zip(lines[0::4], lines[1::4], lines[2::4])]
    def get_solution(test_case):
        a, b, p = test_case
        x1, y1 = a
        x2, y2 = b
        x, y = p
        det = x1*y2 - x2*y1
        if det == 0:
            return (None, None)
        m = (y2*x -x2*y)/det
        if m != int(m):
            return (None, None)
        n = (-y1*x + x1*y)/det
        if n != int(n):
            return (None, None)
        return (int(m), int(n))
    def solve_test_case(test_case):
        a, b = get_solution(test_case)
        if a is None or b is None:
            return 0
        else:
            return 3*a + b
    ret = 0
    for test_case in get_test_cases(lines):
        ret += solve_test_case(test_case)
    return ret

Solution works for both parts (just add that ridiculously large number at the appropriate place).

/* Advent of Code 2024
 * Day 13: Claw Contraption
 */

#import "Basic";
#import "File";
#import "String";

Machine :: struct {
    // No reason to define Vector2_Int when we're only using it here. An
    // anonymous struct works just fine.
    button_a, button_b, prize: struct {
        x, y: int;
    };
}

get_token_cost :: (machines: [] Machine, limit_button_presses: bool) -> int {
    tokens := 0;
    for machines {
        // Saves some typing.
        button_a := it.button_a;
        button_b := it.button_b;
        prize := it.prize;

        determinant := button_a.x * button_b.y - button_b.x * button_a.y;

        a_presses := (
            button_b.y * prize.x - button_b.x * prize.y
        ) / determinant;

        b_presses := (
            button_a.x * prize.y - button_a.y * prize.x
        ) / determinant;

        if
            button_a.x * a_presses + button_b.x * b_presses == prize.x
            && button_a.y * a_presses + button_b.y * b_presses == prize.y
            && a_presses > 0 && b_presses > 0
            && (!limit_button_presses || a_presses <= 100 && b_presses <= 100)
        {
            tokens += a_presses * 3 + b_presses;
        }
    }

    return tokens;
}

main :: () {
    input, success := read_entire_file("inputs/day_13.txt");
    assert(success);

    groups := split(input, "\n\n");
    defer array_free(groups);

    machines: [..] Machine;
    defer array_free(machines);

    for groups {
        // Conveniently, this approach means we don't have to worry about the
        // trailing newline at all; it's ignored automatically.
        lines := split(it, "\n");
        defer array_free(lines);

        button_a := split(slice(lines[0], 12, lines[0].count - 12), ", Y+");
        button_b := split(slice(lines[1], 12, lines[1].count - 12), ", Y+");
        prize := split(slice(lines[2], 9, lines[2].count - 9), ", Y=");
        defer array_free(button_a);
        defer array_free(button_b);
        defer array_free(prize);

        array_add(*machines, Machine.{
            .{string_to_int(button_a[0]), string_to_int(button_a[1])},
            .{string_to_int(button_b[0]), string_to_int(button_b[1])},
            .{string_to_int(prize[0]), string_to_int(prize[1])},
        });
    }

    print("Part 1: %\n", get_token_cost(machines, true));

    for *machines {
        it.prize.x += 10000000000000;
        it.prize.y += 10000000000000;
    }

    print("Part 2: %\n", get_token_cost(machines, false));
}