8000 Day 24 · AbdulRehman56/AdventOfCode-Java@750d624 · GitHub
[go: up one dir, main page]
Skip to content

Commit 750d624

Browse files
SimonBaarsSimonBaars
committed
Day 24
1 parent e8962e2 commit 750d624

File tree

4 files changed

+148
-10
lines changed

4 files changed

+148
-10
lines changed

‎src/main/java/com/sbaars/adventofcode/common/Graph.java

Lines changed: 37 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2,10 +2,7 @@
22

33
import com.sbaars.adventofcode.common.map.ListMap;
44

5-
import java.util.ArrayList;
6-
import java.util.Collection;
7-
import java.util.List;
8-
import java.util.Map;
5+
import java.util.*;
96
import java.util.function.BiConsumer;
107
import java.util.function.BinaryOperator;
118
import java.util.function.Function;
@@ -20,6 +17,7 @@ public Graph(ListMap<T, T> map) {
2017
this(Stream.concat(map.keySet().stream(), map.valueStream()).distinct().map(Node::new).collect(Collectors.toMap(Node::data, a -> a)));
2118
map.forEach((a, b) -> nodes.get(a).children.addAll(b.stream().map(nodes::get).toList()));
2219
map.forEach((a, b) -> b.forEach(c -> nodes.get(c).parents.add(nodes.get(a))));
20+
2321
}
2422

2523
public static <T> Collector<Pair<T, T>, ListMap<T, T>, Graph<T>> toGraph() {
@@ -38,6 +36,41 @@ public Stream<Node<T>> stream() {
3836
return getNodes().stream();
3937
}
4038

39+
public List<Node<T>> dijkstra(T start, T end) {
40+
Map<T, Node<T>> previousNodes = new HashMap<>();
41+
Map<T, Double> shortestDistances = new HashMap<>();
42+
PriorityQueue<Node<T>> queue = new PriorityQueue<>(Comparator.comparing(node -> shortestDistances.get(node.data)));
43+
44+
nodes.values().forEach(node -> shortestDistances.put(node.data, Double.POSITIVE_INFINITY));
45+
shortestDistances.put(start, 0.0);
46+
47+
queue.add(nodes.get(start));
48+
49+
while (!queue.isEmpty()) {
50+
Node<T> currentNode = queue.poll();
51+
52+
for (Node<T> neighbor : currentNode.children) {
53+
double tentativeDistance = shortestDistances.get(currentNode.data) + 1; // assuming all edges have weight=1
54+
55+
if (tentativeDistance < shortestDistances.get(neighbor.data)) {
56+
shortestDistances.put(neighbor.data, tentativeDistance);
57+
previousNodes.put(neighbor.data, currentNode);
58+
59+
queue.remove(neighbor);
60+
queue. 10000 add(neighbor);
61+
}
62+
}
63+
}
64+
65+
List<Node<T>> path = new ArrayList<>();
66+
for (Node<T> node = nodes.get(end); node != null; node = previousNodes.get(node.data)) {
67+
path.add(node);
68+
}
69+
70+
Collections.reverse(path);
71+
return path;
72+
}
73+
4174
public record Node<V>(V data, List<Node<V>> children, List<Node<V>> parents) implements Comparable<Node<V>> {
4275
public Node(V data) {
4376
this(data, new ArrayList<>(), new ArrayList<>());

‎src/main/java/com/sbaars/adventofcode/common/location/Loc3D.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -74,6 +74,34 @@ public Loc3D move(long dx, long dy, long dz) {
7474
return new Loc3D(x + dx, y + dy, z + dz);
7575
}
7676

77+
public Loc3D multiply(long dx, long dy, long dz) {
78+
return new Loc3D(x * dx, y * dy, z * dz);
79+
}
80+
81+
public Loc3D divide(long dx, long dy, long dz) {
82+
return new Loc3D(x / dx, y / dy, z / dz);
83+
}
84+
85+
public Loc3D move(Loc3D p) {
86+
return move(p.x, p.y, p.z);
87+
}
88+
89+
public Loc3D multiply(Loc3D p) {
90+
return multiply(p.x, p.y, p.z);
91+
}
92+
93+
public Loc3D multiply(long m) {
94+
return multiply(m, m, m);
95+
}
96+
97+
public Loc3D divide(Loc3D p) {
98+
return divide(p.x, p.y, p.z);
99+
}
100+
101+
public Loc3D divide(long m) {
102+
return divide(m, m, m);
103+
}
104+
77105
public double distance(Loc3D p) {
78106
return Math.sqrt(Math.pow(x - p.getX(), 2) + Math.pow(y - p.getY(), 2) + Math.pow(z - p.getZ(), 2));
79107
}

‎src/main/java/com/sbaars/adventofcode/network/FetchInput.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,7 @@ public FetchInput() {
2929
}
3030

3131
public static void main(String[] args) {
32-
new FetchInput().retrieveDay("25", "2023");
32+
new FetchInput().retrieveDay("24", "2023");
3333
}
3434

3535
private void retrieveDay(String day, String year) {

‎src/main/java/com/sbaars/adventofcode/year23/days/Day24.java

Lines changed: 82 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,17 @@
11
package com.sbaars.adventofcode.year23.days;
22

3+
import com.sbaars.adventofcode.common.Pair;
4+
import com.sbaars.adventofcode.common.location.Loc;
35
import com.sbaars.adventofcode.common.location.Loc3D;
46
import com.sbaars.adventofcode.year23.Day2023;
57

8+
import java.util.List;
9+
import java.util.TreeMap;
10+
import java.util.function.Function;
11+
612
import static com.sbaars.adventofcode.util.DataMapper.readString;
13+
import static java.util.stream.Collectors.toMap;
14+
import static java.util.stream.IntStream.range;
715

816
public class Day24 extends Day2023 {
917

@@ -15,20 +23,89 @@ public static void main(String[] args) {
1523
new Day24().printParts();
1624
}
1725

18-
public record Input(Loc3D pos, Loc3D vel) {
19-
public Input(long posX, long posY, long posZ, long velX, long velY, long velZ) {
26+
public record Rock(Loc3D p, Loc3D v) {
27+
private static final long min = 200000000000000L;
28+
private static final long max = 400000000000000L;
29+
30+
public Rock(long posX, long posY, long posZ, long velX, long velY, long velZ) {
2031
this(new Loc3D(posX, posY, posZ), new Loc3D(velX, velY, velZ));
2132
}
33+
34+
public Rock positionAt(long t) {
35+
return new Rock(p.move(v.multiply(t)), v);
36+
}
37+
38+
boolean willReach(double x, double y) {
39+
double dx = x - p.x;
40+
double dy = y - p.y;
41+
return switch (dx > 0 ? 1 : dx < 0 ? -1 : 0) {
42+
case 0 -> switch (dy > 0 ? 1 : dy < 0 ? -1 : 0) {
43+
case 0 -> false;
44+
case 1 -> v.y > 0;
45+
default -> v.y < 0;
46+
};
47+
case 1 -> v.x > 0;
48+
default -> v.x < 0;
49+
};
50+
}
51+
52+
boolean intersectsXY(Rock o) {
53+
double d = -v.y * o.v.x + o.v.y * v.x;
54+
if (d != 0) {
55+
double a = v.y * p.x - v.x * p.y;
56+
double b = o.v.y * o.p.x - o.v.x * o.p.y;
57+
double x = (-o.v.x * a + v.x * b) / d;
58+
double y = (-o.v.y * a + v.y * b) / d;
59+
if (willReach(x, y) && o.willReach(x, y)) {
60+
return x >= min && x <= max && y >= min && y <= max;
61+
}
62+
}
63+
return false;
64+
}
65+
66+
public Loc x() {
67+
return new Loc(p.x, v.x);
68+
}
69+
70+
public Loc y() {
71+
return new Loc(p.y, v.y);
72+
}
73+
74+
public Loc z() {
75+
return new Loc(p.z, v.z);
76+
}
77+
2278
}
2379

2480
@Override
2581
public Object part1() {
26-
var in = dayStream().map(s -> readString(s, "%n, %n, %n @ %n, %n, %n", Input.class)).toList();
27-
return "";
82+
var in = dayStream().map(s -> readString(s, "%n, %n, %n @ %n, %n, %n", Rock.class)).toList();
83+
return range(0, in.size())
84+
.mapToLong(i -> range(i + 1, in.size())
85+
.filter(j -> in.get(i).intersectsXY(in.get(j)))
86+
.count())
87+
.sum();
2888
}
2989

3090
@Override
3191
public Object part2() {
32-
return "";
92+
var in = dayStream().map(s -> readString(s, "%n, %n, %n @ %n, %n, %n", Rock.class)).toList();
93+
List<Function<Rock, Loc>> slicers = List.of(Rock::x, Rock::y, Rock::z);
94+
var collisionRecords = slicers.stream().flatMap(slicer -> in.stream().filter(
95+
candidate -> in.stream().filter(h -> !h.equals(candidate)).allMatch(h -> {
96+
var differenceInPosition = slicer.apply(h).x - slicer.apply(candidate).x;
97+
var differenceInVelocity = slicer.apply(h).y - slicer.apply(candidate).y;
98+
return differenceInVelocity != 0 && differenceInPosition % differenceInVelocity == 0 && differenceInPosition / differenceInVelocity < 0;
99+
}
100+
)).map(candidate ->
101+
in.stream().filter(h -> !h.equals(candidate)).map(h -> {
102+
var collisionTime = (slicer.apply(h).x - slicer.apply(candidate).x) / (slicer.apply(candidate).y - slicer.apply(h).y);
103+
return new Pair<>(collisionTime, h.positionAt(collisionTime));
104+
}).collect(toMap(Pair::a, Pair::b, (a, b) -> a, TreeMap::new)))
105+
).toList();
106+
var result = collisionRecords.get(0).entrySet().stream().limit(2).toList();
107+
var velocity = result.get(1).getValue().p().move(result.get(0).getValue().p().multiply(-1)).divide(result.get(1).getKey() - result.get(0).getKey());
108+
var magic = result.get(0).getValue().p().move(velocity.multiply(-result.get(0).getKey()));
109+
return magic.x + magic.y + magic.z;
33110
}
34111
}

0 commit comments

Comments
 (0)
0