Advent of Code 2022 Day 1 part 2

 Like most AoC second-star problems, this one builds on the first star, and, actually, in this case, requires only minimal changes.

The second star, accessible only if you have completed the first, asks this time for the total consumed by the three hungriest elves—the champion you found for the first star, plus the second- and third-place elves.

That can be done with this very simple method, which, including comments and white space, is not even 10 lines:

private static int getSumOfTopNElements(List<Integer> elfCalories, int maxIndex) {
     int topNElfCals = 0;
     // given a sorted list, take the running sum of the elements up to maxIndex
     for (int i = 0; i < maxIndex; i++) {
          topNElfCals += elfCalories.get(i);
     }
     // return that sum
     return topNElfCals;
}

maxIndex in this case is always 3, and a good IDE like IntelliJ (even the Community Edition) will flag this. But I have a reason for building it like this, and not hardcoding the three.

Building the method like this, and allowing any index to be passed—even if we know that, for the elves’ purposes, that index will always be 3—allows the code to be much more portable, and called on by someone else in totally different circumstances who needs to find the total of the first few elements of a sorted list of Grades or Salaries or SquareFootages or what have you. This way, you do not care what the list is for—it could be elves and their diets, or anything else—nor do you care about which index you go to.

There’s another reason for writing like this over hardcoding a 3 or another number: if you hard-code it, you’ll have to remember to find and change every hard-coded instance, in order not to have inconsistencies, if you ever want more or less than the top 3. But if you pass in the 3 (or any other number) dynamically as we have done here, you make it so that the number can change freely without ever having to make those changes—or, by greatly diminishing the number of places where code would have to change if you wanted to modify the logic. It is a good idea to write as generically as possible, hardcoding as little as possible, because each time you hard-code something, you make your code a little more restrictive, harder to maintain, and harder to understand.

 Here's the whole implementation:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ElfCalorieCounter {

     public static void main(String[] args) throws IOException {

          // create a reader object to read through the input file
          BufferedReader reader = new BufferedReader(new FileReader("C:\\Users\\andre\\IdeaProjects\\JavaPractice\\src\\main\\java\\elfCalories.txt"));

          // calculate all the calorie counts of the elves
          List<Integer> elfCalories = calculateCalories(reader);
          reader.close();


          // sort, then reverse the list
          prepareList(elfCalories);

          // find the sum of the top 3 best-performing elves
          int top3Cals = getSumOfTopNElements(elfCalories, 3);

          // display the calorie counts of all elves
          System.out.println("Calories per elf: " + elfCalories);

          // display the calorie count of the 3 most productive, summed together
          System.out.println("The calories collected by the top 3 most productive elves: " + top3Cals);
          System.out.println("elfCalories.size() = " + elfCalories.size());
     }

     private static int getSumOfTopNElements(List<Integer> elfCalories, int maxIndex) {
          int topNElfCals = 0;
          // given a sorted list, take the running sum of the elements up to maxIndex
          for (int i = 0; i < maxIndex; i++) {
               topNElfCals += elfCalories.get(i);
          }
          // return that sum
          return topNElfCals;
     }

     private static void prepareList(List<Integer> elfCalories) {
          Collections.sort(elfCalories);
          Collections.reverse(elfCalories);
     }

     /**
      * @param reader BufferedReader object reads file line by line
      * @return a list containing the calorie counts of various elves
      */
     private static List<Integer> calculateCalories(BufferedReader reader) throws IOException {
          String line;
          List<Integer> elfCalories = new ArrayList<>();
          int totalCalories = 0;

          // while there are still lines of calories
          while ((line = reader.readLine()) != null) {
               int calories;
               // when you hit a blank line, a given elf is done collecting calories
               // add its total to the list and zero out the total to get ready for the next elf
               if (line.isEmpty()) {
                    elfCalories.add(totalCalories);
                    totalCalories = 0;
               }
               // but if the same elf is still collecting calories, then the elf's running total of calories
               // is how many calories they've collected up until now, plus the calories they just collected on this line
               else {
                    calories = Integer.parseInt(line);
                    totalCalories += calories;
               }
          }
          // return a list of calorie counts where 1 number = the production of 1 elf
          return elfCalories;
     }
}

Advent of Code 2022 Day 1 part 1

 This time, we’re going to look at the first submission—for which I only got one star at the time, not both—from the first day of the 2022 contest. (Again, you can do these puzzles whenever you want once they’ve been made public.)

In 2022, the problem was quite straightforward:

• There are a lot of elves, and those elves eat meals and ingest calories
• We know how many calories are in each food eaten by each elf
• We have a way to delimit one elf from another in the input
• We want to know how many calories the elf who ate the most consumed across all meals eaten by that elf

As with the previous Advent of Code articles, the best place to start is always with the sample they give you, which on that day was:

1000
2000
3000

4000

5000
6000

7000
8000
9000

10000

The rules of the problem dictate that this means there are 5 elves:

a.       One ate 3 meals of 1000, 2000, and 3000 calories

b.       One ate 1 meal of 4000 calories

c.       One ate 2 meals of 5000 and 6000 calories

d.       One ate 3 meals of 7000, 8000, and 9000 calories

e.       One ate 1 meal of 10000 calories

At this small scale, the problem is easy to solve, even relying on mental math alone: Which elf ate the most? Naturally, the elf who ate 7000+8000+9000=24000 calories (since the others ate 6000, 4000, 11000, 10000)

The first order of business, like in every AoC puzzle, is to read the input file:

This particular year, unlike the more recent args[0] solution, I actually passed in the path directly, without going through args, like this:

BufferedReader reader = new BufferedReader(new FileReader("C:\\Users\\andre\\IdeaProjects\\AdventOfCode\\elf-input.txt"));

Passing the path like this, or passing the path in through args, as long as both are done correctly, are equivalent methods

The key method is the following:

    private static List<Integer> calculateCalories(BufferedReader reader) throws IOException {

          String line;

          List<Integer> elfCalories = new ArrayList<>();

          int totalCalories = 0;

 

          // while there are still lines of calories

          while ((line = reader.readLine()) != null) {

               int calories;

               //When you hit a blank line, a given elf is done collecting calories

               // add its total to the list and zero out the total to get ready for the next elf

               if (line.equals("")) {

                    elfCalories.add(totalCalories);

                    totalCalories = 0;

               }

               // but if the same elf is still collecting calories, then the elf's running total of calories

               // is how many calories they've collected up until now, plus the calories they just collected on this line

               else {

                    calories = Integer.parseInt(line);

                    totalCalories += calories;

               }

          }

          // return a list of calorie counts where 1 number = the production of 1 elf

          return elfCalories;

     }

The key to solving the problem is making explicit what we know is obvious as human beings—that a blank line separates elf A from elf B from elf C, and so on. That is, when you see a blank line, stop attributing those calories to the current elf, and instead create a new elf to start assigning them to.

Then, since we need the top elf, we need the list to be sorted so that the top elf’s calorie count is somewhere predictable.

So it's perfectly reasonable for      private static void prepareList(List<Integer> elfCalories) {} to include the following line:

          Collections.sort(elfCalories);

But there’s actually a hidden problem with that—the best-performing elf is now last, not first, on account of the default sorting order built into Collections.sort(). However, this problem is easily fixed by using another method in Collections—namely, Collections.reverse(). Calling sort() and then calling reverse() gets us the list sorted in an order such that the hungriest elf is first.
 
The sample has 5 distinct elves; the real problem file has 250. As with other AoC problems, it’s possible to solve this elf problem in any language, or none at all—but I would strongly caution against a purely manual solution simply on account of how long it would take.

All together, the solution looks like:


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ElfCalorieCounter {

     public static void main(String[] args) throws IOException {

          // create a reader object to read through the input file
          BufferedReader reader = new BufferedReader(new FileReader("C:\\Users\\andre\\IdeaProjects\\JavaPractice\\src\\main\\java\\elfCalories.txt"));

          // calculate all the calorie counts of the elves
          List<Integer> elfCalories = calculateCalories(reader);
          reader.close();


          // sort, then reverse the list
          prepareList(elfCalories);


          //Display the calorie counts of all elves
          System.out.println("Calories per elf: " + elfCalories);
     }

     private static void prepareList(List<Integer> elfCalories) {
          Collections.sort(elfCalories);
          Collections.reverse(elfCalories);
     }

     /**
      * @param reader BufferedReader object reads file line by line
      * @return a list containing the calorie counts of various elves
      */
     private static List<Integer> calculateCalories(BufferedReader reader) throws IOException {
          String line;
          List<Integer> elfCalories = new ArrayList<>();
          int totalCalories = 0;

          // while there are still lines of calories
          while ((line = reader.readLine()) != null) {
               int calories;
               //When you hit a blank line, a given elf is done collecting calories
               // add its total to the list and zero out the total to get ready for the next elf
               if (line.isEmpty()) {
                    elfCalories.add(totalCalories);
                    totalCalories = 0;
               }
               // but if the same elf is still collecting calories, then the elf's running total of calories
               // is how many calories they've collected up until now, plus the calories they just collected on this line
               else {
                    calories = Integer.parseInt(line);
                    totalCalories += calories;
               }
          }
          // return a list of calorie counts where 1 number = the production of 1 elf
          return elfCalories;
     }
}

 

 

Advent of Code 2024 Day 1 part 1

 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;

     }

} 

Sorting objects with Comparable or Comparator

 Some things—primitives—are really easy to sort. 1 comes before 2 comes before 3; z comes before q comes before c comes before a (if we’re going in reverse); and so on. But not everything we want to sort is so easy. Suppose, for example, we wanted to sort Students. Students have many properties—names, IDs, years, GPAs, majors, and so on. How do we determine who comes first? What criteria matter? Does a senior with a low GPA come before a junior with a high GPA? Does a zoology major early in the alphabet come before or after an African-American Studies major late in the alphabet?  

When it comes to sorting custom objects like Students in Java, you have two main tools at your disposal: the Comparable interface and the Comparator interface. Both serve to tell Java how your objects should be ordered, but they do so in different ways and are suited to different scenarios. If your class has a natural way of being ordered—say, students by their ID number or last name—you can implement the Comparable interface. This means you define a compareTo() method inside your Student class that tells Java how to compare one Student to another.

compareTo() returns one of three numbers—by convention, -1, 0, or 1. If x comes before y however you want to order it, then x.compareTo(y) returns -1; if x comes after y, then the same call returns 1; if they’re equivalent, then it returns 0.

For example, you might decide that students should be sorted alphabetically by last name. Now, whenever you call Collections.sort() on a list of Students, Java will use this method to determine the order. This is great when there is a single, obvious way to sort your objects.

However, if you want to sort Students by GPA one day, by year the next, and by major after that, the Comparator interface is the better choice. A Comparator is a separate object that defines a compare() method, allowing you to specify different sorting strategies without changing your Student class. For instance, to sort by GPA, you can create a Comparator that compares the GPA values of two students.

 Comparable requires you to implement the compareTo() method inside your class, establishing one default sorting behavior. Comparator, on the other hand, lets you define multiple external sorting strategies through separate objects or lambda expressions. By understanding and applying these two interfaces, you can efficiently sort even complex objects like Students in Java, tailoring the sorting logic to fit your specific needs.

Let’s look at both in action. First, Comparable:

import java.util.Arrays;

 

class Student implements Comparable<Student> {

    private String name;

    private int id;

 

    public Student(String name, int id) {

        this.name = name;

        this.id = id;

    }

 

    public String getName() {

        return name;

    }

 

    public int getId() {

        return id;

    }

 

    @Override

    public String toString() {

        return "Student [name=" + name + ", id=" + id + "]";

    }

 

    @Override

    public int compareTo(Student other) {

        if (this.id < other.id) {

            return -1;

        } else if (this.id > other.id) {

            return 1;

        } else {

            return 0;

        }

    }

}

 

public class ComparableExample {

    public static void main(String[] args) {

        Student[] students = {

            new Student("Alice", 103),

            new Student("Bob", 101),

            new Student("Charlie", 105),

            new Student("David", 102)

        };

 

        System.out.println("Students before sorting:");

        for (Student student : students) {

            System.out.println(student);

        }

 

        Arrays.sort(students);

 

        System.out.println("\nStudents after sorting by ID:");

        for (Student student : students) {

            System.out.println(student);

        }

    }

}

The fact that Student implements Comparable means that Students are comparable. Notice how in main(), the ordering by IDs is not the same as the “Alice, Bob, Charlie, David” ordering we’d get by names. The fact that we want to order by ID, not by name, is defined in the compareTo() method, a method that must be implemented if something is Comparable.

compareTo() rearranges the students in order by ID as we want them, based on the results of those comparisons returning -1, 0, or 1.

Now in this other example, a whole new class—a Comparator—is invoked to make the comparison, by way of Comparator’s compare() method. Note that this time, the method is just “compare,” not “compareTo” as with Comparable.

import java.util.Arrays;

import java.util.Comparator;

 

class Student {

    private String name;

    private int id;

 

    public Student(String name, int id) {

        this.name = name;

        this.id = id;

    }

 

    public String getName() {

        return name;

    }

 

    public int getId() {

        return id;

    }

 

    @Override

    public String toString() {

        return "Student [name=" + name + ", id=" + id + "]";

    }

}

 

public class ComparatorExample {

    public static void main(String[] args) {

        Student[] students = {

            new Student("Alice", 103),

            new Student("Bob", 101),

            new Student("Charlie", 105),

            new Student("David", 102)

        };

 

        System.out.println("Students before sorting:");

        for (Student student : students) {

            System.out.println(student);

        }

 

        // Define a Comparator to sort by name

        Comparator<Student> byName = new Comparator<Student>() {

            @Override

            public int compare(Student s1, Student s2) {

                return s1.getName().compareTo(s2.getName());

            }

        };

 

        Arrays.sort(students, byName);

 

        System.out.println("Students after sorting by name:");

        for (Student student : students) {

            System.out.println(student);

        }

    }

}

Here, the comparison strategy changes. Comparing strings is very easy to do with compareTo. (Strings are naturally Comparable.) Feeding two strings into compareTo() as we have done here will put them in A-Z alphabetical order. (As an exercise, think about how you could reverse this to Z-A order.) Therefore, the Comparator, calling Comparable, puts the Students in order by name, as opposed to ID in the previous example.

If you have an array that isn’t easily sorted (as in our case of the array of Students, since Students have more than one property), Java allows you, in Arrays.sort, to pass in a Comparator to tell sort on what criteria to perform the sort.