Skip to content

Commit 9fc1a0c

Browse files
pareroniapareronia
committed
AoC 2020 Day 23 - java - faster
1 parent b1d4fa5 commit 9fc1a0c

File tree

2 files changed

+53
-128
lines changed

2 files changed

+53
-128
lines changed

‎src/main/java/AoC2020_23.java

Lines changed: 50 additions & 125 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,20 @@
1+
import static com.github.pareronia.aoc.IntegerSequence.Range.range;
2+
import static java.util.stream.Collectors.joining;
13
import static java.util.stream.Collectors.toCollection;
24

35
import java.util.ArrayList;
46
import java.util.Arrays;
5-
import java.util.HashMap;
6-
import java.util.IntSummaryStatistics;
77
import java.util.List;
8-
import java.util.Map;
9-
import java.util.Objects;
8+
import java.util.Set;
9+
import java.util.stream.IntStream;
1010
import java.util.stream.Stream;
1111

1212
import com.github.pareronia.aoc.StringOps;
1313
import com.github.pareronia.aoc.solution.Sample;
1414
import com.github.pareronia.aoc.solution.Samples;
1515
import com.github.pareronia.aoc.solution.SolutionBase;
1616

17-
public class AoC2020_23 extends SolutionBase<List<Integer>, Long, Long> {
17+
public class AoC2020_23 extends SolutionBase<List<Integer>, String, Long> {
1818

1919
private AoC2020_23(final boolean debug) {
2020
super(debug);
@@ -35,92 +35,67 @@ protected List<Integer> parseInput(final List<String> inputs) {
3535
return Arrays.stream(digits).toList();
3636
}
3737

38-
private Map<Integer, Cup> prepareCups(final List<Integer> labels) {
39-
final Map<Integer, Cup> cups = new HashMap<>();
40-
final Integer first = labels.get(0);
41-
final Integer last = labels.get(labels.size() - 1);
42-
final Cup tail = new Cup(last, (Cup) null);
43-
Cup prev = tail;
44-
Cup cup;
45-
for (int i = labels.size() - 2; i > 0; i--) {
46-
final Integer label = labels.get(i);
47-
cup = new Cup(label, prev);
48-
cups.put(label, cup);
49-
prev = cup;
50-
}
51-
final Cup head = new Cup(first, prev);
52-
cups.put(first, head);
53-
tail.setNext(head);
54-
cups.put(last, tail);
55-
return cups;
56-
}
57-
58-
private Cup doMove(
59-
final Map<Integer, Cup> cups,
60-
final Cup current,
61-
final Integer size,
62-
final Integer min,
63-
final Integer max) {
64-
final Cup p1 = current.getNext();
65-
final Cup p2 = p1.getNext();
66-
final Cup p3 = p2.getNext();
67-
current.setNext(p3.getNext());
68-
final List<Integer> pickup
69-
= List.of(p1.getLabel(), p2.getLabel(), p3.getLabel());
70-
Integer d = current.getLabel() - 1;
71-
if (d < min) {
72-
d = max;
73-
}
38+
private int[] prepareCups(final List<Integer> labels) {
39+
final int[] cups = new int[labels.size() + 1];
40+
range(labels.size()).forEach(i -> {
41+
cups[labels.get(i)] = labels.get((i + 1) % labels.size());
42+
});
43+
return cups;
44+
}
45+
46+
private int doMove(
47+
final int[] cups,
48+
final int current,
49+
final int min,
50+
final int max
51+
) {
52+
final int c = current;
53+
final int p1 = cups[c];
54+
final int p2 = cups[p1];
55+
final int p3 = cups[p2];
56+
cups[c] = cups[p3];
57+
final Set<Integer> pickup = Set.of(p1, p2, p3);
58+
int d = c - 1;
59+
if (d < min) {
60+
d = max;
61+
}
7462
while (pickup.contains(d)) {
7563
d--;
7664
if (d < min) {
7765
d = max;
7866
}
7967
}
80-
final Cup destination = cups.get(d);
81-
p3.setNext(destination.getNext());
82-
destination.setNext(p1);
83-
return current.getNext();
84-
}
85-
68+
cups[p3] = cups[d];
69+
cups[d] = p1;
70+
return cups[c];
71+
}
72+
8673
@Override
87-
public Long solvePart1(final List<Integer> labels) {
88-
final Map<Integer, Cup> cups = prepareCups(labels);
89-
final int size = labels.size();
90-
final IntSummaryStatistics stats
91-
= labels.stream().mapToInt(Integer::valueOf).summaryStatistics();
92-
final Integer min = stats.getMin();
93-
final Integer max = stats.getMax();
94-
Cup current = cups.get(labels.get(0));
74+
public String solvePart1(final List<Integer> labels) {
75+
final int[] cups = prepareCups(labels);
76+
int current = labels.get(0);
9577
for (int i = 0; i < 100; i++) {
96-
current = doMove(cups, current, size, min, max);
78+
current = doMove(cups, current, 1, 9);
9779
}
98-
Cup cup = cups.get(1);
99-
final StringBuilder result = new StringBuilder();
100-
while (cup.getNext().getLabel() != 1) {
101-
result.append(cup.getNext().getLabel());
102-
cup = cup.getNext();
103-
}
104-
return Long.valueOf(result.toString());
80+
return IntStream.iterate(cups[1], cup -> cups[cup])
81+
.takeWhile(cup -> cup != 1)
82+
.mapToObj(String::valueOf)
83+
.collect(joining());
10584
}
10685

10786
@Override
10887
public Long solvePart2(final List<Integer> labels) {
109-
final IntSummaryStatistics stats
110-
= labels.stream().mapToInt(Integer::valueOf).summaryStatistics();
111-
final Integer min = stats.getMin();
112-
final Integer max = stats.getMax();
113-
final List<Integer> newLabels = new ArrayList<>(labels);
114-
Stream.iterate(max + 1, i -> i + 1).limit(1_000_000 - labels.size())
88+
final List<Integer> newLabels = new ArrayList<>(1_000_000);
89+
newLabels.addAll(labels);
90+
Stream.iterate(10, i -> i + 1).limit(1_000_000 - labels.size())
11591
.collect(toCollection(() -> newLabels));
116-
final Map<Integer, Cup> cups = prepareCups(newLabels);
117-
Cup current = cups.get(newLabels.get(0));
92+
final int[] cups = prepareCups(newLabels);
93+
int current = labels.get(0);
11894
for (int i = 0; i < 10_000_000; i++) {
119-
current = doMove(cups, current, 1_000_000, min, 1_000_000);
95+
current = doMove(cups, current, 1, 1_000_000);
12096
}
121-
final Cup one = cups.get(1);
122-
final long star1 = one.getNext().getLabel().longValue();
123-
final long star2 = one.getNext().getNext().getLabel().longValue();
97+
final long star1 = cups[1];
98+
final long star2 = cups[cups[1]];
12499
return star1 * star2;
125100
}
126101

@@ -133,54 +108,4 @@ public static void main(final String[] args) throws Exception {
133108
}
134109

135110
private static final String TEST = "389125467";
136-
137-
138-
private static final class Cup {
139-
private final Integer label;
140-
private Cup next;
141-
142-
public Cup(final Integer label, final Cup next) {
143-
this.label = label;
144-
this.next = next;
145-
}
146-
147-
public Integer getLabel() {
148-
return label;
149-
}
150-
151-
public Cup getNext() {
152-
return next;
153-
}
154-
155-
public void setNext(final Cup next) {
156-
this.next = next;
157-
}
158-
159-
@Override
160-
public String toString() {
161-
final StringBuilder builder = new StringBuilder();
162-
builder.append("Cup [label=").append(label).append("]");
163-
return builder.toString();
164-
}
165-
166-
@Override
167-
public boolean equals(final Object obj) {
168-
if (this == obj) {
169-
return true;
170-
}
171-
if (obj == null) {
172-
return false;
173-
}
174-
if (getClass() != obj.getClass()) {
175-
return false;
176-
}
177-
final Cup other = (Cup) obj;
178-
return Objects.equals(label, other.label) && Objects.equals(next, other.next);
179-
}
180-
181-
@Override
182-
public int hashCode() {
183-
return Objects.hash(label, next);
184-
}
185-
}
186111
}

‎src/main/java/com/github/pareronia/aoc/IterTools.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -110,8 +110,8 @@ public static <T> IterToolsIterator<ZippedPair<T>> zip(
110110
return zip(iterable1.iterator(), iterable2.iterator());
111111
}
112112

113-
private static <T> Iterator<T> cycle(final Iterator<T> iterator) {
114-
return new Iterator<>() {
113+
private static <T> IterToolsIterator<T> cycle(final Iterator<T> iterator) {
114+
return new IterToolsIterator<>() {
115115
List<T> saved = new ArrayList<>();
116116
int i = 0;
117117

@@ -132,7 +132,7 @@ public T next() {
132132
};
133133
}
134134

135-
public static <T> Iterator<T> cycle(final Iterable<T> iterable) {
135+
public static <T> IterToolsIterator<T> cycle(final Iterable<T> iterable) {
136136
return cycle(iterable.iterator());
137137
}
138138

0 commit comments

Comments
 (0)