Skip to content

Commit 6b64412

Browse files
codeforkjeffcodeforkjeff
committed
day 13
1 parent 26e68e1 commit 6b64412

File tree

7 files changed

+162
-0
lines changed

7 files changed

+162
-0
lines changed

‎README.md

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,3 +67,16 @@ except count them for part 2. I'll take that win!
6767
Day 11 part 2 is the first problem I had to sleep on. Initially I thought it was one of those where you don't actually
6868
need to iterate, you could pre-calculate the resulting number of stones at a given evolution. I'm still not sure if that
6969
could actually work. In the end, I simply figured out a more efficient representation for iteration. It worked nicely.
70+
71+
### 12/13/2024
72+
73+
I've been dreading the type of problem that came up in Day 13, where the only viable solution isn't based on
74+
time- or spacing-saving algorithms, but on calculation. I won't spoil it here, but I'll just say it took me
75+
a little while to write out the equation.
76+
77+
I often declare records as members of the class when 1) they're only used by that class, 2) there's a bunch of them
78+
that are related and work together, 3) it's nice to see them all in one place instead of in separate files.
79+
Today I randomly discovered
80+
[local classes](https://docs.oracle.com/javase/tutorial/java/javaOO/localclasses.html) and
81+
[records](https://docs.oracle.com/en/java/javase/17/language/records.html). This allows you to scope, say, an intermediate record for a stream transformation, to a single method
82+
and avoid clutter at the class level. Pretty cool!

‎src/main/java/com/codefork/aoc2024/day13/Machine.java

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
package com.codefork.aoc2024.day13;
2+
3+
import java.util.ArrayList;
4+
import java.util.Iterator;
5+
import java.util.List;
6+
import java.util.Optional;
7+
import java.util.regex.Pattern;
8+
9+
public record Machine(Button a, Button b, Prize prize) {
10+
11+
private static Pattern buttonPattern = Pattern.compile("Button ([AB]): X\\+(\\d+), Y\\+(\\d+)");
12+
private static Pattern prizePattern = Pattern.compile("Prize: X=(\\d+), Y=(\\d+)");
13+
14+
public record Button(int moveX, int moveY) {
15+
16+
}
17+
18+
public record Prize(long x, long y) {
19+
20+
}
21+
22+
public record Solution(long countA, long countB) {
23+
24+
}
25+
26+
public Optional<Solution> findSolution() {
27+
// I wrote out on paper the two simultaneous equations, merged them into one using
28+
// substitution, and solved for the number of times button B is pressed (countB).
29+
// Once we have that, we can plug it into one of the original equations to get countA
30+
var numer = (a.moveY() * prize.x()) - (a.moveX() * prize.y());
31+
var denom = (a.moveY() * b.moveX()) - (a.moveX() * b.moveY());
32+
33+
// test that countB and countA are whole numbers; we can't push a button a fraction of a time,
34+
// so reject those solutions
35+
if (numer % denom == 0) {
36+
var countB = numer / denom;
37+
var numerCountA = prize.x() - (b.moveX() * countB);
38+
if (numerCountA % a.moveX() == 0) {
39+
var countA = numerCountA / a.moveX();
40+
return Optional.of(new Solution(countA, countB));
41+
}
42+
}
43+
return Optional.empty();
44+
}
45+
46+
/**
47+
* The nulls here are gross, but IntelliJ warns you're not supposed to use Optionals for parameters,
48+
* so I'm not sure how else to do this more safely.
49+
*/
50+
public static List<Machine> consume(Iterator<String> iter, long prizeAddition, List<Machine> machines, Button a, Button b) {
51+
if (iter.hasNext()) {
52+
var line = iter.next();
53+
var buttonMatcher = buttonPattern.matcher(line);
54+
if (buttonMatcher.find()) {
55+
var button = buttonMatcher.group(1);
56+
var x = Integer.parseInt(buttonMatcher.group(2));
57+
var y = Integer.parseInt(buttonMatcher.group(3));
58+
if (button.equals("A")) {
59+
return consume(iter, prizeAddition, machines, new Button(x, y), b);
60+
}
61+
if (button.equals("B")) {
62+
return consume(iter, prizeAddition, machines, a, new Button(x, y));
63+
}
64+
}
65+
var prizeMatcher = prizePattern.matcher(line);
66+
if (prizeMatcher.find()) {
67+
var x = Integer.parseInt(prizeMatcher.group(1)) + prizeAddition;
68+
var y = Integer.parseInt(prizeMatcher.group(2)) + prizeAddition;
69+
var prize = new Prize(x, y);
70+
// a and b should be present at this point; if they're not, something's wrong with the input
71+
machines.add(new Machine(a, b, prize));
72+
return consume(iter, prizeAddition, machines, null, null);
73+
}
74+
consume(iter, prizeAddition, machines, a, b);
75+
}
76+
return machines;
77+
}
78+
79+
public static List<Machine> consume(Iterator<String> iter, long prizeAddition) {
80+
return consume(iter, prizeAddition, new ArrayList<>(), null, null);
81+
}
82+
}

‎src/main/java/com/codefork/aoc2024/day13/Part01.java

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package com.codefork.aoc2024.day13;
2+
3+
import com.codefork.aoc2024.Problem;
4+
import com.codefork.aoc2024.util.Assert;
5+
6+
import java.util.Optional;
7+
import java.util.stream.Stream;
8+
9+
public class Part01 extends Problem {
10+
11+
public String solve(Stream<String> data) {
12+
var machines = Machine.consume(data.iterator(), 0);
13+
var tokens = machines.stream()
14+
.map(Machine::findSolution)
15+
.filter(Optional::isPresent)
16+
.map(Optional::orElseThrow)
17+
.map(solution -> (solution.countA() * 3) + solution.countB())
18+
.mapToLong(i-> i)
19+
.sum();
20+
21+
return String.valueOf(tokens);
22+
}
23+
24+
@Override
25+
public String solve() {
26+
Assert.assertEquals("480", solve(getSampleInput()));
27+
return solve(getInput());
28+
}
29+
30+
public static void main(String[] args) {
31+
new Part01().run();
32+
}
33+
}

‎src/main/java/com/codefork/aoc2024/day13/Part02.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package com.codefork.aoc2024.day13;
2+
3+
import com.codefork.aoc2024.Problem;
4+
5+
import java.util.Optional;
6+
import java.util.stream.Stream;
7+
8+
public class Part02 extends Problem {
9+
10+
public String solve(Stream<String> data) {
11+
var machines = Machine.consume(data.iterator(), 10000000000000L);
12+
var tokens = machines.stream()
13+
//.peek(System.out::println)
14+
.map(Machine::findSolution)
15+
.filter(Optional::isPresent)
16+
//.peek(System.out::println)
17+
.map(Optional::orElseThrow)
18+
.map(solution -> (solution.countA() * 3) + solution.countB())
19+
.mapToLong(i-> i)
20+
.sum();
21+
22+
return String.valueOf(tokens);
23+
}
24+
25+
@Override
26+
public String solve() {
27+
return solve(getInput());
28+
}
29+
30+
public static void main(String[] args) {
31+
new Part02().run();
32+
}
33+
34+
}

‎src/main/resources/day13/input

20.5 KB
Binary file not shown.

‎src/main/resources/day13/sample

285 Bytes
Binary file not shown.

‎src/main/resources/day13/sample2

22 Bytes
Binary file not shown.

0 commit comments

Comments
 (0)