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 02eba5b

Browse filesBrowse files
l0sl0s
committed
Day 14
1 parent 5a73ccb commit 02eba5b
Copy full SHA for 02eba5b

File tree

2 files changed

+184
-0
lines changed
Filter options

2 files changed

+184
-0
lines changed

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

Copy file name to clipboard
+166Lines changed: 166 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,166 @@
1+
package com.macasaet;
2+
3+
import java.math.BigInteger;
4+
import java.util.*;
5+
import java.util.stream.Collectors;
6+
import java.util.stream.Stream;
7+
import java.util.stream.StreamSupport;
8+
9+
import org.junit.jupiter.api.Test;
10+
11+
/**
12+
* --- Day 14: Extended Polymerization ---
13+
*/
14+
public class Day14 {
15+
16+
protected Stream<String> getInput() {
17+
return StreamSupport
18+
.stream(new LineSpliterator("day-14.txt"),
19+
false);
20+
}
21+
22+
public record Polymer(Map<ElementPair, BigInteger> pairCounts, char firstElement, char lastElement) {
23+
public static Polymer forTemplate(final String templateString) {
24+
final var firstElement = templateString.charAt(0);
25+
final var lastElement = templateString.charAt(templateString.length() - 1);
26+
final var map = new HashMap<ElementPair, BigInteger>();
27+
for (int i = 1; i < templateString.length(); i++) {
28+
map.merge(new ElementPair(templateString.charAt(i - 1), templateString.charAt(i)),
29+
BigInteger.ONE,
30+
BigInteger::add);
31+
}
32+
return new Polymer(Collections.unmodifiableMap(map), firstElement, lastElement);
33+
}
34+
35+
/**
36+
* Apply the pair insertion process one time.
37+
*
38+
* @param rules pair insertion rules for generating a new polymer
39+
* @return the new polymer that results
40+
*/
41+
public Polymer applyRules(final Map<ElementPair, PairInsertionRule> rules) {
42+
final var map = new HashMap<ElementPair, BigInteger>();
43+
for (final var entry : pairCounts().entrySet()) {
44+
final var key = entry.getKey();
45+
final var count = entry.getValue();
46+
final var rule = rules.get(key);
47+
final var left = new ElementPair(key.start(), rule.insert());
48+
final var right = new ElementPair(rule.insert(), key.end());
49+
50+
map.compute(left, (_key, oldCount) -> oldCount == null ? count : oldCount.add(count));
51+
map.compute(right, (_key, oldCount) -> oldCount == null ? count : oldCount.add(count));
52+
}
53+
return new Polymer(Collections.unmodifiableMap(map), firstElement(), lastElement());
54+
}
55+
56+
/**
57+
* Determine how many times each element appears in the polymer
58+
*
59+
* @return the number of times each element appears in the polymer
60+
*/
61+
public SortedMap<BigInteger, Set<Character>> histogram() {
62+
final var map = new HashMap<Character, BigInteger>();
63+
for (final var entry : pairCounts().entrySet()) {
64+
final var pair = entry.getKey();
65+
final var count = entry.getValue();
66+
map.compute(pair.start(),
67+
(_key, oldValue) -> oldValue == null ? count : oldValue.add(count));
68+
map.compute(pair.end(),
69+
(_key, oldValue) -> oldValue == null ? count : oldValue.add(count));
70+
}
71+
for (final var entry : map.entrySet()) {
72+
final var element = entry.getKey();
73+
final var count = entry.getValue();
74+
if (element.equals(firstElement()) || element.equals(lastElement())) {
75+
entry.setValue(count.divide(BigInteger.TWO).add(BigInteger.ONE));
76+
} else {
77+
entry.setValue(count.divide(BigInteger.TWO));
78+
}
79+
}
80+
final var result = new TreeMap<BigInteger, Set<Character>>();
81+
for (final var entry : map.entrySet()) {
82+
final var target = result.computeIfAbsent(entry.getValue(), _key -> new HashSet<>());
83+
target.add(entry.getKey());
84+
}
85+
return Collections.unmodifiableSortedMap(result);
86+
}
87+
}
88+
89+
/**
90+
* A pair of elements that appear adjacent to each other. This may be used in the context of a pair insertion rule
91+
* definition or a polymer.
92+
*
93+
* @see Polymer
94+
* @see PairInsertionRule
95+
*/
96+
protected record ElementPair(char start, char end) {
97+
}
98+
99+
/**
100+
* A single instruction to aid in finding the optimal polymer formula
101+
*/
102+
public record PairInsertionRule(char start, char end, char insert) {
103+
104+
public static PairInsertionRule parse(final String string) {
105+
final var components = string.split(" -> ");
106+
final var match = components[0].toCharArray();
107+
return new PairInsertionRule(match[0], match[1], components[1].toCharArray()[0]);
108+
}
109+
110+
}
111+
112+
protected record Input(Polymer polymerTemplate, List<PairInsertionRule> rules) {
113+
}
114+
115+
protected Input parseInput() {
116+
final var list = getInput().collect(Collectors.toList());
117+
int mode = 0;
118+
Polymer polymer = null;
119+
final var rules = new ArrayList<PairInsertionRule>();
120+
for (final var line : list) {
121+
if (line.isBlank()) {
122+
mode++;
123+
continue;
124+
}
125+
if (mode == 0) {
126+
polymer = Polymer.forTemplate(line);
127+
} else {
128+
rules.add(PairInsertionRule.parse(line));
129+
}
130+
}
131+
return new Input(polymer, rules);
132+
}
133+
134+
@Test
135+
public final void part1() {
136+
final var input = parseInput();
137+
var polymer = input.polymerTemplate();
138+
final var rules = input.rules();
139+
final var ruleMap = new HashMap<ElementPair, PairInsertionRule>();
140+
for (final var rule : rules) {
141+
ruleMap.put(new ElementPair(rule.start(), rule.end()), rule);
142+
}
143+
for (int _i = 0; _i < 10; _i++) {
144+
polymer = polymer.applyRules(ruleMap);
145+
}
146+
final var histogram = polymer.histogram();
147+
System.out.println("Part 1: " + histogram.lastKey().subtract(histogram.firstKey()));
148+
}
149+
150+
@Test
151+
public final void part2() {
152+
final var input = parseInput();
153+
var polymer = input.polymerTemplate();
154+
final var rules = input.rules();
155+
final var ruleMap = new HashMap<ElementPair, PairInsertionRule>();
156+
for (final var rule : rules) {
157+
ruleMap.put(new ElementPair(rule.start(), rule.end()), rule);
158+
}
159+
for (int _i = 0; _i < 40; _i++) {
160+
polymer = polymer.applyRules(ruleMap);
161+
}
162+
final var histogram = polymer.histogram();
163+
System.out.println("Part 2: " + histogram.lastKey().subtract(histogram.firstKey()));
164+
}
165+
166+
}

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

Copy file name to clipboard
+18Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
NNCB
2+
3+
CH -> B
4+
HH -> N
5+
CB -> H
6+
NH -> C
7+
HB -> C
8+
HC -> B
9+
HN -> C
10+
NN -> C
11+
BH -> H
12+
NC -> B
13+
NB -> B
14+
BN -> B
15+
BB -> N
16+
BC -> B
17+
CC -> N
18+
CN -> C

0 commit comments

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