Advent of Code 2024
It is December again and that means it is time for the Advent of Code. Due to my workload and family obligations I will probably not be able to get very far this year, but still I wanted to write a post about it.
This year I am using Java, together with my students. My goal is to write as modern as possible Java, which means using streams and new language constructs where possible.
Day 1 {#day-1}
In day 1 we are parsing 2 lists of numbers, with the lists printed vertically. This means each line has 2 numbers, one for list one and the other for list two. To parse these data structures I used a very nice stream where I map each line onto a String[] using split.
To be sure that the input is valid, the peek method allows you to check if the result is what you intended, and otherwise an exception will terminate everything. From here I map the String[] into a Pair record which holds the 2 numbers. Streaming over the resulting pairs the left and right lists can be extracted quite easily.
I loved this approach, it is very straightforward and does not have a lot of control flow.
@Override
public List<List<Integer>> parseInput(List<String> input) {
var pairs = input.stream()
.map(s -> s.split("\\s+"))
.peek(parts -> {
if (parts.length != 2)
throw new IllegalArgumentException("Invalid input format");
})
.map(parts -> new Pair<>(Integer.parseInt(parts[0]), Integer.parseInt(parts[1])))
.collect(Collectors.toList());
var left = pairs.stream()
.map(Pair::left)
.collect(Collectors.toList());
var right = pairs.stream()
.map(Pair::right)
.collect(Collectors.toList());
return List.of(left, right);
}
Solving the problem with these lists was quite easy. In part 2 there was a need for a frequency table of a list. I also found a very nice solution to that problem using the groupingBy method from Collectors.
input.get(1).stream()
.collect(Collectors.groupingBy(n -> n, Collectors.counting()));
Day 2 {#day-2}
I really liked day 2, the first part was quite straightforward. You have to identify increment or decrement only lists and apply some conditions to them.
Part 2 was much more interesting, here you have to account for fault tolerance. In the Python implementations that were posted the common solution is to concatenate 2 parts of the array and then rerun the validation logic.
Using streams we can something very similar. First we use an IntStream to iterate over every int[] (report). Then for every int in that report, we construct a new array by filtering out the index of the current item. After that it is a simple case of determining increment or decrement and applying the conditional logic.
Suppose you have a list of
[1,2,4,7], while iterating it will first hit index0, thefilterwill prevent that entry from continuing. Next1through3will continue and as a result oftoArray()a new array will be constructed with only those items.
x == 0
| map ------.
v ------- v
[1, 2, 4, 7] [2,4,7]
input.stream()
// Loop over the list
.filter(in -> IntStream.range(0, in.length) // take a report
// for every entry in that int[]
.anyMatch(x -> {
// create a new list, excluding the one we are on now
int[] c = IntStream.range(0, in.length)
.filter(i -> i != x)
.map(i -> in[i])
.toArray();
boolean allInc = IntStream.range(0, c.length - 1)
.allMatch(i -> c[i] <= c[i + 1]);
boolean allDec = IntStream.range(0, c.length - 1)
.allMatch(i -> c[i] >= c[i + 1]);
boolean good = IntStream.range(0, c.length - 1)
.allMatch(i -> Math.abs(c[i] - c[i + 1]) >= 1 &&
Math.abs(c[i] - c[i + 1]) <= 3);
// matching the condition
return (allInc || allDec) && good;
})
)
.count();
My first solution was nothing like this, but after refining it I am very happy with how clean it came out.
Day 3 {#day-3}
This was the traditional easy puzzle after a more complicated one. Basically simple parsing for which I used regular expressions. Nothing special, on to day 4.
Day 4 {#day-4}
For day 4 I solved the first part with an over engineered path finding solution, which turned out to be quite the overkill, but extremely fun to program.
I really like the pattern in use, below is some of the code of it. First you create a Deque that holds the work, then you load it up with the initial starting points. In the case of the puzzle these are the location of the X characters.
From there you just loop over the work, taking a partial solution and seeing if any cells around it will lead to another partial solution, so from XM to XMA and on the next iteration to XMAS. The dx is a collection of Coord that indicate valid movements across the board.
Deque<Path> work = new ArrayDeque<>();
// Load initial points
for (int y = 0; y < input.length; y++) {
for (int x = 0; x < input[y].length; x++) {
if (input[y][x] == 'X') {
work.add( new Path(List.of(new Coord(x,y)), "X", null) );
}
}
}
// Process each outstanding point..
while (!work.isEmpty()) {
var path = work.pop();
for (Coord d : dx) {
if (path.dir() != null && path.dir != d) {
continue;
}
var newCoord = lastStep.add(d);
// Ensure this is a valid point on the grid
if (newCoord.x() >= 0 && newCoord.x() < input[0].length &&
newCoord.y() >= 0 && newCoord.y() < input.length) {
// ... create new paths and string based on location
// Check if we have an end case, else add it to the work
if (target.equals(xmas)) {
matches.add(newPath);
} else if (target.startsWith(xmas)) {
work.add(newPath);
}
}
}
}
A more straightforward approach, which was actually needed for part 2, is to just try to solve it in one step. First you iterate over both y and x coordinates looking for an X, just as above. When you find one, iterate over [-1, 0, 1] on both the x and y axis-es, using dy and dx for the direction. If both direction are 0, we continue as it would give the current position. The beauty of this approach is that you can move outward in steps, x + 3 * dx will give you a value 3 cells in the give direction. From there it is a simple matter of checking if we are in bounds and if the letters spell MAS.
for (int y = 0; y < input.length; y++) {
for (int x = 0; x < input[y].length; x++) {
if (input[y][x] != 'X') continue;
for (int dy = -1; dy <= 1; dy++) {
for (int dx = -1; dx <= 1; dx++) {
if (dy == dx && dx == 0) continue;
if (!(0 <= y + 3 * dy && y + 3 * dy < input.length &&
0 <= x + 3 * dx && x + 3 * dx < input[y].length)) continue;
if (input[y+1*dy][x+1*dx] == 'M' &&
input[y+2*dy][x+2*dx] == 'A' &&
input[y+3*dy][x+3*dx] == 'S') {
matches++;
}
}
}
}
}
For part 2 a similar approach can be used, however the order is not important. So I chose to create a List and then check against a target list with the containsAll method, it does not care about order.
var x1 = List.of(input[y-1][x-1], input[y][x], input[y+1][x+1]);
var x2 = List.of(input[y-1][x+1], input[y][x], input[y+1][x-1]);
if (x1.containsAll( target ) && x2.containsAll( target )){
matches++;
}
Another reminder to not over engineer at the start.
Day 5 {#day-5}
Another fun puzzle, when I initially read it my mind jumped to graphs. There is a 2 part input, the first part being a list of rules, numbers that are only valid when they are placed in front of other numbers.
The second part of the input is a list of report structures. The first quest was to validate the reports and find only the valid ones.
My first attempt, in part 1, was to take the rules for a number (a List<Integer>) and see if there is an anyMatch of the sublist before it using order::contains. Basically if the pages is 75,97,47,61,53 and the rule 97|75 (97 should be before 75), the the loop will iterate over the pages, and check to see if [75] is in the list of rules for 97.
boolean isValid(List<Integer> pages, Instructions input) {
var valid = true;
for (int i = 0; i < pages.size(); i++) {
var order = input.order().get(pages.get(i));
if (order != null) {
var hasAny = pages.subList(0,i+1).stream().anyMatch(order::contains);
if (hasAny) {
valid = false;
}
}
}
return valid;
}
Part 2 had us fixing the broken pages. After some initial magic with arrays I figured out it is a basic sorting problem. In Java you can use Comparator implementations to create custom sorting rules, as long as it responds with -1,0,1 for to the left, the same, to the right. So the lambda Comparator takes a left hand side and right hand side value, retrieves the rules for the left hand side (if null it is equal 0) and checks to see if the right hand side is in the ruleset (-1). If all checks fail, the value should go to the right hand side.
var answer = 0L;
for (var pages : input.pages()) {
var valid = isValid(pages, input);
var work = new ArrayList<>(pages); // pages is immutable
if (!valid) {
Collections.sort(work, (lhs, rhs) -> {
var order = input.order().get(lhs);
if (order == null) return 0;
if (order.contains(rhs)) return -1;
return 1;
});
answer += work.get(work.size()/2);
}
}
A surprisingly easy solution to a messy problem when you want to implement it yourself.
Day 6 {#day-6}
Traditionally the Friday puzzles seem to be somewhat more challenging, this Friday is no exception. We are given a challenge similar to sliding puzzle games.
Instead of sliding over ice we are to map the movements of a guard to ensure we can move safely through the area. For part 1 there was nothing too exciting, just move the guard over the floor and track the places visited. Depending on your loop you might accidentally avoid an edgecase that will show up in part 2.
Lets take a look at the loop:
while (inBounds) {
visited.add(start);
var next = start.add(delta.get(sign));
if (!next.inBound(0, input[0].length, 0, input.length)) {
inBounds = false;
continue;
}
if (input[next.y()][next.x()] == '#') {
sign = turns.get(sign);
continue;
}
start = next;
}
While we are *in bounds* we keep moving, adding each step into the visited list. We then get the next position by retrieving the delta (a lookup table of coordinates such as -1,0, which indicate that the guard will move -1 on the x-axis and 0 on the y-axis). If we are out of bounds, flip the switch and break out of the while loop, if the next position is an obstacle, #, we set the sign to the 90 degree turned version (another lookup table) and rerun the loop. If, for some reason, you continue checking and validating at this point you might miss the edge-case that turning can result in facing another wall. When all the conditions are checked, simply reset the start variable to the next coordinates and move on.
Part 2 becomes much more interesting; we are to find infinite loops by placing exactly 1 extra obstacle. Intuitively you will remark that the obstacle can only be placed on one of the cells that were visited in part 1. This already eliminates part of the board. From here you can loop over the list of coordinates, place an obstacle and let the guard run its route. When you visit a coordinate twice in *the same direction* you know you are in a loop.
I looked for a “smart” solution, but the brute force is done in less then 2 seconds. So I will leave it at this, but somehow feel there might be more optimizations possible.
Day 7 {#day-7}
The end of week 1, and easier then the Friday puzzle. We are given a list of numbers per line that we need to either add or multiply to get to a target number. I chose to use some recursion to solve this problem. Each iteration of the recursion will reduce the array of numbers using one of the operations.
In the end the list of numbers will be reduced to either the target number, or something else. So the base case checks to see if it was successful.
If the base case is not hit, the first recursion is to add the numbers. A trick here is to use a LongStream to range over 1 to the end, mapping the numbers. If number 1 is mapped, we add the number at position 0 to reduce the array.
The second case applies the multiplication in the same way.
The third case (part 2) is to concatenate the numbers, this is easil done through number + "" + number in java, coercing the numbers into a String and then using Long.valueOf() to read the value again.
boolean isValid(long target, long[] numbers, boolean third) {
if (numbers.length == 1) return target == numbers[0];
if (isValid(target, LongStream.range(1, numbers.length)
.map(i -> {
if (i == 1) return numbers[0] + numbers[1];
return numbers[(int)i];
})
.toArray(), third)) return true;
if (isValid(target, LongStream.range(1, numbers.length)
.map(i -> {
if (i == 1) return numbers[0] * numbers[1];
return numbers[(int)i];
})
.toArray(), third)) return true;
if (third && isValid(target, LongStream.range(1, numbers.length)
.map(i -> {
if (i == 1) return Long.valueOf(numbers[0] + "" + numbers[1]);
return numbers[(int)i];
})
.toArray(), third)) return true;
return false;
}
One last trick is to use the Stream feature to filter the list, mapping each object to a long value and summing.
@Override public Long solver1(List<Calibration> input) {
return input.stream().filter(i -> isValid(i.target, i.numbers, false)).mapToLong(cal -> cal.target).sum();
}
Day 8 {#day-8}
Day 8 has us back in history staring at antennas. The description was quite cryptic, but reading it carefully you learn that the necessary step is to find the difference between a pair of coordinates and then extrapolate the path inside the bounds of the grid.
To read the grid into a structure I used a simple nested loop, adding a new list to the map if it is absent, then adding the new coordinate for the antenna.
for (int r = 0; r < gridH; r++) {
for (int c = 0; c < gridW; c++) {
char ch = input.get(r).charAt(c);
if (ch != '.') {
antennas.computeIfAbsent(ch, k -> new ArrayList<>()).add(new Coord(c, r));
}
}
}
We then have to find the antinode for the point which, for the pair, is just a single difference step from the antenna. Interestingly we need to count the *unique* antinodes. Whenever you get such a requirement, always think about using a Set for storage.
Getting the pairs is straightforward, and we have done it earlier in the series already. The first loop starts at 0 and ends the element before the end, size - 1. The inner loop starts at current pos + 1 and ends at the size of the list.
for (int p = 0; p < coords.size() - 1; p++) {
for (int n = p + 1; n < coords.size(); n++) {
Then just compute the difference and add the antinode when it is in bounds.
var antinode1 = cur.add(cur.diff(next));
var antinode2 = next.add(next.diff(cur));
In part 2 the path needs to be extrapolated until it goes out of bounds. This can easily be wrapped in its own method.
void addAntinodesInDirection(Set<Coord> antinodes, Coord start, Coord diff) {
var current = start;
while (true) {
var next = current.add(diff);
if (!next.inBound(0, gridW, 0, gridH)) {
break;
}
antinodes.add(next);
current = next;
}
}
A pretty straightforward problem to solve, on to tomorrow!
Day 9 {#day-9}
For me this was a hard day. We are given a list of numbers that we use to fragment files on a disk. The first part of the puzzle was quite straightforward, create a list that holds the file ids and spaces and just follow the rules.
for (int i = 0; i < input.length(); i++) {
for (int j = 0; j < input.charAt(i)-'0'; j++) {
if (i%2 == 0) {
disk.add(id);
} else {
disk.add(null);
}
}
if (i%2 == 0) {
id++;
}
}
From there just create 2 pointers, one on the left and one on the right. The left tracks the empty space and the right tracks the file ids that we want to put in the empty space. The important thing in Java is to make the implementation of the list a LinkedList. This allows for little-overhead reshuffling of the list.
var l = 0;
var r = disk.size() - 1;
while (l < r) {
if (disk.get(l) != null) {
l++;
continue;
}
if (disk.get(r) == null) {
r--;
continue;
}
disk.set(l, disk.get(r));
disk.set(r, null);
l++;
r--;
}
Part 2 became much harder, we are not to find space for the blocks of files instead of fragments. I first tried the same approach, but it took forever. I then saw the error of my ways and decided to use a lookup table for the empty spaces. This table maps the empty spaces of size N, in the below example 1 and 2, to a list of start/end coordinates.
1 = [1,1] [2,2]
2 = [3,4] [6,7]
The list of coordinates needs to remain sorted, so I used a PriorityQueue for it. Then it is just a matter of determining the size of the file under the r pointer by looping over it until we hit another id, and then looking up the most left candidate of the empty spaces.
// Gets all candidates that will fit the file
for (int i = bs; i < 10; i++) {
var earliest = free[i].peek();
if (earliest != null && earliest < r) {
candidates.add(new Candidate(i, earliest));
}
}
if (candidates.isEmpty()) {
return null;
}
// Sort based on the index (most left first)
candidates.sort((lhs, rhs) -> {
return lhs.idx() - rhs.idx();
});
var can = candidates.getFirst();
free[can.size()].remove();
The final solution runs in a matter of milliseconds, so I am quite happy with that.
Day 10 {#day-10}
Finally a depth first / breath first path seeker! We need to identify a trail that leads to a summit, or rather all trails that lead to the summit. Part 1 wants to know the score (how many summits can a path reach) and part 2 its rating (how many trails are there that reach a summit). This is pretty straightforward in the sense that you create a Queue and put the start of the trail in, then for each direction you construct a more complete path.
As always it is important to check for bounds and if the path is incremental (business rule). If the new path is actually at the summit, add it to the finished paths. If it is not, try to complete it.
Trail solve(char[][] grid, Coord zero) {
var q = new ArrayDeque<List<Coord>>();
q.add(List.of(zero));
List<List<Coord>> paths = new ArrayList<>();
while (!q.isEmpty()) {
var current = q.removeFirst();
for (Coord d : zero.directNeighbors()) {
var last = current.getLast();
var nc = last.add(d);
if (!nc.inBound(0,grid[0].length, 0, grid.length)) continue;
if (grid[nc.y()][nc.x()] != grid[last.y()][last.x()] + 1) continue;
var newPath = new ArrayList<>(current);
newPath.add(nc);
if (grid[nc.y()][nc.x()] == '9') {
paths.add(newPath);
} else {
q.addLast(newPath);
}
}
}
var score = paths.stream().map(l->l.getLast()).collect(Collectors.toSet()).size();
var rating = paths.size();
return new Trail(score, rating);
Day 11 – one to remember {#day-11-one-to-remember}
For the last couple of days the discussion forums have been full with memes about brute forcing the answer. Up to now you could really do so. I have one colleague who wrote a nice brute force for Day 6 that took several minutes, but it did work. Personally I am not a fan of the brute forcing approach, I like to make it more elegant when possible.
Today is this years first Lanternfish type of problem, one where the problem space becomes so large that your computer is not able to brute force it due to memory constraints. It calls for a more elegant solution.
Part 1 and part 2 are basically the same, the difference is the amount of iterations for the problem. In this case we have some rules in which rocks change and split up. We are tasked to find the amount of rocks after 25 and 75 iterations. The first is do-able with a brute force approach, the second is not.
The rules are straightforward, but the solution to the problem space might not be. The trick is to use something called memoization.
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls to pure functions and returning the cached result when the same inputs occur again.
So, basically we store results of method calls. Lets first look at my solution. It is a recursive function that takes a number and the number of iterations to apply to it.
if (iterations == 0) return 1;
var cache = new Cache(number,iterations);
if (memo.containsKey(cache)) {
return memo.get(cache);
}
if (number == 0) {
long l = ways(1, iterations - 1, memo);
memo.put(cache, l);
return l;
}
String s = "" + number;
int l = s.length();
if (l % 2 == 0) {
long c = ways(Long.parseLong(s.substring(0,l/2)), iterations-1, memo) + ways(Long.parseLong(s.substring(l/2,l)), iterations-1, memo);
memo.put(cache, c);
return c;
}
long c = ways(number * 2024, iterations-1, memo);
memo.put(cache, c);
return c;
For this call the result is stored in a memo, a simple HashMap that stores the method arguments in a CacheKey and then stores the count, the result of the recursive call. What happens here is that there might be many different calls to this method, such as (9,23). In this case the number 9 has 23 iterations to go. By computing the result once and then storing the computed value we save the time of doing the same calculations many other times.
This was a really fun and relatively quick challenge, greatly enjoyed it!
Day 12 – Garden Groups {#day-12-garden-groups}
This day had me stumped for quite a time. The puzzle starts off with a simple question; group the garden (grid) into areas that are the same and count the fences required. A simple flood fill type of solution works very well here.
Whenever a neighbor is not the same type (or we are the edge), a fence is required. If it is the same type, add it to the queue for further processing.
for (int r = 0; r < input.length; r++) {
for (int c = 0; c < input[r].length; c++) {
var start = new Coord(c, r);
if (!seen.add(start)) {
continue;
}
var queue = new ArrayDeque<Coord>();
queue.add(start);
var cells = new HashSet<Coord>();
int perimeter = 0;
char fenceType = input[r][c];
while (!queue.isEmpty()) {
Coord cell = queue.poll();
cells.add(cell);
for (Coord neighbor : Coord.directNeighbors()) {
Coord next = cell.add(neighbor);
if (!next.inBound(0, input[0].length, 0, input.length) ||
input[next.y()][next.x()] != fenceType) {
perimeter++;
} else if (seen.add(next)) {
queue.add(next);
}
}
}
fences.add(new Fence(perimeter, cells));
}
}
The next part had me going for a little bit. Instead of the area or fences the elves need the sides counted. This turns out to be quite a thing until it becomes clear that counting corners also works.
Lets say the below map is our grid. When looking at the A in cell 0,2 it is possible to check if it is a corner by checking that the cell above it and the cell to the right are not the same. The same goes for the cell below and the cell to the right.
{{< figure src=“/ox-hugo/corners.png” >}}
A neat trick to find the sides to an area. The code turned out to be relatively easy:
for (var cell : fence.cells()) {
char curr = input[cell.y()][cell.x()];
for (int ud : new int[]{-1, 1}) {
for (int lr : new int[]{-1, 1}) {
int ny = cell.y() + ud;
int nx = cell.x() + lr;
boolean outOfBoundsY = ny < 0 || ny >= input.length;
boolean outOfBoundsX = nx < 0 || nx >= input[0].length;
if ((outOfBoundsY || input[ny][cell.x()] != curr) &&
(outOfBoundsX || input[cell.y()][nx] != curr)) {
corners++;
} else if (!outOfBoundsY && !outOfBoundsX &&
input[ny][cell.x()] == curr &&
input[cell.y()][nx] == curr &&
input[ny][nx] != curr) {
corners++;
}
}
}
On to Friday the 13th!
Day 13 – Claw Contraption {#day-13-claw-contraption}
Today was quite something. We have claw machines that have 2 buttons. The buttons move the arm a set space on the x and y coordinates. Both buttons have a different value for the cost and we are tasked to find the cheapest path to a prize on some distant x and y location.
My initial solution was naive and used dynamic programming to solve it. It did not adhere to the rule every problem has a solution that completes in at most 15 seconds on ten-year-old hardware. So eventually I found a solution (thanks Hyperneutrino!) that uses math to solve this problem.
Basically we are trying to find the amount of x and y movements both the A button (indicated by S) and the B button (indicated by T) have to make in order to get to the prize x and y values.
axS + bxT = px
ayS + byT = py
We can make these equations the same by multiplying with by and bx. We do this so we can remove the B button from the equation and solve A.
axbyS + bxbyT = pxby
aybxS + bybxT = pybx
Now bxbyT == bxbyT
This can then be rewritten in a single equation, from which we can isolate A.
axbyS - aybxS = pxby - pybx
(axby-aybx)S = pxby - pybx
Now we can divide by axby - aybx and get our solution for A. We have to ensure the input is never 0 to prevent division by zero. In the code we can check this by checking that ax * by == ay * bx never occurs.
S = pxby - pybx
-----------
axby - aybx
As we now have the A button value, we can also solve the B button.
axS + bxT = px
bxT = px - axS
T = px-axS
------
bx
In code the solution looks very simple. Notice the ca%1==0 && cb%1==0 check to ensure we do not allow for fractional steps.
private long solve(double ax, double ay, double bx, double by, long px, long py) {
long answer = 0L;
double ca = (px * by - py * bx) / (ax * by - ay * bx);
double cb = (px - ax * ca) / bx;
if (ca % 1 == 0 && cb % 1 == 0) {
answer += (long) (ca*3) + cb;
}
return answer;
}
Day 14 – Restroom redoubt {#day-14-restroom-redoubt}
Today we are back at Easter Bunny HQ, looking for a restroom. We are given a collection of robots, their current position on a grid and their velocity. The question becomes, where are they after 100 iterations (seconds)? An interesting part of this question is that the robots wrap around the grid.
This mechanic allows for very easy calculation of the final coordinates, as (x + vx * 100) % width will give us the final position, instead of having to go through all the calculations.
Interestingly, Java does not really like negative numbers in the modulo operator. For example, -102 % 11 yields -3 while it should yield 8 for it to be useful in our case. So, when the number is negative, just add the width to it.
for (var robot : robots) {
int newX = (robot.start.x() + robot.vel.x() * 100) % width;
if (newX < 0) newX += width;
int newY = (robot.start.y() + robot.vel.y() * 100) % height;
if (newY < 0) newY += height;
positions.merge(new Coord(newX, newY), 1, Integer::sum);
}
Part 2 was a horrible puzzle. There was no clue what to do in order to get this:
{{< figure src=“/ox-hugo/day14.png” >}}
I finally solved it by looking at the field when all robots are on a unique position. I also have seen solution where the minimum safety value is found. The problem description was:
During the bathroom break, someone notices that these robots seem awfully similar to ones built and used at the North Pole. If they're the same type of robots, they should have a hard-coded Easter egg: very rarely, most of the robots should arrange themselves into a picture of a Christmas tree.
What is the fewest number of seconds that must elapse for the robots to display the Easter egg?
Maybe if it had said “very rarely, but when all the robots arrange themselves”, but then again, how are you supposed to know that it means non-overlapping.
Love the Christmas tree though.
Day 15 – Warehouse Woes {#day-15-warehouse-woes}
Yay, the Lanternfish have made an appearance! Sadly this puzzle had me quite stumped for a while. I had to rewrite my solution 2 times in order to get it right.
First, let me explain. We are still not finding the historian (whom I think is just Eric in a costume). Instead we are on a side-quest helping our fishy friends with robots in their warehouses. The first puzzle is straightforward; move the player around, moving objects that you run into.
When we have that sorted we are sent to a second warehouse. This time the boxes that we move are twice as large, but the robot is still the same size. This means we get into situations as the following example:
######
# #
# [] #
# @ #
######
Here the player can move up, but we are only hitting one side of the box. We have to take into account that we need to move the other part along as well. Even more complicated, we can get into the following situation.
######
#[] #
#[][]#
# [] #
# @ #
######
In this situation we can not move, even though the 2nd box on the middle layer might think we can, as it has a white-space above it.
I worked on arrays for a while, but eventually went for a more “Java” solution and create the factory as objects. Using the objects it is possible to attack the problem more in a “game engine” type of way, by making each object react to the interaction.
My code is horrible not-optimized, I apologize for that right away, but it gets the job done :D
Firstly, I split the process out into two segments, first to see if we can move, then to actually move. Side note: I should really use a lookup table for the coordinate to find the objects instead of looping over it.
The objects are simple POJOs, all extending the aptly named Thing.
class Player extends Thing {
public Player(Coord start, Coord end) {
super(start, end);
}
}
class Wall extends Thing {
public Wall(Coord start, Coord end) {
super(start, end);
this.canMove = false;
}
}
class Box extends Thing {
public Box(Coord start, Coord end) {
super(start, end);
}
}
Thing has all the logic, with canMove() and move basically doing the same thing, except for move actually moving the objects into a new coordinate. Only if we have a space as neighbor, or if *all* of the neighbors can move, only then do we move the current object.
boolean move(List<Thing> factory, Coord direction) {
if (!canMove)
return false;
Coord nsp = start.add(direction);
Coord nep = end.add(direction);
Set<Thing> hits = new HashSet<>();
for (var t : factory) {
if (t == this)
continue;
if (t.collidesWith(nsp))
hits.add(t);
if (t.collidesWith(nep))
hits.add(t);
}
if (hits.size() == 0) { // space, so we can move ourself
this.start = this.start.add(direction);
this.end = this.end.add(direction);
return true;
}
if (hits.stream().allMatch(t -> t.move(factory, direction))) {
this.start = this.start.add(direction);
this.end = this.end.add(direction);
return true;
}
return false;
}
Collision is checked against both the left and right hand side of the object. Meaning that we can easily handle boxes of size 2.
boolean collidesWith(Coord c) {
if ((start.x() == c.x() && start.y() == c.y()) || (end.x() == c.x() && end.y() == c.y())) {
return true;
}
return false;
}
Much more work then I thought it would be, but a nice solution anyways.
More to come {#more-to-come}
[This article will be update with more days]