Each year, a team spends months devising and testing problems.
Those problems are then released one at a time from December 1 to 25 as the
Advent of Code contest. Over the next few articles, let’s look at solutions to
some easy old problems from previous years.
The problems generally get harder as the month progresses, so these next few
articles will cover December 1’s problems from different years.
These problems, in theory, can be solved in any language, or
without any language at all, completely by hand (though I don’t recommend that).
What matters most to get your star rewards is that you get the right answer by
some legitimate means and that you have fun along the way.
In 2024—there’s a more elaborate story—you essentially have 2 lists of numbers
which are in the wrong order. Getting them into the proper order is essential,
as is pairing them up, subtracting them, and returning the grand total sum of
all those differences.
I’ll give you my approach:
Lists of numbers look something like this:
3 4
4 3
2 5
1 3
3 9
3 3
(This was the actual sample list that the contest gave me). I
cannot stress enough how important it is to start solving these problems both
from the sample list and by hand, before attempting to write any actual code,
in Java or whatever language you wish.
The problem is the following:
- We need to sort the left
- We need to sort the right
- We need to subtract the first sorted left from the first sorted right, then add that to the total
- We need to subtract the second sorted left from the second sorted right, then add that to the total
- And so on
My first thought was that we need to keep track of two
global lists—one for the left, and one for the right.
static List<Integer> leftList
= new ArrayList<>();
static
List<Integer> rightList = new ArrayList<>();
We need to read a file—be it that test file, or the actual
answer file, which is different for everyone, but which has 1000 numbers in
each list. Reading a file will allow us to populate leftList and rightList.
I cannot stress enough how important it is that you start by reading in a much
smaller file than the actual input file; this is why the organizers gave a much
smaller sample while explaining the problem.
readFile() is relatively straightforward, using BufferedReader and a loop:
private void readFile(String fileName) throws IOException {
BufferedReader reader = new BufferedReader(new FileReader(fileName));
String line;
while ((line
= reader.readLine()) != null) {
String[] arr = line.split("\t");
leftList.add(Integer.parseInt(arr[0]));
rightList.add(Integer.parseInt(arr[1]));
}
}
line.split() takes what’s called a regular expression (often
shortened just to RegEx—more on them in a future post) and splits the line
whenever it finds that regex delimeter. Here, the regex is “\t”, which means
any tab character.
Integer.parseInt() takes a String and converts it to an integer: the String “137”
becomes the integer 137, and so on.
Since the file looks like
10\t20
24\t2798
5789\t3387
etc.
It will be split, line by line, into an array with two elements, which, thanks
to parseInt(), will be integers.
10 and 20
24 and 2798
5789 and 3387
etc.
leftList gets the first element of that array, and rightList gets the second
element.
Lists
are Collections,
so they have access to the method Collections.sort()
for sorting their elements.
You can see it used here, in the main method:
public static void main(String[] args)
throws IOException {
Solution
solution = new Solution();
solution.readFile(args[0]);
sort(leftList); // this is a call to Collections.sort()
sort(rightList); // this is a call to Collections.sort()
int result =
solution.calculateDistance(leftList, rightList);
System.out.println("total distance: " + result);
}
The method that actually calculates the “distances” is quite
simple—most of this method is either comments or whitespace:
·
Start the distance counter at 0
·
In a loop, get the appropriate elements—with the
same index—from each list (the firsts, the seconds, the thirds, etc.)
·
Subtract them
·
Take the absolute value, because what you care about
is the distance between the numbers, not which list’s number is bigger or
smaller
·
Keep adding those distances to the counter
·
When you’ve processed the whole list, return the
value of the counter
Here it is in Java:
public int calculateDistance(List<Integer> leftList, List<Integer>
rightList) {
int
totalDistance = 0;
// pair the
smallest numbers together
// then the
next smallest
// etc.
// and
calculate the running sum of the absolute distances between the pairs
for (int i =
0; i < leftList.size(); i++) {
totalDistance += Math.abs(leftList.get(i) - rightList.get(i));
}
// return
the sum
return
totalDistance;
}
Now, we have all the logic we need to earn one star (out of
two) for this first problem in 2024.
There’s just one more thing we have to do: handle args[0].
Recall that the main method—which must be present as public static void main(String[]
args) in order for the program to be executable (the name of the array can change,
but nothing else in the signature).
In IntelliJ, next to the play button and the ladybug, there are 3 vertical dots.
Click on them. You should now see the following pop-up:
We care about, in this case, the “Program arguments” field. args
is an array, naturally, of arguments, which we pass to main(). It’s perfectly
fine not to pass anything most of the time, but now that we explicitly want to,
this is how you would get that done in IntelliJ.
The program has been written in such a way that args[0] is expected to be the
path to the file where the puzzle input is stored. Into that field, type in the
path. Click OK, and the dialog box will close. Run the program.
Here's all the code for part 1:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import static java.util.Collections.*;
public class Solution {
static
List<Integer> leftList = new ArrayList<>();
static
List<Integer> rightList = new ArrayList<>();
public static
void main(String[] args) throws IOException {
Solution
solution = new Solution();
solution.readFile(args[0]);
sort(leftList);
sort(rightList);
int result =
solution.calculateDistance(leftList, rightList);
System.out.println("total distance: " + result);
}
private void
readFile(String fileName) throws IOException {
BufferedReader reader = new BufferedReader(new FileReader(fileName));
String line;
while ((line
= reader.readLine()) != null) {
String[] arr = line.split("\t");
leftList.add(Integer.parseInt(arr[0]));
rightList.add(Integer.parseInt(arr[1]));
}
}
public int
calculateDistance(List<Integer> leftList, List<Integer> rightList)
{
int
totalDistance = 0;
// pair the
smallest numbers together
// then the
next smallest
// etc.
// and
calculate the running sum of the absolute distances between the pairs
for (int i =
0; i < leftList.size(); i++) {
totalDistance += Math.abs(leftList.get(i) - rightList.get(i));
}
// return
the sum
return
totalDistance;
}
}
