Skip to content

Instantly share code, notes, and snippets.

@carlynorama
Last active December 13, 2024 22:23
Show Gist options
  • Save carlynorama/a362cf61b4003805167924551a007b0e to your computer and use it in GitHub Desktop.
Save carlynorama/a362cf61b4003805167924551a007b0e to your computer and use it in GitHub Desktop.
For advent of code 2024 Day13... there is a simpler way! (code is very messy, apologies)
//https://old.reddit.com/r/adventofcode/comments/1hd4wda/2024_day_13_solutions/m1w6uvc/
//https://old.reddit.com/r/adventofcode/comments/1hd7irq/2024_day_13_an_explanation_of_the_mathematics/
//phrase to search for: Cramer's Rule
//https://math.libretexts.org/Bookshelves/Precalculus/Precalculus_1e_(OpenStax)/09%3A_Systems_of_Equations_and_Inequalities/9.08%3A_Solving_Systems_with_Cramer's_Rule
func solveLinearPair(x1:Int, y1:Int, r1:Int, x2:Int, y2:Int, r2:Int) -> (x:Int, y:Int)? {
let determinant_coeff = (x1 * y2) - (y1 * x2)
if determinant_coeff != 0 {
let determinant_XsAndResults = x1 * r2 - x2 * r1
let ySolution = determinant_XsAndResults.quotientAndRemainder(dividingBy: determinant_coeff)
if ySolution.remainder == 0 {
let xSolution = (r1 - ySolution.quotient * y1).quotientAndRemainder(dividingBy: x1)
if xSolution.remainder == 0 {
return (xSolution.quotient, ySolution.quotient)
}
}
}
return nil
}
struct MatrixSystem {
//Ax = b
//See also the stand alone. It's faster, I suspect.
static func solveLinearPair(x1:Int, y1:Int, r1:Int, x2:Int, y2:Int, r2:Int) -> (x:Int, y:Int)? {
// x1 y1 X r1
// x2 y2 Y r2
let b = Vector2D(x: r1, y: r2)
let A = Matrix2x2(top: Vector2D(x: x1, y: y1), bottom: Vector2D(x: x2, y: y2))
//print(A.pretty, b.pretty)
if let A_inverse = A.inverse() {
let top = (((b.x * A_inverse.topx.0)/A_inverse.topx.1) +
((b.y * A_inverse.topy.0)/A_inverse.topy.1))
let bottom = ((b.x * A_inverse.bottomx.0)/A_inverse.bottomx.1) +
((b.y * A_inverse.bottomy.0)/A_inverse.bottomy.1)
guard (top * x1) + (bottom * y1) == r1 else {
return nil
}
guard (top * x2) + (bottom * y2) == r2 else {
return nil
}
return (top, bottom)
}
return nil
}
struct Vector2D {
let x:Int
let y:Int
var pretty:String {
"(\(x) \(y))"
}
func dotProduct(_ rhs:Vector2D) -> Int {
x*rhs.x + y*rhs.y
}
func mul(_ rhs:Int) -> Self {
Self(x:x*rhs, y:y*rhs)
}
func div(_ rhs:Int) -> Self {
Self(x:x/rhs, y:y/rhs)
}
}
//nice newer one https://www.youtube.com/watch?v=sT9IgHjjhiY
struct Matrix2x2 {
let top:Vector2D
let bottom:Vector2D
var pretty:String {
"[\(top.x) \(top.y) | \(bottom.x) \(bottom.y)]"
}
static var identity:Self {
Matrix2x2(top: Vector2D(x:1, y:0), bottom: Vector2D(x: 0, y: 1))
}
var determinant:Int {
(top.x * bottom.y) - (top.y * bottom.x)
}
var adjugate:Self {
Matrix2x2(top: Vector2D(x: bottom.y, y: -top.y), bottom: Vector2D(x: -bottom.x, y: top.x))
}
//1/(ad-bc) [ (d -b) (-c a) ]
func inverse() -> (topx:(Int,Int), topy:(Int,Int), bottomx:(Int,Int), bottomy:(Int,Int))? {
let d = determinant
if d == 0 { return nil }
let adj = adjugate
return (topx:(adj.top.x,d), topy:(adj.top.y,d), bottomx:(adj.bottom.x,d), bottomy:(adj.bottom.y,d))
}
func mul(by v:Vector2D) -> Vector2D {
Vector2D(x: v.dotProduct(top), y: v.dotProduct(bottom))
}
func div(by n:Int) -> Self {
Matrix2x2(top: top.div(n), bottom: bottom.div(n))
}
func mul(by n:Int) -> Self {
Matrix2x2(top: top.mul(n), bottom: bottom.mul(n))
}
}
}
import UIKit
import Foundation
import Accelerate
import simd
//from datahelpers Solvers.swift
func solveLinearPair(x1:Double, y1:Double, r1:Double, x2:Double, y2:Double, r2:Double) -> SIMD2<Double> {
let a = simd_double2x2(rows: [
simd_double2(x1, y1),
simd_double2(x2, y2)
])
let b = simd_double2(r1, r2)
return simd_mul(a.inverse, b)
}
let pair = solveLinearPair(x1: 1, y1: 1, r1: 35, x2: 2, y2: -1, r2: 25)
print(pair)
//should be 20 and 15
struct ClawMachine {
let Ax:Double
let Ay:Double
let Bx:Double
let By:Double
let Dx:Double
let Dy:Double
func solve() -> simd_double2? {
let determinant =
(Ax * By) - (Bx * Ay)
if determinant != 0 {
return solveLinearPair(x1: Ax, y1: Bx, r1: Dx, x2: Ay, y2: By, r2: Dy)
}
return nil
}
func cost() -> Double? {
if let result = solve() {
guard result.x >= 0 && result.y >= 0 else {
return nil
//fatalError("cant have - button presses \(result)")
}
let xCheck = Int(notExactly: result.x, fuzzBy: 0.001)
let yCheck = Int(notExactly: result.y, fuzzBy: 0.001)
if xCheck != nil && yCheck != nil {
//if (yCheck! + xCheck! <= 100) {
return (result * simd_double2(3, 1)).sum()
//} else {
// return nil
//}
} else {
return nil
}
}
return nil
}
func validatedCost() -> Int? {
//misses some
// Int(exactly: cost())
if let c = cost() {
return Int(notExactly: c, fuzzBy: 0.001)
} else {
return nil
}
}
}
extension Int {
init?(notExactly d:Double, fuzzBy fuzz:Double) {
let dR = d.rounded(.toNearestOrAwayFromZero)
let delta = (d-dR).magnitude
if delta > fuzz {
return nil
} else {
self = Int(dR)
}
}
}
extension ClawMachine {
init(input:some StringProtocol) {
let lines = input.split(separator: "\n").map { extractPositiveInts($0) }
self.Ax = Double(lines[0][0])
self.Ay = Double(lines[0][1])
self.Bx = Double(lines[1][0])
self.By = Double(lines[1][1])
self.Dx = Double(lines[2][0]) + 10000000000000
self.Dy = Double(lines[2][1]) + 10000000000000
}
}
//Ignores negative signs.
func extractPositiveInts(_ input:some StringProtocol) -> [Int] {
input.components(separatedBy: CharacterSet.decimalDigits.inverted).compactMap({Int($0)})
}
let first = ClawMachine(input: test1)
first.cost()
first.validatedCost()
let second = ClawMachine(input: test2)
second.cost()
second.validatedCost()
let third = ClawMachine(input: test3)
third.cost()
third.validatedCost()
let fourth = ClawMachine(input: test3)
fourth.cost()
fourth.validatedCost()
let allMachinesTest = longer.split(separator: "\n\n").compactMap { ClawMachine(input: $0).validatedCost()}.reduce(0,+)
//
//let allMachines = realData.split(separator: "\n\n").compactMap { ClawMachine(input: $0).validatedCost()}.reduce(0,+)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment