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;

     }

} 

Nulls

 Every data type has a default value. For primitives, if they’re numbers, its their form of 0. For booleans, it’s false. For the char type, it’s ASCII 0—which is not literally the character ‘0’, but a NULL value, a sort of way to say “this space contains a thing, and that thing is ‘nothing’”, as distinct from “this is an empty box.”

For objects, then, of any sort, the default value is null. “null” is reserved in Java, so just as you can’t name a variable “int” or “for” or “while,” you can’t name it “null” either.

When you create an object, before it gets a value, if you try to access it—say, to print out its contents—the value you will get on the other end will be null.

If, for example, you’re moving along a List, and you’ve reached the end of the list, then the “next” pointer won’t point to another element of the list, but will point to null, and accessing that phantom element (the one after the last one) will produce a NullPointerException.

This behavior is a core part of how Java manages memory and object references. The use of null is both practical and intentional—it signals that a reference exists, but it doesn’t point to any actual object in memory. However, this design also introduces a common pitfall: attempting to call methods or access fields on a null reference will trigger a NullPointerException. For example, if you try to call .length() on a String variable that’s null, or .next on a null node in a linked list, Java will throw this exception to alert you that your code is trying to operate on nothingness. To avoid these errors, it’s considered best practice to perform explicit null checks before accessing object members.

Java developers often encounter null in more complex scenarios, such as when working with collections or APIs. For instance, some methods may return null to indicate the absence of a value—like when searching for a key that doesn’t exist in a Map, or when a database query finds no matching row. In these cases, it’s up to the programmer to decide how to handle null values: should they throw an exception (we’ll cover this very soon), return a default value, or perhaps propagate the null up the call stack? This decision can have significant implications for the robustness and clarity of your codebase.

Look at this example:

public class NullExample {

    public static void main(String[] args) {

        String message = null; // message is declared but not set to a real string

 

        // This would throw a NullPointerException if uncommented:

        // System.out.println("Message length: " + message.length());

 

        // Safe way: check for null before using message

        if (message != null) {

            System.out.println("Message length: " + message.length());

        } else {

            System.out.println("Message is null!");

        }

    }

}

The String message is declared null, so accessing it a few lines later (that part is commented out, so it woud not execute) would return an error that, in this case, would crash the program. That is why it’s so important to take the safe approach and check whether something is null or not, and only take action on it if we know it isn’t null, as we do at the end. 

HashMaps

 A map is a very powerful data structure that lets us relate one thing to another in pairs. One of these things is a “key,” and the other is a “value,” so we call the pairs “key-value” pairs. For now, know that one of the benefits of maps is that they have very efficient lookup. Whereas arrays or lists might require a linear search, there is some magic going on (which we will eventually cover) that allows maps to find whatever you are looking for almost instantaneously, both in the human-time sense and the computer-time sense.

As I’m sure you’ve gathered by now, I’m a huge fan of putting links to official Java documentation in these articles. Look at it here.

If you open the documentation link, you’ll immediately see how HashMaps are created: with the declaration of two types in the angle brackets, just as we had one type in angle brackets for Lists, Queues, and Stacks. Recall that, since we need both a key and a value, we need the two types this time, not just one.

Look at this example code snippet:

import java.util.HashMap;

 

public class HashMapExample {

    public static void main(String[] args) {

        // Create a HashMap

        HashMap<String, Integer> map = new HashMap<>(); // notice the pair of types

 

        // Add key-value pairs

        map.put("Apple", 3);

        map.put("Banana", 5);

        map.put("Orange", 2);

 

        // Access a value by key

        System.out.println("Quantity of Apples: " + map.get("Apple"));

 

        // Check if a key exists

        if (map.containsKey("Banana")) {

            System.out.println("Banana is in the map.");

        }

 

        // Remove a key-value pair

        map.remove("Orange");

 

        // Iterate through the HashMap

        for (String key : map.keySet()) {

            System.out.println(key + ": " + map.get(key));

        }

    }

}

First, notice the import statement and how we declare the HashMap. (The declaration is legal because every HashMap is a Map.) Second, take note of the names of the operations: the “add” operation is called “put,” and the “retrieve” operation is called “get.” To check if a particular key exists, there is a containsKey() method; for values, there is a similar containsValue(). Removing a pair—not just a key, or not just a value—is done by remove(), passing in the key. get() takes in a key and returns the associated value.

In this case, the mapping is one-directional: “Delta 105” maps to “Atlanta to Guarulhos.” Naturally, “Atlanta to Guarulhos” should map to “Delta 105,” since it does in the real world: the delta flight from ATL to GRU is 105; and Delta 105 is the flight from ATL to GRU. These kinds of maps do exist, but the HashMap is not one by default. To get bidirectional mapping, either make two HashMaps with opposite keys and values (the key of one is the value of the other) or use a BiMap. Google has an implementation in their Guava library, but, whenever I’ve wanted to do something bidirectional, I have always found it easier to write (and to understand later) the code that just uses two opposite maps the regular way.

This is how bidirectional mapping would look:
import java.util.HashMap;

import java.util.Map;

public class SimpleBiMap<K, V> {

    private final Map<K, V> forwardMap = new HashMap<>();

    private final Map<V, K> reverseMap = new HashMap<>();

 

    public void put(K key, V value) {

        if (forwardMap.containsKey(key) || reverseMap.containsKey(value)) {

            throw new IllegalArgumentException("Key or value already exists in the bimap");

        }

        forwardMap.put(key, value);

        reverseMap.put(value, key);

    }

 

    public V getValue(K key) {

        return forwardMap.get(key);

    }

 

    public K getKey(V value) {

        return reverseMap.get(value);

    }

 

    public void removeByKey(K key) {

        V value = forwardMap.remove(key);

        if (value != null) {

            reverseMap.remove(value);

        }

    }

 

    public void removeByValue(V value) {

        K key = reverseMap.remove(value);

        if (key != null) {

            forwardMap.remove(key);

        }

    }

}

 

public class AirlineRouteMap {

    public static void main(String[] args) {

        SimpleBiMap<String, String> routeMap = new SimpleBiMap<>();

 

        // Assign routes

        routeMap.put("Delta 105", "Atlanta to Sao Paulo");

        routeMap.put("United 222", "New York to London");

        routeMap.put("American 333", "Los Angeles to Tokyo");

 

        // Look up by flight code

        System.out.println("Route for Delta 105: " + routeMap.getValue("Delta 105"));

        // Output: Route for Delta 105: Atlanta to Sao Paulo

 

        // Look up by route description

        System.out.println("Flight code for 'New York to London': " + routeMap.getKey("New York to London"));

        // Output: Flight code for 'New York to London': United 222

    }

}

Here, SimpleBiMap maintains the two opposite maps. AirlineRouteMap simply implements a specific case for airline routes: given a city pair, you get the number, and given the number, you get the city pair.

Keys must be unique in a HashMap; values need not be. Because of this, if you want to get all the keys, the data structure that is returned is a Set, and the data structure of all the values is a Collection. If what you want is a Set of key-value pairs, that can come out of a HashMap as the entrySet. Map has inside of itself the class Map.Entry<K,V>, so should you want a Set of key-value pairs rather than a Map, you can get it.  

Queues: Just like at the grocery store

 A Queue is another data structure that operates with many similar functions as Lists do, but with a key difference. In a List (as in an array—either with arr[37] or list.get(41) or whatever you want), it’s easy to get to any particular element and do something with it: check its value, change its value, remove it, add it, and so on.

But a queue is different. A queue is, really, just an implementation of “I’m in line at the grocery store to check out, and there’s an order of the people who got here.” Social norms dictate that the cashier only helps the first person in line—the person who has been in line longer than anyone else. They got there because the person ahead of them cleared the queue, and the person before that cleared before them, and the person before that, and so on.

The line only shrinks from the cashier end of the line, and only grows from the back end of the line. The longer you’ve been in line, the sooner you’ll get the cashier’s attention. If you just arrived, you have to wait for everyone ahead of you. Jumping ahead (technically possible with real people) is not allowed with a Queue.

Queues implement the “first-in-first-out” principle, which we call “FIFO” for short. (There is also a “LIFO”—you may have guessed “last-in-first-out”—structure called a Stack. We’ll cover it very soon.)

To add to a queue, you use add(). Queues are like Lists—they take generics, so you make a Queue<Puppy> to store a queue of (only) Puppy objects, or Queue<Student> to store a queue of Student objects. To remove from a queue, you use remove(). Under certain circumstances, you may remove with poll().

You may not want to outright add or remove an element, just look at something—remember, only the front element is visible—and, to do this (again, only for the front element), you can use poll().

Look at this example:

import java.util.Queue;

import java.util.LinkedList;

 

public class QueueExample {

    public static void main(String[] args) {

        // Create a queue using LinkedList

        Queue<Integer> queue = new LinkedList<>();

 

        // Enqueue (add) elements to the queue

        queue.offer(1);  // offer() is preferred for adding elements

        queue.offer(2);

        queue.offer(3);

 

        System.out.println("Queue: " + queue);

 

        // Dequeue (remove) the front element

        int removedItem = queue.poll();

        System.out.println("Removed element: " + removedItem);

 

        System.out.println("Queue after dequeue: " + queue);

    }

}

Adding an element is called “enqueueing,” and removing is also called “dequeueing.” Notice the declaration Queue<Integer> queue = new LinkedList<>();. What does that tell us? Recall from our discussion of inheritance that this is valid, if and only if (and this is true), a Queue is implemented as a LinkedList, since every Queue is a LinkedList, but not every LinkedList is a Queue.

On account of this, the element indexed 0—the “first” element—is the element at the head of the queue, or, the next one to be processed (the person being checked out by the cashier in our earlier story). The highest index in the queue, therefore, lies at the opposite end, at the tail of the queue.

This queue we have shown here is the simplest kind of queue. Later, we’ll get to a more specialized queue called a priority queue. Priority queues aren’t that much different, so don’t be too scared; in essence, they keep elements in the proper order, by some priority (“keep the seniors above the juniors above the sophomores above the freshmen”; or “keep the oldest people at the back of the queue.”)

The general queue imposes no such restriction, and you’re free to enqueue and dequeue as much as you want—add 3 things, remove 1, add 57, remove 48, add 1, take away 2, and so on—without messing with order.

Play around with building your own queue of an object of your choice (or the wrapper classes of primitives like Integer for integers), and have fun enqueueing and dequeing. 

LinkedLists and ArrayLists

 The first data structure we’ll look at is the List. List is an interface in Java, so there are many implementations. We will focus on the two most commonly used, the ArrayList and the LinkedList.

An ArrayList can be thought of, essentially, as a self-resizing array. Regular arrays are declared with the type of thing they’ll hold and how many they can hold. ArrayList declarations look a little different:

List<Integer> myList = new ArrayList();

Remember from our discussion of inheritance a few posts ago how this works, even if the class names aren’t the same. Every ArrayList is a List, so this declaration is fine. (We would run into trouble if List and ArrayList were reversed, since not every List is an ArrayList.) The use of “Integer” here is both a generic and a wrapper class. For now, I’ll be handwavy about this and say that, to create a list of integers, you use these and not the int primitive type, but I promise I’ll address this very soon and link back to the explanation as soon as it is posted.

Imagine a real list you’re making when you go shopping. There are certain things you might want to do:

• Add or remove an item from the beginning
• Add or remove an item from somewhere in the middle
• Add or remove an item from the end
• Figure out how many items you have
• Figure out if you have any items at all
• Find out what the item at some position is

These are all things you can do thanks to the way List is implemented.

There are methods to add(), remove(), and get(). Now, contrary to arrays—of the int[] myArray = new int[20]; variety—the way to access the number of things in a List is not with length (which is a property, so it really is length, and not length()), is actually with the method call to size(). This, again, unlike arrays, is an actual method call, so don’t forget the parentheses! Lists start counting from index 0, just like arrays.

ArrayLists essentially hide from you the process of copying arrays and adding in items whenever you exceed the maximum allocated space. LinkedLists, however, are a little different. Whereas arrays took some fixed chunk of memory (let’s say, 80 bytes to store 20 integers at 4 bytes each) and found a chunk of unused memory of that size, all in sequence, LinkedLists don’t care about that consecutive memory constraint.
There are generally two types of LinkedLists: singly-linked, and doubly-linked. Your browser is probably implementing a doubly-linked list, since you can go backward in a tab and you can go forward: there are links to the previous thing, and to the next thing, as opposed to links in only one direction.

Typically, you’ll probably see LinkedLists made of Nodes (again, with those angle-brackets we’ll discuss very shortly), looking something like this:

// Node class

class Node<T> {

    T data;

    Node<T> next;

 

    Node(T data) {

        this.data = data;

        this.next = null;

    }

}

 

// LinkedList class

class LinkedList<T> {

    Node<T> head;

 

    // Add a new node at the end

    void add(T data) {

        Node<T> newNode = new Node<>(data);

        if (head == null) {

            head = newNode;

        } else {

            Node<T> current = head;

            while (current.next != null) {

                current = current.next;

            }

            current.next = newNode;

        }

    }

 

    // Print all nodes

    void printList() {

        Node<T> current = head;

        while (current != null) {

            System.out.print(current.data + " ");

            current = current.next;

        }

        System.out.println();

    }

}

 

// Example usage

public class Main {

    public static void main(String[] args) {

        LinkedList<Integer> list = new LinkedList<>();

        list.add(1);

        list.add(2);

        list.add(3);

 

        list.printList(); // Output: 1 2 3

    }

}

 
A “Node” object has two things in it: a piece of data of type T, and a pointer to the next node in the list. It does not matter where in memory that is, and, say, the item at index 3 need not be earlier in memory than the item at index 327. As long as there’s a pointer from 3 to 4 to 5 to 6… to 325 to 326 to 327—as long as you can follow the trail of breadcrumbs left by those “next” Node objects—you can find your way around a list. (If the list were doubly-linked, you would have your payload, plus links to both “next” and “prev” Nodes.)