Advent of Code 2021

[PHolder]

Part two of day 9 had me brute force a flood fill for the first time in my programming career. I'm sure it's possible to do it more efficiently than I did, as I was definitely iterating over the same spots too many times, but, for expediency, I did what I knew would work rather than getting fancier.

I represented the given data in a class I called HeightMap. I thought it would make my life easier if a grew the map by a unit in every direction, so that I could work inside the perimeter without worrying about special casing for the edges. (Not sure that really paid off, but neither do I think it really hurt any.) It didn't start out storing the locations for part one, because of course the part one answer didn't call for them. When I realized I would need them for part two, I had to quickly refactor my part one to start using a Point record and store all the Points from part one to use in part two. The HeightMap class has all the logic to find the answers, but I ended up including a sort() in the method for part two.

The HeightMap class

final class HeightMap
{
  final int[][] heights;
  final int width;
  final int height;
  HeightMap(final String[] mapHeights)
  {
    width  = mapHeights[0].length();
    height = mapHeights.length;
    heights = new int[width+2][height+2];

    for (int x=0; x<=width+1; x++)
    {
      for (int y=0; y<=height+1; y++)
      {
        heights[x][y] = -1;
      }
    }

    for (int x=1; x<=width; x++)
    {
      for (int y=1; y<=height; y++)
      {
        heights[x][y] = mapHeights[y-1].charAt(x-1)-'0';
      }
    }
  }

  int getRiskLevel()
  {
    int totalRiskLevel = 0;
    final Point[] allLowPoints = getAllLowPoints();
    for (final Point p : allLowPoints)
    {
      totalRiskLevel += 1+heights[p.x][p.y];
    }
    return totalRiskLevel;
  }

  @org.eclipse.jdt.annotation.NonNullByDefault({})
  record Point(int x, int y) {}
 
  Point[] getAllLowPoints()
  {
    final List<Point> lowPoints = new ArrayList<>();
    for (int x=1; x<=width; x++)
    {
      for (int y=1; y<=height; y++)
      {
        if (isLowPoint(new Point(x,y)))
        {
          lowPoints.add(new Point(x,y));
        }
      }
    }
    return lowPoints.toArray(new Point[lowPoints.size()]);
  }
 
  int[] getSizesOfAllBasins()
  {
    final List<Integer> basinSizes = new ArrayList<>();
    for (final Point p : getAllLowPoints())
    {
      final int basinSize = getBasinSize(p);
      basinSizes.add(basinSize);
    }
    final int[] result = new int[basinSizes.size()];
    for (int i=0; i<basinSizes.size(); i++) result[i] = basinSizes.get(i);
    return result;
  }

  private int getBasinSize(final Point startingPoint)
  {
    final Set<Point> pointsInBasin = new HashSet<>();
    pointsInBasin.add(startingPoint);

    growBasin(pointsInBasin);
 
    return pointsInBasin.size();
  }

  private void growBasin(final Set<Point> pointsInBasin)
  {
    final Set<Point> pointsToAdd = new HashSet<>();
    for (final Point p : pointsInBasin)
    {
      final Point[] adjacentPoints = getAdjacentPoints(p);
      for (final Point adjacentPoint : adjacentPoints)
      {
        if (!pointsInBasin.contains(adjacentPoint))
        {
          if (heights[adjacentPoint.x][adjacentPoint.y] < 9)
          {
            pointsToAdd.add(adjacentPoint);
          }
        }
      }
    }
    if (!pointsToAdd.isEmpty())
    {
      pointsInBasin.addAll(pointsToAdd);
      growBasin(pointsInBasin);  // recursively check the newly added points
                                 // (inefficient because it will recheck already checked points too)
    }
  }

  private boolean isLowPoint(final Point point)
  {
    final Point[] adjacentPoints = getAdjacentPoints(point);
    final int c = heights[point.x][point.y];
    boolean allGreater = true;
    for (final Point otherPoint : adjacentPoints)
    {
      if (heights[otherPoint.x][otherPoint.y] <= c)
      {
        allGreater = false;
        break;
      }
    }
    return allGreater;
  }

  private Point[] getAdjacentPoints(final Point p)
  {
    final Set<Point> adjacentPoints = new HashSet<>();
    int t = heights[p.x][p.y-1];
    if (t >=0) adjacentPoints.add(new Point(p.x, p.y-1));
    int l = heights[p.x-1][p.y];
    if (l >=0) adjacentPoints.add(new Point(p.x-1, p.y));
    int r = heights[p.x+1][p.y];
    if (r >=0) adjacentPoints.add(new Point(p.x+1, p.y));
    int b = heights[p.x][p.y+1];
    if (b >=0) adjacentPoints.add(new Point(p.x, p.y+1));
    return adjacentPoints.toArray(new Point[adjacentPoints.size()]);
  }

  @Override
  public String toString()
  {
    final StringBuilder sb = new StringBuilder();
    for (int y=0; y<=height+1; y++)
    {
      for (int x=0; x<=width+1; x++)
      {
        if (heights[x][y] < 0)
          sb.append('X');
        else
          sb.append((char)('0'+heights[x][y]));
      }
      sb.append('\n');
    }
    return sb.toString();
  }
}

Here's the part one and part two code, including the aforementioned sort(). I don't think there is anything here to bother spoiler blurring:

public static long getPart1Answer(final String day09Input, final String[] day09InputLines)
{
  final HeightMap hm = new HeightMap(day09InputLines);
  return hm.getRiskLevel();
}

public static long getPart2Answer(final String day09Input, final String[] day09InputLines)
{
  final HeightMap hm = new HeightMap(day09InputLines);
  final int[] basinSizes = hm.getSizesOfAllBasins();
  Arrays.sort(basinSizes);
  return (long)basinSizes[basinSizes.length-1] *
         (long)basinSizes[basinSizes.length-2] *
         (long)basinSizes[basinSizes.length-3];
}

 

[Paul F]

While an intellectual challenge for sure, there seems little benefit to pursuing it, especially if you're at all hurrying to solve quickly.

I'll agree if you omit 'especially'. I have no hope of getting on the Leaderboard. I don't even start the puzzle until the morning - at least 6 hours after it's posted. I enjoy thinking about the problem and working on the program at a leisurely pace.

If you want to get on the Leaderboard you may have to abandon your well-organized programming method and resort to a single 'for' loop with single character variables .

My previous Day 8 Part 2 algorithm was not very satisfying. It required a lot of programming to handle all the individual cases which took far longer than the execution time saved by not brute-forcing - which, I think was your point.

I thought of another interesting approach that's easier to follow:

We are already given '1', '4', '7', (with unique number f segments)
Determine the frequency of each segment over the ten numbers:
A=8, B=6, C=8, D=7, E=4, F=9, G=7
B, E, and F are unique
A and C can be resolved by using digit '1' (only has C)
D and G can be resolved by using digit '4' (only has D)
Knowing all the segments we can make up the remaining digits

 

[miquelfire]

I'm in the same boat as Paul.

My coding style might be closer to the lines of the folks on the leaderboard however even though I may be at a point where at least 8 hours past by already before I even read the instructions.

 

[PHolder]

may have to abandon your well-organized programming method and resort to a single 'for' loop with single character variables .

*shiver* no can do. Too many years of working the way I do. I know this keeps me off the leaderboard, but I would like to, at least once again this year, be in the "top 1000" if possible. My usual range is 20-30 mins for part one and sometimes very quick for part two depending, but more often an hour to an hour and a half. This puts me in the 4000-7000 range, on average. The satisfaction of a job fairly well done, with unit tests and readable code, is really all I take from it. And sharing and discussing with you all here, too, of course

 

[Paul F]

Day 9:

Part 1 is fairly straightforward. I added a border of 9s to avoid dealing with the edge conditions. I also saved the coordinates of the low points for use in part 2.

I had to think about Part 2 for a while, not sure how to map out the basins. Then I thought of the following fairly simple approach. To my great surprise, it gave the right answer the first time. It starts each basin at a low point found in Part 1.

# Part 2

    def recurse(cave, row, col, size):
        # this is called with a (row, col) point that is in the current basin
        # it increments the size and finds surrounding points in the basin
        size+=1

        # save the current level for later comparison
        level=cave[row][col]
        
        # set the level to -1 so it doesn't get counted again
        cave[row][col]=-1

        # for each point: left, right, up, and down
        # if the level is the same or higher than the current level
        #  and is not 9, it is in the current basin
        for coords in ((row, col-1), (row, col+1), (row-1, col), (row+1, col)):
            r=coords[0]
            c=coords[1]
            if cave[r][c]>=level and cave[r][c]!=9:
                size=recurse(cave, r, c, size)
                pass
            pass

        return size

    sizes=[]
    for low_point in low_points:
        row=low_point[0]
        col=low_point[1]

        # find the basin around this point
        size=recurse(cave, row, col, 0)

        # save the size of the basin
        sizes.append(size)
        pass

    # sort the sizes so we can easily find the three highest
    sizes.sort()

    print('Part 2 - Product of the sizes of the three largest basins:', sizes[-1]*sizes[-2]*sizes[-3])

 

[PHolder]

Day 10 tests whether you know how to handle and validate nesting of things. I believe the most common way to do this is with a stack of some sort. Assuming you know this, then it's not terribly challenging to solve day 10. Part one has you finding improperly nested items and part two has you filter out the improperly nested ones to find the incomplete ones and calculate how to complete them. You do this by popping the stack of open braces to figure out what the corresponding close brace would be.

I built a more general class to handle the task, and in theory it could work with any pairs of open and close characters, not just the 4 braces used by the problem. (I just can't not be general when it costs so little, but of course that means I'll never be on the leader boards.)

Here is my NestingChecker class:

the NestingChecker class

final class NestingChecker
{
  private final Deque<Character> stack = new ArrayDeque<>();
  private final String openChars;
  private final String closeChars;

  NestingChecker(final String openChars, final String closeChars)
  {
    this.openChars = openChars;
    this.closeChars = closeChars;
  }
 
  @org.eclipse.jdt.annotation.NonNullByDefault({})
  record CheckResult(boolean isProperlyNested, char errorChar) {}
 
  CheckResult checkNestingOf(final String stringToCheck)
  {
    stack.clear();
    for (final char c : stringToCheck.toCharArray())
    {
      if (isOpenChar(c))
      {
        stack.push(c);
      }
      else if (isCloseChar(c))
      {
        if (stack.isEmpty()) return new CheckResult(false, c);
        final char openC = stack.pop();
        if (!charsCorrespond(openC, c)) return new CheckResult(false, c);
      }
      else
      {
        // ignore non-open and non-close chars?
        System.out.println("Non-open and non-close char detected: " + c);
      }
    }
    // To make this a proper checker of balanced quotes one would need to check here if the stack was empty
    return new CheckResult(true, ' ');
  }

  private boolean charsCorrespond(final char openChar, final char closeChar)
  {
    for (int i=0; i<openChars.length(); i++)
    {
      if (openChars.charAt(i) == openChar)
      {
        if (closeChars.charAt(i) == closeChar) return true;
      }
    }
    return false;
  }

  private boolean isOpenChar(final char c)
  {
    if (openChars.contains(""+c)) return true;
    return false;
  }

  private boolean isCloseChar(final char c)
  {
    if (closeChars.contains(""+c)) return true;
    return false;
  }

  // Really should have just returned the necessary characters and moved the problem math out
  // to the calling code, but hindsight is 20/20 as they say...  that's just a small refactor away
  long getScoreOfNestingCompletion(final String input)
  {
    final CheckResult cr = checkNestingOf(input);
    if (!cr.isProperlyNested) throw new IllegalStateException("Can't do nesting completion on improperly nested input: " + input);

    long sum=0;
    while (!stack.isEmpty())
    {
      final char openChar = stack.pop();
      final char neededCloseChar = getNeededCloseChar(openChar);
      sum*=5;
      switch (neededCloseChar)
      {
        case ')': sum+=1; break;
        case ']': sum+=2; break;
        case '}': sum+=3; break;
        case '>': sum+=4; break;
        default:
          break;
      }
    }
    
    return sum;
  }

  private char getNeededCloseChar(final char openChar)
  {
    for (int i=0; i<openChars.length(); i++)
    {
      if (openChars.charAt(i) == openChar)  return closeChars.charAt(i);
    }
    throw new IllegalStateException("Can't getNeededCloseChar: " + openChar);
  }
}

The two solver methods are pretty straight forward, not sure there is anything interesting enough to be a spoiler here:

public static long getPart1Answer(final String day10Input, final String[] day10InputLines)
{
  final NestingChecker nc = new NestingChecker("([{<", ")]}>");
  long sum = 0;
  for (final String input : day10InputLines)
  {
    final CheckResult cr = nc.checkNestingOf(input);
    if (!cr.isProperlyNested())
    {
      switch(cr.errorChar())
      {
        case ')': sum +=3; break;
        case ']': sum +=57; break;
        case '}': sum +=1197; break;
        case '>': sum +=25137; break;
        default:
          break;
      }
    }
  }
  return sum;
}

public static long getPart2Answer(final String day10Input, final String[] day10InputLines)
{
  final NestingChecker nc = new NestingChecker("([{<", ")]}>");
  final List<Long> unsortedResults = new ArrayList<>();
  for (final String input : day10InputLines)
  {
    final CheckResult cr = nc.checkNestingOf(input);
    if (cr.isProperlyNested())
    {
      final long itemResult = nc.getScoreOfNestingCompletion(input);
      unsortedResults.add(itemResult);
    }
  }
  final Long[] sortedResults = unsortedResults.toArray(new Long[0]);
  Arrays.sort(sortedResults);
  return sortedResults[sortedResults.length/2];
}

One thing to note is that my "isProperlyNested" result is a bit of a lie. It's just indicating that it's not an invalid nesting (for part 1) not that it's actually fully validly nested, as that was never called for. One more line at the end of the method in the checker class would handle that, where one would need to make sure the stack is empty to get an indication of proper nesting.

 

[PHolder]

I was expecting a huge input for Day 11, and it wasn't huge at all. It wasn't really a much of a challenge either, I don't think.

I created a class to model the octopus cave, and had it able to iterate a day at a time while performing the necessary updates and tracking the stats (like the number of flashes and iterations and if the part two condition was met on any given iteration.) This felt a lot like the challenge from day 9, which I tackled the edges cases by adding a perimeter. This time I decided, for kicks, to add the nine if statements to handle all the edge cases.

The OctopusCave class

final class OctopusCave
{
  private final int width;
  private final int height;
  private final int[][] octopi;
  private long numberOfFlashes = 0;
  private long iterationNumber = 0;
  private boolean didAllFlashAtOnce = false;
  
  public OctopusCave(final String[] octopusLayout)
  {
    width = octopusLayout[0].length();
    height = octopusLayout.length;
    octopi = new int[width][height];
    
    for (int y=0; y<height; y++)
    {
      for (int x=0; x<width; x++)
      {
        octopi[x][y] = octopusLayout[y].charAt(x)-'0';
      }
    }
  }

  public void iterate()
  {
    iterationNumber++;
    boolean loopAgain = true;
    boolean doIncrement = true;
    while(loopAgain)
    {
      loopAgain = false;
      for (int y=0; y<height; y++)
      {
        for (int x=0; x<width; x++)
        {
          if (doIncrement)
            if (octopi[x][y]>=0) octopi[x][y]++;

          if (octopi[x][y] > 9)
          {
            numberOfFlashes++;
            if (energizeNeighbouringOctopi(x,y))
            {
              loopAgain = true;
            }
            octopi[x][y] = -1;
          }
        }
      }
      doIncrement = false;
    }

    didAllFlashAtOnce = true;
    for (int y=0; y<height; y++)
    {
      for (int x=0; x<width; x++)
      {
        if (octopi[x][y]<0)
          octopi[x][y]=0;
        else
          didAllFlashAtOnce = false;
      }
    }
  }

  private boolean energizeNeighbouringOctopi(final int x, final int y)
  {
    boolean anotherOctopusNeedsToFlash = false;

    if ((x>0) && (y>0))
    {
      if (octopi[x-1][y-1] >= 0)
        if (++octopi[x-1][y-1] > 9)  anotherOctopusNeedsToFlash = true;
    }

    if (y>0)
    {
      if (octopi[x][y-1] >= 0)
        if (++octopi[x][y-1] > 9)  anotherOctopusNeedsToFlash = true;
    }

    if ((x<width-1) && (y>0))
    {
      if (octopi[x+1][y-1] >= 0)
        if (++octopi[x+1][y-1] > 9)  anotherOctopusNeedsToFlash = true;
    }

    if (x>0)
    {
      if (octopi[x-1][y] >= 0)
        if (++octopi[x-1][y] > 9)  anotherOctopusNeedsToFlash = true;
    }

    if (x<width-1)
    {
      if (octopi[x+1][y] >= 0)
        if (++octopi[x+1][y] > 9)  anotherOctopusNeedsToFlash = true;
    }

    if ((x>0) && (y<height-1))
    {
      if (octopi[x-1][y+1] >= 0)
        if (++octopi[x-1][y+1] > 9)  anotherOctopusNeedsToFlash = true;
    }

    if (y<height-1)
    {
      if (octopi[x][y+1] >= 0)
        if (++octopi[x][y+1] > 9)  anotherOctopusNeedsToFlash = true;
    }

    if ((x<width-1) && (y<height-1))
    {
      if (octopi[x+1][y+1] >= 0)
        if (++octopi[x+1][y+1] > 9)  anotherOctopusNeedsToFlash = true;
    }

    return anotherOctopusNeedsToFlash;
  }

  public void iterateNTimes(final int numberOfIterations)
  {
    for (int i=0; i<numberOfIterations; i++) iterate();
  }
  
  @Override
  public String toString()
  {
    final StringBuilder sb = new StringBuilder();
    for (int y=0; y<height; y++)
    {
      for (int x=0; x<width; x++)
      {
        sb.append(octopi[x][y]);
      }
      sb.append('\n');
    }
    return sb.toString();
  }

  public long getNumberOfFlashes()
  {
    return numberOfFlashes;
  }

  public boolean getDidAllFlashAtOnce()
  {
    return didAllFlashAtOnce;
  }

  public long getIterationNumber()
  {
    return iterationNumber;
  }
}

To actually get the results, the code is pretty straight forward, but I will spoiler blur it since it will give away part two:

Getting the part one and part two answers

public static long getPart1Answer(final String day11Input, final String[] day11InputLines)
{
  final OctopusCave oc = new OctopusCave(day11InputLines);
  oc.iterateNTimes(100);
  return oc.getNumberOfFlashes();
}

public static long getPart2Answer(final String day11Input, final String[] day11InputLines)
{
  final OctopusCave oc = new OctopusCave(day11InputLines);
  while (!oc.getDidAllFlashAtOnce())
  {
    oc.iterate();
  }
  return oc.getIterationNumber();
}

 

[PHolder]

Okay Day 12 brought some difficulty, it took me an hour and a half for part one and then almost another hour to do part two. It's a graph problem (or at least to me that seems the most obvious way to view it.) I tackled it by making two objects, one to do cave navigation (to find the paths to solve the challenge) and one to represent each cave and it's connections to other caves.

I initially thought I had a problem with my solution for part one because of a design decision I made. I decided to make my Cave class manage lookups for all the Caves, and I also implemented three unit tests together for the three provided examples. I forgot to clear out the list of caves between each pass, so of course I didn't get correct answers for the second and third example. Adding a "newCaveSystem()" to clear it out at the start of each pass fixed it right up.

Part two was more challenging to me, for some reason. I have an approach that I knew would work, but seemed to have a mental block about how to fully implement it. In the end, I had an extra "else" I didn't need, and once I commented it out, everything came together. (I left that comment in my code, in case anyone is curious.)

Here's my Cave class, I don't think there is anything here that would be a spoiler, so not blurring:

final class Cave
{
  private static final Map<String,Cave> caveList = new HashMap<>();

  private final String caveName;
  private final Set<Cave> connectedCaves = new HashSet<>();
 
  private Cave(final String caveNameToCreate)
  {
    caveName = caveNameToCreate;
  }
 
  public void addConnectedCave(final Cave caveToConnect)
  {
    connectedCaves.add(caveToConnect);
  }

  public static Cave createOrLookupByName(final String caveNameToCreateOrLookup)
  {
    if (caveList.containsKey(caveNameToCreateOrLookup))
      return caveList.get(caveNameToCreateOrLookup);
    final Cave newCave = new Cave(caveNameToCreateOrLookup);
    caveList.put(caveNameToCreateOrLookup, newCave);
    return newCave;
  }

  public static Cave lookupByName(final String caveNameToLookup)
  {
    if (!caveList.containsKey(caveNameToLookup))
      throw new IllegalStateException("Couldn't lookup cave by name: " + caveNameToLookup);
    return caveList.get(caveNameToLookup);
  }

  public String getName()
  {
    return caveName;
  }

  public Cave[] getConnectedCaves()
  {
    final Cave[] result = connectedCaves.toArray(new Cave[0]);
    return result;
  }

  public static void newCaveSystem()
  {
    caveList.clear();
  }
}

The CaveNaviagtor class is doing most of the work. I created a findAllPaths() for part one and a findAllPaths2() which copies part one but makes the necessary change to handle the single cave that allows two visits.

The CaveNavigator class

final class CaveNavigator
{
  public CaveNavigator(final String[] day12InputLines)
  {
    Cave.newCaveSystem();
    for (final String caveConnectionPath : day12InputLines)
    {
      final String[] twoCaves = caveConnectionPath.split("\\-");
      if (twoCaves.length != 2)
        throw new IllegalStateException("Unable to parse cave path: " + caveConnectionPath);
      // System.out.format("Cave 1 %s connects to cave 2 %s%n", twoCaves[0], twoCaves[1]);
      final Cave cave1 = Cave.createOrLookupByName(twoCaves[0]);
      final Cave cave2 = Cave.createOrLookupByName(twoCaves[1]);
      cave1.addConnectedCave(cave2);
      cave2.addConnectedCave(cave1);
    }
    // dumpCaveList();
  }

  Set<String> findAllPaths()
  {
    final Set<String> result = new HashSet<>();

    final Deque<Cave> stack = new ArrayDeque<>();
    final Cave startCave = Cave.lookupByName("start");
    final Set<Cave> visitedCaves = new HashSet<>();

    stack.push(startCave);
    visitedCaves.add(startCave);
    seekPathFrom(startCave, stack, visitedCaves, result);
    return result;
  }

  private void seekPathFrom(final Cave currentCave, final Deque<Cave> stack, final Set<Cave> visitedCaves, final Set<String> result)
  {
    final Cave[] connectedCaves = currentCave.getConnectedCaves();
    for (final Cave connectedCave : connectedCaves)
    {
      final Set<Cave> newVisitedCavesCopy = new HashSet<>();
      newVisitedCavesCopy.addAll(visitedCaves);
      if (connectedCave.getName().equals("end"))
      {
        stack.push(connectedCave);
        final String currentPath = getCurrentPath(stack);
        result.add(currentPath);
        stack.pop();
        continue;
      }
      if (isOneVisitCave(connectedCave.getName()))
      {
        if (newVisitedCavesCopy.contains(connectedCave)) continue;
        newVisitedCavesCopy.add(connectedCave);
      }
      stack.push(connectedCave);
      seekPathFrom(connectedCave, stack, newVisitedCavesCopy, result);
      stack.pop();
    }
  }

  Set<String> findAllPaths2()
  {
    final Set<String> result = new HashSet<>();

    final Deque<Cave> stack = new ArrayDeque<>();
    final Cave startCave = Cave.lookupByName("start");
    final Set<Cave> visitedCaves = new HashSet<>();

    stack.push(startCave);
    visitedCaves.add(startCave);
    seekPathFrom2(startCave, stack, visitedCaves, result, "");
    return result;
  }

  private void seekPathFrom2(final Cave currentCave, final Deque<Cave> stack, final Set<Cave> visitedCaves, final Set<String> result, final String caveVisitedTwiceIfAny)
  {
    final Cave[] connectedCaves = currentCave.getConnectedCaves();
    for (final Cave connectedCave : connectedCaves)
    {
      final Set<Cave> newVisitedCavesCopy = new HashSet<>();
      newVisitedCavesCopy.addAll(visitedCaves);
      if (connectedCave.getName().equals("start"))  continue;
      if (connectedCave.getName().equals("end"))
      {
        stack.push(connectedCave);
        final String currentPath = getCurrentPath(stack);
        result.add(currentPath);
        stack.pop();
        continue;
      }
      if (isOneVisitCave(connectedCave.getName()))
      {
        if (caveVisitedTwiceIfAny.isEmpty())
        {
          stack.push(connectedCave);
          seekPathFrom2(connectedCave, stack, newVisitedCavesCopy, result, connectedCave.getName());
          stack.pop();
        }
        // else  // This was a bug!!
        {
          if (newVisitedCavesCopy.contains(connectedCave)) continue;
          newVisitedCavesCopy.add(connectedCave);
          stack.push(connectedCave);
          seekPathFrom2(connectedCave, stack, newVisitedCavesCopy, result, caveVisitedTwiceIfAny);
          stack.pop();
        }
      }
      else
      {
        stack.push(connectedCave);
        seekPathFrom2(connectedCave, stack, newVisitedCavesCopy, result, caveVisitedTwiceIfAny);
        stack.pop();
      }
    }
  }

  private String getCurrentPath(final Deque<Cave> stack)
  {
    final StringBuilder sb = new StringBuilder();
    final Iterator<Cave> iterator = stack.descendingIterator();
    boolean isFirst = true;
    while (iterator.hasNext())
    {
      if (!isFirst) sb.append(",");
      isFirst = false;
      final Cave cave = iterator.next();
      sb.append(cave.getName());
    }
    return sb.toString();
  }

  private boolean isOneVisitCave(final String caveName)
  {
    return (caveName.toLowerCase() == caveName);
  }

  private void dumpCaveList()
  {
    final Deque<Cave> stack = new ArrayDeque<>();
    final Cave startCave = Cave.lookupByName("start");
    stack.push(startCave);

    final Set<Cave> visitedCaves = new HashSet<>();
   
    while (!stack.isEmpty())
    {
      final Cave currentCave = stack.pop();
      if (!visitedCaves.contains(currentCave))
      {
        visitedCaves.add(currentCave);
        System.out.println(currentCave.getName());
        final Cave[] connectedCaves = currentCave.getConnectedCaves();
        for (final Cave connectedCave : connectedCaves)
        {
          System.out.println("  - " + connectedCave.getName());
          stack.push(connectedCave);
        }
      }
    }
  }
}

The code that calls into CaveNavigator to solve each of the two parts is very straightforward. While part one is virtually instant, part two solution takes a noticeable amount of time to produce an answer, like maybe 5 or 10 seconds.

  public static long getPart1Answer(final String day12Input, final String[] day12InputLines)
  {
    final CaveNavigator cn = new CaveNavigator(day12InputLines);
    final Set<String> allPaths = cn.findAllPaths();
    return allPaths.size();
  }

  public static long getPart2Answer(final String day12Input, final String[] day12InputLines)
  {
    final CaveNavigator cn = new CaveNavigator(day12InputLines);
    final Set<String> allPaths = cn.findAllPaths2();
    return allPaths.size();
  }

 

[PHolder]

Day 13 is folding transparent paper. Mark the paper with dots at the supplied list of locations, then make the horizontal or vertical folds at the supplied locations, then overlapping dots will spell out a code for part 2. This seemed daunting at first, until I realized that the folds are actually very straight forward. The only trick you need to know is to remember that the folds dictate the new size of the paper (it will get smaller in width or height with each fold.)

I made a FoldingTransparentPaper class:

the FoldingTransparentPaper class

final class FoldingTransparentPaper
{
  private final int originalWidth;
  private final int originalHeight;
  private final char[][] paper;
  private int foldedWidth;
  private int foldedHeight;

  public FoldingTransparentPaper(final int width, final int height)
  {
    originalWidth = width;
    originalHeight = height;
    paper = new char[originalWidth][originalHeight];
    foldedWidth = width;
    foldedHeight = height;
  }

  public void addDotsAtLocations(final String[] dotLocations)
  {
    for (final String dotLocation : dotLocations)
    {
      final String parts[] = dotLocation.split(",");
      if (parts.length != 2) throw new IllegalStateException("Couldn't parse dot location: " + dotLocation);
      final int x = Integer.parseInt(parts[0]);
      final int y = Integer.parseInt(parts[1]);
      paper[x][y] = '#';
    }
  }

  public void makeAFold(final String foldInstruction)
  {
    if (!foldInstruction.startsWith("fold along "))
      throw new IllegalStateException("Invalid fold instruction: " + foldInstruction);
    final int foldLine = Integer.parseInt(foldInstruction.substring(13));
    if (foldInstruction.charAt(11)=='y')
      doYFold(foldLine);
    else if (foldInstruction.charAt(11)=='x')
      doXFold(foldLine);
    else
      throw new IllegalStateException("Couldn't get fold direction: " + foldInstruction);
  }

  public void makeFolds(final String[] foldInstructions)
  {
    for (final String foldInstruction : foldInstructions)
    {
      makeAFold(foldInstruction);
    }
  }

  private void doXFold(final int foldLine)
  {
    int xLeft=foldLine-1;
    int xRight=foldLine+1;
    while (xLeft >= 0)
    {
      for (int y=0; y<foldedHeight; y++)
      {
        if (paper[xLeft][y] != '#')
        {
          paper[xLeft][y] = paper[xRight][y];
        }
      }
      xLeft--;
      xRight++;
      if (xRight>=foldedWidth) break;
    }
    foldedWidth=foldLine;
  }

  private void doYFold(final int foldLine)
  {
    int yUp=foldLine-1;
    int yDown=foldLine+1;
    while (yUp >= 0)
    {
      for (int x=0; x<foldedWidth; x++)
      {
        if (paper[x][yUp] != '#')
        {
          paper[x][yUp] = paper[x][yDown];
        }
      }
      yUp--;
      yDown++;
      if (yDown>=foldedHeight) break;
    }
    foldedHeight=foldLine;
  }

  int getNumberOfDots()
  {
    int result = 0;
    for (int x=0; x<foldedWidth; x++)
    {
      for (int y=0; y<foldedHeight; y++)
      {
        if (paper[x][y] == '#')  result++;
      }
    }
    return result;
  }

  @Override
  public String toString()
  {
    final StringBuilder sb = new StringBuilder();
    for (int y=0; y<foldedHeight; y++)
    {
      for (int x=0; x<foldedWidth; x++)
      {
        if (paper[x][y]=='#')
          sb.append('#');
        else
          sb.append('.');
      }
      sb.append('\n');
    }
    return sb.toString();
  }
}

For these problems I start with a preset bit of template code. It assumes each part will return a long integer. For part 2 I had to change this to a String. There is nothing here that is a spoiler, so I won't blur it.

public static long getPart1Answer(final String[] dotLocations, final String[] foldInstructions, final int width, final int height)
{
  final FoldingTransparentPaper ftp = new FoldingTransparentPaper(width, height);
  ftp.addDotsAtLocations(dotLocations);
  ftp.makeAFold(foldInstructions[0]);
  return ftp.getNumberOfDots();
}

public static String getPart2Answer(final String[] dotLocations, final String[] foldInstructions, final int width, final int height)
{
  final FoldingTransparentPaper ftp = new FoldingTransparentPaper(width, height);
  ftp.addDotsAtLocations(dotLocations);
  ftp.makeFolds(foldInstructions);
  return ftp.toString();
}

 

[PHolder]

So day 14... has the obvious way to solve it, and the right way. I coded both because I guessed wrong about the risk of the problem exploding to infinity because so far in this years challenges there haven't really been any of the challenges that did. (I guess that might technically be a spoiler, but I think he gives plenty of foreshadowing in the challenge text.)

Anyway, my thought process was to wrap the processing in a class that I called PolymerizationTool. It handled parsing the rules, taking the base polymer and then applying the rules and counting the results. This is a spoiler for part one, but won't be much use for part two:

The PolymerizationTool class

final class PolymerizationTool
{
  record PolymerizationRule(String pair, String result) {}
  
  private final Map<String, PolymerizationRule> polymerizationRules = new HashMap<>();
  private String currentPolymer;
  
  PolymerizationTool(final String startingPolymer, final String[] inputPolymerizationRules)
  {
    currentPolymer = startingPolymer;
    for (final String polymerizationRule : inputPolymerizationRules)
    {
      final String[] parts = polymerizationRule.split(" -> ");
      if (parts.length != 2)  throw new IllegalStateException("Couldn't parse polymerization rule: " + polymerizationRule);
      final PolymerizationRule pr = new PolymerizationRule(parts[0], parts[1]);
      polymerizationRules.put(parts[0], pr);
    }
  }

  public void processNPolymerizationSteps(final int numberOfStepsToProcess)
  {
    for (int i=0; i<numberOfStepsToProcess; i++)  processOnePolymerizationStep();
  }

  void processOnePolymerizationStep()
  {
    final StringBuilder newPolymerization = new StringBuilder();
    for (int i=0; i<currentPolymer.length()-1; i++)
    {
      final String currentPair = currentPolymer.substring(i, i+2);
      newPolymerization.append(currentPair.charAt(0));
      if (polymerizationRules.containsKey(currentPair))
      {
        newPolymerization.append(polymerizationRules.get(currentPair).result);
      }
    }
    newPolymerization.append(currentPolymer.charAt(currentPolymer.length()-1));
    currentPolymer = newPolymerization.toString();
  }

  public String getCurrentPolymer()
  {
    return currentPolymer;
  }

  public long[] getElementCounts()
  {
    final long[] elementCounts = new long[26];
    for (int i=0; i<currentPolymer.length(); i++)
    {
      elementCounts[currentPolymer.charAt(i)-'A']++;
    }

    int numDiffElements = 0;
    for (int i=0; i<26; i++) if (elementCounts[i] != 0)  numDiffElements++;
    
    final long[] result = new long[numDiffElements];
    int j = 0;
    for (int i=0; i<26; i++) if (elementCounts[i] != 0)  result[j++] = elementCounts[i];
    Arrays.sort(result);

    return result;
  }
}

For part two, a new approach to the problem was necessary. I copied PolymerizationTool to PolymerizationTool2 and then made the necessary changes. I tested, and this version still worked for part one, but also worked for part two.

The PolymerizationTool2 class

final class PolymerizationTool2
{
  record PolymerizationRule(String pair, char result) {}
  record PolymerizationCount(String pair, long count) {}
  
  private final Map<String, PolymerizationRule> polymerizationRules = new HashMap<>();
  private Map<String, PolymerizationCount> polymerizationCounts = new HashMap<>();
  final long[] elementCounts = new long[26];
  
  PolymerizationTool2(final String startingPolymer, final String[] inputPolymerizationRules)
  {
    for (int i=0; i<startingPolymer.length(); i++)
    {
      elementCounts[startingPolymer.charAt(i)-'A']++;
    }

    for (int i=0; i<startingPolymer.length()-1; i++)
    {
      final String currentPair = startingPolymer.substring(i, i+2);
      updatePolymerizationCount(polymerizationCounts, currentPair, 1);
    }
    
    for (final String polymerizationRule : inputPolymerizationRules)
    {
      final String[] parts = polymerizationRule.split(" -> ");
      if (parts.length != 2)  throw new IllegalStateException("Couldn't parse polymerization rule: " + polymerizationRule);
      final PolymerizationRule pr = new PolymerizationRule(parts[0], parts[1].charAt(0));
      polymerizationRules.put(parts[0], pr);
    }
  }

  private void updatePolymerizationCount(final Map<String, PolymerizationCount> polymerizationCounts, final String polymerPair, final long increment)
  {
    long count = increment;
    if (polymerizationCounts.containsKey(polymerPair))
    {
      count = polymerizationCounts.get(polymerPair).count+increment;
    }
    final PolymerizationCount newPolymerizationCount = new PolymerizationCount(polymerPair, count);
    polymerizationCounts.put(polymerPair, newPolymerizationCount);
  }

  public void processNPolymerizationSteps(final int numberOfStepsToProcess)
  {
    for (int i=0; i<numberOfStepsToProcess; i++)  processOnePolymerizationStep();
  }

  void processOnePolymerizationStep()
  {
    final Map<String, PolymerizationCount> newPolymerizationCounts = new HashMap<>();

    for (final Entry<String, PolymerizationRule> entry: polymerizationRules.entrySet())
    {
      final String polymerPair = entry.getKey();
      if (polymerizationCounts.containsKey(polymerPair))
      {
        final long numberOfPolymerPair = polymerizationCounts.get(polymerPair).count;
        final char addedMiddleElement = entry.getValue().result;
        final String newPairOne = "" + polymerPair.charAt(0) + addedMiddleElement;
        final String newPairTwo = "" + addedMiddleElement + polymerPair.charAt(1); 
        updatePolymerizationCount(newPolymerizationCounts, newPairOne, numberOfPolymerPair);
        updatePolymerizationCount(newPolymerizationCounts, newPairTwo, numberOfPolymerPair);
        elementCounts[addedMiddleElement-'A'] += numberOfPolymerPair;
      }
    }
    polymerizationCounts = newPolymerizationCounts;
  }

  public long[] getElementCounts()
  {
    int numDiffElements = 0;
    for (int i=0; i<26; i++) if (elementCounts[i] != 0)  numDiffElements++;
    
    final long[] result = new long[numDiffElements];
    int j = 0;
    for (int i=0; i<26; i++) if (elementCounts[i] != 0)  result[j++] = elementCounts[i];
    Arrays.sort(result);

    return result;
  }
}

The part that gets the two answers is, as usual, very simple:

public static long getPart1Answer(final String day14Input, final String[] day14InputLines)
{
  final PolymerizationTool pt = new PolymerizationTool(day14Input, day14InputLines);
  pt.processNPolymerizationSteps(10);

  long[] elementCounts = pt.getElementCounts();  // returned sorted

  return elementCounts[elementCounts.length-1] - elementCounts[0];
}

I will spoiler blur part two because it could give something away (although I suspect the challenge text foreshadowed it sufficiently):

Getting the answer for part two

public static long getPart2Answer(final String day14Input, final String[] day14InputLines)
{
  final PolymerizationTool2 pt2 = new PolymerizationTool2(day14Input, day14InputLines);
  pt2.processNPolymerizationSteps(40);

  long[] elementCounts = pt2.getElementCounts();  // returned sorted

  return elementCounts[elementCounts.length-1] - elementCounts[0];
}

 

[PHolder]

Day 15 was a challenge for me. Graph type algorithms are not something I have a lot of experience with. I created three different versions of solvers before I got to one that made sense to me, and ran in reasonable time and of course got the correct answers. What finally worked for me was realizing I could do a flood fill type algorithm where I only used moves to the right or down. Then that gave the correct answers for the sample input and the first part of the challenge input but not for the second part of the challenge input. I then realized that I had calculated a value that could be the best but that there might be better. I added an optimization pass and that got m all the way.

I created a class called RiskResolver to do the majority of the work:

The RiskResolver class

final class RiskResolver
{
  @org.eclipse.jdt.annotation.NonNullByDefault({})
  record MapLocation(int x, int y) {}

  private final int[][] riskMap;
  private final int[][] riskFill;
  private final int width;
  private final int height;
  private final int tileWidth;
  private final int tileHeight;

  public RiskResolver(final String[] inputRiskMap)
  {
    width = inputRiskMap[0].length();
    height = inputRiskMap.length;
    tileWidth=width;
    tileHeight=height;
    riskMap  = new int[width][height];
    riskFill = new int[width][height];
    for (int y=0; y<height; y++)
    {
      for (int x=0; x<width; x++)
      {
        riskMap[x][y] = inputRiskMap[y].charAt(x)-'0';
      }
    }
  }

  public RiskResolver(final String[] inputRiskMap, int sizeMultiplier)
  {
    tileWidth = inputRiskMap[0].length();
    tileHeight = inputRiskMap.length;
    width = inputRiskMap[0].length() * sizeMultiplier;
    height = inputRiskMap.length * sizeMultiplier;
    riskMap  = new int[width][height];
    riskFill = new int[width][height];
    for (int y=0; y<tileHeight; y++)
    {
      for (int x=0; x<tileWidth; x++)
      {
        riskMap[x][y] = inputRiskMap[y].charAt(x)-'0';
      }
    }
    
    for (int i=1; i<sizeMultiplier; i++)
    {
      for (int y=0; y<tileHeight; y++)
      {
        for (int x=0; x<tileWidth; x++)
        {
          final int tileX = tileWidth*i + x;
          final int tileY = y;
          int tileValue = riskMap[x][y] + i;
          if (tileValue > 9) tileValue -= 9;
          riskMap[tileX][tileY] = tileValue;
        }
      }
    }

    for (int i=1; i<sizeMultiplier; i++)
    {
      for (int j=0; j<sizeMultiplier; j++)
      {
        for (int y=0; y<tileHeight; y++)
        {
          for (int x=0; x<tileWidth; x++)
          {
            final int tileX = tileWidth*j + x;
            final int tileY = tileHeight*i + y;
            int tileValue = riskMap[tileX][tileY-tileHeight] + 1;
            if (tileValue > 9) tileValue -= 9;
            riskMap[tileX][tileY] = tileValue;
          }
        }
      }
    }
  }
 
  long getLowestRiskPath()
  {
    fillMap();
    optimizeMap();
    return riskFill[width-1][height-1];
  }

  private void fillMap()
  {
    riskFill[0][0] = 0;
    riskFill[0][1] = riskMap[0][1];
    riskFill[1][0] = riskMap[1][0];
    riskFill[1][1] = riskMap[1][1] + Math.min(riskFill[0][1], riskFill[1][0]);

    int l=2;
    while (l<width)
    {
      riskFill[l][0] = riskFill[l-1][0] + riskMap[l][0];
      riskFill[0][l] = riskFill[0][l-1] + riskMap[0][l];
      for (int i=1; i<=l; i++)
      {
        riskFill[i][l] = riskMap[i][l] + Math.min(riskFill[i-1][l], riskFill[i][l-1]);
        riskFill[l][i] = riskMap[l][i] + Math.min(riskFill[l-1][i], riskFill[l][i-1]);
      }
      l++;
    }
  }

  private void optimizeMap()
  {
    boolean madeChange = true;
    while (madeChange)
    {
      madeChange = false;
      for (int y=0; y<height; y++)
      {
        for (int x=0; x<width; x++)
        {
          int min=riskFill[x][y];
          final Set<MapLocation> neighbours = getNeightbours(x,y);
          for (final MapLocation neighbour : neighbours)
          {
            if (riskFill[neighbour.x][neighbour.y] + riskMap[x][y] < min)
            {
              riskFill[x][y] = riskFill[neighbour.x][neighbour.y] + riskMap[x][y];
              min = riskFill[x][y];
              madeChange = true;
            }
          }
        }
      }
    }
  }

  private Set<MapLocation> getNeightbours(final int x, final int y)
  {
    final Set<MapLocation> neighbours = new HashSet<>();
    if (x>0) neighbours.add(new MapLocation(x-1, y));
    if (x<width-1) neighbours.add(new MapLocation(x+1, y));
    if (y>0) neighbours.add(new MapLocation(x, y-1));
    if (y<height-1) neighbours.add(new MapLocation(x, y+1));

    return neighbours;
  }
}

The two parts just call into the RiskResolver class, in the second part I call a different constructor to handle the changes to the map:

public static long getPart1Answer(final String day15Input, final String[] day15InputLines)
{
  final RiskResolver rr = new RiskResolver(day15InputLines);
    
  return rr.getLowestRiskPath();
}

public static long getPart2Answer(final String day15Input, final String[] day15InputLines)
{
  final RiskResolver rr = new RiskResolver(day15InputLines, 5);
    
  return rr.getLowestRiskPath();
}

 

[PHolder]

Day 16 is a binary protocol that implements a mathematical expression parser. You need to be able to convert hex input to binary and read from it in groups of bits at a time. To that end, I created a HexToBitStringTranslator class. There are various ways to tackle this, but for me the simplest way was to convert the text hex string into a text binary string. The only tricky bit is that you will need a way to get subsections that you can treat individually.

The HexToBitStringTranslator class

final class HexToBitStringTranslator
{
  private final String bitString;
  private int currentBit = 0;
  private int bitsLeft;
  
  HexToBitStringTranslator(final String hexInput)
  {
    bitString = convertHexToBitString(hexInput);
    bitsLeft = bitString.length();
  }

  private HexToBitStringTranslator(final String inputBitString, final int startOffset, final int length)
  {
    bitString = inputBitString.substring(startOffset, startOffset+length);
    bitsLeft = length;
  }

  int getNextNBits(final int numberOfBitsToGet)
  {
    if (bitsLeft < numberOfBitsToGet)
    {
      throw new IllegalStateException(String.format("Request to get %d bits when only %d bits are left", numberOfBitsToGet, bitsLeft));
    }
    // add a zero sign bit just in case
    final String nextBits = "0" + bitString.substring(currentBit, currentBit+numberOfBitsToGet);
    final int result = Integer.parseInt(nextBits, 2);
    currentBit += numberOfBitsToGet;
    bitsLeft -= numberOfBitsToGet;
    return result;
  }

  private String convertHexToBitString(final String hexInput)
  {
    final StringBuilder sb = new StringBuilder();
    for (final char c: hexInput.toCharArray())
    {
      switch (c)
      {
        case '0': sb.append("0000"); break;
        case '1': sb.append("0001"); break;
        case '2': sb.append("0010"); break;
        case '3': sb.append("0011"); break;
        case '4': sb.append("0100"); break;
        case '5': sb.append("0101"); break;
        case '6': sb.append("0110"); break;
        case '7': sb.append("0111"); break;
        case '8': sb.append("1000"); break;
        case '9': sb.append("1001"); break;
        case 'A': sb.append("1010"); break;
        case 'B': sb.append("1011"); break;
        case 'C': sb.append("1100"); break;
        case 'D': sb.append("1101"); break;
        case 'E': sb.append("1110"); break;
        case 'F': sb.append("1111"); break;
        default:  throw new IllegalStateException("Invalid hex digit: " + c);
      }
    }
    return sb.toString();
  }

  public int getBitsLeft()
  {
    return bitsLeft;
  }

  public HexToBitStringTranslator getSubPacket(final int lengthToGet)
  {
    final HexToBitStringTranslator result = new HexToBitStringTranslator(bitString, currentBit, lengthToGet);
    currentBit += lengthToGet;
    bitsLeft -= lengthToGet;
    return result;
  }
}

Now that you can get groups of bits as integers as needed, for part one I created a parser to get the sums of the verison numbers. The challenge calls the input BITS so I created the class BITSDecoder. The best approach for the parsing it to use recursion, so you need to make sure you can pass in various different instances of HexToBitStringTranslator, and HexToBitStringTranslator needed to have a way to create them.

The part one BITSDecoder class

final class BITSDecoder
{
  private final HexToBitStringTranslator h2bst;

  public BITSDecoder(final HexToBitStringTranslator h2bst)
  {
    this.h2bst = h2bst;
  }
  
  long decodeAllInstructionsAndSumVersions()
  {
    return decodeAllInstructionsAndSumVersions(h2bst);
  }

  private long decodeAllInstructionsAndSumVersions(final HexToBitStringTranslator h2bst)
  {
    long versionSum = 0;
    while (h2bst.getBitsLeft() > 7)
    {
      versionSum += parsePacket(h2bst);
    }
    return versionSum;
  }

  private long parsePacket(final HexToBitStringTranslator h2bst)
  {
    long verSum = h2bst.getNextNBits(3);
    final int type = h2bst.getNextNBits(3);
    switch (type)
    {
      case 4:   parseLiteralValue(h2bst); break;
      default:  verSum += parseOperator(h2bst); break;
    }
    return verSum;
  }

  private void parseLiteralValue(final HexToBitStringTranslator h2bst)
  {
    boolean more = true;
    while (more)
    {
      more = h2bst.getNextNBits(1) == 1;
      h2bst.getNextNBits(4);
    }
  }

  private long parseOperator(final HexToBitStringTranslator h2bst)
  {
    int subTypeIndicator = h2bst.getNextNBits(1);
    if (subTypeIndicator == 0)
    {
      final int lengthToGet = h2bst.getNextNBits(15);
      return parseSubPacket(h2bst.getSubPacket(lengthToGet));
    }
    else
    {
      final int numSubPackets = h2bst.getNextNBits(11);
      long sum = 0;
      for (int i=0; i<numSubPackets; i++)
      {
        sum += parsePacket(h2bst);
      }
      return sum;
    }
  }

  private long parseSubPacket(final HexToBitStringTranslator subPacket)
  {
    return decodeAllInstructionsAndSumVersions(subPacket);
  }
}

For part two, since the version numbers weren't relevant any more, I copied my part one BITSDecoder into BITSDecoder2, and changed it to suit the part two task:

The part two BITSDecoder2 class

final class BITSDecoder2
{
  private final HexToBitStringTranslator h2bst;

  public BITSDecoder2(final HexToBitStringTranslator h2bst)
  {
    this.h2bst = h2bst;
  }
  
  long decodeAndCalulate()
  {
    return decodeAllInstructionsAndCalculateResult(h2bst);
  }

  private long decodeAllInstructionsAndCalculateResult(final HexToBitStringTranslator h2bst)
  {
    final long result = parsePacket(h2bst);
    return result;
  }

  private long parsePacket(final HexToBitStringTranslator h2bst)
  {
    h2bst.getNextNBits(3);
    final int type = h2bst.getNextNBits(3);
    switch (type)
    {
      case 4:   return parseLiteralValue(h2bst);
      case 0:   return sum(h2bst);
      case 1:   return product(h2bst);
      case 2:   return minimum(h2bst);
      case 3:   return maximum(h2bst);
      case 5:   return greaterThan(h2bst);
      case 6:   return lessThan(h2bst);
      case 7:   return equalTo(h2bst);
      default:  throw new IllegalStateException("Unknown type: " + type);
    }
  }

  private long sum(final HexToBitStringTranslator h2bst)
  {
    long sum=0;
    for (final Long value: parseOperator(h2bst))
    {
      sum += value;
    }
    return sum;
  }

  private long product(final HexToBitStringTranslator h2bst)
  {
    long product=1;
    for (final Long value: parseOperator(h2bst))
    {
      product *= value;
    }
    return product;
  }

  private long minimum(final HexToBitStringTranslator h2bst)
  {
    long minimum=Long.MAX_VALUE;
    for (final Long value: parseOperator(h2bst))
    {
      if (value < minimum) minimum = value;
    }
    return minimum;
  }

  private long maximum(final HexToBitStringTranslator h2bst)
  {
    long maximum=Long.MIN_VALUE;
    for (final Long value: parseOperator(h2bst))
    {
      if (value > maximum) maximum = value;
    }
    return maximum;
  }

  private long greaterThan(final HexToBitStringTranslator h2bst)
  {
    final List<Long> values = parseOperator(h2bst);
    if (values.size() != 2)  throw new IllegalStateException("Not precisely two values in greaterThan");

    if (values.get(0) > values.get(1))
    {
      return 1;
    }
    return 0;
  }

  private long lessThan(final HexToBitStringTranslator h2bst)
  {
    final List<Long> values = parseOperator(h2bst);
    if (values.size() != 2)  throw new IllegalStateException("Not precisely two values in lessThan");
    if (values.get(0) < values.get(1))
    {
      return 1;
    }
    return 0;
  }

  private long equalTo(final HexToBitStringTranslator h2bst)
  {
    final List<Long> values = parseOperator(h2bst);
    if (values.size() != 2)  throw new IllegalStateException("Not precisely two values in equalTo");
    if (values.get(0).equals(values.get(1)))
    {
      return 1;
    }
    return 0;
  }

  private long parseLiteralValue(final HexToBitStringTranslator h2bst)
  {
    long result = 0;
    boolean more = true;
    while (more)
    {
      more = h2bst.getNextNBits(1) == 1;
      int digit = h2bst.getNextNBits(4);
      result = result*16 + digit;
    }
    return result;
  }

  private List<Long> parseOperator(final HexToBitStringTranslator h2bst)
  {
    final List<Long> values = new ArrayList<>();
    int subTypeIndicator = h2bst.getNextNBits(1);
    if (subTypeIndicator == 0)
    {
      final int lengthToGet = h2bst.getNextNBits(15);
      final List<Long> subValues = parseSubPacket(h2bst.getSubPacket(lengthToGet));
      values.addAll(subValues);
    }
    else
    {
      final int numSubPackets = h2bst.getNextNBits(11);
      for(int i=0; i<numSubPackets; i++)
      {
        final long subValue = parsePacket(h2bst);
        values.add(subValue);
      }
    }
    return values;
  }

  private List<Long> parseSubPacket(final HexToBitStringTranslator subPacket)
  {
    final List<Long> values = new ArrayList<>();
    while (subPacket.getBitsLeft() > 6)
    {
      final long value = parsePacket(subPacket);
      values.add(value);
    }
    return values;
  }
}

and finally the two parts need to call the two BITSDecoder classes to get the answers:

public static long getPart1Answer(final String day16Input)
{
  final HexToBitStringTranslator h2bst = new HexToBitStringTranslator(day16Input);
  final BITSDecoder bd = new BITSDecoder(h2bst);
  return bd.decodeAllInstructionsAndSumVersions();
}

public static long getPart2Answer(final String day16Input)
{
  final HexToBitStringTranslator h2bst = new HexToBitStringTranslator(day16Input);
  final BITSDecoder2 bd2 = new BITSDecoder2(h2bst);
  return bd2.decodeAndCalulate();
}

 

[PHolder]

Day 17 is all about physics of projectiles and optimizing a trajectory. I started of with records (so basically read only classes with no logic) to represent a point and a box and a velocity. I then created a ProjectileOptimizer class to actually do all the work. Rather than try anything fancy, I just brute forced some reasonable values for initial velocities, from 0 to 200 for part one (because we're looking for a positive upward value, and -200 to 200 for part 2 because anything that works is considered valid.)

The ProjectileOptimizer class

final class ProjectileOptimizer
{
  record Velocity(int xVector, int yVector) {}
  
  private final Point startPosition;
  private final Box targetArea;
  private int maximumHeight = Integer.MIN_VALUE;

  public ProjectileOptimizer(final Point startPosition, final Box targetArea)
  {
    this.startPosition = startPosition;
    this.targetArea    = targetArea;
  }

  public void optimizeTrajectoryForMaximumHeight()
  {
    for (int xVector = 0; xVector < 100; xVector++)
    {
      for (int yVector = 0; yVector < 200; yVector++)
      {
        Point projectile = startPosition;
        Velocity velocity = new Velocity(xVector, yVector);
        boolean reachedTarget = false;
        int maxProjectileHeight = 0;
        while (!reachedTarget)
        {
          if (!projectileCanStillReachTargetArea(projectile, velocity)) break;
          projectile = updateProjectile(projectile, velocity);
          velocity = updateVelocity(velocity);
          if (projectile.y() > maxProjectileHeight)  maxProjectileHeight = projectile.y(); 
          if (projectileReachedTargetArea(projectile))
          {
            reachedTarget = true;
            break;
          }
        }
        if (reachedTarget)
        {
          if (maxProjectileHeight > maximumHeight)  maximumHeight = maxProjectileHeight;
        }
      }
    }
  }
 
  public int findNumberOfPossibleTrajectoriesThatReachTarget()
  {
    int result = 0;

    for (int xVector = -200; xVector < 200; xVector++)
    {
      for (int yVector = -200; yVector < 200; yVector++)
      {
        Point projectile = startPosition;
        Velocity velocity = new Velocity(xVector, yVector);
        boolean reachedTarget = false;
        int maxProjectileHeight = 0;
        while (!reachedTarget)
        {
          if (!projectileCanStillReachTargetArea(projectile, velocity)) break;
          projectile = updateProjectile(projectile, velocity);
          velocity = updateVelocity(velocity);
          if (projectile.y() > maxProjectileHeight)  maxProjectileHeight = projectile.y(); 
          if (projectileReachedTargetArea(projectile))
          {
            reachedTarget = true;
            break;
          }
        }
        if (reachedTarget)
        {
          result++;
        }
      }
    }
    return result;
  }
  
  private boolean projectileCanStillReachTargetArea(final Point projectile, final Velocity velocity)
  {
    if (projectile.y() < Math.min(targetArea.y1(), targetArea.y2())) return false;
    return true;
  }

  private Point updateProjectile(final Point projectile, final Velocity velocity)
  {
    int px = projectile.x();
    int py = projectile.y();
    px += velocity.xVector;
    py += velocity.yVector;
    return new Point(px,py);
  }

  private Velocity updateVelocity(final Velocity velocity)
  {
    int vx=0;
    int vy=velocity.yVector-1;
    if (velocity.xVector > 0)
    {
      vx = velocity.xVector-1;
    }
    else if (velocity.xVector < 0)
    {
      vx = velocity.xVector+1;
    }

    return new Velocity(vx, vy);
  }

  private boolean projectileReachedTargetArea(final Point projectile)
  {
    if ( (projectile.y() >= Math.min(targetArea.y1(), targetArea.y2()))  && 
         (projectile.y() <= Math.max(targetArea.y1(), targetArea.y2()))  && 
         (projectile.x() >= Math.min(targetArea.x1(), targetArea.x2()))  && 
         (projectile.x() <= Math.max(targetArea.x1(), targetArea.x2()))   )
    {
      return true;
    }
    return false;
  }

  public long getMaximumHeight()
  {
    return maximumHeight;
  }
}

To actually get the required answers, the solvers just call the necessary method(s) on the ProjectileOptimizer :

record Point(int x, int y) {}
record Box(int x1, int y1, int x2, int y2) {}
  
public static long getPart1Answer(
    final int startX,
    final int startY,
    final int targetX1,
    final int targetY1,
    final int targetX2,
    final int targetY2
  )
{
  final Point startPosition = new Point(startX, startY);
  final Box   targetArea    = new Box(targetX1, targetY1, targetX2, targetY2);
  final ProjectileOptimizer popt = new ProjectileOptimizer(startPosition, targetArea);
  popt.optimizeTrajectoryForMaximumHeight();
  return popt.getMaximumHeight();
}

public static long getPart2Answer(
    final int startX,
    final int startY,
    final int targetX1,
    final int targetY1,
    final int targetX2,
    final int targetY2
  )
{
  final Point startPosition = new Point(startX, startY);
  final Box   targetArea    = new Box(targetX1, targetY1, targetX2, targetY2);
  final ProjectileOptimizer popt = new ProjectileOptimizer(startPosition, targetArea);
  return popt.findNumberOfPossibleTrajectoriesThatReachTarget();
}

 

[Paul F]

... brute forced some reasonable values for initial velocities, from 0 to 200 for part one (because we're looking for a positive upward value, and -200 to 200 for part 2 because anything that works is considered valid.) ...

Spoiler(?)

I wondered if these initial velocity ranges could be calculated. The target area range is x1 to x2 where x2 > x1 > 0 and y1 to y2 where y1 < y2 < 0. The x velocity for parts 1 and 2 is straightforward: it can be from 1 to x2. The y velocity range is more interesting. If the y velocity is positive, the probe goes up and back down to 0 before continuing negative to the target. The y positions on the way up from 0 and on the way back down to 0 are identical. If the initial velocity is vy, the velocity on returning to 0 is -vy; so the next velocity for the first negative step is -vy-1 and that can't be more negative than the target y1. Therefore the positive limit for the y velocity is -y1-1 and the negative limit is y1. So for part 1 the range is 1 to -y1-1, and for part 2 the range is y1 to -y1-1.

 

[PHolder]

[ This is another case where I have too much code for the 10,000 character limit on the forums. I will break it into three parts. ]

Ever get into the middle of a situation and wonder if you've made the right choices to end up there? That was day 18 for me! I typically code immutable data structures/classes whenever I can. The problem presented in day 18 is probably best addressed by a mutable binary tree of some design. I didn't do that, and didn't really realize I wished I had, until after I was like 3 hours in. (It took me just over five hours for part one, and then another two minutes for part two.)

I created a class to represent the snailfish numbers in the problem, and another class to wrap the math needed to be done on them. (Although, in the end, I'm unsure I really needed the second class, and I'm unsure the boundaries are clean between them. I was too fried after the 5 hours to consider any further refactoring.... maybe later when I've slept.)

I'm not even really sure I want to share this code, as it's not something I'm the most proud of... but it does indeed solve the present problem(s)... it's just a LOT more code that I wish it were.

This is the SnailFishNumber class. The one odd/tricky thing I did was to manage the explode and split operations by converting the snailfish number back to text with the modifications, and then reparsing it back into a new immutable snailfish number:

The first half of the SnailFishNumber class

final class SnailFishNumber
{
  public static final SnailFishNumber ZERO = new SnailFishNumber("[0]");

  private final SnailFishNumberElement theNumber;

  private SnailFishNumber(final SnailFishNumberElement theNumber)
  {
    this.theNumber = theNumber;
  }
 
  public SnailFishNumber(final String textualSnailFishNumber)
  {
    final Deque<SnailFishNumberElementBuilder> stack = new ArrayDeque<>();
  
    SnailFishNumberElementBuilder currentElementBuilder = new SnailFishNumberElementBuilder();
    SnailFishNumberElement currentElement = SnailFishNumberElement.INVALID;

    for (final char c : textualSnailFishNumber.toCharArray())
    {
      switch(c)
      {
        case '[':
        {
          stack.push(currentElementBuilder);
          currentElementBuilder = new SnailFishNumberElementBuilder();
        }
        break;
      
        case ']':
        {
          currentElement = currentElementBuilder.build();
          currentElementBuilder = stack.pop();
          currentElementBuilder.processElement(currentElement);
        }
        break;

        case ',':
        {
          currentElementBuilder.processComma();
        }
        break;

        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
        {
          currentElementBuilder.processDigit(c);
        }
        break;
      
        default:
          throw new IllegalStateException("Don't know how to process char: " + c);
      }
    }
    theNumber = currentElement;
  }

  static SnailFishNumber doAddition(final SnailFishNumber leftSide, final SnailFishNumber rightSide)
  {
    final SnailFishNumberElementBuilder builder = new SnailFishNumberElementBuilder();
    builder.processElement(leftSide.theNumber);
    builder.processComma();
    builder.processElement(rightSide.theNumber);
    return new SnailFishNumber(builder.build());
  }

  public long getMagnitude()
  {
    return getMagnitude(theNumber);
  }

  private long getMagnitude(final SnailFishNumberElement currentElement)
  {
    if (currentElement.isRegularNumber)
    {
      return currentElement.regularNumber;
    }
    final long leftSide = getMagnitude(currentElement.leftSideElement);
    final long rightSide = getMagnitude(currentElement.rightSideElement);
    return 3*leftSide + 2*rightSide;
  }

  public SnailFishNumber doExplode(final ExplodeComponents explodeComponents)
  {
    final StringBuilder sb = new StringBuilder();
    writeIntoDoExplodeStringBuilder(sb, theNumber, explodeComponents);
    return new SnailFishNumber(sb.toString());
  }

  public SnailFishNumber doSplit(final SnailFishNumberElement splitElement)
  {
    final StringBuilder sb = new StringBuilder();
    writeIntoDoSplitStringBuilder(sb, theNumber, splitElement);
    return new SnailFishNumber(sb.toString());
  }

  private void writeIntoDoExplodeStringBuilder(final StringBuilder sb, final SnailFishNumberElement snailFishNumberElement, final ExplodeComponents explodeComponents)
  {
    if (snailFishNumberElement.isRegularNumber)
    {
      if (snailFishNumberElement == explodeComponents.leftSide)
      {
        sb.append(snailFishNumberElement.regularNumber + explodeComponents.explodeElement.leftSideElement.regularNumber);
      }
      else if (snailFishNumberElement == explodeComponents.rightSide)
      {
        sb.append(snailFishNumberElement.regularNumber + explodeComponents.explodeElement.rightSideElement.regularNumber);
      }
      else
        sb.append(snailFishNumberElement.regularNumber);
    }
    else
    {
      if (snailFishNumberElement == explodeComponents.explodeElement)
      {
        sb.append("0");
      }
      else
      {
        sb.append("[");
        final StringBuilder nestedLeftSB = new StringBuilder();
        writeIntoDoExplodeStringBuilder(nestedLeftSB, snailFishNumberElement.leftSideElement, explodeComponents);
        sb.append(nestedLeftSB);
        sb.append(",");
        final StringBuilder nestedRightSB = new StringBuilder();
        writeIntoDoExplodeStringBuilder(nestedRightSB, snailFishNumberElement.rightSideElement, explodeComponents);
        sb.append(nestedRightSB);
        sb.append("]");
      }
    }
  }

  private void writeIntoDoSplitStringBuilder(final StringBuilder sb, final SnailFishNumberElement snailFishNumberElement, final SnailFishNumberElement splitElement)
  {
    if (snailFishNumberElement.isRegularNumber)
    {
      if (snailFishNumberElement == splitElement)
      {
        sb.append('[');
        final int leftSideVal = snailFishNumberElement.regularNumber / 2;
        final int rightSideVal = snailFishNumberElement.regularNumber - leftSideVal;
        sb.append(leftSideVal);
        sb.append(',');
        sb.append(rightSideVal);
        sb.append(']');
      }
      else
        sb.append(snailFishNumberElement.regularNumber);
    }
    else
    {
      sb.append("[");
      final StringBuilder nestedLeftSB = new StringBuilder();
      writeIntoDoSplitStringBuilder(nestedLeftSB, snailFishNumberElement.leftSideElement, splitElement);
      sb.append(nestedLeftSB);
      sb.append(",");
      final StringBuilder nestedRightSB = new StringBuilder();
      writeIntoDoSplitStringBuilder(nestedRightSB, snailFishNumberElement.rightSideElement, splitElement);
      sb.append(nestedRightSB);
      sb.append("]");
    }
  }

// this code was broken to fit... the remiander of this class will be in the next post

 

[PHolder]

[ this is the second part of three of the day 18 post because it wouldn't all fit in one post ]

The second half of the SnailFishNumber class

// continuation of  final class SnailFishNumber

  boolean shouldExplode()
  {
    final Deque<SnailFishNumberElement> stack = new ArrayDeque<>();
    SnailFishNumberElement explodeElement = getExplodeElement(stack, theNumber, 1);
    if (explodeElement != SnailFishNumberElement.INVALID)
    {
      return true;
    }
    return false;
  }

  public SnailFishNumberElement getSplitElement()
  {
    final Deque<SnailFishNumberElement> stack = new ArrayDeque<>();
    SnailFishNumberElement splitElement = getSplitElement(stack, theNumber);
    if (splitElement != SnailFishNumberElement.INVALID)
    {
      return splitElement;
    }
    return SnailFishNumberElement.INVALID;
  }

  record ExplodeComponents(SnailFishNumberElement leftSide, SnailFishNumberElement explodeElement, SnailFishNumberElement rightSide) {};

  ExplodeComponents getExplodeComponents()
  {
    SnailFishNumberElement leftSide       = SnailFishNumberElement.INVALID;
    SnailFishNumberElement explodeElement = SnailFishNumberElement.INVALID;
    SnailFishNumberElement rightSide      = SnailFishNumberElement.INVALID;
  
    final Deque<SnailFishNumberElement> stack = new ArrayDeque<>();
    explodeElement = getExplodeElement(stack, theNumber, 1);
    if (explodeElement != SnailFishNumberElement.INVALID)
    {
      explodeElement = stack.peek();
      leftSide  = getLeftRegularNumberBefore(explodeElement);
      rightSide = getRightRegularNumberAfter(explodeElement);
    }

    return new ExplodeComponents(leftSide, explodeElement, rightSide);
  }

  private SnailFishNumberElement getLeftRegularNumberBefore(final SnailFishNumberElement explodeElement)
  {
    final Deque<SnailFishNumberElement> stack = new ArrayDeque<>();
    SnailFishNumberElement result = SnailFishNumberElement.INVALID;
    SnailFishNumberElement currentElement = theNumber;
    while (currentElement != explodeElement)
    {
      if (currentElement.isRegularNumber)
      {
        result = currentElement;
        currentElement = stack.pop();
      }
      else
      {
        stack.push(currentElement.rightSideElement);
        currentElement = currentElement.leftSideElement;
      }
    }
    return result;
  }

  private SnailFishNumberElement getRightRegularNumberAfter(SnailFishNumberElement explodeElement)
  {
    final Deque<SnailFishNumberElement> stack = new ArrayDeque<>();
    SnailFishNumberElement currentElement = theNumber;
    while (currentElement != explodeElement)
    {
      if (currentElement.isRegularNumber)
      {
        currentElement = stack.pop();
      }
      else
      {
        stack.push(currentElement.rightSideElement);
        currentElement = currentElement.leftSideElement;
      }
    }

    while (!stack.isEmpty())
    {
      currentElement = stack.pop();
      if (currentElement.isRegularNumber)
      {
        return currentElement;
      }
      else
      {
        stack.push(currentElement.rightSideElement);
        stack.push(currentElement.leftSideElement);
      }
    }
    return SnailFishNumberElement.INVALID;
  }

  private SnailFishNumberElement getExplodeElement(final Deque<SnailFishNumberElement> stack, final SnailFishNumberElement currentElement, final int currentDepth)
  {
    if (currentElement.isRegularNumber)
    {
      if (currentDepth > 5) return currentElement;
      return SnailFishNumberElement.INVALID;
    }
    stack.push(currentElement);
    final SnailFishNumberElement leftSide = getExplodeElement(stack, currentElement.leftSideElement, currentDepth+1);
    if (leftSide != SnailFishNumberElement.INVALID) return leftSide;
    final SnailFishNumberElement rightSide = getExplodeElement(stack, currentElement.rightSideElement, currentDepth+1);
    if (rightSide != SnailFishNumberElement.INVALID) return rightSide;
    stack.pop();
    return SnailFishNumberElement.INVALID;
  }
 
  private SnailFishNumberElement getSplitElement(final Deque<SnailFishNumberElement> stack, final SnailFishNumberElement currentElement)
  {
    if (currentElement.isRegularNumber)
    {
      if (currentElement.regularNumber > 9) return currentElement;
      return SnailFishNumberElement.INVALID;
    }
    stack.push(currentElement);
    final SnailFishNumberElement leftSide = getSplitElement(stack, currentElement.leftSideElement);
    if (leftSide != SnailFishNumberElement.INVALID) return leftSide;
    final SnailFishNumberElement rightSide = getSplitElement(stack, currentElement.rightSideElement);
    if (rightSide != SnailFishNumberElement.INVALID) return rightSide;
    stack.pop();
    return SnailFishNumberElement.INVALID;
  }

  @Override
  public String toString()
  {
    return theNumber.toString();
  }
 
  static final class SnailFishNumberElement
  {
    static final SnailFishNumberElement INVALID = new SnailFishNumberElement(-1);

    final boolean isRegularNumber;
    final int regularNumber;
    final SnailFishNumberElement leftSideElement;
    final SnailFishNumberElement rightSideElement;
  
    private SnailFishNumberElement(final int regularNumber)
    {
      isRegularNumber = true;
      this.regularNumber = regularNumber;
      leftSideElement = INVALID;
      rightSideElement = INVALID;
    }

    private SnailFishNumberElement(final SnailFishNumberElement leftSide, final SnailFishNumberElement rightSide)
    {
      isRegularNumber = false;
      this.regularNumber = -1;
      leftSideElement = leftSide;
      rightSideElement = rightSide;
    }

    static SnailFishNumberElement makeRegularNumber(final int regularNumberToMake)
    {
      return new SnailFishNumberElement(regularNumberToMake);
    }

    static SnailFishNumberElement makeSnailFishNumber(final SnailFishNumberElement leftSide, final SnailFishNumberElement rightSide)
    {
      return new SnailFishNumberElement(leftSide, rightSide);
    }
 
    @Override
    public String toString()
    {
      final StringBuilder sb = new StringBuilder();
      writeIntoStringBuilder(sb, this);
      return sb.toString();
    }

    private void writeIntoStringBuilder(final StringBuilder sb, final SnailFishNumberElement snailFishNumberElement)
    {
      if (snailFishNumberElement.isRegularNumber)
      {
        sb.append(snailFishNumberElement.regularNumber);
      }
      else
      {
        sb.append("[");
        final StringBuilder nestedLeftSB = new StringBuilder();
        writeIntoStringBuilder(nestedLeftSB, snailFishNumberElement.leftSideElement);
        sb.append(nestedLeftSB);
        sb.append(",");
        final StringBuilder nestedRightSB = new StringBuilder();
        writeIntoStringBuilder(nestedRightSB, snailFishNumberElement.rightSideElement);
        sb.append(nestedRightSB);
        sb.append("]");
      }
    }
  }

  static final class SnailFishNumberElementBuilder
  {
    private int leftSide = -1;
    private int rightSide = -1;
    private boolean wasComma = false;
    private SnailFishNumberElement leftSideElement = SnailFishNumberElement.INVALID;
    private SnailFishNumberElement rightSideElement = SnailFishNumberElement.INVALID;

    SnailFishNumberElementBuilder()
    {
    }

    public void processElement(final SnailFishNumberElement e)
    {
      if (wasComma)
      {
        rightSideElement = e;
      }
      else
      {
        leftSideElement = e;
      }
    }

    public void processDigit(final char c)
    {
      if (wasComma)
      {
        if (rightSide < 0)
          rightSide = c - '0';
        else
          rightSide = rightSide*10 + (c - '0');
      }
      else
      {
        if (leftSide < 0)
          leftSide = c - '0';
        else
          leftSide = leftSide * 10 + (c - '0');
      }
    }

    public void processComma()
    {
      wasComma = true;
    }

    public SnailFishNumberElement build()
    {
      if (!wasComma)
      {
        return SnailFishNumberElement.makeRegularNumber(leftSide);
      }
      if (leftSideElement != SnailFishNumberElement.INVALID)
      {
        if (rightSideElement != SnailFishNumberElement.INVALID)
        {
          return SnailFishNumberElement.makeSnailFishNumber(leftSideElement, rightSideElement);
        }
        return SnailFishNumberElement.makeSnailFishNumber(leftSideElement, SnailFishNumberElement.makeRegularNumber(rightSide));
      }
      if (rightSideElement != SnailFishNumberElement.INVALID)
      {
        return SnailFishNumberElement.makeSnailFishNumber(SnailFishNumberElement.makeRegularNumber(leftSide), rightSideElement);
      }
      return SnailFishNumberElement.makeSnailFishNumber(SnailFishNumberElement.makeRegularNumber(leftSide), SnailFishNumberElement.makeRegularNumber(rightSide));
    }
  }
}

 

[PHolder]

[ This is the final third part of the day 18 post because it wouldn't all fit in one post ]

The SnailFishMath class really just helps make the part one and part two methods read a little more clealy. I'm not actually sure much of it is any sort of a spoiler, but there might be one thing that isn't completely obvious, so I will blur it.

The SnailFishMath class

final class SnailFishMath
{
  public static SnailFishNumber add(final SnailFishNumber leftSide, final SnailFishNumber rightSide)
  {
    if (leftSide  == SnailFishNumber.ZERO)  return rightSide;
    if (rightSide == SnailFishNumber.ZERO)  return leftSide;

    final SnailFishNumber unreducedAddition = SnailFishNumber.doAddition(leftSide, rightSide);
    return doReduction(unreducedAddition);
  }

  static SnailFishNumber doReduction(final SnailFishNumber unreducedSnailFishNumber)
  {
    SnailFishNumber reductionResult = unreducedSnailFishNumber;

    boolean madeAChange = true;
    while (madeAChange)
    {
      madeAChange = false;
      if (shouldExplode(reductionResult))
      {
        madeAChange = true;
        final ExplodeComponents explodeComponents = reductionResult.getExplodeComponents();
        reductionResult = reductionResult.doExplode(explodeComponents);
        continue;
      }
      final SnailFishNumberElement splitElement = reductionResult.getSplitElement();
      if (splitElement != SnailFishNumberElement.INVALID)
      {
        madeAChange = true;
        reductionResult = reductionResult.doSplit(splitElement);
        continue;
      }
    }

    return reductionResult;
  }

  static boolean shouldExplode(final SnailFishNumber snailFishNumberToCheck)
  {
    return snailFishNumberToCheck.shouldExplode();
  }

  public static long getMagnitude(final SnailFishNumber snailFishNumberToGetMagnitudeOf)
  {
    return snailFishNumberToGetMagnitudeOf.getMagnitude();
  }
}

The solvers for each part should be pretty obvious, but the handling of part two has one trick:

The calculation of part one and part two answers

public static long getPart1Answer(final String day18Input, final String[] day18InputLines)
{
  SnailFishNumber currentSum = SnailFishNumber.ZERO;
  for (final String textualSnailFishNumber :  day18InputLines)
  {
    final SnailFishNumber sfn = new SnailFishNumber(textualSnailFishNumber);
    currentSum = SnailFishMath.add(currentSum, sfn);
  }
  return SnailFishMath.getMagnitude(currentSum);
}

public static long getPart2Answer(final String day18Input, final String[] day18InputLines)
{
  long maxMagnitude = -1;
  for (int i=0; i<day18InputLines.length; i++)
  {
    for (int j=0; j<day18InputLines.length; j++)
    {
      if (i==j) continue;
      final SnailFishNumber sfn1 = new SnailFishNumber(day18InputLines[i]);
      final SnailFishNumber sfn2 = new SnailFishNumber(day18InputLines[j]);
      final SnailFishNumber sum = SnailFishMath.add(sfn1, sfn2);
      final long magnitude = SnailFishMath.getMagnitude(sum);
      if (magnitude > maxMagnitude)  maxMagnitude = magnitude;
    }
  }
  return maxMagnitude;
}

 

[PHolder]

I still don't have working code for Day 19. I know an approach that should work, but life has gotten in the way of getting it debugged. I think what you need to do is use [3D Manhatten Distatance](https://en.wikipedia.org/wiki/Taxicab_geometry) for each beacon at each scanner. Since the distance between beacons won't change no matter which scanner sees them (even though they each may not see all) then you can use identical distances to start to hone in on which sets of beacons pairs of scanners have in common. Then you can use the pinned scanners (initially only scanner 0) to translate other scanners into the same space and pin them down too. Repeat until done.

One of the things that got in the way of getting this debugged was driving to another city to get computer parts and then assembling a new computer and installing and configuring it so that I can use it to continue with the challenges. I'm not concerned about missing one since I figured out an approach to solve it that I feel I could implement (with available time.)

Coincidentally, 3D geometry is some of the types of coding I enjoy least... so I'm not terribly motivated to work on the problem anyway. I knew I was never going to be on the leaderboard...

 

[PHolder]

Day 20 would be very straightforward, if only Eric wasn't deliberately making it a tricky situation. The trick is to consider what pixel value should occupy the infinite portion of the image.

Further consider that the problem only asks for even numbered iterations of the picture, because if the infinite background was on when he asked for the count of pixels, the answer would be infinite too.

To solve the problem I made three classes: PixelImage and PixelImageWriter and ImageEnhancer. None of them have significant code.

Here's PixelImage:

The PixelImage class

final class PixelImage
{
  private final int width;
  private final int height;
  private final String[] pixelLines;
  private final boolean infiniteBackgroundPixel;

  public PixelImage(final String[] pixelLines)
  {
    this(pixelLines, false);
  }

  public PixelImage(final String[] pixelLines, final boolean infiniteBackgroundPixel)
  {
    width = pixelLines[0].length();
    height = pixelLines.length;
    this.pixelLines = pixelLines;
    this.infiniteBackgroundPixel = infiniteBackgroundPixel;
  }

  boolean isPixelLit(int x, int y)
  {
    if ((x<0) || (x>=width))  return infiniteBackgroundPixel;
    if ((y<0) || (y>=height))  return infiniteBackgroundPixel;
    return pixelLines[y].charAt(x) == '#';
  }
  
  int getClusterValue(final int x, final int y)
  {
    int result = 0;
    if (isPixelLit(x-1, y-1))  result+=256;
    if (isPixelLit(x  , y-1))  result+=128;
    if (isPixelLit(x+1, y-1))  result+= 64;
    if (isPixelLit(x-1, y  ))  result+= 32;
    if (isPixelLit(x  , y  ))  result+= 16;
    if (isPixelLit(x+1, y  ))  result+=  8;
    if (isPixelLit(x-1, y+1))  result+=  4;
    if (isPixelLit(x  , y+1))  result+=  2;
    if (isPixelLit(x+1, y+1))  result+=  1;
    return result;
  }

  public int getWidth()
  {
    return width;
  }

  public int getHeight()
  {
    return height;
  }

  public long getNumberOfLitPixels()
  {
    int count = 0;
    for (int y=0; y<height; y++)
    {
      for (int x=0; x<width; x++)
      {
        if (isPixelLit(x, y)) count++;
      }
    }

    return count;
  }

  public boolean getInfinitBackgroundPixel()
  {
    return infiniteBackgroundPixel;
  }
}

Here's PixelImageWriter, spoiler blurred for one parameter name:

The PixelImageWriter class

final class PixelImageWriter
{
  final int width;
  final int height;
  final char[][] pixels;
  public PixelImageWriter(final int width, final int height)
  {
    this.width  = width;
    this.height = height;
    pixels = new char[width][height];
  }

  public void putPixel(final int x, final int y, final boolean isPixelLit)
  {
    if (isPixelLit)
      pixels[x][y] = '#';
    else
      pixels[x][y] = '.';
  }
  
  PixelImage getPixelImage(final boolean infiniteBackgroundPixel)
  {
    final String[] pixelStrings = new String[height];
    for (int y=0; y<height; y++)
    {
      final StringBuilder sb = new StringBuilder();
      for (int x=0; x<width; x++)
      {
        sb.append(pixels[x][y]);
      }
      pixelStrings[y] = sb.toString();
    }
    return new PixelImage(pixelStrings, infiniteBackgroundPixel);
  }
}

And here's ImageEnhancer:

The ImageEnhancer class

final class ImageEnhancer
{
  private final String imageEnhancementLookup;
  
  ImageEnhancer(final String imageEnhancementLookup)
  {
    this.imageEnhancementLookup = imageEnhancementLookup;
  }

  PixelImage enhanceImage(final PixelImage inputImage)
  {
    final PixelImageWriter piw = new PixelImageWriter(inputImage.getWidth()+6, inputImage.getHeight()+6);
    for (int y=-3; y<inputImage.getHeight()+3; y++)
    {
      for (int x=-3; x<inputImage.getWidth()+3; x++)
      {
        piw.putPixel(x+3, y+3, imageEnhancementLookup.charAt(inputImage.getClusterValue(x, y)) == '#');
      }
    }
    
    final boolean infinitBackgroundPixel;
    if (inputImage.getInfinitBackgroundPixel())
    {
      infinitBackgroundPixel = getVal(511);
    }
    else
    {
      infinitBackgroundPixel = getVal(0);
    }
    return piw.getPixelImage(infinitBackgroundPixel);
  }

  boolean getVal(int lookupPos)
  {
    return imageEnhancementLookup.charAt(lookupPos) == '#';
  }
}

And finally, here's the two methods to get the answers for the two parts, nothing special here to blur:

public static long getPart1Answer(final String day20Input, final String[] day20InputLines)
{
  final ImageEnhancer ie = new ImageEnhancer(day20Input);
  final PixelImage pi = new PixelImage(day20InputLines);
    
  final PixelImage pi2 = ie.enhanceImage(pi);
  final PixelImage pi3 = ie.enhanceImage(pi2);

  return pi3.getNumberOfLitPixels();
}

public static long getPart2Answer(final String day20Input, final String[] day20InputLines)
{
  final ImageEnhancer ie = new ImageEnhancer(day20Input);
  PixelImage pi = new PixelImage(day20InputLines);
  for (int i=0; i<50; i++)
  {
    pi = ie.enhanceImage(pi);
  }
  return pi.getNumberOfLitPixels();
}

 

[PHolder]

Day 21 has us play quantum dice games... WTF!! I actually cracked 1000 with part one, coming in at 740 or so. I just straight out simulated the game, and it was so little code, I didn't even code a new class, I just included it into the part one solution finder. For part two, I came up with the two tables I needed by working on paper. Three dice throws is a row where each one "splits" three ways, is 27 possible outcomes. There will only be one case with three ones (a sum of three), but there are three ways to get a sum of four, six ways to get a sum of five, seven ways to get a sum of six, six ways to get a sum of seven, three ways to get a sum of eight and finally one way to get a sum of nine.

The major trick for part two is to realize you will see the same outcomes occur many times over and so you can pass the number of times into a recursive call.

Here's the solution for part one along with the part two call to the DiceGame class:

Part one solution and the part two invocation of the DiceGame class

public static long getPart1Answer(final int player1StartingLocation, final int player2StartingLocation)
{
  int player1Score = 0;
  int player2Score = 0;
  int diceVal = 1;
  int player1Location = player1StartingLocation;
  int player2Location = player2StartingLocation;
  int numberOfDiceRolls = 0;
  while (player1Score < 1000 && player2Score < 1000)
  {
    final int player1Move = diceVal*3+3;
    numberOfDiceRolls += 3;
    diceVal += 3;
    player1Location = ((player1Location-1) + player1Move) % 10 + 1;
    player1Score += player1Location;
    if (player1Score >= 1000) break;

    final int player2Move = diceVal*3+3;
    numberOfDiceRolls += 3;
    diceVal += 3;
    player2Location = ((player2Location-1) + player2Move) % 10 + 1;
    player2Score += player2Location;
  }

  return Math.min(player1Score, player2Score) * numberOfDiceRolls;
}

public static long getPart2Answer(final int player1StartingLocation, final int player2StartingLocation)
{
  final DiceGame dg = new DiceGame(21);
    
  return dg.playAGame(player1StartingLocation, player2StartingLocation);
}

And here's the part two class DiceGame:

The DiceGame class

final class DiceGame
{
  private long numberOfPlayer1Wins;
  private long numberOfPlayer2Wins;
  private final int winningScore;
  
  public DiceGame( final int winningScore)
  {
    this.winningScore = winningScore;
  }

  long playAGame(final int player1StartingLocation, final int player2StartingLocation)
  {
    numberOfPlayer1Wins = 0;
    numberOfPlayer2Wins = 0;
    playARound(player1StartingLocation, player2StartingLocation, 0, 0, 1, 1);
    return Math.max(numberOfPlayer1Wins, numberOfPlayer2Wins);
  }

  private static final int[] EACH_DICE_ROLL_COUNT   = {1, 3, 6, 7, 6, 3, 1};
  private static final int[] EACH_DICE_ROLL_ADVANCE = {3, 4, 5, 6, 7, 8, 9};

  void playARound(
      final int player1Position,
      final int player2Position,
      final int player1Score,
      final int player2Score,
      final int whichPlayersTurn,
      long numberOfGamesThatReachThisSituation
    )
  {
    if (whichPlayersTurn == 1)
    {
      for (int i=0; i<EACH_DICE_ROLL_COUNT.length; i++)
      {
        final int p1NewPos = (player1Position-1 + EACH_DICE_ROLL_ADVANCE[i]) % 10 + 1;
        final int p1NewScore = player1Score + p1NewPos;
        if (p1NewScore >= winningScore)
          numberOfPlayer1Wins += numberOfGamesThatReachThisSituation * EACH_DICE_ROLL_COUNT[i];
        else playARound(p1NewPos, player2Position, p1NewScore, player2Score, 2, numberOfGamesThatReachThisSituation * EACH_DICE_ROLL_COUNT[i]);
      }
    }
    else
    {
      for (int i=0; i<EACH_DICE_ROLL_COUNT.length; i++)
      {
        final int p2NewPos = (player2Position-1 + EACH_DICE_ROLL_ADVANCE[i]) % 10 + 1;
        final int p2NewScore = player2Score + p2NewPos;
        if (p2NewScore >= winningScore)
          numberOfPlayer2Wins += numberOfGamesThatReachThisSituation * EACH_DICE_ROLL_COUNT[i];
        else playARound(player1Position, p2NewPos, player1Score, p2NewScore, 1, numberOfGamesThatReachThisSituation * EACH_DICE_ROLL_COUNT[i]);
      }
    }
  }
}