day13.nim (3640B)
1 # Copyright (c) 2024, Natacha Porté 2 # 3 # Permission to use, copy, modify, and distribute this software for any 4 # purpose with or without fee is hereby granted, provided that the above 5 # copyright notice and this permission notice appear in all copies. 6 # 7 # THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 8 # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 9 # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 10 # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 11 # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 12 # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 13 # OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 14 15 from std/math import gcd, lcm 16 from std/sequtils import foldl, map, mapIt, toSeq 17 from std/strutils import parseInt, split 18 19 # Read input file 20 21 type 22 Point = tuple 23 x, y: int 24 Machine = tuple 25 A, B, Prize: Point 26 27 proc process_text(s: seq[string]): seq[Machine] = 28 assert len(s) mod 4 == 3 29 for i in 0 .. len(s) div 4: 30 let p1 = s[4*i].split(", ") 31 let p2 = s[4*i+1].split(", ") 32 let p3 = s[4*i+2].split(", ") 33 assert len(p1) == 2 34 assert len(p2) == 2 35 assert len(p3) == 2 36 assert p1[0][0 .. 11] == "Button A: X+" 37 assert p1[1][0 .. 1] == "Y+" 38 assert p2[0][0 .. 11] == "Button B: X+" 39 assert p2[1][0 .. 1] == "Y+" 40 assert p3[0][0 .. 8] == "Prize: X=" 41 assert p3[1][0 .. 1] == "Y=" 42 result.add((A: (x: parseInt(p1[0][12 .. ^1]), y: parseInt(p1[1][2 .. ^1])), B: (x: parseInt(p2[0][12 .. ^1]), y: parseInt(p2[1][2 .. ^1])), Prize: (x: parseInt(p3[0][9 .. ^1]), y: parseInt(p3[1][2 .. ^1])))) 43 44 let data = process_text(stdin.lines().toSeq()) 45 46 # Puzzle 1 47 48 proc brute_cost(m: Machine): int = 49 result = 0 50 # echo "Machine: ", m 51 for nA in 0 .. 100: 52 for nB in 0 .. 100: 53 # if m.A.x * nA + m.B.x * nB == m.Prize.x: 54 # echo " X (", nA, ", ", nB, ")" 55 # if m.A.y * nA + m.B.y * nB == m.Prize.y: 56 # echo " Y (", nA, ", ", nB, ")" 57 if m.A.x * nA + m.B.x * nB == m.Prize.x and m.A.y * nA + m.B.y * nB == m.Prize.y: 58 if result == 0 or result > 3 * nA + nB: 59 result = 3 * nA + nB 60 61 echo "Puzzle 1: ", data.map(brute_cost).foldl(a + b) 62 63 # Puzzle 2 64 # 957820661643 is too low 65 # 79320801324501 is too low 66 # 79320806751012 is too low 67 68 proc cost(m: Machine): int = 69 # Looking for number of presses kA,kB so that: 70 # {1}: m.Prize.x = kA * m.A.x + kB * m.B.x 71 # {2}: m.Prize.y = kA * m.A.y + kB * m.B.y 72 # Eliminating kB or kA: 73 # {3}: {1} * m.B.y - {2} * m.B.x 74 # m.Prize.x * m.B.y - m.Prize.y * m.B.x 75 # = kA * (m.A.x * m.B.y - m.A.y * m.B.x) 76 # {4}: {2} * m.A.x - {1} * m.A.y 77 # m.Prize.y * m.A.x - m.Prize.x * m.A.y 78 # = kB * (m.A.x * m.B.y - m.A.y * m.B.x) 79 let 80 dividend_A = m.Prize.x * m.B.y - m.Prize.y * m.B.x 81 dividend_B = m.Prize.y * m.A.x - m.Prize.x * m.A.y 82 divisor = m.A.x * m.B.y - m.A.y * m.B.x 83 assert divisor != 0 84 if dividend_A mod divisor != 0 or dividend_B mod divisor != 0: 85 return 0 86 let 87 kA = dividend_A div divisor 88 kB = dividend_B div divisor 89 assert m.Prize.x == kA * m.A.x + kB * m.B.x 90 assert m.Prize.y == kA * m.A.y + kB * m.B.y 91 return 3 * kA + kB 92 93 for m in data: 94 let 95 c1 = brute_cost(m) 96 c2 = cost(m) 97 assert c1 == c2 or c1 == 0 98 99 func make2(m: Machine): Machine = 100 (A: m.A, B: m.B, Prize: (x: m.Prize.x + 10000000000000, y: m.Prize.y + 10000000000000)) 101 102 proc puzzle2(s: seq[Machine]): int = 103 result = 0 104 for i in 0 ..< len(s): 105 result += cost(make2(s[i])) 106 107 echo "Puzzle 2: ", puzzle2(data), " "