Advent of Code 2021

[PHolder]

In just a few hours the 2021 version of Advent of Code begins. I will be attempting it again this year, and posting about it, much as I did last year.

 

[Barry Wallis]

In just a few hours the 2021 version of Advent of Code begins. I will be attempting it again this year, and posting about it, much as I did last year.

Thanks for the reminder. I may try it and see how far I go before I give up.

 

[PHolder]

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;

Part 1 Spoiler

  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;

Part 2 Spoiler

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

 

[Paul F]

Day 01 Part 2

Spoiler(?)

What's interesting about the sliding sums is: if the numbers are a, b, c, d . . . then A=a+b+c and B=b+c+d. So, since b and c are common, if d > a then B > A; you don't need to do the sums.

 

[PHolder]

you don't need to do the sums.

Yeah, I considered that after I had already taken the boring predictable route just trying to get a solution submitted in quick time.

 

[miquelfire]

I saw that in a post on Reddit long after I got my answer. Stuff like that is why I never get to the end, I miss simple stuff like that.

 

[PHolder]

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:

Code for parts 1 and 2

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.

 

[PHolder]

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.

Part 1

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.

Part 2

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)
{
  final Set<String> bitStringsToProcess = new HashSet<>();
  final 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(); Done at top of loop
     
    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.

 

[PHolder]

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.

BingoCard Class

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:

Part Two (with hint for Part One)

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

 

[PHolder]

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()
  {

The line to point mapping code is mildly tricky

// 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)  // Just comment out this line for part two
    {
      grid.mapALineIntoGrid(line);
    }
  }
  return grid.getNumberOfPointsWithSpecifiedNumberOfLinesOrMore(2);
}

 

[PHolder]

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:

SchoolOfLaternFish class

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

 

[miquelfire]

Does Java have a shift and pop functions for arrays?

Since I'm using Javascript, my array bit looked like this:

function rotate_array(arr) {
    const first = arr.shift();
    arr.push(first);
}

Then the code that called this just added the value in 8 to 6

 

[PHolder]

Does Java have a shift and pop functions for arrays?

No, but you could use an array backed list I guess. I suspect that Javascript is much like Lua and treats any array as a [hash]map or something because treating an array like a stack seems odd to me. In Lua you can have array["foo"] as legitimately as array[n].

 

[PHolder]

Day 7 had me thinking there must be a simpler way to solve it than I came up with, but I brute forced it anyway as it was running through my 1000 inputs in less than a second. Part two did have a formulaic way to speed up the math, that anyone should have learned in algebra class (or combinatorics class). The sum of the numbers from 1 to n is n(n+1)/2 .

My approach was to find the minimum and maximum horizontal values as I parsed the string values to integers. (I keep them as strings, but in the future I probably should just do an array initialization with the provided values as a speedup... And I could probably find a standard library or 3rd party library to find the min and max in an array without having to code my own loop... but as I don't currently know if they exist, it would take me longer to find out than to just code the loop myself.)

Then I coded another loop to go between the minimum and the maximum and calculate the fuel used at each step, remembering the minimum value of the fuel used to supply the answer. I actually screwed up initially because I thought the best position was being requested as the answer and not the fuel used for that position... so that wasted me a good 5 minutes while I debugged code that didn't actually have a bug

The only change for part two was the means of calculating the fuel used, so it was pretty quick to get from a correct submission of part one to the correct submission of part two. (Although I can't actually find out how long because the site won't let me see my personal stats and says "This page has been temporarily disabled. Sorry!" )

Here's my code for part two as it's one line longer than the code for part one:

Code for part two

public static long getPart2Answer(final String day07Input, final String[] day07InputLines)
{
  final int[] crabHVals = new int[day07InputLines.length];
  int min = 100_000_000;
  int max = -1;
  for(int i=0; i<day07InputLines.length; i++)
  {
    final int crabHVal = Integer.parseInt(day07InputLines[i]);
    crabHVals[i] = crabHVal;
    if (crabHVal < min) min = crabHVal;
    if (crabHVal > max) max = crabHVal;
  }
  // System.out.format("Num crabs=%d, minHPos=%d, maxHPos=%d%n", day07InputLines.length, min, max);
  long bestMin = 100_000_000_000_000_000L;
  int bestPos = -1;
  // Brute force all values in range to find smallest fuel usage
  for (int i=min; i<=max; i++)
  {
    final long minGuess = calculateFuelUse2(crabHVals, i);
    if (minGuess < bestMin)
    {
      bestMin = minGuess;
      bestPos = i;
    }
  }
  // System.out.format("Best position=%d with fuel=%d%n", bestPos, bestMin);
  return bestMin;
}

private static long calculateFuelUse2(final int[] crabHVals, final int hPosition)
{
  long fuelUsed = 0;
  for (final int crabHVal : crabHVals)
  {
    final int n = Math.abs(hPosition - crabHVal);
    fuelUsed += n*(n+1)/2;  // the sum of numbers from 1 to n is N(N+1)/2
  }
  return fuelUsed;
}

 

[Paul F]

Day 7 had me thinking there must be a simpler way to solve it than I came up with, but I brute forced it anyway as it was running through my 1000 inputs in less than a second.

I originally solved this using basically the same algorithms you did. Then I thought about Part 1 a bit more and have a few observations.

If there is a unique minimum, it is a position occupied by one or more crabs. Proof(?): If it is not, then, if the position is moved left or right the cost will remain the same (what's added to one side is subtracted from the other) until it reaches a position occupied by one or more crabs in which case their cost becomes 0 and the total cost is reduced by the number of crabs at that position. Thus the previous position could not be a minimum.

Next, the minimum is at (or within 1 crab position of ?) the position where the number of crabs to the left is as equal as possible (depending on the clumping of the crabs) to the number of crabs on the right. Qualitatively: at an arbitrary position, if you move in the direction where there more crabs, the cost reduces on that side more than it increases on the other side, and as crabs move to the other side the amount the cost changes reduces until the minimum position is reached, after which the cost increases as you keep moving in the same direction and more crabs change sides.

Finally, I believe there are no local minimums (the cost increases monotonically as you move away from the minimum). So I believe a solution can be found by starting at the median position of the crabs and then checking it and adjacent positions for the minimum.

 

[PHolder]

// In trying to make this post, when I tried to post initially, I was greeted with "Please enter a message with no more than 10000 characters."
// So... I guess I wrote a lot of code!
// I will try breaking it up into two posts

For day 8 I was telling my friend I "brute^2 forced it" LOL. I got done in 1h22m (after doing part one in 16m.) This is the first day this year where I hardly used any code from part one in part two. I kept feeling like there should be a more clever answer, but I knew the brute force approach was going to get me there so I just soldiered on. The second level of brute force was I knew I could code something clever, but I did copy and paste and quick edits instead for expediency.

I could have been faster on the first part, but I got tripped up on the pipe char being special to regex and forgetting to escape it. Oops. I also initially misunderstood that my case for the required digits in part one needed to match on the length of the string. Luckily my unit tests saved me multiple times even though they cost time to code.

In my approach, I have methods like isZeroDigit(), isOneDigit(), isTwoDigit() etc... and that exposed a bug in my initial approach. I was initially only considering the lit segments and not the unlit ones. Of course that meant I was getting multiple possible digits.. for example 8 has all segments lit, so it can also be any other digit if you just looked at the lit segments.

Because of all my brute forcishness, I have a lot more code this time around. Here's my class that does the majority of the hard work, it represents a single seven segment display:

SevenSegmentLED class Part one of two

final class SevenSegmentLED
{
  final char[] signalWireLetters;
 
  SevenSegmentLED(final String[] signalsToDecode)
  {
    signalWireLetters = bruteForceDecodeSignalLetters(signalsToDecode);
  }

  int getDigitFromSignals(final String signal)
  {
    final boolean[] litSegments = decodeSignalToLitSegments(signalWireLetters, signal);

    if (isZeroDigit(litSegments))   return 0;
    if (isOneDigit(litSegments))    return 1;
    if (isTwoDigit(litSegments))    return 2;
    if (isThreeDigit(litSegments))  return 3;
    if (isFourDigit(litSegments))   return 4;
    if (isFiveDigit(litSegments))   return 5;
    if (isSixDigit(litSegments))    return 6;
    if (isSevenDigit(litSegments))  return 7;
    if (isEightDigit(litSegments))  return 8;
    if (isNineDigit(litSegments))   return 9;

    throw new IllegalStateException("Couldn't get digit from signal");
  }

  private char[] bruteForceDecodeSignalLetters(final String[] signalsToDecode)
  {
    final char[] signalWireLetters = new char[7];
   
    for(int a=0; a<7; a++)
    {
      for(int b=0; b<7; b++)
      {
        if (b==a) continue;
        for(int c=0; c<7; c++)
        {
          if ((c==a) || (c==b)) continue;
          for(int d=0; d<7; d++)
          {
            if ((d==a) || (d==b) || (d==c)) continue;
            for(int e=0; e<7; e++)
            {
              if ((e==a) || (e==b) || (e==c) || (e==d)) continue;
              for(int f=0; f<7; f++)
              {
                if ((f==a) || (f==b) || (f==c) || (f==d) || (f==e)) continue;
                for(int g=0; g<7; g++)
                {
                  if ((g==a) || (g==b) || (g==c) || (g==d) || (g==e) || (g==f)) continue;
                  signalWireLetters[a]=0;
                  signalWireLetters[b]=1;
                  signalWireLetters[c]=2;
                  signalWireLetters[d]=3;
                  signalWireLetters[e]=4;
                  signalWireLetters[f]=5;
                  signalWireLetters[g]=6;
                  if (signalsDecodeCorrectly(signalWireLetters, signalsToDecode))
                  {
                    return signalWireLetters;
                  }
                }
              }
            }
          }
        }
      }
    }
    throw new IllegalStateException("Couldn't find a valid signal decode");
  }

  private boolean signalsDecodeCorrectly(final char[] signalWireLetters, final String[] signalsToDecode)
  {
    for (final String signal : signalsToDecode)
    {
      final boolean[] litSegments = decodeSignalToLitSegments(signalWireLetters, signal);
   
      if (!isValidDigit(litSegments))  return false;
    }

    return true;
  }

  private boolean[] decodeSignalToLitSegments(final char[] signalWireLetters, final String signal)
  {
    final boolean[] litSegments = new boolean[7];
    for (final char c : signal.toCharArray())
    {
      switch (c)
      {
        case 'a':
          litSegments[signalWireLetters[0]] = true;
          break;
        case 'b':
          litSegments[signalWireLetters[1]] = true;
          break;
        case 'c':
          litSegments[signalWireLetters[2]] = true;
          break;
        case 'd':
          litSegments[signalWireLetters[3]] = true;
          break;
        case 'e':
          litSegments[signalWireLetters[4]] = true;
          break;
        case 'f':
          litSegments[signalWireLetters[5]] = true;
          break;
        case 'g':
          litSegments[signalWireLetters[6]] = true;
          break;
        default:
          throw new IllegalStateException("Invalid letter: " + c);
      }
    }
    return litSegments;
  }

  // the rest of the code will be in the next post

 

[PHolder]

// In trying to make this post, when I tried to post initially, I was greeted with "Please enter a message with no more than 10000 characters."
// So... I guess I wrote a lot of code!
// this is the second part

SevenSegmentLED class Part two of two

  // the first part of this code is in the previous post

  private boolean isValidDigit(final boolean[] litSegments)
  {
    if (isZeroDigit(litSegments))   return true;
    if (isOneDigit(litSegments))    return true;
    if (isTwoDigit(litSegments))    return true;
    if (isThreeDigit(litSegments))  return true;
    if (isFourDigit(litSegments))   return true;
    if (isFiveDigit(litSegments))   return true;
    if (isSixDigit(litSegments))    return true;
    if (isSevenDigit(litSegments))  return true;
    if (isEightDigit(litSegments))  return true;
    if (isNineDigit(litSegments))   return true;

    return false;
  }

  private boolean isZeroDigit(final boolean[] litSegments)
  {
    if (
         (litSegments[0])  &&
         (litSegments[1])  &&
         (litSegments[2])  &&
         (litSegments[4])  &&
         (litSegments[5])  &&
         (litSegments[6])  &&
         (!litSegments[3])
       ) return true;
    return false;
  }

  private boolean isOneDigit(final boolean[] litSegments)
  {
    if (
         (litSegments[2])  &&
         (litSegments[5])  &&
         (!litSegments[0]) &&
         (!litSegments[1]) &&
         (!litSegments[3]) &&
         (!litSegments[4]) &&
         (!litSegments[6])
       ) return true;
    return false;
  }

  private boolean isTwoDigit(final boolean[] litSegments)
  {
    if (
         (litSegments[0]) &&
         (litSegments[2]) &&
         (litSegments[3]) &&
         (litSegments[4]) &&
         (litSegments[6]) &&
         (!litSegments[1]) &&
         (!litSegments[5])
       ) return true;
    return false;
  }

  private boolean isThreeDigit(final boolean[] litSegments)
  {
    if (
         (litSegments[0])  &&
         (litSegments[2])  &&
         (litSegments[3])  &&
         (litSegments[5])  &&
         (litSegments[6])  &&
         (!litSegments[1]) &&
         (!litSegments[4])
       ) return true;
    return false;
  }

  private boolean isFourDigit(final boolean[] litSegments)
  {
    if (
         (litSegments[1])  &&
         (litSegments[2])  &&
         (litSegments[3])  &&
         (litSegments[5])  &&
         (!litSegments[0]) &&
         (!litSegments[4]) &&
         (!litSegments[6])
       ) return true;
    return false;
  }

  private boolean isFiveDigit(final boolean[] litSegments)
  {
    if (
         (litSegments[0])  &&
         (litSegments[1])  &&
         (litSegments[3])  &&
         (litSegments[5])  &&
         (litSegments[6])  &&
         (!litSegments[2]) &&
         (!litSegments[4])
       ) return true;
    return false;
  }

  private boolean isSixDigit(final boolean[] litSegments)
  {
    if (
         (litSegments[0])  &&
         (litSegments[1])  &&
         (litSegments[3])  &&
         (litSegments[4])  &&
         (litSegments[5])  &&
         (litSegments[6])  &&
         (!litSegments[2])
       ) return true;
    return false;
  }

  private boolean isSevenDigit(final boolean[] litSegments)
  {
    if (
         (litSegments[0])  &&
         (litSegments[2])  &&
         (litSegments[5])  &&
         (!litSegments[1]) &&
         (!litSegments[3]) &&
         (!litSegments[4]) &&
         (!litSegments[6])
       ) return true;
    return false;
  }

  private boolean isEightDigit(final boolean[] litSegments)
  {
    if (
         (litSegments[0]) &&
         (litSegments[1]) &&
         (litSegments[2]) &&
         (litSegments[3]) &&
         (litSegments[4]) &&
         (litSegments[5]) &&
         (litSegments[6])
       ) return true;
    return false;
  }

  private boolean isNineDigit(final boolean[] litSegments)
  {
    if (
         (litSegments[0])  &&
         (litSegments[1])  &&
         (litSegments[2])  &&
         (litSegments[3])  &&
         (litSegments[5])  &&
         (litSegments[6])  &&
         (!litSegments[4])
       ) return true;
    return false;
  }
}

Then the solvers for each of the two parts were smaller:

The solvers for part one and part two

public static long getPart1Answer(final String day08Input, final String[] day08InputLines)
{
  final Pattern p = Pattern.compile("[\\w\\s]+ \\| ([\\w\\s]+)");
  int count = 0;
  for (final String s: day08InputLines)
  {
    final Matcher m = p.matcher(s);
    if (!m.matches())  throw new IllegalStateException("Couldn't parse pattern: " + s);
    final String[] parts = m.group(1).split(" ");
    if (parts.length != 4)  throw new IllegalStateException("Didn't get 4 parts after the | " + m.group(1));
    for (final String part: parts)
    {
      switch(part.length())
      {
        case 2:
        case 3:
        case 4:
        case 7:
          count++;
          break;
        default:  // ignore
      }
    }
  }
  return count;
}

public static long getPart2Answer(final String day08Input, final String[] day08InputLines)
{
  long sum = 0;
  final Pattern p = Pattern.compile("([\\w\\s]+) \\| ([\\w\\s]+)");
  for (final String s: day08InputLines)
  {
    final Matcher m = p.matcher(s);
    if (!m.matches())  throw new IllegalStateException("Couldn't parse pattern: " + s);
    final String[] leftParts = m.group(1).split(" ");
    if (leftParts.length != 10)  throw new IllegalStateException("Didn't get 10 parts before the | " + m.group(1));
    final String[] rightParts = m.group(2).split(" ");
    if (rightParts.length != 4)  throw new IllegalStateException("Didn't get 4 parts after the | " + m.group(1));
    final SevenSegmentLED ssLED = new SevenSegmentLED(leftParts);
    int fourDigits = 0;
    for (final String digitSignals: rightParts)
    {
      fourDigits *= 10;
      fourDigits += ssLED.getDigitFromSignals(digitSignals);
    }
    sum += fourDigits;
  }
  return sum;
}

 

[miquelfire]

Part 1 was a lambda chain, split on the | character (I used split, but only used the part after the |), then split on spaces, filter only the values that are a unique value, then reduce sum the length of the post filter array.

Part 2, I solved the mapping, so the logic was along the lines like this:

The logic I used for my coding

• I have a mapping object, starting with possible values, so the starting string is: abcedfg
• Using the ten values before the pipe, I logic out by process of elimination each segment should be
• So I start by using the segments of 1 (for the one line example, it happens to ab) and set the two right segments to that, then remove those two letters from the others
• I had also grabbed the letters for 7 and during the loop of removing the letters from the others, I removed from 7 as well to find the top value
• I set the top segment to that and remove the letters from the others (except right because it wouldn't be there at this point)
• I get the letters for 4, and calculate which is the middle segment next by removing the segments used by 1, and comparing the final two with to see which of the 6 lit up segment numbers doesn't have one of the two remaining values
• This in turns gives me the top left segment as well
• I then figure out the bottom segment by removing all known segments (even though at this state, the I don't don't which of the two rights are which) by finding the 5 lit segment numbers only has the bottom lit when removing the known segments (Which ever one happens to be 9 will trigger this, the others will have the bottom left lit as well)
• Using those 5 lit segments again, I look for one that would be 5, and use that to know which of the right segments is which. Just needed to avoid 3
• Then I just translate the output and get the number, and add it all up.

 

[Paul F]

I'd like to see a YouTube video of a 7 minute (from the AoC Leaderboard) solution to Parts 1 and 2. It takes me longer than that to read the instructions and follow the example. My first approach to Part 2 was a brute force 'try all permutations of the segments '. It worked, then I decided to look for a better method.
My algorithm for Part 2:
A
B C
D
E F
G
Based on the number of segments we immediately know digits 1, 4, 7, and 8
This leaves 2, 3, and 5 with 5 segments and 0, 6, 9 with 6 segments
From 1 and 7 we can determine segment A
From 1 and 4 we can determine the segment pair BD
For 5-segment digits only 5 has the pair BD
From 2 and 3 we can determine the segment pair EF
We now have segments ABDEF
For 6-segment digits only 6 has ABDEF which then gives us segment G
Knowing ABDG and ABDEFG we can get segment F from 5 and segment C from 8
ABCDFG gives us digit 9 leaving 0 as the last 6-segment digit which then gives us segment B
For 5-segment digits only 3 has ACFG leaving 2 as the remaining digit.

 

[PHolder]

then I decided to look for a better method.

While an intellectual challenge for sure, there seems little benefit to pursuing it, especially if you're at all hurrying to solve quickly. I was assuming such an approach was possible as I was doing the brute force permutations, but I decided it would be far faster to copy and paste nested loops than it would be to try any other approach. I wrote a card game server once, and it needed to check card permutations, so I have that code around here somewhere... but again it would have taken longer to find and integrate it than to do what I did.

I wonder about some of the other days how people solve both parts in 1 and a half minutes... I would really like to see someone doing this... but I feel like if they wrote any code I wouldn't want to see it, as it would have to be unmaintainable garbage to fly out of their fingers that fast. I have heard some people use spreadsheets and whatnot for their answers, rather than even writing any code. I feel pretty sure they're using a REPL and not a compiler, because they wouldn't even have time to declare variables let alone types or make structures/classes or unit tests.