Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 392f19a

Browse files
day07 for AoC 2024 (part 2) refactor to use a common logic for part 1 and part 2; fail-fast with a guard for the subtractions too; prioritize the multiplication over concat and concat over additions because they of their natual magnitude
Took 36 minutes
1 parent c0f5343 commit 392f19a

File tree

1 file changed

+61
-114
lines changed
  • src/main/java/aminetti/adventofcode2024/day07

1 file changed

+61
-114
lines changed
Lines changed: 61 additions & 114 deletions
Original file line numberDiff line numberDiff line change
@@ -1,29 +1,26 @@
11
package aminetti.adventofcode2024.day07;
22

3-
import com.google.common.collect.Iterables;
43
import org.apache.commons.lang3.StringUtils;
54
import org.slf4j.Logger;
65
import org.slf4j.LoggerFactory;
76

87
import java.util.ArrayList;
98
import java.util.Arrays;
9+
import java.util.EnumSet;
1010
import java.util.List;
1111

12-
import static aminetti.adventofcode2024.day07.Day07.Op.MULT;
12+
import static aminetti.adventofcode2024.day07.Day07.Op.*;
1313
import static com.google.common.collect.Lists.newArrayList;
1414

1515
public class Day07 {
1616
private static final Logger LOGGER = LoggerFactory.getLogger(Day07.class);
17-
private List<String> input;
1817
private final List<Long> results = new ArrayList<>();
1918
private final List<List<Long>> components = new ArrayList<>();
2019

2120
public Day07() {
2221
}
2322

2423
public void parseInput(List<String> input) {
25-
this.input = input;
26-
2724
for (String s : input) {
2825
String[] split = s.split(":");
2926
results.add(Long.parseLong(split[0]));
@@ -33,12 +30,19 @@ public void parseInput(List<String> input) {
3330
}
3431

3532
public long solvePart1() {
33+
EnumSet<Op> allowedOps = EnumSet.of(SUM, MULT);
34+
return countValidEquations(allowedOps);
35+
}
36+
37+
private long countValidEquations(EnumSet<Op> allowedOps) {
3638
long sum = 0;
3739
for (int i = 0; i < results.size(); i++) {
3840
Long result = results.get(i);
39-
long count = countOfCorrectOperators(result, components.get(i), List.of(), newArrayList());
40-
LOGGER.debug("count for {}: {}", result, count);
41-
if (count > 0) {
41+
42+
boolean valid = isValid(allowedOps, result, components.get(i), List.of(), newArrayList());
43+
LOGGER.debug("Is {}: valid? {}", result, valid);
44+
45+
if (valid) {
4246
sum += result;
4347
}
4448
}
@@ -48,7 +52,7 @@ public long solvePart1() {
4852
public enum Op {
4953
SUM, MULT, CONCAT;
5054

51-
public String print() {
55+
public String toString() {
5256
return switch (this) {
5357
case SUM -> "+";
5458
case MULT -> "*";
@@ -57,136 +61,79 @@ public String print() {
5761
}
5862
}
5963

64+
public long solvePart2() {
65+
EnumSet<Op> allowedOps = EnumSet.allOf(Op.class);
66+
return countValidEquations(allowedOps);
67+
}
6068

61-
private long countOfCorrectOperators(long result, List<Long> longs, List<Op> operators, List<Long> components) {
62-
if (longs.size() == 1) {
63-
Long lastEl = Iterables.getOnlyElement(longs);
64-
if (result == lastEl) {
6569

66-
String fullOperation = "(".repeat(operators.size()) + lastEl;
70+
private boolean isValid(final EnumSet<Op> allowedOps, long result, List<Long> lefts, List<Op> operators, List<Long> rights) {
71+
if (lefts.isEmpty()) {
72+
return false;
73+
}
6774

68-
ArrayList<Op> mutableOps = newArrayList(operators);
69-
ArrayList<Long> mutableComponents = newArrayList(components);
70-
while (!mutableOps.isEmpty()) {
71-
fullOperation += mutableOps.removeLast().print() + "" + mutableComponents.removeLast() + ")";
72-
}
75+
ArrayList<Long> nextLeft = newArrayList(lefts);
76+
Long current = nextLeft.removeLast();
7377

74-
LOGGER.debug("Operation: {}", fullOperation);
75-
LOGGER.info("Found correct operators");
76-
return 1;
78+
if (lefts.size() == 1) {
79+
if (result == current) {
80+
String fullOperation = printOperation(operators, rights, current);
81+
LOGGER.debug("Found correct operators, operations: {}", fullOperation);
82+
return true;
7783
}
78-
79-
return 0;
80-
84+
return false;
8185
}
8286

83-
if (result <= 0 || longs.isEmpty()) {
84-
return 0;
85-
}
86-
87-
88-
ArrayList<Op> opsForSum = newArrayList(operators);
89-
opsForSum.add(Op.SUM);
9087

91-
ArrayList<Op> opsForMult = newArrayList(operators);
92-
opsForMult.add(MULT);
88+
ArrayList<Long> nextRights = newArrayList(rights);
89+
nextRights.add(current);
9390

94-
ArrayList<Long> next = newArrayList(longs);
95-
Long component = next.removeLast();
96-
97-
ArrayList<Long> nextComponents = newArrayList(components);
98-
nextComponents.add(component);
99-
100-
long sumMult = 0;
101-
if (result % component == 0) {
102-
sumMult += countOfCorrectOperators(result / component, next, opsForMult, nextComponents);
103-
}
104-
return sumMult
105-
+ countOfCorrectOperators(result - component, next, opsForSum, nextComponents);
106-
}
107-
108-
public long solvePart2() {
109-
long sum = 0;
110-
for (int i = 0; i < results.size(); i++) {
111-
Long result = results.get(i);
112-
113-
LOGGER.debug("Checking {}", result);
114-
long count = countOfCorrectOperatorsWithConcat(result, components.get(i), List.of(), newArrayList());
115-
LOGGER.debug("count for {}: {}", result, count);
116-
if (count > 0) {
117-
sum += result;
91+
if (allowedOps.contains(MULT) && result % current == 0) { // divisions are the fastest to decrease a value
92+
ArrayList<Op> opsForMult = newArrayList(operators);
93+
opsForMult.add(MULT);
94+
if (isValid(allowedOps, result / current, nextLeft, opsForMult, nextRights)) {
95+
return true;
11896
}
11997
}
120-
return sum;
121-
}
122-
123-
124-
private long countOfCorrectOperatorsWithConcat(long result, List<Long> longs, List<Op> operators, List<Long> components) {
125-
if (longs.size() == 1) {
126-
Long lastEl = Iterables.getOnlyElement(longs);
127-
if (result == lastEl) {
128-
129-
String fullOperation = "(".repeat(operators.size()) + lastEl;
13098

131-
ArrayList<Op> mutableOps = newArrayList(operators);
132-
ArrayList<Long> mutableComponents = newArrayList(components);
133-
while (!mutableOps.isEmpty()) {
134-
fullOperation += mutableOps.removeLast().print() + "" + mutableComponents.removeLast() + ")";
135-
}
99+
String stringResult = "" + result;
100+
String stringComponent = "" + current;
101+
if (allowedOps.contains(CONCAT) && stringResult.length() > stringComponent.length() && stringResult.endsWith(stringComponent)) {
102+
// split a number (~divide by 10^log10(current) ) could be slower than divisions but faster than subtractions to decrease a value
103+
ArrayList<Op> opsForConcat = newArrayList(operators);
104+
opsForConcat.add(CONCAT);
136105

137-
LOGGER.debug("Operation: {}", fullOperation);
138-
LOGGER.info("Found correct operators");
139-
return 1;
106+
longexpectedResult = Long.parseLong(stringResult.substring(0, stringResult.length() - stringComponent.length()));
107+
if (isValid(allowedOps, expectedResult, nextLeft, opsForConcat, nextRights)) {
108+
return true;
140109
}
141-
142-
return 0;
143-
144110
}
145111

146-
if (result <= 0 || longs.isEmpty()) {
147-
return 0;
112+
if (allowedOps.contains(SUM) && result - current > 0) {
113+
ArrayList<Op> opsForSum = newArrayList(operators);
114+
opsForSum.add(SUM);
115+
if (isValid(allowedOps, result - current, nextLeft, opsForSum, nextRights)) {
116+
return true;
117+
}
148118
}
149119

150120

151-
ArrayList<Op> opsForSum = newArrayList(operators);
152-
opsForSum.add(Op.SUM);
153121

122+
return false;
123+
}
154124

125+
private static String printOperation(List<Op> operators, List<Long> components, Long lastEl) {
126+
StringBuilder fullOperation = new StringBuilder("(".repeat(operators.size()) + lastEl);
155127

156-
ArrayList<Long> next = newArrayList(longs);
157-
Long component = next.removeLast();
158-
159-
ArrayList<Long> nextComponents = newArrayList(components);
160-
nextComponents.add(component);
161-
162-
long sumConcat = 0;
163-
String stringResult = "" + result;
164-
String stringComponent = "" + component;
165-
166-
LOGGER.info("Result: {} - longs: {}", result, longs);
167-
LOGGER.info("Result: {} - stringComponent: {}", stringResult, stringComponent);
168-
169-
if (stringResult.length() > stringComponent.length() && stringResult.endsWith(stringComponent)) {
170-
LOGGER.info("Trailing matches: Result: {} - stringComponent: {}", stringResult, stringComponent);
171-
172-
ArrayList<Op> opsForConcat = newArrayList(operators);
173-
opsForConcat.add(Op.CONCAT);
128+
ArrayList<Op> mutableOps = newArrayList(operators);
129+
ArrayList<Long> mutableComponents = newArrayList(components);
174130

175-
long expectedResult = Long.parseLong(stringResult.substring(0, stringResult.length() - stringComponent.length()));
176-
LOGGER.info("expectedResult: {}", expectedResult);
177-
sumConcat += countOfCorrectOperatorsWithConcat(
178-
expectedResult,
179-
next, opsForConcat, nextComponents);
131+
while (!mutableOps.isEmpty()) {
132+
fullOperation.append(mutableOps.removeLast())
133+
.append(mutableComponents.removeLast()).append(")");
180134
}
181135

182-
long sumMult = 0;
183-
if (result % component == 0) {
184-
ArrayList<Op> opsForMult = newArrayList(operators);
185-
opsForMult.add(MULT);
186-
sumMult += countOfCorrectOperatorsWithConcat(result / component, next, opsForMult, nextComponents);
187-
}
188-
return sumMult + sumConcat
189-
+ countOfCorrectOperatorsWithConcat(result - component, next, opsForSum, nextComponents);
136+
return fullOperation.toString();
190137
}
191138

192139
}

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /