Skip Navigation
Advent Of Code @programming.dev
CameronDev @programming.dev

πŸ¦€ - 2024 DAY 13 SOLUTIONS -πŸ¦€

Day 13: Claw Contraption

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

34 comments

  • I have nothing. I hate Diophantine equations. That is all I have to say today.

    (edit) I came back to it after a 24 hour break. All that nonsense about scoring multiple results really took me in yesterday.

     
        
import 'dart:math';
import 'package:collection/collection.dart';

List<List<Point<int>>> getMachines(List<String> lines) => lines
    .splitBefore((e) => e == '')
    .map((m) => m
        .whereNot((e) => e.isEmpty)
        .map((l) => RegExp(r'(\d+)')
            .allMatches(l)
            .map((m) => int.parse(m.group(0)!))
            .toList())
        .map((pr) => Point(pr.first, pr.last))
        .toList())
    .toList();

bool isInteger(num n) => (n - n.round()).abs() < 0.00001;

int cost(Point a, Point b, Point goal) {
  var resA = (goal.x * b.y - goal.y * b.x) / (a.x * b.y - a.y * b.x);
  var resB = (a.x * goal.y - a.y * goal.x) / (a.x * b.y - a.y * b.x);
  return (isInteger(resA) && isInteger(resB))
      ? resA.round() * 3 + resB.round() * 1
      : 0;
}

int solve(mx, p) => [for (var m in mx) cost(m[0], m[1], m[2] + p)].sum;

const large = Point(10000000000000, 10000000000000);
part1(List<String> lines) => solve(getMachines(lines), Point(0, 0));
part2(List<String> lines) => solve(getMachines(lines), large);

  • Haskell

    Pen and Paper solved these equations for me.

     haskell
        
import Control.Arrow

import qualified Data.Char as Char
import qualified Data.List as List
import qualified Data.Maybe as Maybe


window6 :: [Int] -> [[Int]]
window6 [] = []
window6 is = List.splitAt 6 
        >>> second window6
        >>> uncurry (:)
        $ is

parse :: String -> [[Int]]
parse s = window6 . map read . words . List.filter ((Char.isDigit &&& Char.isSpace) >>> uncurry (||)) $ s

solveEquation (ax:ay:bx:by:tx:ty:[]) transformT
        | (aNum `mod` aDenom) /= 0   = Nothing
        | (bNum `mod` bDenom) /= 0   = Nothing
        | otherwise                  = Just (abs $ aNum `div` aDenom, abs $ bNum `div` bDenom)
        where
                tx' = transformT tx
                ty' = transformT ty
                aNum   = (bx*ty')  - (by*tx')
                aDenom = (ax*by)   - (bx*ay)
                bNum   = (ax*ty')  - (ay*tx')
                bDenom = (ax*by)   - (bx*ay)

part1 = map (flip solveEquation id)
        >>> Maybe.catMaybes
        >>> map (first (*3))
        >>> map (uncurry (+))
        >>> sum
part2 = map (flip solveEquation (+ 10000000000000))
        >>> Maybe.catMaybes
        >>> map (first (*3))
        >>> map (uncurry (+))
        >>> sum

main = getContents
        >>= print
        . (part1 &&& part2)
        . parse

    (Edit: coding style)

  • Haskell

    Whee, linear algebra! Converting between numeric types is a bit annoying in Haskell, but I'm reasonably happy with this solution.

     
        
import Control.Monad
import Data.Matrix qualified as M
import Data.Maybe
import Data.Ratio
import Data.Vector qualified as V
import Text.Parsec

type C = (Int, Int)

readInput :: String -> [(C, C, C)]
readInput = either (error . show) id . parse (machine `sepBy` newline) ""
  where
    machine = (,,) <$> coords <*> coords <*> coords
    coords =
      (,)
        <$> (manyTill anyChar (string ": X") >> anyChar >> num)
        <*> (string ", Y" >> anyChar >> num)
        <* newline
    num = read <$> many1 digit

presses :: (C, C, C) -> Maybe C
presses ((ax, ay), (bx, by), (px, py)) =
  do
    let m = fromIntegral <$> M.fromLists [[ax, bx], [ay, by]]
    m' <- either (const Nothing) Just $ M.inverse m
    let [a, b] = M.toList $ m' * M.colVector (fromIntegral <$> V.fromList [px, py])
    guard $ denominator a == 1
    guard $ denominator b == 1
    return (numerator a, numerator b)

main = do
  input <- readInput <$> readFile "input13"
  mapM_
    (print . sum . map (\(a, b) -> 3 * a + b) . mapMaybe presses)
    [ input,
      map (\(a, b, (px, py)) -> (a, b, (10000000000000 + px, 10000000000000 + py))) input
    ]

  • Python

    Execution time: ~<1 millisecond (800 microseconds on my machine)

    Good old school linear algebra from middle school. we can solve this really really fast. With minimal changes from part 1!

  • Haskell, 14 ms. The hardest part was the parser today. I somehow thought that the buttons could have negative values in X or Y too, so it's a bit overcomplicated.

     haskell
        
import Text.ParserCombinators.ReadP

int, signedInt :: ReadP Int
int = read <$> (many1 $ choice $ map char ['0' .. '9'])
signedInt = ($) <$> choice [id <$ char '+', negate <$ char '-'] <*> int

machine :: ReadP ((Int, Int), (Int, Int), (Int, Int))
machine = do
    string "Button A: X"
    xa <- signedInt
    string ", Y"
    ya <- signedInt
    string "\nButton B: X"
    xb <- signedInt
    string ", Y"
    yb <- signedInt
    string "\nPrize: X="
    x0 <- int
    string ", Y="
    y0 <- int
    return ((xa, ya), (xb, yb), (x0, y0))

machines :: ReadP [((Int, Int), (Int, Int), (Int, Int))]
machines = sepBy machine (string "\n\n")

calc :: ((Int, Int), (Int, Int), (Int, Int)) -> Maybe (Int, Int)
calc ((ax, ay), (bx, by), (x0, y0)) = case
        ( (x0 * by - y0 * bx) `divMod` (ax * by - ay * bx)
        , (x0 * ay - y0 * ax) `divMod` (bx * ay - by * ax)
        ) of
    ((a, 0), (b, 0)) -> Just (a, b)
    _                -> Nothing

enlarge :: (a, b, (Int, Int)) -> (a, b, (Int, Int))
enlarge (u, v, (x0, y0)) = (u, v, (10000000000000 + x0, 10000000000000 + y0))

solve :: [((Int, Int), (Int, Int), (Int, Int))] -> Int
solve ts = sum
    [ 3 * a + b
    | Just (a, b) <- map calc ts
    ]

main :: IO ()
main = do
    ts <- fst . last . readP_to_S machines <$> getContents
    mapM_ (print . solve) [ts, map enlarge ts]

  • C

    "The cheapest way" "the fewest tokens", that evil chap!

    I'm on a weekend trip and thought to do the puzzle in the 3h train ride but I got silly stumped on 2D line intersection*, was too stubborn to look it up, and fell asleep 🀑

    When I woke up, so did the little nugget of elementary algebra somewhere far in the back of my mind. Tonight I finally got to implementing, which was smooth sailing except for this lesson I learnt:

    int64 friends don't let int64 friends play with float32s.

    *) on two parts:

    1. how can you capture a two-dimensional problem in a linear equation (ans: use slopes), and
    2. what unknown was I supposed to be finding? (ans: either x or y of intersection will do)

    https://github.com/sjmulder/aoc/blob/master/2024/c/day13.c

    • Line intersection is a nice way of looking at it. My immediate thought was "change of basis".

  • Python

    I just threw linear algebra and float64 on this question and it stuck. Initially in order to decrease the numbers a bit (to save precision) I tried to find greatest common divisors for the coordinates of the target but in many cases it was 1, so that was that went down the drain. Luckily float64 was able to achieve precisions up to 1e-4 and that was enough to separate wheat from chaff. So in the end I did not have to use exact formulas for the inverse of the matrix though probably would be a more satisfying solution if I did. 

     
        

import numpy as np
from functools import partial
from pathlib import Path
cwd = Path(__file__).parent

def parse_input(file_path, correction):

  with file_path.open("r") as fp:
    instructions = fp.readlines()

  machine_instructions = []
  for ind in range(0,len(instructions)+1,4):

    mins = instructions[ind:ind+3]
    machine_instructions.append([])
    for i,s in zip(range(3),['+','+','=']):
      machine_instructions[-1].append([int(mins[i].split(',')[0].split(s)[-1]),
                                   int(mins[i].split(',')[1].split(s)[-1])])

    for i in range(2):
      machine_instructions[-1][-1][i] += correction

  return machine_instructions


def solve(threshold, maxn, vectors):

  c = np.array([3, 1])

  M = np.concat([np.array(vectors[0])[:,None],
                 np.array(vectors[1])[:,None]],axis=1).astype(int)

  if np.linalg.det(M)==0:
    return np.nan

  Minv = np.linalg.inv(M)
  nmoves = Minv @ np.array(vectors[2])

  if np.any(np.abs(nmoves - np.round(nmoves))>threshold) or\
    np.any(nmoves>maxn) or np.any(nmoves<0):
      return np.nan

  return np.sum(c * (Minv @ np.array(vectors[2])))


def solve_problem(file_name, correction, maxn, threshold=1e-4):
  # correction 0 or 10000000000000
  # maxn 100 or np.inf

  machine_instructions = parse_input(Path(cwd, file_name), correction)

  _solve = partial(solve, threshold, maxn)

  tokens = list(map(_solve, machine_instructions))

  return int(np.nansum(list(tokens)))

  • C#

     
        
public partial class Day13 : Solver
{
  private record struct Button(int X, int Y);
  private record struct Machine(int X, int Y, Button A, Button B);
  private List<Machine> machines = [];

  [GeneratedRegex(@"^Button (A|B): X\+(\d+), Y\+(\d+)$")]
  private static partial Regex ButtonSpec();

  [GeneratedRegex(@"^Prize: X=(\d+), Y=(\d+)$")]
  private static partial Regex PrizeSpec();

  public void Presolve(string input) {
    var machine_specs = input.Trim().Split("\n\n").ToList();
    foreach (var spec in machine_specs) {
      var lines = spec.Split("\n").ToList();
      if (ButtonSpec().Match(lines[0]) is not { Success: true } button_a_match
        || ButtonSpec().Match(lines[1]) is not { Success: true } button_b_match
        || PrizeSpec().Match(lines[2]) is not { Success:true} prize_match) {
        throw new InvalidDataException($"parse error: ${lines}");
      }
      machines.Add(new Machine(
        int.Parse(prize_match.Groups[1].Value),
        int.Parse(prize_match.Groups[2].Value),
        new Button(int.Parse(button_a_match.Groups[2].Value), int.Parse(button_a_match.Groups[3].Value)),
        new Button(int.Parse(button_b_match.Groups[2].Value), int.Parse(button_b_match.Groups[3].Value))
        ));
    }
  }

  private string Solve(bool unit_conversion) {
    BigInteger total_cost = 0;
    foreach (var machine in machines) {
      long prize_x = machine.X + (unit_conversion ? 10000000000000 : 0);
      long prize_y = machine.Y + (unit_conversion ? 10000000000000 : 0);
      BigInteger det = machine.A.X * machine.B.Y - machine.B.X * machine.A.Y;
      if (det == 0) continue;
      BigInteger det_a = prize_x * machine.B.Y - machine.B.X * prize_y;
      BigInteger det_b = prize_y * machine.A.X - machine.A.Y * prize_x;
      var (a, a_rem) = BigInteger.DivRem(det_a, det);
      var (b, b_rem) = BigInteger.DivRem(det_b, det);
      if (a_rem != 0 || b_rem != 0) continue;
      total_cost += a * 3 + b;
    }
    return total_cost.ToString();
  }

  public string SolveFirst() => Solve(false);
  public string SolveSecond() => Solve(true);
}

  • C#

    Thank goodness for high school algebra!

     
        
using System.Diagnostics;
using Common;

namespace Day13;

static class Program
{
    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var sampleInput = Input.ParseInput("sample.txt");
        var programInput = Input.ParseInput("input.txt");

        Console.WriteLine($"Part 1 sample: {Part1(sampleInput)}");
        Console.WriteLine($"Part 1 input: {Part1(programInput)}");

        Console.WriteLine($"Part 2 sample: {Part2(sampleInput)}");
        Console.WriteLine($"Part 2 input: {Part2(programInput)}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static object Part1(Input i) => i.Machines
        .Select(m => CalculateCoins(m, 100))
        .Where(c => c > 0)
        .Sum();

    static object Part2(Input i) => i.Machines
        .Select(m => m with { Prize = new XYValues(
            m.Prize.X + 10000000000000,
            m.Prize.Y + 10000000000000) })
        .Select(m => CalculateCoins(m, long.MaxValue))
        .Where(c => c > 0)
        .Sum();

    static long CalculateCoins(Machine m, long limit)
    {
        var bBottom = (m.A.X * m.B.Y) - (m.A.Y * m.B.X);
        if (bBottom == 0) return -1;

        var bTop = (m.Prize.Y * m.A.X) - (m.Prize.X * m.A.Y);
        var b = bTop / bBottom;
        if ((b <= 0) || (b > limit)) return -1;
        
        var a = (m.Prize.X - (b * m.B.X)) / m.A.X;
        if ((a <= 0) || (a > limit)) return -1;

        var calcPrizeX = (a * m.A.X) + (b * m.B.X);
        var calcPrizeY = (a * m.A.Y) + (b * m.B.Y);
        if ((m.Prize.X != calcPrizeX) || (m.Prize.Y != calcPrizeY)) return -1;

        return (3 * a) + b;
    }
}

public record struct Machine(XYValues A, XYValues B, XYValues Prize);
public record struct XYValues(long X, long Y);

public class Input
{
    private Input()
    {
    }

    public List<Machine> Machines { get; init; }

    public static Input ParseInput(string file)
    {
        var machines = new List<Machine>();

        var lines = File.ReadAllLines(file);
        for(int l=0; l<lines.Length; l+=4)
        {
            machines.Add(new Machine(
                ParseXYValues(lines[l + 0]),
                ParseXYValues(lines[l + 1]),
                ParseXYValues(lines[l + 2])));
        }

        return new Input()
        {
            Machines = machines,
        };
    }

    private static readonly char[] XYDelimiters = ['X', 'Y', '=', '+', ',', ' '];

    private static XYValues ParseXYValues(string s)
    {
        var parts = s
            .Substring(s.IndexOf(':') + 1)
            .SplitAndTrim(XYDelimiters)
            .Select(long.Parse)
            .ToArray();
        
        return new XYValues(parts[0], parts[1]);
    }
}

  • Rust

    This problem is basically a linear system, which can be solved by inverting the 2x2 matrix of button distances. I put some more detail in the comments.

    Also on github

  • J

    I think this puzzle is a bit of a missed opportunity. They could have provided inputs with no solution or with a line of solutions, so that the cost optimization becomes meaningful. As it is, you just have to carry out Cramer's rule in extended precision rational arithmetic.

     
        
load 'regex'

data_file_name =: '13.data'
raw =: cutopen fread data_file_name
NB. a b sublist y gives elements [a..b) of y
sublist =: ({~(+i.)/)~"1 _
parse_button =: monad define
  match =. 'X\+([[:digit:]]+), Y\+([[:digit:]]+)' rxmatch y
  ". (}. match) sublist y
)
parse_prize =: monad define
  match =. 'X=([[:digit:]]+), Y=([[:digit:]]+)' rxmatch y
  ". (}. match) sublist y
)
parse_machine =: monad define
  3 2 $ (parse_button >0{y), (parse_button >1{y), (parse_prize >2{y)
)
NB. x: converts to extended precision, which gives us rational arithmetic
machines =: x: (parse_machine"1) _3 ]\ raw

NB. A machine is represented by an array 3 2 $ ax ay bx by tx ty, where button
NB. A moves the claw by ax ay, button B by bx by, and the target is at tx ty.
NB. We are looking for nonnegative integer solutions to ax*a + bx*b = tx,
NB. ay*a + by*b = ty; if there is more than one, we want the least by the cost
NB. function 3*a + b.

solution_rank =: monad define
  if. 0 ~: -/ . * }: y do. 0  NB. system is nonsingular
  elseif. */ (=/"1) 2 ]\ ({. % {:) |: y do. 1  NB. one equation is a multiple of the other
  else. _1 end.
)
NB. solve0 yields the cost of solving a machine of solution rank 0
solve0 =: monad define
  d =. -/ . * }: y
  a =. (-/ . * 2 1 { y) % d
  b =. (-/ . * 0 2 { y) % d
  if. (a >: 0) * (a = &lt;. a) * (b >: 0) * (b = &lt;. b) do. b + 3 * a else. 0 end.
)
NB. there are actually no machines of solution rank _1 or 1 in the test set
result1 =: +/ solve0"_1 machines

machines2 =: machines (+"2) 3 2 $ 0 0 0 0 10000000000000 10000000000000
NB. there are no machines of solution rank _1 or 1 in the modified set either
result2 =: +/ solve0"_1 machines2

    • Ooh, Cramer's rule is new to me. That will come in handy if I can remember it next year!

  • Rust

    Hardest part was parsing the input, i somehow forgot how regexes work and wasted hours.

    Learning how to do matrix stuff in rust was a nice detour as well.

     rust
        
#[cfg(test)]
mod tests {
    use nalgebra::{Matrix2, Vector2};
    use regex::Regex;

    fn play_game(ax: i128, ay: i128, bx: i128, by: i128, gx: i128, gy: i128) -> i128 {
        for a_press in 0..100 {
            let rx = gx - ax * a_press;
            let ry = gy - ay * a_press;
            if rx % bx == 0 && ry % by == 0 && rx / bx == ry / by {
                return a_press * 3 + ry / by;
            }
        }
        0
    }

    fn play_game2(ax: i128, ay: i128, bx: i128, by: i128, gx: i128, gy: i128) -> i128 {
        // m * p = g
        // p = m' * g
        // |ax bx|.|a_press| = |gx|
        // |ay by| |b_press|   |gy|
        let m = Matrix2::new(ax as f64, bx as f64, ay as f64, by as f64);
        match m.try_inverse() {
            None => return 0,
            Some(m_inv) => {
                let g = Vector2::new(gx as f64, gy as f64);
                let p = m_inv * g;
                let pa = p[0].round() as i128;
                let pb = p[1].round() as i128;
                if pa * ax + pb * bx == gx && pa * ay + pb * by == gy {
                    return pa * 3 + pb;
                }
            }
        };
        0
    }

    #[test]
    fn day13_part1_test() {
        let input = std::fs::read_to_string("src/input/day_13.txt").unwrap();
        let re = Regex::new(r"[0-9]+").unwrap();

        let games = input
            .trim()
            .split("\n\n")
            .map(|line| {
                re.captures_iter(line)
                    .map(|x| {
                        let first = x.get(0).unwrap().as_str();
                        first.parse::<i128>().unwrap()
                    })
                    .collect::<Vec<i128>>()
            })
            .collect::<Vec<Vec<i128>>>();

        let mut total = 0;
        for game in games {
            let cost = play_game2(game[0], game[1], game[2], game[3], game[4], game[5]);
            total += cost;
        }
        // 36870
        println!("{}", total);
    }

    #[test]
    fn day12_part2_test() {
        let input = std::fs::read_to_string("src/input/day_13.txt").unwrap();
        let re = Regex::new(r"[0-9]+").unwrap();

        let games = input
            .trim()
            .split("\n\n")
            .map(|line| {
                re.captures_iter(line)
                    .map(|x| {
                        let first = x.get(0).unwrap().as_str();
                        first.parse::<i128>().unwrap()
                    })
                    .collect::<Vec<i128>>()
            })
            .collect::<Vec<Vec<i128>>>();

        let mut total = 0;
        for game in games {
            let cost = play_game2(
                game[0],
                game[1],
                game[2],
                game[3],
                game[4] + 10000000000000,
                game[5] + 10000000000000,
            );
            total += cost;
        }
        println!("{}", total);
    }
}

  • Uiua

    Pretty much just a transcription of my Dart solution.

     
        
Data  ← ⊜(⊜(βŠœβ‹•βŠΈβˆˆ"0123456789")βŠΈβ‰ @\n)⊸(Β¬β¦·"\n\n")"Button A: X+94, Y+34\nButton B: X+22, Y+67\nPrize: X=8400, Y=5400\n\nButton A: X+26, Y+66\nButton B: X+67, Y+21\nPrize: X=12748, Y=12176\n\nButton A: X+17, Y+86\nButton B: X+84, Y+37\nPrize: X=7870, Y=6450\n\nButton A: X+69, Y+23\nButton B: X+27, Y+71\nPrize: X=18641, Y=10279"
IsInt ← <0.00001⌡-⁅.
AB    ← Γ·Β°βŠ‚β‰‘(/-Γ—β‡ŒΒ°βŠŸ)⊏[0_1 2_1 0_2]
Cost  ← /+Γ—IsInt.Γ—3_1AB
&p /+≑Cost Data
&p /+≑(Cost⍜(⊑2|+1e13))Data

  • Nim

    I'm embarrasingly bad with math. Couldn't have solved this one without looking up the solution. =C

     nim
        
type Vec2 = tuple[x,y: int64]

const
  PriceA = 3
  PriceB = 1
  ErrorDelta = 10_000_000_000_000

proc isInteger(n: float): bool = n.round().almostEqual(n)
proc `+`(a: Vec2, b: int): Vec2 = (a.x + b, a.y + b)

proc solveEquation(a, b, prize: Vec2): int =
  let res_a = (prize.x*b.y - prize.y*b.x) / (a.x*b.y - a.y*b.x)
  let res_b = (a.x*prize.y - a.y*prize.x) / (a.x*b.y - a.y*b.x)
  if res_a.isInteger and res_b.isInteger:
    res_a.int * PriceA + res_b.int * PriceB
  else: 0

proc solve(input: string): AOCSolution[int, int] =
  let chunks = input.split("\n\n")
  for chunk in chunks:
    let lines = chunk.splitLines()
    let partsA = lines[0].split({' ', ',', '+'})
    let partsB = lines[1].split({' ', ',', '+'})
    let partsC = lines[2].split({' ', ',', '='})

    let a = (parseBiggestInt(partsA[3]), parseBiggestInt(partsA[6]))
    let b = (parseBiggestInt(partsB[3]), parseBiggestInt(partsB[6]))
    let c = (parseBiggestInt(partsC[2]), parseBiggestInt(partsC[5]))

    result.part1 += solveEquation(a,b,c)
    result.part2 += solveEquation(a,b,c+ErrorDelta)

  • I had to borrow some of y'alls code to finish part 2. My approach and all the attempts I did at trying to get the slopes of lines and such couldn't get it high enough.

    I thought to move from the prize along it's furthest away axis until I got to the intersection of the slope of the two buttons.

    I thought that maybe that wasn't the cheapest way, so I fiddled around with the order of button A and B, but still couldn't get it high enough.

    It looks like this group was mostly doing the cross product of the prize to the two buttons. I'm too dumb to realize how that would work. I thought you'd want to move along the furthest away axis first, but maybe it doesn't matter.

    If anyone can see if I did anything obviously wrong, I'd appreciate it. I normally don't like to take code without fixing whatever it is I was doing since it always bites me in the butt later, but here I am.

    F#

34 comments