Advent of Code 2021

It’s soon to be that time of year… Advent of Code 2021 starts on Dec 1st. (I guess you have one week to prepare from the time I am making the post.) I will be attempting the challenges again this year, and sharing my thoughts here (with spoiler tags) in case you need a hint. (Assuming I don’t get stumped myself.) I also expect @Leo will give the first week a go as well, LISPing all the way :wink:

In the mean time, you can still do past years, some discussion about them is available here:

I’m trying to decide how to handle input this year. In past years I always kept my customized input in a text file in my resources folder for the problem. Since last year, Java has added a new feature for multi-line raw strings. So now I could do:

static final String PROVIDED_INPUT =
   """
     [provided input text goes here]
  """ ;

Which is probably a faster way to tackle getting the input unless it gets way too long. (I think Java has some limits on statics that restrict the total size to 64K bytes.

I’m excited although I suspect I’ll be slower than usual this year. I still have a lot of Lisp to learn!

I’m excited to begin again–just a few more hours until the first challenge unlocks.

I did a few finger exercises on 2015’s problems just to get warmed up. I’ll be fine until I have to use Djikstra’s stratagem or the Chinese Sandwich Theorem. This year I’ll post my solutions on Github instead of pasting them in here. But I’ll put comments here. 20 minutes to go!

Day 01 (I number them with two digits so they align up to 25) was pretty easy. Took me about 10 minutes, by which time over 2000 others had already submitted their answers.

Here’s a sketch of what I did, starting with a very boring main:

final int increaseCount = Day01.countIncreases(theDepthIntegers);
System.out.println("Part 1: " + increaseCount);

final int slidingWindowIncreaseCount = Day01.countSlidingWindowIncreases(theDepthIntegers);
System.out.println("Part 2: " + slidingWindowIncreaseCount);

Nothing unusual or exciting to see there.

The actual Day01 class is just two methods with a for loop each.

public static int countIncreases(final int[] theDepthIntegers)
{
  int result = 0;
  for (int i=1; i<theDepthIntegers.length; i++)
  {
    if (theDepthIntegers[i-1] < theDepthIntegers[i]) result++;
  }
  return result;
}

public static int countSlidingWindowIncreases(final int[] theDepthIntegers)
{
  int result = 0;
  for (int i=3; i<theDepthIntegers.length; i++)
  {
    final int sum1 = theDepthIntegers[i-1] + theDepthIntegers[i-2] + theDepthIntegers[i-3];
    final int sum2 = theDepthIntegers[i]   + theDepthIntegers[i-1] + theDepthIntegers[i-2];
    if (sum1 < sum2) result++;
  }
  return result;
}

Yeah, fairly easy. I hate how Eric Wastl teases us!

https://github.com/leolaporte/aoc

Day       Time  Rank  Score       Time   Rank  Score
  1   00:24:22  7349      0   12:27:40  59726      0

Hey, I’ve got a life you know!

It’s interesting to compare the imperative (Java) solution with the functional (Racket) solution. For the longest time I wished for a simple for loop, but once I got used to recursion everywhere I accepted my fate. Now I kind of think in lists which helps a lot.

I got to my computer minutes before, and hadn’t prepared at all (getting my submission tool ready, etc.), so I ended up totally winging it and using the Python REPL to solve this. Literally copy-pasted the input from my browser into triple-quotes. :joy:

I’ve mentioned in this forum before, I’m one of the people who tries to solve it as quickly as possible at release-time, so…

Day       Time  Rank  Score       Time  Rank  Score
  1   00:01:44   455      0   00:03:32   234      0

FYI, there’s an #adventofcode channel on Libera.Chat. There are some fun people in there, so come join us! Disclosure, I’m an op there.

Nice job! I will check out the AOC channel, too!

As I was coding part 2 I was mulling whether I should act on the fact that Sum1 = A + B + C and Sum2 = B + C + D so B and C are in common and the actual comparison is between A and D. I didn’t bother not doing the sums because there was nothing to be gained from the efficiency in this case.

That’s the kind of thinking I have to remember to do. I think later on it will become important - the naive answer is often not the best.

So Day 2 is a parsing/regex problem with some simple variable increment/decrement and a final multiplication. Part two adds a little twist, but for me I just reworked part one to add a boolean as to whether or not to do the new thing. I had preemptively passed in the initial values of 0 because with these problems, frequently making part one more general leads to better handling part two. (Which really makes me wonder what kind of gross code the people rushing for a one minute solution must write. I was in the 7000+ range with my submission in only 15 minutes, but I wrote test cases too.)

Anyway the main is pretty much always a variation of invoking code in the object with the methods to solve for the problem of the day (and then print them, of course.)

final long part1Result = Day02.followSubmarineInstructions(0, 0, 0, day02InputLines, false);
final long part2Result = Day02.followSubmarineInstructions(0, 0, 0, day02InputLines, true);

The main work is the parsing and “following/execution” of the instructions:

  final Pattern p = Pattern.compile("(\\w+) +(\\d+)");
  for (final String submarineInstruction : inputSubmarineInstructions)
  {
    final Matcher m = p.matcher(submarineInstruction);
    if (m.matches())
    {
      final String instruction = m.group(1);
      final int distance = Integer.parseInt(m.group(2));
      switch (instruction)
      {
        case "up":
        {
          if (shouldUseAim)
            aim -= distance;
          else
            depth -= distance;
        }
        break;
      
        case "down":
        {
          if (shouldUseAim)
            aim += distance;
          else
            depth += distance;
        }
        break;

        case "forward":
        {
          if (shouldUseAim)
          {
            depth += distance * aim;
          }
          horizontalPosition += distance;
        }
        break;
      
        default:
          throw new IllegalStateException("Don't know how to execute submarine instruction: " + submarineInstruction);
      }
    }
    else
    {
      throw new IllegalStateException("Invalid submarine instruction: " + submarineInstruction);
    }
  }

  return depth * horizontalPosition;

A regex feeding a switch() makes quick work of this easy level of parsing. There isn’t much of a twist in the variable manipulation beyond the up being minus and down being plus as is well called out multiple times in the problem text.

Here’s my code as of submission, sans boilerplate; data is a list of strings, one for each line:

def part1(data):
    horz = 0
    depth = 0
    for command in data:
        where, dist = command.split()
        dist = int(dist)

        if where == "forward":
            horz += dist
        if where == "up":
            depth -= dist
        if where == "down":
            depth += dist

    return horz * depth


def part2(data):
    horz = 0
    depth = 0
    aim = 0
    for command in data:
        where, dist = command.split()
        dist = int(dist)

        if where == "forward":
            horz += dist
            depth += aim * dist
        if where == "up":
            aim -= dist
        if where == "down":
            aim += dist

    return horz * depth
Day       Time  Rank  Score       Time  Rank  Score
  2   00:02:39   675      0   00:04:05   430      0

Had to do this before going to bed! Not as fast as you guys, though!

     --------Part 1--------   --------Part 2--------
Day       Time   Rank  Score       Time   Rank  Score
  2   00:38:41  13051      0   01:06:26  14647      0

Okay, Day 3 is still straight forward, but there is a fair bit more to do (at least in Java, maybe other [less strictly typed] languages can munge strings into bits and back more easily.)

Part one wasn’t actually that challenging, I finished it in 18 minutes or so. (The unit test of the provided example ran correctly the first try.) I did waste a bit of time by assuming (without checking) that the input width of the challenge input was the same size as the sample input… I wasted some time going back to pass in the missing width parameter.

public static long getPart1Answer(final String day03Input, final String[] day03InputLines, final int bitWidth)
{
  int gamma = 0;
  int epsilon = 0;
  for(int i=bitWidth; i>0; i--)
  {
    final int bit = getBit(i, day03InputLines, bitWidth);
    gamma = (gamma << 1) | bit;
    epsilon = (epsilon << 1) | (bit==0?1:0);
  }

  return gamma*epsilon;
}

private static int getBit(final int bitNum, final String[] day03InputLines, final int bitWidth)
{
  int oneBitCount = 0;
  int zeroBitCount = 0;
  final int bitCharPos = bitWidth - bitNum;
  for (final String bitLine: day03InputLines)
  {
    final char bitChar = bitLine.charAt(bitCharPos);
    if (bitChar == '0') zeroBitCount++;
    else if (bitChar == '1') oneBitCount++;
    else throw new IllegalStateException("Invalid bit char: " + bitChar);
  }

  if (oneBitCount > zeroBitCount) return 1;
  return 0;
}

Part two was different enough that it didn’t really reuse any of my code for part one. I decided to represent the list of strings as a Set, which was probably a mistake that luckily didn’t bite me back. After I finished and got the correct answers I realized that was luck, because there really wasn’t any guarantee that the same bit string wouldn’t occur more than once. (Although in my challenge input it obviously must not have.) Part of the processing requires eliminating a subset of entries from the list (or set in my case) and it’s never safe in Java to walk the entries while attempting to concurrently modify them. This required having a set being processed and a new set contain the extracted remainders.

public static long getPart2Answer(final String day03Input, final String[] day03InputLines, final int bitWidth)
{
  final Set<String> oxygenBits = new HashSet<>();
  final Set<String> co2Bits = new HashSet<>();
  for (final String s: day03InputLines)
  {
    oxygenBits.add(s);
    co2Bits.add(s);
  }

  final int oxygenVal = workDownToOneVal(oxygenBits, 1, bitWidth);
  final int co2Val = workDownToOneVal(co2Bits, 0, bitWidth);

  return oxygenVal * co2Val;
}

private static int workDownToOneVal(final Set<String> bitStrings, final int bitVal, final int bitWidth)
{
  Set<String> bitStringsToProcess = new HashSet<>();
  Set<String> remainingStringsToProcess = new HashSet<>();
  bitStringsToProcess.addAll(bitStrings);

  for(int i=bitWidth; i>0; i--)
  {
    remainingStringsToProcess.clear();
    final int bit = getBit(i, bitStringsToProcess, bitWidth, bitVal);

    final int bitCharPos = bitWidth - i;
    for (final String s: bitStringsToProcess)
    {
      final char bitChar = s.charAt(bitCharPos);
      if ((bitChar == '1') && (bit == 1)) remainingStringsToProcess.add(s);
      if ((bitChar == '0') && (bit == 0)) remainingStringsToProcess.add(s);
    }

    bitStringsToProcess.clear();
    bitStringsToProcess.addAll(remainingStringsToProcess);
    remainingStringsToProcess.clear();
  
    if (bitStringsToProcess.size() == 1) break;
  }

  if (bitStringsToProcess.size() != 1) throw new IllegalStateException("Processing didn't result in a single value");

  //  A bit of a hack to extract the single value from the Set<>
  final List<String> entries = new ArrayList<>();
  entries.addAll(bitStringsToProcess);
  final String entry = entries.get(0);

  // Realized too late that this loop could be replaced by
  // final int result = Integer.parseInt(entry, 2);
  int result = 0;
  for(int i=bitWidth; i>0; i--)
  {
    final char bitChar = entry.charAt(bitWidth-i);
    result = (result << 1) | (bitChar=='1'?1:0);
  }

  return result;
}

private static int getBit(final int bitNum, final Set<String> bitStringsToProcess, final int bitWidth, final int bitVal)
{
  int oneBitCount = 0;
  int zeroBitCount = 0;
  final int bitCharPos = bitWidth - bitNum;
  for (final String bitLine: bitStringsToProcess)
  {
    final char bitChar = bitLine.charAt(bitCharPos);
    if (bitChar == '0') zeroBitCount++;
    else if (bitChar == '1') oneBitCount++;
    else throw new IllegalStateException("Invalid bit char: " + bitChar);
  }

  if (bitVal == 1)
  {
    if (oneBitCount == zeroBitCount) return 1;
    if (oneBitCount > zeroBitCount) return 1;
    return 0;
  }

  if (oneBitCount == zeroBitCount) return 0;
  if (oneBitCount > zeroBitCount) return 0;
  return 1;
}

It’s far from the most elegant code, but it is very straightforward. I probably could have parsed the bit string to Integer in one line, now that I think of it, but it’s not something I do often so it didn’t jump quickly to mind and by the time I remembered that you could pass bases into Integer.ParseInt() I had already coded the loop.

On Day 4 we’re playing BINGO. This was fairly straightforward. I started by making an object to represent a bingo card and to keep track of which numbers on that card have been played and to check if the card is a winner. Having built and tested that, it was just then a matter of building code to “draw the numbers and play them” until the required condition is met.

My BingoCard class. The initialization part is a little clunky, but I was still trying to rush a bit to have good speed and copy and paste is pretty fast coding.

final class BingoCard
{
  private final int[][]     bingoCardNumbers = new int[5][5];
  private final boolean[][] wasNumberPlayed = new boolean[5][5];
  private final int         bingoCardNumber;
  private int               winningRow = -1;
  private int               winningCol = -1;

  public BingoCard(final int bingoCardNumber,
      final String line1,
      final String line2,
      final String line3,
      final String line4,
      final String line5)
  {
    this.bingoCardNumber = bingoCardNumber;
    int[] lineVals = getLineVals(line1);
    putIntLineVals(1, lineVals);
    lineVals = getLineVals(line2);
    putIntLineVals(2, lineVals);
    lineVals = getLineVals(line3);
    putIntLineVals(3, lineVals);
    lineVals = getLineVals(line4);
    putIntLineVals(4, lineVals);
    lineVals = getLineVals(line5);
    putIntLineVals(5, lineVals);
  }

  private int[] getLineVals(final String lineOfNumbers)
  {
    final Pattern p = Pattern.compile(" *(\\d+) +(\\d+) +(\\d+) +(\\d+) +(\\d+)");
    final Matcher m = p.matcher(lineOfNumbers);
    final int[] result = new int[5];
    if (!m.matches())  throw new IllegalStateException("Couldn't parse bingo card line: " + lineOfNumbers);
    result[0] = Integer.parseInt(m.group(1));
    result[1] = Integer.parseInt(m.group(2));
    result[2] = Integer.parseInt(m.group(3));
    result[3] = Integer.parseInt(m.group(4));
    result[4] = Integer.parseInt(m.group(5));
    return result;
  }

  private void putIntLineVals(final int lineNumber, int[] lineVals)
  {
    bingoCardNumbers[lineNumber-1][0] = lineVals[0];
    bingoCardNumbers[lineNumber-1][1] = lineVals[1];
    bingoCardNumbers[lineNumber-1][2] = lineVals[2];
    bingoCardNumbers[lineNumber-1][3] = lineVals[3];
    bingoCardNumbers[lineNumber-1][4] = lineVals[4];
  }

  public int getValAtPos(final int row, final int col)
  {
    return bingoCardNumbers[row-1][col-1];
  }

  public boolean playNumber(final int numberToPlay)
  {
    for(int i=0; i<5; i++)
    {
      for(int j=0; j<5; j++)
      {
        if (bingoCardNumbers[i][j] == numberToPlay)
        {
          wasNumberPlayed[i][j] = true;
        }
      }
    }
    return isABingo();
  }

  private boolean isABingo()
  {
    for(int i=0; i<5; i++)
    {
      boolean fullLine = true;
      for(int j=0; j<5; j++)
      {
        if (!wasNumberPlayed[i][j])
        {
          fullLine = false;
          break;
        }
      }
      if (fullLine)
      {
        winningRow = i;
        return true;
      }
    }

    for(int j=0; j<5; j++)
    {
      boolean fullLine = true;
      for(int i=0; i<5; i++)
      {
        if (!wasNumberPlayed[i][j])
        {
          fullLine = false;
          break;
        }
      }
      if (fullLine)
      {
        winningCol = j;
        return true;
      }
    }

    return false;
  }

  public int getCardNumber()
  {
    return bingoCardNumber;
  }

  public int getWinningRow()
  {
    return winningRow;
  }

  public int getWinningCol()
  {
    return winningCol;
  }

  public int getSumOfNonPlayedNumbers()
  {
    int result = 0;
    for(int i=0; i<5; i++)
    {
      for(int j=0; j<5; j++)
      {
        if (!wasNumberPlayed[i][j]) result += bingoCardNumbers[i][j];
      }
    }
    return result;
  }

  public boolean alreadyWon()
  {
    return winningRow>=0 || winningCol>=0;
  }

  @Override
  public final String toString()
  {
    final StringBuilder sb = new StringBuilder();
    for(int i=0; i<5; i++)
    {
      for(int j=0; j<5; j++)
      {
        if (wasNumberPlayed[i][j])
          sb.append(String.format(" [%2d]", bingoCardNumbers[i][j]));
        else
          sb.append(String.format("  %2d ", bingoCardNumbers[i][j]));
      }
      sb.append('\n');
    }
    return sb.toString();
  }
}

I included a debugging method to dump the card, indicating the played numbers, this allowed me to do some easy debugging as I was unit testing. Here’s a sample output:

 [14] [21] [17] [24] [ 4]
  10   16   15  [ 9]  19 
  18    8  [23]  26   20 
  22  [11]  13    6  [ 5]
 [ 2] [ 0]  12    3  [ 7]

Part two is only slightly more complicated than part one, so I will show my part two code and leave part one as an “exercise for the reader”. The only trick for part 2 was to make sure you never re-counted a bingo card that had already won:

public static long getPart2Answer(final String day04Input1, final String[] day04InputLines2)
{
  final Map<Integer, BingoCard> bingoCards = new HashMap<>();
  int bingoCardNumber = 0;
  int bingoCardStartLine = 0;
  while (bingoCardStartLine+4 < day04InputLines2.length)
  {
    bingoCardNumber++;
    final BingoCard newBingoCard = new BingoCard(bingoCardNumber,
      day04InputLines2[bingoCardStartLine],
      day04InputLines2[bingoCardStartLine+1],
      day04InputLines2[bingoCardStartLine+2],
      day04InputLines2[bingoCardStartLine+3],
      day04InputLines2[bingoCardStartLine+4]);
    bingoCards.put(bingoCardNumber, newBingoCard);
    bingoCardStartLine = bingoCardNumber*6; // 5 lines and a blank line
  }
  final int numberOfBingoCards = bingoCards.size();
  System.out.println("Number of bingo cards = " + numberOfBingoCards);

  int numberOfWinningCards = 0;

  final int[] numbersToPlay = parseNumbersToPlay(day04Input1);

  int numberPlayedThatResultedInWin = 0;
  int sumOfNonPlayedNumbersOnCard = 0;
  boolean haveWinner = false;
  for (final int numberToPlay: numbersToPlay)
  {
    for (final BingoCard bingoCard: bingoCards.values())
    {
      if (!bingoCard.alreadyWon())
      {
        if (bingoCard.playNumber(numberToPlay))
        {
          numberOfWinningCards++;
          if (numberOfWinningCards == numberOfBingoCards)  // HINT:  change this line to do part one
          {
            System.out.println(bingoCard);
            System.out.format("Found final winner playing %d on card %d winningRow=%d winningCol=%d%n", numberToPlay, bingoCard.getCardNumber(), bingoCard.getWinningRow(), bingoCard.getWinningCol());
            haveWinner = true;
            numberPlayedThatResultedInWin = numberToPlay;
            sumOfNonPlayedNumbersOnCard = bingoCard.getSumOfNonPlayedNumbers();
            System.out.format("numberPlayedThatResultedInWin=%d sumOfNonPlayedNumbersOnCard=%d%n", numberPlayedThatResultedInWin, sumOfNonPlayedNumbersOnCard);
          }
        }
      }
      if (haveWinner) break;
    }
    if (haveWinner)  break;
  }
  return (long)numberPlayedThatResultedInWin * (long)sumOfNonPlayedNumbersOnCard;
}

On Day 5 we’re mapping lines onto a 2D plane/grid and counting the number of intersections (well not exactly that, but close enough.)

The input lines are all either horizontal, vertical, or perfectly at 45 degrees. For part one you need to filter out the ones at 45 degrees.

For my solution, I created classes to represent points, lines and the grid itself. Then I regex’d the input into 4 integers representing x1,y1 and x2,y2 to create a line. I then asked the grid to map the line onto itself, which had it ask the line for all of its constituent points to do the mapping. To get the result you just ask the grid to count all the points where the number of intersections is at or above the threshold.

Here’s my basic Point class, this is practically boilerplate to most developers I assume, to the point (no pun intended) that there is no point (no pun intended again) to spoiler blur it:

final class Point
{
  final int x;
  final int y;

  Point(final int x, final int y)
  {
    this.x = x;
    this.y = y;
  }

  int getX()
  {
    return x;
  }

  int getY()
  {
    return y;
  }
}

The line class is only slightly less boilerpoint because the conversion to points is mildly tricky:

final class Line
{
  final int x1;
  final int y1;
  final int x2;
  final int y2;
  // For part 1 we need to filter on only horizontal or vertical lines
  final boolean isHorizontal;
  final boolean isVertical;

  Line(final int x1, final int y1, final int x2, final int y2)
  {
    this.x1=x1;
    this.y1=y1;
    this.x2=x2;
    this.y2=y2;
    if (x1==x2) isVertical   = true; else isVertical   = false;
    if (y1==y2) isHorizontal = true; else isHorizontal = false;
  }

  Point[] getPointsOnLine()
  {
    // For 45 degree lines both values will be identical, otherwise one will be 1
    final int lineLen = Math.max(getSize(x1,x2), getSize(y1,y2));
    final Point[] result = new Point[lineLen];

    int x=x1;
    int y=y1;
    int xdir=0;
    if (x1<x2) xdir=1;
    if (x2<x1) xdir=-1;
    int ydir=0;
    if (y1<y2) ydir=1;
    if (y2<y1) ydir=-1;
    for (int i=0; i<lineLen; i++)
    {
      final Point p = new Point(x, y);
      x+=xdir;
      y+=ydir;
      result[i] = p;
    }
    return result;
  }

  private static int getSize(final int val1, final int val2)
  {
    final int result;
    if (val1<=val2)
      result = val2-val1+1;
    else
      result = val1-val2+1;
    return result;
  }

  @Override
  public String toString()
  {
    return String.format("Line[%d,%d -> %d,%d]", x1,y1, x2,y2);
  }
}

And the grid class is hardly tricky at all, I don’t think there is anything here that isn’t obvious, so no point blurring any:

final class GridForLines
{
  final int[][] grid;
  final int width;
  final int height;

  GridForLines(final int width, final int height)
  {
    this.width = width;
    this.height = height;
    grid = new int[width][height];
  }

  void mapALineIntoGrid(final Line lineToMap)
  {
    final Point[] points = lineToMap.getPointsOnLine();
    for(final Point p : points)
    {
      grid[p.getX()][p.getY()]++;
    }
  }

  int getNumberOfPointsWithSpecifiedNumberOfLinesOrMore(final int numberOfLines)
  {
    int result = 0;
    for(final int[] row: grid)
    {
      for(final int i: row)
      {
        if (i>=numberOfLines) result++;
      }
    }
    return result;
  }

  @Override
  public String toString()
  {
    final StringBuilder sb = new StringBuilder();
    for (int x=0; x<width; x++)
    {
      for (int y=0; y<height; y++)
      {
        sb.append(String.format("[%2d] ", grid[x][y]));
      }
      sb.append("\n");
    }
    return sb.toString();
  }
}

The rest of the code is just the “problem” of parsing the input and pulling it all together, here’s the code for part one which is actually more code than part two because you need to filter the 45 degree lines out. Again, I don’t think there is anything here that’s not obvious, so no point blurring anything. I did pass in the grid size as a parameter, so I could reasonably debug the provided example, but I made it 1000 for the sample input as I did a quick look through mine and didn’t see anything bigger than three digits.

public static long getPart1Answer(final String day05Input, final String[] day05InputLines, final int gridSize)
{
  final Pattern p = Pattern.compile(" *(\\d+),(\\d+) *-> *(\\d+),(\\d+)");
  final GridForLines grid = new GridForLines(gridSize, gridSize);
  for (final String lineDescription : day05InputLines)
  {
    final Matcher m = p.matcher(lineDescription);
    if (!m.matches())  throw new IllegalStateException("Couldn't parse line description: " + lineDescription);
    final Line line = new Line(
        Integer.parseInt(m.group(1)), 
        Integer.parseInt(m.group(2)), 
        Integer.parseInt(m.group(3)), 
        Integer.parseInt(m.group(4)));
    if (line.isHorizontal || line.isVertical)
    {
      grid.mapALineIntoGrid(line);
    }
  }
  return grid.getNumberOfPointsWithSpecifiedNumberOfLinesOrMore(2);
}

@PHolder I’m not sure why your code doesn’t have syntax highlighting; it does for me in the preview. But even then, it’s not “correctly” highlighted, I think because the language detection is off. You can specify the language, and perhaps kill two birds with one stone, by putting java after the opening triple-backtick, like this: ```java

Hmm, it’s probably because I am not using backticks. If you just put 4 spaces in front of text it changes it to pre-formatted text. (I use enough different forum BB codes that I don’t know which forums use which codes and so I frequently rely on the tools in the toolbar above the post text box.) I guess Discourse also supports markdown (which is not something I know that well TBH, but I’ve used it once or twice on GitHub I guess.) Anyway, I can try it on my next post in a few hours :wink:

1 Like

Day 6 is like a super-simplified game of life simulation. You have to make sure you approach it the right way because if you try to simulate each fish, you will definitely not be able to complete part 2 (my input had results like Part 1: 35X_XXX and Part 2: 1_61X_XXX_XXX_XXX .)

The simplest approach I could think of was to represent the school of fish as an array of integers (initially, before I realized how big the numbers were going to get, and changed them to longs.) Basically you only need an array of 9 longs, where each one represents the number of fish at each level. Every day when you evolve it one day, you just update the array accordingly. Save the value in position 0 as that is going to be added to day 6 and written into day 8 but only after you update everything else. (Doing it in the wrong order will give you too many fish.) Then you just code a little loop to move array elements down, so the value in array[1] moves to array[0] and so on until array[8] moves to array[7]. Now you add that value to array[6] and write it into array[8]. Also update the count of the number of fish by the number of new fish (the same value you wrote into 8.)

Here’s that pseudo code in actual code:

final class SchoolOfLaternFish
{
  private final long[] numberOfFishAtEachLevel = new long[9];
  private long totalNumberOfFish = 0;
  
  void putAFishIn(final int fishNumber)
  {
    numberOfFishAtEachLevel[fishNumber]++;
    totalNumberOfFish++;
  }

  void evolveOneDay()
  {
    final long  numberToAddToDay6 = numberOfFishAtEachLevel[0];
    final long  numberToPutAtDay8 = numberOfFishAtEachLevel[0];
    totalNumberOfFish += numberOfFishAtEachLevel[0];
    for (int i=0; i<8; i++)
    {
      numberOfFishAtEachLevel[i]=numberOfFishAtEachLevel[i+1];
    }
    numberOfFishAtEachLevel[6] += numberToAddToDay6;
    numberOfFishAtEachLevel[8]  = numberToPutAtDay8;
  }
  
  long getNumberOfFishInSchool()
  {
    return totalNumberOfFish;
  }
}

Really not very much code at all. I wrote more code in the unit test making sure I did it right :wink: