Last active
December 13, 2024 22:23
-
-
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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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 | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)) | |
} | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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