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
Appearance settings

Commit a943bfd

Browse filesBrowse files
l0sl0s
committed
Day 16
1 parent 4409fc7 commit a943bfd
Copy full SHA for a943bfd

File tree

2 files changed

+353
-0
lines changed
Filter options

2 files changed

+353
-0
lines changed

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

Copy file name to clipboard
+352Lines 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

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

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.