Advent of Code 2022

Don’t give Eric any ideas… or soon we’ll be expected to create algorithms that run in negative time and be doing Advent of Christmases Past :grin:

1 Like

Day 7 has us simulating a file system. I swear Eric must be planning to have us build a whole OS eventually :wink:

My first task was to build a class to simulate the file system, which is basically a wrapper around a tree data structure.

This code encapsulates the operations on the file system, and doesn’t expose tree nodes. I suppose I could have found a way to have the filesystem have a concept of current working directory, but it doesn’t really need that to work, and so I decided to handle all the operations by basing them on a path from the root.

final class DiskSim
{
  final DiskEntry root = new DiskEntry();

  public void addDirectory(final String[] pathParts, final String dirName)
  {
    final StringBuilder pathsb = new StringBuilder();
    final DiskEntry dir = navigateToDirFromRoot(pathParts, pathsb);

    if (dirName.contains("/"))
    {
      if (pathParts.length == 0)  return;
      if ((pathParts.length == 1) && (pathParts[0].contains("/")))  return;
      throw new IllegalStateException("Illegal \"root\" at " + pathsb.toString());
    }

    if (dirName.contains(".."))
    {
      throw new IllegalStateException("Illegal \"..\" at " + pathsb.toString());
    }
    
    if (dir.subDirectories.containsKey(dirName))
    {
      throw new IllegalStateException(String.format("Duplicate dir (%s) in dir (%s)", dirName, pathsb.toString()));
    }
    else
    {
      final DiskEntry newSubDir = new DiskEntry();
      dir.subDirectories.put(dirName, newSubDir);
    }
  }

  public void addFile(final String[] pathParts, final String filename, final long fileSize)
  {
    final StringBuilder pathsb = new StringBuilder();
    final DiskEntry dir = navigateToDirFromRoot(pathParts, pathsb);
    
    if (filename.equals("/"))  throw new IllegalStateException("Bad \"root\" filename at " + pathsb.toString());
    if (filename.equals(".."))  throw new IllegalStateException("Bad \"..\" filename at " + pathsb.toString());
    
    if (dir.files.containsKey(filename))
    {
      throw new IllegalStateException(String.format("Duplicate filename (%s) in dir (%s)", filename, pathsb.toString()));
    }
    else
    {
      dir.files.put(filename, fileSize);
    }
  }
  
  private DiskEntry navigateToDirFromRoot(final String[] pathParts, final StringBuilder pathsb)
  {
    pathsb.append('/');
    if (pathParts.length == 0)  return root;
    if ((pathParts.length == 1) && (pathParts[0].equals("/")))  return root;

    DiskEntry curDir = root;
    for(final String pathPart: pathParts)
    {
      // Ignore root being specified if we're there, that's expected, but if we're
      // not there, that's a problem
      if (pathPart.contains("/"))
      {
        if (curDir == root) continue;
        else
        {
          throw new IllegalStateException("Got root in the middle of a path");
        }
      }
      if (curDir.subDirectories.containsKey(pathPart))
      {
        curDir = curDir.subDirectories.get(pathPart);
      }
      else
      {
        final DiskEntry newSubDir = new DiskEntry();
        curDir.subDirectories.put(pathPart, newSubDir);
        curDir = newSubDir;
      }
      pathsb.append(pathPart);
    }
    pathsb.append('/');
    return curDir;
  }

  public long getSizeOfAllSubdirsInPath(final String[] pathParts)
  {
    final StringBuilder pathsb = new StringBuilder();
    final DiskEntry dir = navigateToDirFromRoot(pathParts, pathsb);
    return sizeOfAllSubdirs(dir);
  }

  private long sizeOfAllSubdirs(final DiskEntry diskEntry)  // recursive
  {
    long result = 0;
    for (final DiskEntry subDir: diskEntry.subDirectories.values())
    {
      result += sizeOfAllSubdirs(subDir);
    }

    for (final Long fileSize: diskEntry.files.values()) result += fileSize;
    
    return result;
  }

  public void dumpFileStructure()
  {
    System.out.println("/");
    dumpFileStructure(root, "  ");
  }

  private void dumpFileStructure(final DiskEntry diskEntry, final String indent)
  {
    for (final Entry<String, DiskEntry> ent: diskEntry.subDirectories.entrySet())
    {
      final String dirName = ent.getKey();
      System.out.println(indent + "dir " + dirName);
      dumpFileStructure(ent.getValue(), indent + "  ");
    }
    for (final Entry<String, Long> ent: diskEntry.files.entrySet())
    {
      System.out.println(indent + ent.getKey() + " " + ent.getValue());
    }
  }

  // ========================================================================
  private static final class DiskEntry
  {
    final Map<String, DiskEntry> subDirectories;
    final Map<String, Long> files;
    DiskEntry()
    {
      subDirectories = new HashMap<>();
      files = new HashMap<>();
    }
  }
}

Once the file system simulation was tested and working then I need a driver to make it do something useful toward getting the requested answer. First I added this code to the simulation, which provides a new public method, and has most of the work done in the private recursive method:

  public long sumSubDirSizesOfOrUnder(final long maxSubDirSizeToIncludeInSum)
  {
    return sumSubDirSizesOfOrUnder(root, maxSubDirSizeToIncludeInSum);
  }

  private long sumSubDirSizesOfOrUnder(final DiskEntry diskEntry, long maxSubDirSizeToIncludeInSum)
  {
    long result = 0;
    final long thisDirSize = sizeOfAllSubdirs(diskEntry);
    if (thisDirSize <= maxSubDirSizeToIncludeInSum) result += thisDirSize;
    for (final DiskEntry subDir: diskEntry.subDirectories.values())
    {
      result += sumSubDirSizesOfOrUnder(subDir, maxSubDirSizeToIncludeInSum);
    }
    return result;
  }

and then this is the driver code:

I did run into one thing that slowed me down. In Java is you look at the Stack<> class, it will tell you it’s deprecated by the Deque<> class. If you do push(a) push(b) push(c) on the Deque and then you convert it to an array, you may be surprised to find it’s backward from what you would suspect and the array will be [C,B,A] which was not what I wanted or needed for my path from the root of the file system.

Most of this code is in comming with part 2 because most of it is about parsing the input and building the simulated file system. After all the parsing, the real work of getting an answer is the one line call to ds.sumSubDirSizesOfOrUnder(100000L);

final class Day07
{
  public static long part1(final String[] day07InputLines)
  {
    final DiskSim ds = processInput(day07InputLines);
    return ds.sumSubDirSizesOfOrUnder(100000L);
  }

  private static DiskSim processInput(String[] day07InputLines)
  {
    final DiskSim ds = new DiskSim();
    final Deque<String> path = new ArrayDeque<String>();

    for (final String input : day07InputLines)
    {
      if (input.startsWith("$ "))
        processCommand(input.substring(2), path, ds);
      else if (input.startsWith("dir "))
        processDir(input.substring(4), path, ds);
      else
        processFile(input, path, ds);
    }
    // ds.dumpFileStructure();
    return ds;
  }

  private static void processFile(final String fileSizeAndName, final Deque<String> path, final DiskSim ds)
  {
    final String[] fileParts = fileSizeAndName.split(" ");
    if (fileParts.length != 2)  throw new IllegalStateException("Couldn't understand file: " + fileSizeAndName);
    final String[] pathParts = makeDirParts(path);
    final long fileSize = Long.parseLong(fileParts[0]);
    ds.addFile(pathParts, fileParts[1], fileSize);
  }

  private static void processDir(final String dirName, final Deque<String> path, final DiskSim ds)
  {
    final String[] pathParts = makeDirParts(path);
    ds.addDirectory(pathParts, dirName);
  }

  private static String[] makeDirParts(final Deque<String> path)
  {
    // return path.toArray(new String[0]);  // result is backwards from what is needed, a path starting at root

    // Don't technically need this, as an empty array should be equivalent
    /*
    if (path.size() == 0)
    {
      final String[] result = new String[1];
      result[0] = "/";
      return result;
    }
    */

    final String[] result = new String[path.size()];
    final Iterator<String> i = path.descendingIterator();
    int p = 0;
    while (i.hasNext())
    {
      final String s= i.next();
      result[p++] = s;
    }
    return result;
  }

  private static void processCommand(final String command, final Deque<String> path, final DiskSim ds)
  {
    if (command.startsWith("cd "))
    {
      final String cdPath = command.substring(3);
      if (cdPath.contains("/"))
      {
        path.clear();
        path.push("/");
        return;
      }
      if (cdPath.equals(".."))
      {
        if (path.size() > 0)
        {
          path.pop();
          return;
        }
        throw new IllegalStateException("Attempt to cd.. when already at root");
      }
      // confirmSubDirExists(ds, path, cdPath);
      path.push(cdPath);
      return;
    }

    if (command.startsWith("ls"))
    {
      // ignore
      return;
    }
    throw new IllegalStateException("Unknown command: " + command);
  }

For part 2 I had to add a new public method (and the private recursive part) to the simulation class

This implements a different recursive traversal of the tree based on the part 2 requirements.

  public long findSmallestSubDirThatIsAtLeast(final long minimumSizeNeeded)
  {
    return findSmallestSubDirThatIsAtLeast(root, minimumSizeNeeded, sizeOfAllSubdirs(root));
  }

  private long findSmallestSubDirThatIsAtLeast(final DiskEntry diskEntry, final long minimumSizeNeeded, final long bestSoFar)
  {
    long localBest = bestSoFar;
    final long thisDirSize = sizeOfAllSubdirs(diskEntry);
    if (thisDirSize >= minimumSizeNeeded)
    {
      if (thisDirSize < localBest)  localBest = thisDirSize;
    }
    for (final DiskEntry subDir: diskEntry.subDirectories.values())
    {
      localBest = findSmallestSubDirThatIsAtLeast(subDir, minimumSizeNeeded, localBest);
    }
    return localBest;
  }

And then I added a new part 2 driver, which is very similar to part 1 in that it too parses the input to the simulated file system, but it uses the new method above to get the part 2 solution.

This method needs to do a little math to set the parameters for the call to ds.findSmallestSubDirThatIsAtLeast(neededAdditionalSpace);

  public static long part2(final String[] day07InputLines)
  {
    final DiskSim ds = processInput(day07InputLines);
    final long availableSpace =  70000000 - ds.getSizeOfAllSubdirsInPath(new String[0]);
    final long neededAdditionalSpace = 30000000 - availableSpace;
    System.out.println("availableSpace = " + availableSpace);
    System.out.println("neededAdditionalSpace = " + neededAdditionalSpace);
    final long result = ds.findSmallestSubDirThatIsAtLeast(neededAdditionalSpace);
    return result;
  }

I initially thought I was going to have to build a directory tree and deal with recursion. Then I ‘manually’ stepped through the sample input and realized there was an easier way:

I created a list to hold directory paths and their sizes (initially 0). I stepped through each line of the input data.
CD is used to update the current path.
LS gives a list of directories and files:
For a directory, its full path (current path + directory name) is added to the list of directories.
For a file, its size is added to the size of each directory in its path (the current path).
With a list of directories and their sizes, parts 1 and 2 are straightforward.

Yeah I started that way but now I’m thinking it might be better to do the tree for part two (and future OS updates?)

I’m now getting off the express and taking the local. Y’all have fun. I’ll be back here whittling away.

I didn’t think of not simulating the whole tree until it was too late. On the other hand, my classes (above) are a good start for someone who needs to track a bunch of files in their structure (say making a ZIP clone or backup tool) so it doesn’t feel like a total waste of over-engineering. :wink: I usually make a robust class because I assume part 2 is going to force me to anyway.

For today, both parts have the same init code, in which I just track the size of each directory.

Creating the tree

I use a map to keep track of the size of the directory. It’s kind of odd to come up with a solution that works for both. I always assume that I won’t correctly guess what part 2 will ask. Anyway, I start with an empty map object and empty array to keep track of the current directory.

Then I read each line of the input.
First, I handle commands. I ignore the ls command, and for cd / I just clear out the current directory array and push root to it. So at this point, all paths will be root/a/b(Didn’t know whether the map object would like empty strings or not)
If there’s a directory, I push it to the array by taking the last directory and adding / and the directory we will go to (I assume there might be two directories that have the same name otherwise), and for .. I pop the array. So for the root/a/b example, the cd b command will result in an array of

[
   'root',
   'root/a',
   'root/b'
]

Second, if it’s not a command, I treat it as a file. Like ls, my code actually ignores the directories. It gets the size, convert to a number, and loops through the current directory array and adds the size to each directory, so a file in b above will add it’s size to root, root/a, and root/b in the map. There’s a special operator I use to default the value to 0 if the map entry doesn’t exist yet.

	const data = d.split('\n');
	const directorySizes = new Map();
	const cwd = [];
	while (data.length) {
		const line = data.shift();
		const cmd = line.match(/^\$ (cd|ls)(?: (.*))?$/);
		const file = line.match(/^(dir|\d+) (.+)$/);
		if (cmd) {
			if (cmd[1] == 'ls') continue;
			if (cmd[2] == '/') {
				cwd.splice(0, cwd.length);
				cwd.push('root');
			} else if (cmd[2] == '..') {
				cwd.pop();
			} else {
				cwd.push(cwd[cwd.length - 1] + '/' + cmd[2]);
			}

		} else if (file) {
			if (file[1] == 'dir') continue;
			const size = parseInt(file[1], 10);
			cwd.forEach((dir) => {
				directorySizes.set(dir, (directorySizes.get(dir) ?? 0) + size);
			});
		} else {
			console.log(line);
		}
	}
Part 1 only code

I just convert the map to an array, filter on directories that are less than/equal to 100000, and add it up. Chaining functions go!

return Array.from(directorySizes.values()).filter((v) => v <= 100000).reduce((c, v) => c + v, 0);
Part 2 only code

First, get the free space

const freeSpace = 70000000 - directorySizes.get('root');

Second, we let the chaining functions loose to convert the map to an array, filter out directories that don’t have enough space to all use to free up enough space for the upgrade, and reverse sort the rest, so the smallest directory is at the end of the array.

const files = Array.from(directorySizes.entries()).filter((v) => v[1] > 30000000 - freeSpace).sort((a, b) => b[1] - a[1]);

Finally, we return the last item on the array (For some reason, I didn’t fully read part 2, so I thought I need the path for some reason and not just the size)

return (files.pop())[1];

The full file

Day 8 and we’re unable to see the forest for the trees! I decided to implement this one as basically some slightly odd calculations on numbers in a 2D array/matrix. Accordingly I made a Forest class to wrap the matrix and the calculations. To solve part one I created a public method getNumberOfVisibleTrees() and the only real trick here is that I cloned the array so I could modify it, and then flagged already counted trees by making their heights negative. To do this, I had to offset the input heights up by one to avoid the inability to make 0 negative. This actually led to a bug wherein I forgot to use Math.abs() when I should have, and led me to submit a wrong part 1 answer (before I fixed the bug.) In hindsight, I should just have used a boolean array of the same size, it wouldn’t have required the offset and probably would have avoided the bug.

final class Forest
{
  private final int[][] treeHeights;
  private final int width;
  private final int height;

  public Forest(final String[] forestHeightMap)
  {
    width  = forestHeightMap[0].length();
    height = forestHeightMap.length;
    treeHeights = new int[height][width];
    for (int row=0; row<height; row++)
    {
      for (int col=0; col<width; col++)
      {
        // Because we'll use negatives as an indicator, we need to boost the tree heights by one so
        // that we don't need to try and deal with zero height trees
        treeHeights[row][col] = Integer.parseInt(""+forestHeightMap[row].charAt(col)) + 1;
      }
    }
  }

  public long getNumberOfVisibleTrees()
  {
    final int[][] treeHeights = this.treeHeights.clone();

    // Down from top
    {
      for (int col=0; col<width; col++)
      {
        int curHeight = Math.abs(treeHeights[0][col]);
        makeNegative(treeHeights, 0, col);  // First one is always visible
        for (int row=1; row<height; row++)
        {
          if (Math.abs(treeHeights[row][col]) > curHeight)
          {
            curHeight = Math.abs(treeHeights[row][col]);
            makeNegative(treeHeights, row, col);
          }
        }
      }

      // left to right
      {
        for (int row=0; row<height; row++)
        {
          int curHeight = Math.abs(treeHeights[row][0]);
          makeNegative(treeHeights, row, 0);  // First one is always visible
          for (int col=1; col<width; col++)
          {
            if (Math.abs(treeHeights[row][col]) > curHeight)
            {
              curHeight = Math.abs(treeHeights[row][col]);
              makeNegative(treeHeights, row, col);
            }
          }
        }
      }

      // right to left
      {
        for (int row=0; row<height; row++)
        {
          int curHeight = Math.abs(treeHeights[row][width-1]);
          makeNegative(treeHeights, row, width-1);  // First one is always visible
          for (int col=width-2; col>0; col--)
          {
            if (Math.abs(treeHeights[row][col]) > curHeight)
            {
              curHeight = Math.abs(treeHeights[row][col]);
              makeNegative(treeHeights, row, col);
            }
          }
        }
      }

      // Up from bottom
      {
        for (int col=0; col<width; col++)
        {
          int curHeight = Math.abs(treeHeights[height-1][col]);
          makeNegative(treeHeights, height-1, col);  // First one is always visible
          for (int row=height-2; row>0; row--)
          {
            if (Math.abs(treeHeights[row][col]) > curHeight)
            {
              curHeight = Math.abs(treeHeights[row][col]);
              makeNegative(treeHeights, row, col);
            }
          }
        }
      }
    }
    
    // count up all the negative cells
    int result = 0;
    for (int row=0; row<height; row++)
      for (int col=0; col<width; col++)
        if (treeHeights[row][col] < 0)  result++;
    
    return result;
  }

  private void makeNegative(final int[][] treeHeights, final int row, final int col)
  {
    if (treeHeights[row][col]>0) treeHeights[row][col] = -treeHeights[row][col];
  }

  @Override
  public String toString()
  {
    final StringBuilder sb = new StringBuilder();
    for (int row=0; row<height; row++)
    {
      for (int col=0; col<width; col++)
      {
        if (treeHeights[row][col]>0)
        {
          sb.append(' ');
          sb.append(treeHeights[row][col]);
        }
        else
        {
          sb.append(treeHeights[row][col]);
        }
      }
      sb.append("\n");
    }
    return sb.toString();
  }
}

The driver for part 1 is very simple, not even worth a spoiler, I don’t think:

final class Day08
{
  public static long part1(final String[] day08InputLines)
  {
    final Forest forest = new Forest(day08InputLines);
    // System.out.println(forest);
    return forest.getNumberOfVisibleTrees();
  }

For part 2, I needed to add a new public method to the Forest class. I somehow had the completely wrong mental model for how to count the values needed in the calculations, which wasted me a good 20 or more minutes in the debugger. When the light finally came on and I had that aha moment, it was a very rapid completion thereafter. My basic bug was, as I was looking in each direction, I was wanting to count trees that were as high as (but not higher than) the one under consideration, but I wasn’t initially counting the higher tree when I stopped… basically a one off error in some sense.

  public long getScoreForMostScenicTree()
  {
    int bestScoreSoFar = -1;
    for (int row=0; row<height; row++)
    {
      for (int col=0; col<width; col++)
      {
        final int scoreForThisTree = getScenicScoreForTreeAt(row, col);
        if (scoreForThisTree > bestScoreSoFar)  bestScoreSoFar = scoreForThisTree;
      }
    }
    return bestScoreSoFar;
  }
  
  private int getScenicScoreForTreeAt(final int row, final int col)
  {
    // the trees on every edge have a 0 for one direction so the multiplication
    // means the score has to be zero
    if ((row==0) || (col==0)) return 0; 
    if ((row==height-1) || (col==width-1)) return 0; 

    int result = 1;
    int c = 0;
    final int referenceTreeHeight = treeHeights[row][col];
    
    for (int goingLeftWithCol=col-1; goingLeftWithCol>=0; goingLeftWithCol--)
    {
      final int thisTreeHeight = treeHeights[row][goingLeftWithCol];
      c++;
      if (thisTreeHeight >= referenceTreeHeight) break;
    }
    result = result*c;

    c = 0;
    for (int goingRightWithCol=col+1; goingRightWithCol<=width-1; goingRightWithCol++)
    {
      final int thisTreeHeight = treeHeights[row][goingRightWithCol];
      c++;
      if (thisTreeHeight >= referenceTreeHeight) break;
    }
    result = result*c;

    c = 0;
    for (int goingUpWithRow=row-1; goingUpWithRow>=0; goingUpWithRow--)
    {
      final int thisTreeHeight = treeHeights[goingUpWithRow][col];
      c++;
      if (thisTreeHeight >= referenceTreeHeight) break;
    }
    result = result*c;

    c = 0;
    for (int goingDownWithRow=row+1; goingDownWithRow<=height-1; goingDownWithRow++)
    {
      final int thisTreeHeight = treeHeights[goingDownWithRow][col];
      c++;
      if (thisTreeHeight >= referenceTreeHeight) break;
    }
    result = result*c;

    return result;
  }

And then a continue the driver in the usual way:

  public static long part2(final String[] day08InputLines)
  {
    final Forest forest = new Forest(day08InputLines);
    return forest.getScoreForMostScenicTree();
  }

I really enjoyed today’s challenge. Not too hard, which means I could spend some time polishing the code to make it as “pythonic” as possible. This is a python learning exercise for me after all. But being pythonic means you know there’s going to be a ton of list comprehensions in there!

Commit message should tell you what bug I had to fight with

image

For part 1

I tried to a simple loop, but I was doing something wrong with my logic, so what I settled required me to have 3 arrays for part 1, the normal array with the usual splitting, a transposed copy of the first array, and one that says the tree is visible from the edge.

Code
	const data = d.split('\n').map(e => e.split('').map(e => parseInt(e, 10)));
	const dataTranspose = data[0].map((_, colIndex) => data.map(row => row[colIndex]));
	const ret = deepCopy(data);

The transpose array allowed me to use slice on a column of trees. Either way, I took a slice from both sides of the array from the tree in question, filter that array to only include tree that are blocking the view, and if the length is 0, set the grid as true.

Lines 11 to 44. I fix the loops, I can remove lines 36 to 44, but I only noticed this as I typed this up…

Flatten the array, filter out false, and get the count, and I’m done!

Code
return ret.flat().filter(e => e).length;
Part 2...

We’ll get to the bug in a moment

So just the single array and a variable to keep track of the max score.

The next bit is a big old double loop (x and y) starting at line 55

I have a curScore variable, but that’s really only for debugging purposes. Where I use it, I can collapse two lines without defining this variable. I have an array to count how many trees are visible in a direction.

Then I count the number of trees in that direction, and here’s where I had a bug. I thought that trees of height 0 were no trees in that spot, so I had if (data[c][c] !==0) trees++, but I only needed tress++. As a result, my answer for my input was too small!

Anyway, used reduce to multiply the four directions and store the match of the current score and max score in max score, and the last line just returns max score.

Day 9 is all about a weird rope bridge, which is really a wrapper around an implementation of a co-ordinate class or language feature (to handle x,y co-ordinates and implement things like move up, down, left right.)

Initially I thought this might also be a challenge to see if the coder knows how Manhattan Distance calculations work, but in the end I became less convinced of that.

Although I have created co-ordinate classes before, I decided to do it again for this challenge. Here is my basic co-ordinate class, properly implementing the hashCode() and equals() so I can throw them in to a hashmap (more on why after.)

final class Coordinates
{
  private int x;
  private int y;
  
  public Coordinates(final int initialX, final int initialY)
  {
    x = initialX;
    y = initialY;
  }

  public int getX()
  {
    return x;
  }

  public int getY()
  {
    return y;
  }
  
  public void moveX(int newX)
  {
    x = newX;
  }

  public void moveY(int newY)
  {
    y = newY;
  }
  
  public void moveTo(int x, int y)
  {
    moveX(x);
    moveY(y); 
  }
  
  public void moveUp()
  {
    y--;
  }

  public void moveDown()
  {
    y++;
  }
  
  public void moveLeft()
  {
    x--;
  }

  public void moveRight()
  {
    x++;
  }
  
  public int getXDistanceFrom(final Coordinates other)
  {
    return x-other.x;
  }

  public int getYDistanceFrom(final Coordinates other)
  {
    return y-other.y;
  }
  
  @Override
  public int hashCode()
  {
    return y*10003+x;
  }
  
  @Override
  public boolean equals(final @Nullable Object other)
  {
    if (other == null) return false;
    if (other == this) return true;
    if (other instanceof Coordinates)
    {
      if ((this.x == ((Coordinates)other).x) && (this.y == ((Coordinates)other).y)) return true;
    }
    return false;
  }
  
  @Override
  public String toString()
  {
    return String.format("Coordinates[x=%d, y=%d]", x, y);
  }
}

Having that out of the way and tested, I moved on to using it to create a RopeSimulation class to simulate the ends of the rope and their necessary movements and following movements. It also tracks where the tail of the rope has been, as that is the answer for part 1. The easiest way to not waste time while tracking where the rope has been is to just throw EVERY updated tail position into a set. Set’s don’t care about duplicates, so it’s perfect for this use case. I spent a lot of time (read that as wasted a lot of time) thinking there must be a more clever way to do the necessary manipulations to have the tail follow the head. In the end I realized it was easier (and would have been faster) to just brute force code out the actual movements that were described, and had examples of, in the text.

final class RopeSimulation1 implements RopeSimulation
{
  private Coordinates currentHeadPosition = new Coordinates(0,4); 
  private Coordinates currentTailPosition = new Coordinates(0,4);
  private Set<Coordinates> placesTheTailHasBeen = new HashSet<>();

  RopeSimulation1()
  {
    placesTheTailHasBeen.add(currentTailPosition);
  }

  @Override
  public void moveUp(final int amount)
  {
    for (int i=0; i<amount; i++)
    {
      currentHeadPosition.moveUp();
      moveTailToFollowHead();
      placesTheTailHasBeen.add(currentTailPosition);
    }
  }

  @Override
  public void moveDown(final int amount)
  {
    for (int i=0; i<amount; i++)
    {
      currentHeadPosition.moveDown();
      moveTailToFollowHead();
      placesTheTailHasBeen.add(currentTailPosition);
    }
  }

  @Override
  public void moveLeft(final int amount)
  {
    for (int i=0; i<amount; i++)
    {
      currentHeadPosition.moveLeft();
      moveTailToFollowHead();
      placesTheTailHasBeen.add(currentTailPosition);
    }
  }

  @Override
  public void moveRight(final int amount)
  {
    for (int i=0; i<amount; i++)
    {
      currentHeadPosition.moveRight();
      moveTailToFollowHead();
      placesTheTailHasBeen.add(currentTailPosition);
    }
  }

  private void moveTailToFollowHead()
  {
    if (currentHeadPosition == currentTailPosition) return;
    final int xDist = currentHeadPosition.getXDistanceFrom(currentTailPosition);
    final int yDist = currentHeadPosition.getYDistanceFrom(currentTailPosition);
    
    if (xDist == 0)
    {
      if (yDist < -1)
      {
        currentTailPosition.moveUp();
      }
      else if (yDist > 1)
      {
        currentTailPosition.moveDown();
      }
      return;
    }

    if (yDist == 0)
    {
      if (xDist < -1)
      {
        currentTailPosition.moveLeft();
      }
      else if (xDist > 1)
      {
        currentTailPosition.moveRight();
      }
      return;
    }

    if (yDist == 2)
    {
      currentTailPosition.moveDown();
      if (xDist < 0)
      {
        currentTailPosition.moveLeft();
      }
      else if (xDist > 0)
      {
        currentTailPosition.moveRight();
      }
      return;
    }

    if (yDist == -2)
    {
      currentTailPosition.moveUp();
      if (xDist < 0)
      {
        currentTailPosition.moveLeft();
      }
      else if (xDist > 0)
      {
        currentTailPosition.moveRight();
      }
      return;
    }

    if (xDist == 2)
    {
      currentTailPosition.moveRight();
      if (yDist < 0)
      {
        currentTailPosition.moveUp();
      }
      else if (yDist > 0)
      {
        currentTailPosition.moveDown();
      }
      return;
    }

    if (xDist == -2)
    {
      currentTailPosition.moveLeft();
      if (yDist < 0)
      {
        currentTailPosition.moveUp();
      }
      else if (yDist > 0)
      {
        currentTailPosition.moveDown();
      }
      return;
    }
  }

  @Override
  public long getNumberOfPositionsVisitedByTail()
  {
    return placesTheTailHasBeen.size();
  }
}

One thing that became apparent as I later started part 2 was that it would be faster to copy my part 1 RopeSimulation class for part 2. Accordingly, I renamed RopeSimulation to RopeSimulation1 and then extracted an Interface which I named RopeSimulation, and then I copied RopeSimulaion1 to RopeSimulation2 and started making changes.

Here’s the driver for part 1, nothing to spoiler protect here as the minimal parsing should be pretty obvious by now:

  public static long part1(final String[] day09InputLines)
  {
    final RopeSimulation rs1 = new RopeSimulation1();
    for (final String movementDescription : day09InputLines)
    {
      doMovement(rs1, movementDescription);
    }
    return rs1.getNumberOfPositionsVisitedByTail();
  }

  private static void doMovement(final RopeSimulation rs, final String movementDescription)
  {
    final char dir = movementDescription.charAt(0);
    final int amount = Integer.parseInt(movementDescription.substring(2));
    switch (dir)
    {
      case 'U': rs.moveUp(amount); return;
      case 'D': rs.moveDown(amount); return;
      case 'L': rs.moveLeft(amount); return;
      case 'R': rs.moveRight(amount); return;
      default:  throw new IllegalStateException("Unknown move command: " + movementDescription);
    }
  }

For part 2, I realized the rope simulation just needed to be more complex than having just a head and a tail. It also seemed likely that most of the rest of the code would be similar, so, as I mentioned above, I copied it and starting making RopeSimulation2:

final class RopeSimulation2 implements RopeSimulation
{
  private Coordinates[] currentKnotPositions = new Coordinates[10]; 
  private Set<Coordinates> placesTheTailHasBeen = new HashSet<>();

  RopeSimulation2()
  {
     // The start location is arbitrary
    for (int i=0; i<10; i++) currentKnotPositions[i] = new Coordinates(100, 100);
    placesTheTailHasBeen.add(currentKnotPositions[9]);
  }

  @Override
  public void moveUp(final int amount)
  {
    for (int i=0; i<amount; i++)
    {
      currentKnotPositions[0].moveUp();
      moveKnots();
      placesTheTailHasBeen.add(currentKnotPositions[9]);
    }
  }

  @Override
  public void moveDown(final int amount)
  {
    for (int i=0; i<amount; i++)
    {
      currentKnotPositions[0].moveDown();
      moveKnots();
      placesTheTailHasBeen.add(currentKnotPositions[9]);
    }
  }

  @Override
  public void moveLeft(final int amount)
  {
    for (int i=0; i<amount; i++)
    {
      currentKnotPositions[0].moveLeft();
      moveKnots();
      placesTheTailHasBeen.add(currentKnotPositions[9]);
    }
  }

  @Override
  public void moveRight(final int amount)
  {
    for (int i=0; i<amount; i++)
    {
      currentKnotPositions[0].moveRight();
      moveKnots();
      placesTheTailHasBeen.add(currentKnotPositions[9]);
    }
  }

  private void moveKnots()
  {
    for(int i=0; i<9; i++)
    {
      moveKnotToFollowOtherKnot(currentKnotPositions[i], currentKnotPositions[i+1]);
    }
  }

  private void moveKnotToFollowOtherKnot(final Coordinates knot1Position, final Coordinates knot2Position)
  {
    if (knot1Position == knot2Position) return;
    final int xDist = knot1Position.getXDistanceFrom(knot2Position);
    final int yDist = knot1Position.getYDistanceFrom(knot2Position);
    
    if (xDist == 0)
    {
      if (yDist < -1)
      {
        knot2Position.moveUp();
      }
      else if (yDist > 1)
      {
        knot2Position.moveDown();
      }
      return;
    }

    if (yDist == 0)
    {
      if (xDist < -1)
      {
        knot2Position.moveLeft();
      }
      else if (xDist > 1)
      {
        knot2Position.moveRight();
      }
      return;
    }

    if (yDist == 2)
    {
      knot2Position.moveDown();
      if (xDist < 0)
      {
        knot2Position.moveLeft();
      }
      else if (xDist > 0)
      {
        knot2Position.moveRight();
      }
      return;
    }

    if (yDist == -2)
    {
      knot2Position.moveUp();
      if (xDist < 0)
      {
        knot2Position.moveLeft();
      }
      else if (xDist > 0)
      {
        knot2Position.moveRight();
      }
      return;
    }

    if (xDist == 2)
    {
      knot2Position.moveRight();
      if (yDist < 0)
      {
        knot2Position.moveUp();
      }
      else if (yDist > 0)
      {
        knot2Position.moveDown();
      }
      return;
    }

    if (xDist == -2)
    {
      knot2Position.moveLeft();
      if (yDist < 0)
      {
        knot2Position.moveUp();
      }
      else if (yDist > 0)
      {
        knot2Position.moveDown();
      }
      return;
    }
  }

  @Override
  public long getNumberOfPositionsVisitedByTail()
  {
    return placesTheTailHasBeen.size();
  }
}

And the part 2 driver is basically identical to part 1’s and uses the same parsing function:

  public static long part2(final String[] day09InputLines)
  {
    final RopeSimulation rs2 = new RopeSimulation2();
    for (final String movementDescription : day09InputLines)
    {
      doMovement(rs2, movementDescription);
    }
    return rs2.getNumberOfPositionsVisitedByTail();
  }

Day 9 was another where the code was fairly readily apparent but the fun was in figuring out a lean and clean way to do it without millions of nested if statements. I re-wrote parts of my solution several times before I ended up with what I think is pretty tidy. Plus I got to use a lambda, and that’s always a win!

1 Like

Well I’m on to day 8 now. I won’t peek I promise!

Day 9, I got part one done quickly, go to do part 2, some error gave me the wrong answer (Which was one off!).

The only real difference with how I counted the spots, PHolder used a numbering system where it was y*1000+x, and I just made a string (x + ‘x’ + y, so ‘0x0’, ‘4x6’, etc.).

Movement code is all my own however (with some pre-optimization going on, which cause some knots to move two far during steps)

Nothing to comment on block by block today from me, so here’s the code.

Actually it’s a little more complex/subtle than that. In Java, your own custom objects are only comparable as pointer unless you implement to methods hashCode() and equals(). So for example, if you don’t implement them and you had x=new Foo(12,34); y = new Foo(12,34); then x.equals(y) is false because they don’t occupy the same memory. Depending on how you implement hashCode() and equals() for the Foo class, you can make them equal. So what you saw was my crappy little hashCode() implementation. The Java logic is: if the hashCode() results for two instances differ, the objects themselves must also differ. If the hashCode() results for two instances are the same, than equals() will have the chance to decide if the two instances match.

I did it that way so that I could throw my Coordinate()s into a Set and thus two Coordinate(x,y) instances with the same x,y would match, even though they’re not located in the same memory address.

Day 10 is building a little virtual machine that runs 2 different instructions. The trick is that the instructions take 1 or 2 cycles and you have to have the ability to capture state from the machine even when an instruction has not completed its multiple cycles.

I created a class called ElfMachine and then it eventually got renamed to ElfMachine1 when I started part 2.

final class ElfMachine1
{
  final String[] instructions;

  public ElfMachine1(final String[] instructions)
  {
    this.instructions = instructions;
  }

  public long[] runProgramGatheringXValuesAtInterestingCycles(final int[] interestingcycles)
  {
    final long[] result = new long[interestingcycles.length];
    int cycle = -1;
    int numCyclesUntilCurrentInstructionCompletes = 1;
    boolean moreInstructions = true;
    int instructionPointer = -1;
    int interestingCycleIndex = 0;
    int xValue = 1;
    int xInc = 0;
    
    while (moreInstructions)
    {
      cycle++;
      if (cycle == interestingcycles[interestingCycleIndex])
      {
        result[interestingCycleIndex] = xValue;
        interestingCycleIndex++;
        if (interestingCycleIndex >= interestingcycles.length)
        {
          return result;  // Can't get any more useful data from this program, so stop
        }
      }

      numCyclesUntilCurrentInstructionCompletes--;
      if (numCyclesUntilCurrentInstructionCompletes == 0)
      {
        xValue += xInc; xInc = 0;
        instructionPointer++;
        if (instructionPointer >= instructions.length)
        {
          moreInstructions = false;
          return result;  // No more instructions
        }
        final String currentInstruction = instructions[instructionPointer];
        final String[] instructionParts = currentInstruction.trim().split(" ");
        switch (instructionParts[0])
        {
          case "noop": numCyclesUntilCurrentInstructionCompletes =1; xInc = 0; break;
          case "addx": numCyclesUntilCurrentInstructionCompletes =2; xInc = Integer.parseInt(instructionParts[1]); break;
          default:  throw new IllegalStateException("Invalid instruction: " + currentInstruction);
        }
      }
    }

    return result;
  }
}

The driver just had to implement the sum of the multiplications:

  private static final int[] interestingCycles = {20, 60, 100, 140, 180, 220};
  public static long part1(final String[] day10InputLines)
  {
    final ElfMachine1 em = new ElfMachine1(day10InputLines);
    final long[] xValueAtInterestingCycles = em.runProgramGatheringXValuesAtInterestingCycles(interestingCycles);
    long sum = 0;
    for (int i=0; i<interestingCycles.length; i++)
    {
      sum += interestingCycles[i]*xValueAtInterestingCycles[i];
    }
    return sum;
  }

For part 2, things got a little trickier. I decided it would be better to copy my ElfMachine to a new file and make an ElfMachine2. I struggled and wasted a good 10 minutes because I initially put the storePixelIfRequired() call at the top of the loop instead of after the instruction decoding at the bottom of the loop. Surprisingly, this made a big difference in the output.

final class ElfMachine2
{
  private final String[] instructions;
  private final int screenWidth;
  private final int screenHeight;
  
  public ElfMachine2(final String[] instructions, final int screenWidth, final int screenHeight)
  {
    this.instructions = instructions;
    this.screenWidth = screenWidth;
    this.screenHeight = screenHeight;
  }

  public final char[][] runProgramWithScreenOutput()
  {
    final char[][] screen = new char[screenWidth][screenHeight];
    int cycle = -1;
    int numCyclesUntilCurrentInstructionCompletes = 1;
    boolean moreInstructions = true;
    int instructionPointer = -1;
    int xValue = 1;
    int xInc = 0;
    
    clearScreen(screen);
    
    while (moreInstructions)
    {
      cycle++;

      numCyclesUntilCurrentInstructionCompletes--;
      if (numCyclesUntilCurrentInstructionCompletes == 0)
      {
        xValue += xInc; xInc = 0;
        instructionPointer++;
        if (instructionPointer >= instructions.length)
        {
          moreInstructions = false;
          return screen;  // No more instructions
        }
        final String currentInstruction = instructions[instructionPointer];
        final String[] instructionParts = currentInstruction.trim().split(" ");
        switch (instructionParts[0])
        {
          case "noop": numCyclesUntilCurrentInstructionCompletes =1; xInc = 0; break;
          case "addx": numCyclesUntilCurrentInstructionCompletes =2; xInc = Integer.parseInt(instructionParts[1]); break;
          default:  throw new IllegalStateException("Invalid instruction: " + currentInstruction);
        }
      }

      final int crtPixelNumber = cycle; 
      storePixelIfRequired(screen, crtPixelNumber, xValue);
    }

    return screen;
  }

  private void storePixelIfRequired(final char[][] screen, int crtPixelNumber, int xValue)
  {
    final int spritePos = xValue;
    final int crtPos = crtPixelNumber % 40;
    if ( (crtPos == spritePos-1) || (crtPos == spritePos) || (crtPos == spritePos+1))
    {
      storePixel(screen, crtPixelNumber);
    }
  }

  private void storePixel(final char[][] screen, final int crtPixelNumber)
  {
    final int y = crtPixelNumber / 40;
    final int x = crtPixelNumber % 40;
    screen[x][y] = '#';
  }

  private void clearScreen(final char[][] screen)
  {
    for (int y=0; y<screenHeight; y++)
    {
      for (int x=0; x<screenWidth; x++)
      {
        screen[x][y] = '.';
      }
    }
  }
}

The driver for part 2 is pretty straightforward, but because it is a spoiler for the goal of part 2, I will put it behind spoiler protection:

  public static long part2(final String[] day10InputLines)
  {
    final ElfMachine2 em = new ElfMachine2(day10InputLines, 40, 6);
    final char[][] screen = em.runProgramWithScreenOutput();
    for(int y=0; y<6; y++)
    {
      for (int x=0; x<40; x++)
      {
        System.out.print(screen[x][y]);
      }
      System.out.println();
    }
    return 0;
  }

Day 10 part 1 should not have gotten the correct answer. I bet if I had a different input, I would have had to spend more time on it.

Because of a pattern I noticed with how the input code is written, when I was working on part 2. I ended up with this magical line

const data = d.split('\n').join(' ').split(' ');

Basically, I only added to the register when the value I was looking at was a number.

I used some crazy math in doing my work, though.

Today’s code

Day 11 is about monkeys and throwing around numbers between them. I created a Monkey class for each monkey, and then a MonkeyCage class to keep them all together in.

The input is very verbose, with the definition of each monkey over multiple lines (6 lines per monkey with a blank between them.) Here’s the first monkey from the provided example (with 4 monkeys total.)

Monkey 0:
  Starting items: 79, 98
  Operation: new = old * 19
  Test: divisible by 23
    If true: throw to monkey 2
    If false: throw to monkey 3

Since I wanted to be as fast as possible, I decided to not even bother parsing the input at all, and went for taking my supplied input (which had 8 monkeys) and manually converting them to calls to new monkey(...) with the correct values from the input. This does mean that I can’t show my driver without showing my actual inputs, so I will probably elide some monkeys. Because I forsaw something about the inputs, I had a very good guess about part 2, so started off with Money1 and MonkeyCage1 figuring I would need to make certain changes for part 2 that would be easier if I copied my part 1 as a starting point.

Here is the Monkey1 class, you can see how I build the constructor to take the inputs I would extract from the problem input Monkey1(final MonkeyCage1 monkeyCage, final int monkeyNumber, final int[] items, final int plus, final int mult, final boolean timesSelf, final int div, final int trueMonkey, final int falseMonkey) The three possible things a monkey can do are add to the worry level, multiply by the worry level, or square the worry level (multiply it by itself.) Then the monkey does a divisibility check based on a divisor and forwards to one of two monkeys depending on if the value if divisible or not.

final class Monkey1
{
  private int[] items = new int[0];
  private final int plus;
  private final int mult;
  private final boolean timesSelf;
  private final int div;
  private final int trueMonkey;
  private final int falseMonkey;
  private int numItemsInspected = 0;
  private final MonkeyCage1 monkeyCage;
  private final List<Integer> futureItems = new ArrayList<>();
  final int monkeyNumber;

  public Monkey1(final MonkeyCage1 monkeyCage, final int monkeyNumber, final int[] items, final int plus, final int mult, final boolean timesSelf, final int div, final int trueMonkey, final int falseMonkey)
  {
    this.monkeyCage = monkeyCage;
    this.monkeyNumber = monkeyNumber;  // for debugging
    for(int i=0; i<items.length; i++)
    {
      this.futureItems.add(items[i]);
    }
    this.plus = plus;
    this.mult = mult;
    this.timesSelf = timesSelf;
    this.div = div;
    this.trueMonkey = trueMonkey;
    this.falseMonkey = falseMonkey;
  }

  public void takeTurn()
  {
    items = makeFutureItemsCurrent();
    
    if (false)
    {
      System.out.print("Monkey " + monkeyNumber);
      System.out.print(" start of turn: ");
      for (final int worryLevel : items)
      {
        System.out.print(" " + worryLevel);
      }
      System.out.println();
    }

    for (final int worryLevel : items)
    {
      numItemsInspected++;
      int newWorryLevel;
      if (timesSelf)
      {
        newWorryLevel = worryLevel * worryLevel;
      }
      else if (plus != 0)
      {
        newWorryLevel = worryLevel + plus;
      }
      else if (mult != 0)
      {
        newWorryLevel = worryLevel * mult;
      }
      else throw new IllegalStateException("Monkey has no operation");
      
      newWorryLevel=newWorryLevel / 3;
      
      boolean isTrueMonkey = (newWorryLevel % div) == 0;
      if (isTrueMonkey)
        monkeyCage.throwToMonkey(trueMonkey, newWorryLevel);
      else
        monkeyCage.throwToMonkey(falseMonkey, newWorryLevel);
    }
  }
  
  private int[] makeFutureItemsCurrent()
  {
    final int[] result = new int[futureItems.size()];
    for (int i=0; i<futureItems.size(); i++)
    {
      result[i] = futureItems.get(i);
    }
    futureItems.clear();
    return result;
  }

  public void addFutureItem(final int worryLevel)
  {
    futureItems.add(worryLevel);
  }
  
  public int getNumItemsInspected()
  {
    return numItemsInspected;
  }
}

The MonkeyCage class is what actually creates and houses the monkeys, so the driver will pass in the definition for each monkey and it will get stored in the array of monkeys in the cage. It also handled forwarding work between the monkeys.

final class MonkeyCage1 implements MonkeyCage
{
  private Monkey1 monkeysInCage[];
  private final int maxNumberOfMonkeys;
  private int numberOfMonkeys = 0;
  
  MonkeyCage1(final int maxNumberOfMonkeys)
  {
    this.maxNumberOfMonkeys = maxNumberOfMonkeys;
    this.monkeysInCage = new Monkey1[maxNumberOfMonkeys];
  }
  
  @Override
  public void putMonkeyInCage(final int[] items, final int plus, final int mult, final boolean timesSelf, final int div, final int trueMonkey, final int falseMonkey)
  {
    monkeysInCage[numberOfMonkeys] = new Monkey1(this, numberOfMonkeys, items, plus, mult, timesSelf, div, trueMonkey, falseMonkey);
    numberOfMonkeys++;
  }

  public void throwToMonkey(final int monkeyToThrowTo, final int worryLevel)
  {
    monkeysInCage[monkeyToThrowTo].addFutureItem(worryLevel);
  }
  
  @Override
  public long letMonkeysInspectItems(final int numberOfRounds)
  {
    for (int i=0; i<numberOfRounds; i++)
    {
      for (final Monkey1 monkey : monkeysInCage)
      {
        monkey.takeTurn();
      }
    }
    return getPart1Answer();
  }
  
  private long getPart1Answer()
  {
    final int[] numItemsPerMonkey = new int[numberOfMonkeys];
    for (int i=0; i<numberOfMonkeys; i++)
    {
      numItemsPerMonkey[i] = monkeysInCage[i].getNumItemsInspected();
      // System.out.println(i + ": " + numItemsPerMonkey[i]);
    }
    Arrays.sort(numItemsPerMonkey);
    return numItemsPerMonkey[numberOfMonkeys-1] * numItemsPerMonkey[numberOfMonkeys-2];
  }
}

Other than the obvious interface for MonkeyCage there is the driver. I am eliding all but two of my inputs. Also, because of my hard coding, I have different driver methods for the unit test and the personal/provided input.

  public static long part1Test()  // For unit test of the provided example
  {
    final MonkeyCage mc = new MonkeyCage1(4);
    putTestMonkeysInCage(mc);
    return mc.letMonkeysInspectItems(20);
  }

  // The 4 example monkeys
  private static void putTestMonkeysInCage(final MonkeyCage mc)
  {
    mc.putMonkeyInCage(new int[] {79, 98}, 0, 19, false, 23, 2, 3);
    mc.putMonkeyInCage(new int[] {54, 65, 75, 74}, 6, 0, false, 19, 2, 0);
    mc.putMonkeyInCage(new int[] {79, 60, 97}, 0, 0, true, 13, 1, 3);
    mc.putMonkeyInCage(new int[] {74}, 3, 0, false, 17, 0, 1);
  }
  
  public static long part1()
  {
    final MonkeyCage mc = new MonkeyCage1(8);
    putMonkeysInCage(mc);
    return mc.letMonkeysInspectItems(20);
  }

  private static void putMonkeysInCage(final MonkeyCage mc)
  {
    mc.putMonkeyInCage(new int[] {84, 72, 58, 51}, 0, 3, false, 13, 1, 7);
    // 6 of my monkeys are removed, as these are hard coded from my specific inputs
    mc.putMonkeyInCage(new int[] {91}, 1, 0, false, 19, 2, 5);
  }

As this has already gotten pretty long, I will continue part 2 in a new post.

Day 11 part 2 is going to be challenging for a lot of people. The big change in part 2 is that the worry levels are no longer being cut down by being divided by 3. This means they will blow up exponentially… and Eric gives you a very clear warning about that.

I saw it coming from part 1 because (warning this spoiler will give away the technique needed to solve part 2 in non-exponential time) all the divisors were prime numbers, so this implies working in a Galois Field. A quote from someone else who talked online about the problem: “It works because you’re working with all the monkeys in a finite field (Galois field). All the operations the monkeys do are based on modulo, so if you work in a finite field that’s bounded by the LCM of all monkeys’ modulos, then all the operations will work as if there wasn’t a finite field.”

Even though I knew I wouldn’t be able to brute force it, I pretended I could and wrote the code anyway, using BigIntegers. After about 900 iterations of the 10_000 it was no longer responding in linear time, and I stopped it running after waiting about one minute. This wasted some time on my submission time, but I though I would do it for completeness anyway. I named those classes Monkey2a and MonkeyCage2a, and I could include them below, but I don’t know they’re really that valuable, someone could ask to see them and I would post them, I guess.

I created Monkey2 and MonkeyCage 2 to address part 2. The big change is to pass in the manually calculated values for the primes for all the monkeys as worryCap. Again I will elide my specific inputs.

Monkey2:

final class Monkey2
{
  private long[] items = new long[0];
  private final int plus;
  private final int mult;
  private final boolean timesSelf;
  private final int div;
  private final int trueMonkey;
  private final int falseMonkey;
  private int numItemsInspected = 0;
  private final MonkeyCage2 monkeyCage;
  private final List<Long> futureItems = new ArrayList<>();
  final int monkeyNumber;
  final long worryCap;

  public Monkey2(final MonkeyCage2 monkeyCage, final int monkeyNumber, final long worryCap, final int[] items, final int plus, final int mult, final boolean timesSelf, final int div, final int trueMonkey, final int falseMonkey)
  {
    this.monkeyCage = monkeyCage;
    this.monkeyNumber = monkeyNumber;  // for debugging
    this.worryCap = worryCap;
    for(int i=0; i<items.length; i++)
    {
      this.futureItems.add((long) items[i]);
    }
    this.plus = plus;
    this.mult = mult;
    this.timesSelf = timesSelf;
    this.div = div;
    this.trueMonkey = trueMonkey;
    this.falseMonkey = falseMonkey;
  }

  public void takeTurn()
  {
    items = makeFutureItemsCurrent();
    
    if (false)
    {
      System.out.print("Monkey " + monkeyNumber);
      System.out.print(" start of turn: ");
      for (final long worryLevel : items)
      {
        System.out.print(" " + worryLevel);
      }
      System.out.println();
    }

    for (final long worryLevel : items)
    {
      numItemsInspected++;
      long newWorryLevel;
      if (timesSelf)
      {
        newWorryLevel = worryLevel * worryLevel;
      }
      else if (plus != 0)
      {
        newWorryLevel = worryLevel + plus;
      }
      else if (mult != 0)
      {
        newWorryLevel = worryLevel * mult;
      }
      else throw new IllegalStateException("Monkey has no operation");
      
      // newWorryLevel=newWorryLevel / 3;
      newWorryLevel=newWorryLevel % worryCap;
      
      boolean isTrueMonkey = (newWorryLevel % div) == 0;
      if (isTrueMonkey)
        monkeyCage.throwToMonkey(trueMonkey, newWorryLevel);
      else
        monkeyCage.throwToMonkey(falseMonkey, newWorryLevel);
    }
  }
  
  private long[] makeFutureItemsCurrent()
  {
    final long[] result = new long[futureItems.size()];
    for (int i=0; i<futureItems.size(); i++)
    {
      result[i] = futureItems.get(i);
    }
    futureItems.clear();
    return result;
  }

  public void addFutureItem(final long worryLevel)
  {
    futureItems.add(worryLevel);
  }
  
  public int getNumItemsInspected()
  {
    return numItemsInspected;
  }
}

and MonkeyCage2:

final class MonkeyCage2 implements MonkeyCage
{
  private Monkey2 monkeysInCage[];
  private final int maxNumberOfMonkeys;
  private int numberOfMonkeys = 0;
  private final long worryCap;
  
  MonkeyCage2(final int maxNumberOfMonkeys, final long worryCap)
  {
    this.maxNumberOfMonkeys = maxNumberOfMonkeys;
    this.monkeysInCage = new Monkey2[maxNumberOfMonkeys];
    this.worryCap = worryCap;
  }
  
  @Override
  public void putMonkeyInCage(final int[] items, final int plus, final int mult, final boolean timesSelf, final int div, final int trueMonkey, final int falseMonkey)
  {
    monkeysInCage[numberOfMonkeys] = new Monkey2(this, numberOfMonkeys, worryCap, items, plus, mult, timesSelf, div, trueMonkey, falseMonkey);
    numberOfMonkeys++;
  }

  public void throwToMonkey(final int monkeyToThrowTo, final long worryLevel)
  {
    monkeysInCage[monkeyToThrowTo].addFutureItem(worryLevel);
  }
  
  @Override
  public long letMonkeysInspectItems(final int numberOfRounds)
  {
    for (int i=0; i<numberOfRounds; i++)
    {
      for (final Monkey2 monkey : monkeysInCage)
      {
        monkey.takeTurn();
      }
    }
    return getPart2Answer();
  }
  
  private long getPart2Answer()
  {
    final long[] numItemsPerMonkey = new long[numberOfMonkeys];
    for (int i=0; i<numberOfMonkeys; i++)
    {
      numItemsPerMonkey[i] = monkeysInCage[i].getNumItemsInspected();
      // System.out.println(i + ": " + numItemsPerMonkey[i]);
    }
    Arrays.sort(numItemsPerMonkey);
    return numItemsPerMonkey[numberOfMonkeys-1] * numItemsPerMonkey[numberOfMonkeys-2];
  }
}

and then adding a couple of new methods to the driver:

  public static long part2Test()  // for the unit test of the example input
  {
    final long worryCap = 23*19*13*17;
    final MonkeyCage mc = new MonkeyCage2(4, worryCap);
    putTestMonkeysInCage(mc);
    return mc.letMonkeysInspectItems(10_000);
  }

  public static long part2()
  {
    final long worryCap = 13* /* 6 monkey values elided */ *19;
    final MonkeyCage2 mc = new MonkeyCage2(8, worryCap);
    putMonkeysInCage(mc);
    return mc.letMonkeysInspectItems(10_000);
  }

Day 11: Finally a puzzle that provided a challenge. At first I thought the problem with Part 2 was the large number of rounds. Then I realized it was the size of the numbers. I suspected modular arithmetic was involved and the presence of prime numbers in the input data was very suspicious. Not being familiar with Galois fields (as mentioned in a previous message), I made an educated guess for what to try. I was very surprised that it worked on the sample data. Through a comedy of errors I needed three attempts to get my second gold star. I should have derived the product of primes from the input data instead of hard coding it.

From Wikipedia:

Galois Field (a mathematical concept that explains the “answer” for part 2) Finite field - Wikipedia quote "Finite fields are widely used in number theory, as many problems over the integers may be solved by reducing them modulo one or several prime numbers. "