Advent of Code 2024 Day 1 part 2

 To get their big prize at Christmas, the elves you’re helping by solving these puzzles need you to solve two puzzles a day—the second always uses the same input as the first—to get 50 stars by Christmas. (Of course, you can solve the puzzles anytime after they’re released, and there’s no penalty for solving a puzzle outside of the December in which it came out.)

The second part of the December 1, 2024 puzzle, which you’ll only see if you finish the first one, deals with what the elves call “similarity.” That doesn’t mean anything outright, but they give a definition for this puzzle specifically: the product of a left-list number and the number of times it shows up in the right list.

All the other logic can stay—you still need to take advantage of the reading of the file into two lists, anyway.

What changes in part 2 is that you now have an extra method for calculating this new metric:

     public int calculateSimilarity(List<Integer> leftList, List<Integer> rightList) {

          int similarity = 0;

 

          // multiply each number in the left list by how many occurrences it has in the right list

          // and keep a running total of these products

          for (int elem : leftList) {

               int count = frequency(rightList, elem);

               similarity += (count * elem);

          }

 

          // return the total

          return similarity;

     }

The easiest way to count the number of occurrences is the way I’ve done it here—with Collections.frequency(). Collections.frequency() takes in two parameters: the collection through which you want to search, and the element for which you want to search within that collection; it returns the number of times the element appears.

The loop, therefore:

·       Goes through every element of the left list

·       Determines the frequency of that element in the left list

·       Multiplies the frequency by the element’s own value

·       Adds that product to the global measurement of similarity

·       Returns the total once everything has been processed

The whole code for Day 1, parts 1 and 2, in 2024, is as follows:

package org.example.c01;

 

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);

 

          int similarity = solution.calculateSimilarity(leftList, rightList);

          System.out.println("similarity = " + similarity);

     }

 

     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;

     }

 

     public int calculateSimilarity(List<Integer> leftList, List<Integer> rightList) {

          int similarity = 0;

 

 

          // multiply each number in the left list by how many ocurrences it has in the right list

          // and keep a running total of these products

          for (int elem : leftList) {

               int count = frequency(rightList, elem);

               similarity += (count * elem);

          }

 

          // return the total

          return similarity;

     }

 

 

}

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;

     }

} 

Tribonaccis as an example for all K-bonaccis

 Tribonacci numbers (and, in general, K-bonacci numbers) are defined not with 2 base cases (1, 1) and the rule to add the two predecessors, but K base cases and the rule to add the K predecessors.

The good news is that they look very similar to traditional Fibonacci, so the intuitive solution (the elegant recursive solution) comes naturally to almost anyone who has solved traditional Fibonacci.  

The bad news is that they look very similar to traditional Fibonacci, so the same problems encountered with it also apply to these extended Fibonacci-like sequences, namely, that the complexity grows way out of hand even more quickly for K-bonacci than for Fibonacci.

Fibonacci grew at 2^n because the rule was to add the 2 previous terms. Tribonacci (add the previous 3), then, will grow at 3^n (2^10 is about 1,000; 3^10 is about 59,000); 4-bonacci will grow at 4^n (2^10 is about 1,000; 4^10 is about 1,050,000) and so on.

Any Fibonacci-type sequence like this will grow at a rate of K^n, where K is the number of terms you have to compute to get the next one (2 for Fibonacci; 3 for Tribonacci; 4 for 4-bonacci; etc.)

However, you don’t need to panic if you ever see K-bonacci sequences in a homework assignment or interview. You know the strategy to make Fibonacci more efficient, and if it works for Fibonacci with 2 base cases, then it’ll work for Tribonacci with 3 base cases, and so on: don’t throw away the work you’ve already done. This becomes especially critical with bigger K-value K-bonacci sequences, since the increase in K really drives up the values of K to a power at lightning speed. (Recall that 2^10 was about a thousand, 3^10 is about 59 thousand, and 4^10 is more than a million.)

Here's what a tribonnaci solution would look like, using the same principle of saving our work as we go:

import java.util.HashMap;

import java.util.Map;

 

class Solution {

     Map<Integer, Integer> tribonacciMap = new HashMap<>();

 

     public void setTribonacciMap() {

          tribonacciMap.put(0, 0);

          tribonacciMap.put(1, 1);

          tribonacciMap.put(2, 1);

     }

 

     public int tribonacci(int n) {

          setTribonacciMap();

          if (n == 0 || n == 1 || n == 2) {

               return tribonacciMap.get(n);

          }

          if (!tribonacciMap.containsKey(n)) {

               tribonacciMap.put(n, (tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)));

          }

          return tribonacciMap.get(n);

     }

}

Binary and Hex basics

Every good programmer needs to know—of course—how to count and do basic math in the decimal system with digits 0123456789. But good programmers should also know how to count and do basic math in two other bases: binary and hexadecimal. The two are related, and it's especially easy to go between them, so we’ll cover conversions before we wrap up here.

First, binary. We normally count with 0123456789, so we have 10 symbols, and our numbers revolve around powers of 10: 1 is 1, 10 is ten times more; 100 is ten times more than that; 1000 is ten times more still; etc. On the other hand, 0.1 is one tenth of 1; 0.01 is one tenth of 0.1; 0.001 is one tenth of 0.01; and so on.

Binary reduces the symbol load to only two—01. Anything you can do in decimal, you can do in binary, and vice versa. The only difference is that place values aren’t 1s, 10s, 100s, 1000s, etc.—they’re 1s, 2s, 4s, 8s, 16s, etc. So binary numbers roll over to more places sooner than base 10 does (about 3.32 times faster), but how the numbers behave when counting, adding, multiplying, dividing, and subtracting is exactly the same.

And just like 9,999,999 is one less than 10,000,000 (which is a perfect power of 10), the equivalent is that 1111 1111 is one less than 1 0000 0000, which is a perfect power of 2. (In decimal, that’s equivalent to saying that 255 is one less than 256, by the way.)

Here's how I like to convert numbers from decimal to binary. Let’s convert 485.

• I happen to know the biggest power of 2 less than or equal to 485 is 256 (which is 2*2*2*2… 8 times, or 2^8)
• Subtract that number from 485, and we’re left with 229.
• We have 1 grouping of 256, plus 229
• Now, look at the biggest power of 2 less than 229. That’s 128. Make a note. Subtracting it off leaves 101.
• 1 group of 256
• 1 group of 128
• Now, the biggest power left is 64, and subtracting it off leaves 37.
• 1 group of 256
• 1 group of 128
• 1 group of 64
• Now do the same for 37. The biggest power is 32. Subtracting it leaves 5.
• 1 group of 256
• 1 group of 128
• 1 group of 64
• 1 group of 32
• 5 is smaller than 16 and 8, so we won’t have any groups of those
• 1 group of 256
• 1 group of 128
• 1 group of 64
• 1 group of 32
• 0 groups of 16
• 0 groups of 8
• But we will have 1 group of 4, and that leaves us with 1 left
• 1 group of 256
• 1 group of 128
• 1 group of 64
• 1 group of 32
• 0 groups of 16
• 0 groups of 8
• 1 group of 4
• 0 groups of 2
• 1 group of 1

We then write the number by converting the vertical list into a horizontal one: 357 in binary is 1 1110 0101. Checking our math is very easy: we can simply add all the powers where we have 1s, and ignore the powers where we have 0s, and the sum should be the number we started with. 256+64+32+4+1 is, in fact, 357, so we did everything right. Notice something: because we only have 2 digits, we can immediately know if our answer is wrong if the parity does not match as expected. If a supposedly even number comes back with a last digit of 1, we did something wrong. If a supposedly odd number comes back with a last digit of 0, we did something wrong.

Adding and subtracting work much the same way as in decimal, only there are more frequent carries or borrowings, since there are fewer symbols.

Hexadecimal uses 16 symbols, as opposed to just 10. In addition to 0123456789, we also use ABCDEF.

So counting in hexadecimal looks like 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, 10, 11, 12…, and that is equivalent in decimal to 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18…

Hexadecimal-binary conversions are nice because 16 is a power of 2, so the mapping between the bases is really easy: much, much easier than either binary or hexadecimal to decimal, or vice versa.

You’ll notice that, earlier in the article, I split up a binary number like 1 0110 0101. This makes seeing things in 4-bit groupings (as opposed to 3 decimal-digits groupings of thousands together, millions, billions, etc.) so much easier, and lets the hexadecimal practically jump off the page.

The conversion becomes almost trivial:

• Starting from the rightmost place, break up the number into 4-bit segments, as done above: 1 1110 0101.
• If the left-most segment (the most significant) is less than 4 bits, pad it on the left with zeroes: 0001 1110 010
• Now, just treat every 4-bit section as a single hex digit—because it is—and convert it, remembering that A is decimal 10, B is decimal 11, C is decimal 12, D is decimal 13, E is decimal 14, and F is decimal 15

·       The number becomes:

• Left-most group: 0001 in binary is 1 in hex
• Second group: 1110 in binary is E in hex (because 1110 is 14 in decimal, which is E in hex)
• Third group: 0101 in binary is 5 in hex

·       So the final number is 1E5 in hexadecimal

To convert this back into decimal, we know that our columns now are 1s, 16s, 256s, etc., so we have

• 5 1s
• E 16s (that is, 14 16s), or 224 in this column
• 1 256

And the sum of all that (5 + 224 + 256) is in fact our original number of 485.

 

Harsahad Numbers and the Ternary operator

Today’s problem has less to do with computing Harshad numbers—I was unaware of the name until I solved the problem, just a few days before this went live—and much more to do with a piece of Java syntax that tightens up conditionals. By now, you are certainly advanced enough in Java to have come across it if you’ve looked anywhere else for tutorials, so I certainly should address it here.

The problem is the following:

A number is a Harshad number if it’s divisible by the sum of its digits. Given a number, figure out if it is one of these numbers. If it is, return the sum of the digits. If it isn’t—as is convention when things fail, are not found, etc.—return -1.

Here's the logic that gets it done:

public int sumOfTheDigitsOfHarshadNumber(int x) {

          int num = x;

          int currentDigit;

          int sumOfDigits = 0;

         

          while (x > 0) {

               currentDigit = x % 10;

               x /= 10;

               sumOfDigits += currentDigit;

          }

         

          return num % sumOfDigits == 0 ? sumOfDigits : -1;

     }

I need the parameter number x to do things to it—get its digits, etc.—but I also need that value somewhere else for safekeeping. So I created another variable, num, to also store the same value.

The variable currentDigit will store, as I’m looping through, the digit I’m currently working on.

sumOfDigits is declared and initialized to 0 outside the loop, naturally, to store the sum of the digits of the number, which will determine if the number is a Harshad number or not.

Successively modding by 10 and dividing by 10 exposes and captures one digit at a time from the right, i.e., the least significant places. I’m doing addition here, so I don’t care much about the order of the numbers. This way works, and is much easier than coming from the left, so I might as well do what I know well. As I capture digits, I’m adding them to the running total of the sum of all the number’s digits.

There aren’t any leading zeroes, so while the value of x (which is initially the same as my parameter num) is bigger than zero, I can keep looping—I have to keep looping—because I still have digits to process.

Once I finish looping, I can do my Harshad calculation. This is the whole point of this article—that last line of code.

This is a ternary operator, a syntactical choice in Java and other languages that allows programmers to condense if-else logic into one line.

The ternary statement a ? b : c is exactly equivalent to the more verbose

if(a){
     b;
} else{
     c;
}

Get used to reading and writing both styles. They are interchangeable, and a good programmer knows and uses both.

Given this, that last line means the following: if num % sumOfDigits == 0  is true (that is, if num—passed in as x, but  I did all kinds of manipulation to the original x, so I made a copy for this reason—is divisible by sumOfDigits), then return sumOfDigits; if not, return -1.