Skip to content

Commit a943bfd

Browse files
l0sl0s
committed
Day 16
1 parent 4409fc7 commit a943bfd

File tree

2 files changed

+353
-0
lines changed

2 files changed

+353
-0
lines changed

‎src/test/java/com/macasaet/Day16.java

Lines changed: 352 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,352 @@
1+
package com.macasaet;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
import static org.junit.jupiter.api.Assertions.assertTrue;
5+
6+
import java.util.*;
7+
import java.util.stream.Collectors;
8+
import java.util.stream.Stream;
9+
import java.util.stream.StreamSupport;
10+
11+
import org.junit.jupiter.api.Nested;
12+
import org.junit.jupiter.api.Test;
13+
14+
/**
15+
* --- Day 16: Packet Decoder ---
16+
*/
17+
public class Day16 {
18+
19+
protected Stream<String> getInput() {
20+
return StreamSupport
21+
.stream(new LineSpliterator("day-16.txt"),
22+
false);
23+
}
24+
25+
public interface Packet {
26+
long version();
27+
28+
void accept(PacketVisitor packetVisitor);
29+
30+
long evaluate();
31+
}
32+
33+
public record Literal(long version, long value) implements Packet {
34+
35+
public void accept(PacketVisitor packetVisitor) {
36+
packetVisitor.visit(this);
37+
}
38+
39+
public long evaluate() {
40+
return value();
41+
}
42+
}
43+
44+
public enum OperatorType {
45+
SUM {
46+
public long evaluate(List<? extends Packet> operands) {
47+
return operands.stream().mapToLong(Packet::evaluate).sum();
48+
}
49+
},
50+
PRODUCT {
51+
public long evaluate(List<? extends Packet> operands) {
52+
return operands.stream().mapToLong(Packet::evaluate).reduce(1, (x, y) -> x * y);
53+
}
54+
},
55+
MINIMUM {
56+
public long evaluate(List<? extends Packet> operands) {
57+
return operands.stream().mapToLong(Packet::evaluate).min().orElseThrow();
58+
}
59+
},
60+
MAXIMUM {
61+
public long evaluate(List<? extends Packet> operands) {
62+
return operands.stream().mapToLong(Packet::evaluate).max().orElseThrow();
63+
}
64+
},
65+
GREATER_THAN {
66+
public long evaluate(List<? extends Packet> operands) {
67+
if (operands.size() != 2) {
68+
throw new IllegalArgumentException("Invalid operand list for \"greater than\" operator: " + operands);
69+
}
70+
final var x = operands.get(0).evaluate();
71+
final var y = operands.get(1).evaluate();
72+
return x > y ? 1 : 0;
73+
}
74+
},
75+
LESS_THAN {
76+
public long evaluate(List<? extends Packet> operands) {
77+
if (operands.size() != 2) {
78+
throw new IllegalStateException("Invalid operand list for \"less than\" operator: " + operands);
79+
}
80+
final var x = operands.get(0).evaluate();
81+
final var y = operands.get(1).evaluate();
82+
return x < y ? 1 : 0;
83+
}
84+
},
85+
EQUAL_TO {
86+
public long evaluate(List<? extends Packet> operands) {
87+
if (operands.size() != 2) {
88+
throw new IllegalStateException("Invalid operand list for \"equal to\" operator: " + operands);
89+
}
90+
final var x = operands.get(0).evaluate();
91+
final var y = operands.get(1).evaluate();
92+
return x == y ? 1 : 0;
93+
}
94+
};
95+
96+
public abstract long evaluate(List<? extends Packet> operands);
97+
98+
public static OperatorType forId(final int typeId) {
99+
return switch (typeId) {
100+
case 0 -> SUM;
101+
case 1 -> PRODUCT;
102+
case 2 -> MINIMUM;
103+
case 3 -> MAXIMUM;
104+
case 5 -> GREATER_THAN;
105+
case 6 -> LESS_THAN;
106+
case 7 -> EQUAL_TO;
107+
default -> throw new IllegalArgumentException("Invalid operator type ID: " + typeId);
108+
};
109+
}
110+
}
111+
112+
public record Operator(long version, OperatorType operatorType, List<Packet> operands) implements Packet {
113+
114+
public void accept(PacketVisitor packetVisitor) {
115+
packetVisitor.enter(this);
116+
for (final var subPacket : operands()) {
117+
subPacket.accept(packetVisitor);
118+
}
119+
packetVisitor.exit(this);
120+
}
121+
122+
public long evaluate() {
123+
return operatorType().evaluate(operands());
124+
}
125+
}
126+
127+
public interface PacketVisitor {
128+
void visit(Literal literal);
129+
130+
void enter(Operator operator);
131+
132+
void exit(Operator operator);
133+
}
134+
135+
public static class PacketBuilder {
136+
137+
private long version;
138+
private long typeId;
139+
private OptionalLong literalValue = OptionalLong.empty();
140+
private final List<Packet> subPackets = new ArrayList<>();
141+
142+
public Packet readHex(final String hexString) {
143+
final var hexDigits = hexString.toCharArray();
144+
final var bits = hexToBits(hexDigits);
145+
read(bits, 0);
146+
return toPacket();
147+
}
148+
149+
public int read(final List<Byte> bits, int transmissionCursor) {
150+
final var versionBits = bits.subList(transmissionCursor, transmissionCursor + 3);
151+
transmissionCursor += 3;
152+
this.version = toLong(versionBits);
153+
154+
final var typeBits = bits.subList(transmissionCursor, transmissionCursor + 3);
155+
transmissionCursor += 3;
156+
this.typeId = toLong(typeBits);
157+
158+
// TODO consider adding methods to parse each type specifically
159+
if (this.typeId == 4) {
160+
boolean finalGroup = false;
161+
final var literalBits = new ArrayList<Byte>();
162+
while (!finalGroup) {
163+
final var groupBits = bits.subList(transmissionCursor, transmissionCursor + 5);
164+
transmissionCursor += 5;
165+
finalGroup = groupBits.get(0) == 0;
166+
literalBits.addAll(groupBits.subList(1, 5));
167+
}
168+
if (literalBits.size() > 63) {
169+
throw new IllegalArgumentException("Literal is too large for an long: " + literalBits.size());
170+
}
171+
literalValue = OptionalLong.of(toLong(literalBits));
172+
return transmissionCursor;
173+
} else {
174+
final var lengthTypeIdBits = bits.subList(transmissionCursor, transmissionCursor + 1);
175+
transmissionCursor += 1;
176+
final var lengthTypeId = toLong(lengthTypeIdBits);
177+
if (lengthTypeId == 0) {
178+
final var lengthOfSubPacketsBits = bits.subList(transmissionCursor, transmissionCursor + 15);
179+
transmissionCursor += 15;
180+
final var lengthOfSubPackets = toLong(lengthOfSubPacketsBits);
181+
int bitsRead = 0;
182+
while (bitsRead < lengthOfSubPackets) {
183+
final var subPacketBuilder = new PacketBuilder();
184+
final var newCursor = subPacketBuilder.read(bits, transmissionCursor);
185+
final var subPacketSize = newCursor - transmissionCursor; // size of sub-packet in bits
186+
transmissionCursor = newCursor;
187+
188+
subPackets.add(subPacketBuilder.toPacket());
189+
bitsRead += subPacketSize;
190+
}
191+
return transmissionCursor;
192+
} else if (lengthTypeId == 1) {
193+
final var numSubPacketsBits = bits.subList(transmissionCursor, transmissionCursor + 11);
194+
transmissionCursor += 11;
195+
final var numSubPackets = toLong(numSubPacketsBits);
196+
for (int packetsRead = 0; packetsRead < numSubPackets; packetsRead++) {
197+
final var subPacketBuilder = new PacketBuilder();
198+
transmissionCursor = subPacketBuilder.read(bits, transmissionCursor);
199+
subPackets.add(subPacketBuilder.toPacket());
200+
}
201+
return transmissionCursor;
202+
} else {
203+
throw new IllegalArgumentException("Invalid length type ID: " + lengthTypeId);
204+
}
205+
}
206+
}
207+
208+
public Packet toPacket() {
209+
if (typeId == 4) {
210+
return new Literal(version, literalValue.orElseThrow());
211+
} else {
212+
return new Operator(version, OperatorType.forId((int) typeId), subPackets);
213+
}
214+
}
215+
216+
protected long toLong(final List<Byte> bits) {
217+
long result = 0;
218+
for (int i = 0; i < bits.size(); i++) {
219+
final var bit = bits.get(i);
220+
if (bit == 1) {
221+
final long shiftDistance = bits.size() - i - 1;
222+
result |= 1L << shiftDistance;
223+
} else if (bit != 0) {
224+
throw new IllegalArgumentException("Invalid bit representation of an integer: " + bits);
225+
}
226+
}
227+
return result;
228+
}
229+
230+
protected List<Byte> hexToBits(final char[] hexDigits) {
231+
final var result = new ArrayList<Byte>(hexDigits.length * 4);
232+
for (final var digit : hexDigits) {
233+
final var bits = switch (digit) {
234+
case '0' -> Arrays.asList((byte) 0, (byte) 0, (byte) 0, (byte) 0);
235+
case '1' -> Arrays.asList((byte) 0, (byte) 0, (byte) 0, (byte) 1);
236+
case '2' -> Arrays.asList((byte) 0, (byte) 0, (byte) 1, (byte) 0);
237+
case '3' -> Arrays.asList((byte) 0, (byte) 0, (byte) 1, (byte) 1);
238+
case '4' -> Arrays.asList((byte) 0, (byte) 1, (byte) 0, (byte) 0);
239+
case '5' -> Arrays.asList((byte) 0, (byte) 1, (byte) 0, (byte) 1);
240+
case '6' -> Arrays.asList((byte) 0, (byte) 1, (byte) 1, (byte) 0);
241+
case '7' -> Arrays.asList((byte) 0, (byte) 1, (byte) 1, (byte) 1);
242+
case '8' -> Arrays.asList((byte) 1, (byte) 0, (byte) 0, (byte) 0);
243+
case '9' -> Arrays.asList((byte) 1, (byte) 0, (byte) 0, (byte) 1);
244+
case 'A', 'a' -> Arrays.asList((byte) 1, (byte) 0, (byte) 1, (byte) 0);
245+
case 'B', 'b' -> Arrays.asList((byte) 1, (byte) 0, (byte) 1, (byte) 1);
246+
case 'C', 'c' -> Arrays.asList((byte) 1, (byte) 1, (byte) 0, (byte) 0);
247+
case 'D', 'd' -> Arrays.asList((byte) 1, (byte) 1, (byte) 0, (byte) 1);
248+
case 'E', 'e' -> Arrays.asList((byte) 1, (byte) 1, (byte) 1, (byte) 0);
249+
case 'F', 'f' -> Arrays.asList((byte) 1, (byte) 1, (byte) 1, (byte) 1);
250+
default -> throw new IllegalStateException("Unexpected value: " + digit);
251+
};
252+
result.addAll(bits);
253+
}
254+
return Collections.unmodifiableList(result);
255+
}
256+
}
257+
258+
@Test
259+
public final void testParseLiteral() {
260+
// given
261+
final var input = "D2FE28";
262+
final var builder = new PacketBuilder();
263+
264+
// when
265+
final var result = builder.readHex(input);
266+
267+
// then
268+
assertTrue(result instanceof Literal);
269+
final var literal = (Literal) result;
270+
assertEquals(2021, literal.value);
271+
}
272+
273+
@Test
274+
public final void testOperatorWithTwoSubPackets() {
275+
// given
276+
final var input = "38006F45291200";
277+
final var builder = new PacketBuilder();
278+
279+
// when
280+
final var result = builder.readHex(input);
281+
282+
// then
283+
assertTrue(result instanceof Operator);
284+
final var operator = (Operator) result;
285+
assertEquals(1, operator.version());
286+
assertEquals(OperatorType.LESS_THAN, operator.operatorType());
287+
assertEquals(2, operator.operands().size());
288+
final var a = (Literal) operator.operands().get(0);
289+
assertEquals(10, a.value());
290+
final var b = (Literal) operator.operands().get(1);
291+
assertEquals(20, b.value());
292+
}
293+
294+
@Test
295+
public final void part1() {
296+
final var line = getInput().collect(Collectors.toList()).get(0);
297+
final var builder = new PacketBuilder();
298+
final var packet = builder.readHex(line);
299+
class VersionSummer implements PacketVisitor {
300+
301+
int sum = 0;
302+
303+
public void visit(Literal literal) {
304+
sum += literal.version();
305+
}
306+
307+
public void enter(Operator operator) {
308+
}
309+
310+
public void exit(Operator operator) {
311+
sum += operator.version();
312+
}
313+
}
314+
final var summer = new VersionSummer();
315+
packet.accept(summer);
316+
317+
System.out.println("Part 1: " + summer.sum);
318+
}
319+
320+
@Test
321+
public final void part2() {
322+
final var line = getInput().collect(Collectors.toList()).get(0);
323+
final var builder = new PacketBuilder();
324+
final var packet = builder.readHex(line);
325+
System.out.println("Part 2: " + packet.evaluate());
326+
}
327+
328+
@Nested
329+
public class PacketBuilderTest {
330+
@Test
331+
public void testToInt() {
332+
// given
333+
final var builder = new PacketBuilder();
334+
// when
335+
// then
336+
assertEquals(2021, builder.toLong(Arrays.asList((byte) 0, (byte) 1, (byte) 1, (byte) 1, (byte) 1, (byte) 1, (byte) 1, (byte) 0, (byte) 0, (byte) 1, (byte) 0, (byte) 1)));
337+
}
338+
339+
@Test
340+
public final void testMaths() {
341+
assertEquals(3, new PacketBuilder().readHex("C200B40A82").evaluate());
342+
assertEquals(54, new PacketBuilder().readHex("04005AC33890").evaluate());
343+
assertEquals(7, new PacketBuilder().readHex("880086C3E88112").evaluate());
344+
assertEquals(9, new PacketBuilder().readHex("CE00C43D881120").evaluate());
345+
assertEquals(1, new PacketBuilder().readHex("D8005AC2A8F0").evaluate());
346+
assertEquals(0, new PacketBuilder().readHex("F600BC2D8F").evaluate());
347+
assertEquals(0, new PacketBuilder().readHex("9C005AC2F8F0").evaluate());
348+
assertEquals(1, new PacketBuilder().readHex("9C0141080250320F1802104A08").evaluate());
349+
}
350+
}
351+
352+
}

‎src/test/resources/sample/day-16.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
D2FE28

0 commit comments

Comments
 (0)