Advent of Code

  • Be sure to checkout “Tips & Tricks”
    Dear Guest Visitor → Once you register and log-in:

    This forum does not automatically send notices of new content. So if, for example, you would like to be notified by mail when Steve posts an update to his blog (or of any other specific activity anywhere else), you need to tell the system what to “Watch” for you. Please checkout the “Tips & Tricks” page for details about that... and other tips!

    /Steve.
  • Larger Font Styles
    Guest:

    Just a quick heads-up that I've implemented larger font variants of our forum's light and dark page styles. You can select the style of your choice by scrolling to the footer of any page here. This might be more comfortable (it is for me) for those with high-resolution displays where the standard fonts, while permitting a lot of text to fit on the screen, might be uncomfortably small.

    (You can permanently dismiss this notification with the “X” at the upper right.)

    /Steve.

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
Day 15 is a bizarre sequence of numbers in the form of an Elf game. I don’t see any way to not brute force this one, even though the part 2 number of round is in the many millions. I added some output every 200k or so rounds to make sure my code hadn’t crashed and that it was going to run fast enough to get an answer in reasonable time… it seemed like it would, so I let it go.

Here’s the main structure, nothing interesting to see here, I don’t think:

Java:
private static final int[] startingInput = {2,0,... more numbers removed as I assume my input was unique};

public static void main(final String[] args)
{
  final ElfGame eg = new ElfGame(startingInput);
  final int part1 = eg.playGameUntilRound(2020);
  System.out.println("Part 1: " + part1);
  final int part2 = eg.playGameUntilRound(I don't know if my round number is unique, so eliminated);
  System.out.println("Part 2: " + part2);
}

The most interesting part is how to implement the rules in some semi sane way. I could have tried an array, but that would have had to be arbitrarily large because the numbers keep growing. Instead I decided to use a set of hashmaps. I’m not sure there is much better of a way to do this, maybe a tree or something.

Anyway, this is what I ended up doing:

Java:
final class ElfGame
{
  private int currentRound;
  private int lastNumberSpoken;
  private Map<Integer,Integer> valueAtRound = new HashMap<>();
  private Map<Integer,Integer> numberOfTimesSpoken = new HashMap<>();
  private Map<Integer,Integer> previouslySpoken = new HashMap<>();

…

  public void playRound()
  {
    currentRound++;
    final int nextNumber;
    if (getNumberOfTimesSpoken(lastNumberSpoken) == 1)
    {
      nextNumber = 0;
    }
    else
    {
      int prevRoundSpoken = getPreviousRoundSpoken(lastNumberSpoken);
      nextNumber = currentRound - prevRoundSpoken - 1;
    }

    updatePreviouslySpoken(nextNumber);
    valueAtRound.put(nextNumber, currentRound);
    numberOfTimesSpoken.put(nextNumber, numberOfTimesSpoken.getOrDefault(nextNumber, 0)+1);
    lastNumberSpoken = nextNumber;
  }
 

Paul F

Member
Sep 17, 2020
23
11
Toronto
Day 15 is a bizarre sequence of numbers in the form of an Elf game.
Those elves could memorize PI to 30, 000, 000 digits.
I figured the numbers might approach 30M but wouldn't exceed it, so I made an 30M element integer array where Array[n] contains the previous position of the number n, and is initialize with the numbers given in the puzzle. Then I had one big loop to keep track of numbers and position while updating the array. In C language and on an average PC it did all 30M in about a second. There were about 3.6M unique numbers, so it's a fairly sparse array.
 
Last edited:

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
And day 16 was a challenge to find the “right” solution for part 2. It is basically teaching your computer to play that matching game “Mastermind”:

Mastermind (board game)
Mastermind or Master Mind is a code-breaking game for two players. The modern game with pegs was invented in 1970 by Mordecai Meirowitz, an Israeli postmaster and telecommunications expert. It resembles an earlier pencil and paper game called Bulls and Cows that may date back a century. The game is played using: The two players decide in advance how many games they will play, which must be an even number. One player becomes the codemaker, the other the codebreaker. ...


For part one, my approach was to combine all the various rules into one rule with valid numbers for any rule. This way you could quickly cycle through all the tickets and find any number that was not valid for at least one field somewhere, and adding it to the sum. Any ticket that had no bad numbers is collected for part 2.

For part 2, you need to do a process of elimination. I took a couple of different straightforward iterative approaches at first, but that won’t work because some rules have multiple possible matches. What I ended up doing was putting all possible rules into a pool, finding any rules with only one valid match, then removing that match from the pool, and repeating until the pool was empty.

I’ll be honest that I didn’t initially use any unit testing, and put a lot of my code in main() to start. I got lucky, I guess, and everything worked right the first time, I didn’t need to refer back to the supplied example. Since finishing part2 I’ve refactored my code and added unit tests.

After much refactoring and unit testing, I have a main() that I like:

Java:
final Ticket myTicket = new Ticket(new int[] {127,83,rest of my unique input deleted});

final NumberRulesReader nrr = new FileNumberRulesReader(FILE);
final NearbyTicketReader ntr = new FileNearbyTicketReader(FILE);

final NumberRulesList nrl = new NumberRulesList();
nrl.readRules(nrr);

final ValidTicketList vtl = new ValidTicketList(nrl);
vtl.addTicket(myTicket);

final int sum = vtl.readTicketsAddValidAndSumInvalidFields(ntr);
System.out.println("Part 1: " + sum);
System.out.format("%d valid tickets (including mine)%n", vtl.getSize());

final TicketFieldNames tfn = TicketFieldNames.resolve(nrl, vtl);
final int[] part2Vals = myTicket.getAllFieldsWhosNameStartWith("departure", tfn);
long part2=part2Vals[0];
for(int i=1; i<part2Vals.length; i++) part2*=part2Vals[i];
System.out.println("Part 2: " + part2);

The tricky bit from that, for part 2, is in TicketFieldNames.resolve() :
Java:
final Map<String, Integer> fieldNameToNumberMapping = new HashMap<>();
final Set<NumberRules> rulesYetMatched = new HashSet<>(nrl.getRules());
while (!rulesYetMatched.isEmpty())
{
  for (int i=0; i<nrl.getSize(); i++)
  {
    final Set<Integer> allNumbersFromAllTickets = getAllNumbersAtIndexFromAllTickets(vtl, i);
    final List<NumberRules> matchedRules = findAnyRulesThatWorkWithAllNumbers(rulesYetMatched, allNumbersFromAllTickets);
    if (matchedRules.size() == 1)
    {
      final NumberRules matched = matchedRules.get(0);
      fieldNameToNumberMapping.put(matched.getName(), i);
      rulesYetMatched.remove(matched);
    }
  }
}
 

Steve

(as in GRC)
Staff member
Feb 1, 2019
354
1
908
66
Southern CA, USA
www.grc.com
The site is very simple, but fairly advanced. It generates unique inputs for each user, so you can't submit someone else's results as your own. Also, don't assume these are easy-peasy little challenges... Some of them will be fairly straightforward, and some of them will be anything but. I did some of the challenges from last year (after the fact, because that was when I first learned about it) but stopped when I got completely stumped on a maze walking challenge and wasted a couple of days on it without progress.

I think you can still go back and do past years challenges if you want... Here's the maze one I found stumping https://adventofcode.com/2019/day/18 (warning that if you want to do all them in order, they will form a story. Additionally, some of the challenges from 2019 had you building a special virtual machine IntCode parser and you will probably have to solve those problems in order as they build on each other.)

Here's a post about last years progression live as it happened (and then eventually stopped happening) https://www.twit.community/t/advent-of-code-2019/4362/1

BOY that sounds like the best thing I've ever heard of. Someday!! What a PERFECT way to spend retirement and keep sharp and challenged!
 

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
Well the game of life in multiple dimensions made a showing for day 17. Luckily for me, I chose to make my own representation of the data because the problem defined it as "The pocket dimension contains an infinite 3-dimensional grid." I knew it wouldn't really be infinite, obviously, but I also saw negative dimensions in the examples, and I just didn't want to deal with all that. My choice was very lucky, because part 2 was mostly a very straight forward copy/paste and slight rework of my new classes.

Here's my main:
Java:
private static final String INITIAL_STATE =
"""
#.#.#.##
// removed the middle of my personalized input
#.##..##         
""";

  public static void main(final String[] args)
  {
    final TwoDimensionalPlane initialState = new TwoDimensionalPlane();
    initialState.loadFrom(INITIAL_STATE);

    ThreeDimensionalSpace cube = new ThreeDimensionalSpace();
    cube.loadFrom(initialState);
    for (int i=1; i<=6; i++)
    {
      cube = CubeEvolver.evolve(cube);
    }
    System.out.println("Part 1: " + cube.getNumberOfOccupiedCoordinates());

    FourDimensionalSpace cube4d = new FourDimensionalSpace();
    cube4d.loadFrom(initialState);
    for (int i=1; i<=6; i++)
    {
      cube4d = CubeEvolver.evolve(cube4d);
    }
    System.out.println("Part 2: " + cube4d.getNumberOfOccupiedCoordinates());
  }
 

Paul F

Member
Sep 17, 2020
23
11
Toronto
Day 17: What's interesting about this puzzle is that it shows how easy it is to move from 3 dimensions to 4 dimensions in math and how difficult it is to visualize geometrically. But I'll give it a try. Start with a line 1 unit in length in 1 dimension. Repeat the line in the same direction to make 3 line segments. The middle one has 2 (3-1)neighbours. Next extend the 3 segment line 1 unit in a 2nd dimension to make 3 squares. Repeat to make 9 squares (like tic-tac-toe). The middle square has 8 (9-1) neighbours. Then extend the squares 1 unit in a 3rd dimension to make 9 cubes. Repeat to make 27 cubes (like a Rubik's cube). The middle cube has 26 (27-1) neighbours. Finally extend the cubes 1 unit in a 4th dimension to make 27 tesseracts. Repeat to make 81 tesseracts. A 3-D exploded view of this can been seen here:
The diagram shows 3 sets of 27 tesseracts with quite a bit of superposition in the centre . A square is made from 4 lines, a cube is made from 6 squares, and a tesseract is made from 8 cubes. In the diagram 6 cubes in a shell and 2 superimposed cubes in the centre form a tesseract. The tesseract in the very centre is surrounded by 3 superimposed groups of 26 tesseracts plus 2 that superimpose it for a total of 80 (also 81-1). A single rotating tesseract can be seen here:
https://upload.wikimedia.org/wikipedia/commons/5/55/Tesseract.gif. You can see the 8 cubes.
 
  • Like
Reactions: hyperbole

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
Day 18 was a struggle for me. It’s all about parsing some math with strange precedence rules. I could have gone the long way and used something like Antlr to throw together an actual parser with the correct precedence rules baked in… and considering how long I wasted on this, maybe that’s what I should have actually done!

In any case after a number of false starts, I found a way to do part one with iteration. I didn’t expect the result to be so large, so I had to go back and rework for that. (AoC is probably the only time I have every used long instead of int… can’t imagine where else I would ever encounter such huge numbers.)
I can post my main without a spoiler, because this is very boring code that gives away nothing that isn’t totally obvious:

Java:
public static void main(final String[] args)
{
  final MathExpressionReader reader = new MathExpressionFileReader(FILE);
  long sum1 = 0;
  long sum2 = 0;
  int numberOfExpressions = 0;
  while (reader.isMoreInput())
  {
    final String mathExpression = reader.getNextMathExpression();
    sum1 += MathExpressionComputer.compute(mathExpression);
    sum2 += MathExpressionComputer.compute2(mathExpression);
    numberOfExpressions++;
  }
  System.out.println("Number of math expressions: " + numberOfExpressions);
  System.out.println("Part 1: " + sum1);
  System.out.println("Part 2: " + sum2);
}

The “magic” is what to put in the compute() and compute2() methods.
My compute() method is just a wrapper to get ride of the pesky spaces, nothing interesting to see here either:

Java:
// eliminate pesky spaces
public static long compute(final String mathExpression)
{
  final String expr = mathExpression.replaceAll(" ", "");
  return _compute(expr);
}

but the compute() method itself, is a little tricky and icky:

Java:
private static long _compute(final String expr)
{
  long curVal=0;
  int curOp='+';
  int i=0;
  while(i<expr.length())
  {
    long num = 0;
    if (expr.charAt(i)=='(')
    {
      int bracket=0;
      for(int j=i; j<expr.length(); j++)
      {
        if (expr.charAt(j)=='(') bracket++;
        if (expr.charAt(j)==')') bracket--;
        if (bracket==0)
        {
          final String subExpr = expr.substring(i+1, j);
          num = _compute(subExpr);
          i=j+1;
          break;
        }
      }
    }
    else
    {
      num=expr.charAt(i)-'0';
      i++;
    }

    switch(curOp)
    {
      case '+':
      {
        curVal=curVal+num;
      }
      break;

      case '*':
      {
        curVal=curVal*num;
      }
      break;
    }

    if (i<expr.length())
    {
      curOp = expr.charAt(i);
      i++;
    }
    else
    {
      return curVal;
    }
  }
  return curVal;
}

I couldn’t find an easy way to massage that into the part 2 answer, although I tried a half dozen different approaches before deciding I needed to just make a hand made recursive parser.
Java:
// This eliminates all expressions in brackets, replacing them with their computed value
private static long _compute2(final String expr)
{
  String modExpr = expr;
  while (modExpr.contains("("))
  {
    int b1 = -1;
    int b2 = -1;
    int bc = 0;
    for (int i=0; i<modExpr.length(); i++)
    {
      final char c = modExpr.charAt(i);
      if (c=='(')
      {
        if (b1<0) b1=i;
        bc++;
      }
      if (c==')')
      {
        bc--;
        if (bc == 0)
        {
          b2=i;
          break;
        }
      }
    }
    final String before = modExpr.substring(0,b1);
    final String bracedExpr = modExpr.substring(b1+1,b2);
    final String after = modExpr.substring(b2+1);
    modExpr = before + _compute2(bracedExpr) + after;
  }
  return _calc2a(modExpr);
}

Java:
// This makes sure that multiplication happens after addition because of the strange precedence rules
private static long _calc2a(final String expr)
{
  if (expr.contains("*"))
  {
    int m1 = -1;
    for (int i=0; i<expr.length(); i++)
    {
      final char c = expr.charAt(i);
      if (c=='*')
      {
        m1=i;
        break;
      }
    }
    final String before = expr.substring(0,m1);
    final String after = expr.substring(m1+1);
    return _calc2b(before) * _calc2a(after);
  }
  return _calc2b(expr);
}

Java:
// This is a simplification of part 1 but one that can parse multidigit numbers
private static long _calc2b(final String expr)
{
  long curVal=0;
  int i=0;
  while(i<expr.length())
  {
    long num=0;
    while (i<expr.length() && isdigit(expr.charAt(i)))
    {
      num=num*10 + (expr.charAt(i)-'0');
      i++;
    }

    curVal=curVal+num;

    if (i<expr.length())
    {
      i++;
    }
    else
    {
      return curVal;
    }
  }
  return curVal;
}

I in no way commend my approach to anyone, but it did work well for me in the end, after spending 5 hours more than I should have banging my head trying wrong approaches.
 
  • Like
Reactions: Barry Wallis

Paul F

Member
Sep 17, 2020
23
11
Toronto
Day 18 was a struggle for me. It’s all about parsing some math with strange precedence rules.
...
I in no way commend my approach to anyone, but it did work well for me in the end, after spending 5 hours more than I should have banging my head trying wrong approaches.
Day 18 was a lot of work for me too. It was interesting enough that didn't mind spending a lot of time on it.
For part 1 I used a recursive evaluator that looked for left operand - operator - right operand, and recursed if an operand was in parentheses.
For part 2, instead of writing another evaluator, I thought it would be interesting to try inserting parentheses into the expressions to explicitly give priority to '+' over '*' so I could used my evaluator from part 1. That wasn't as easy as I thought it would be and it ended up putting extra parentheses where they weren't needed. Unfortunately my evaluator choked on the extra parentheses and I had to go back and modify it.
 
Last edited:
  • Like
Reactions: Barry Wallis

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
I thought it would be interesting to try inserting parentheses into the expressions to explicitly give priority to '+' over '*'

I tried your approach too. In fact I spent a good hour getting it really close to working, but it couldn't handle things like 5+4+3+2*... I was trying to be iterative rather than recursive, and I wanted to output the updated formula all in one go. Once I realized I couldn't succeed in one pass, I realized another approach would be easier to write and debug.
 

Paul F

Member
Sep 17, 2020
23
11
Toronto
I tried your approach too ... I was trying to be iterative rather than recursive ... in one pass ...
My approach is almost one-pass. I scan left to right. When I find a '+' I work backwards to put a '(' then forwards to put a ')'. It's very crude but gets the job done for the puzzle.
 

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
OMG!! I ranked in the top 1000 for day 19:
That’s the right answer! You are one gold star closer to saving your vacation. You got rank 945 on this star’s leaderboard.
It was an interesting challenge, which I solved in a very interesting (and potentially unusual) way.

The part 2 twist is really twisted, too. He pretty much tells you you’ll have to do something specific to the problem as the general approach would require way too much work.

The presumed logical approach to dealing with this problem would be a state machine… you have states you enter into and leave via rule numbers. And with some back tracking (read recursion) you could probably get that approach to work for part 1. I thought of that before deciding my approach, and that is basically what regex does for you… it builds a state machine with backtracking support. So I figure I would have my code translate the rules into a regex string and let the regex pattern matcher do all the work. That worked great for part 1, here’s a sample of the output:

Number of rules: 130
regexStr: (a((b(a((a(ba|ab)|b(bb|aa))b|(a(aa|b(a|b))|bba)a)|b((bab|(a(a|b)|ba)a)b|(baa|(aa|ba)b)a)) … very truncated
Number of messages: 458

Part 2 throws in a serious twist thou… the expressions can now be self-referential… My approach for this was kind of ugly, but it allowed me to trap out the changes needed without having to rewrite all my code:

Java:
private void _buildRecursive(final StringBuilder sb, final int ruleNumber)
{
  if (inRule2Mode)
  {
    if (ruleNumber == 8)
    {
      handlePart2Rule8(sb);
      return;
    }
    if (ruleNumber == 11)
    {
      handlePart2Rule11(sb);
      return;
    }
  }

then all I had to do was figure out what changes to make to handle the two new rules. For one, it would match inputs like a, aa, aaa, aaaa, aaaaa, and so on, so a simple (a+) matches one more more a’s. For the second one, that was harder. Here you want to match patterns where there are the same number of a’s as b’s like: ab aabb aaabbb aaaabbbb and so on. General regex is not well equipped for this, you can say a+b+ but that would match a different number of a’s and b’s. (I did try to cheat with this approach, but I generated a wrong (too high) number, and also got the warning about how it interestingly matched someone else’s answer.)

The only way I could think to handle this in regex was to make pretty long set of specific rules specifying the numbers. So I generated a regex containing (ab|a{2}b{2}|a{3}b{3}|a{4}b{4}|a{5}b{5}| … and had to decide how high to go. I stopped at 20, which was apparently enough for this problem.

Here’s my main code:

Java:
final RuleWrangler rw = new RuleWrangler();

final RuleReader rr = new FileRuleReader(FILE);
int numberOfRules = 0;
while (rr.isMoreInput())
{
  final String rule = rr.getNextRule();
  numberOfRules++;
  rw.addRule(rule);
}
System.out.println("Number of rules: " + numberOfRules);

final Pattern p1 = rw.getMasterPattern(0);
final MessageReader mr = new FileMessageReader(FILE);
int numberOfMessages = 0;
int numberOfValidMessages = 0;
while (mr.isMoreInput())
{
  final String message = mr.getNextMessage();
  numberOfMessages++;
  final Matcher m = p1.matcher(message);
  if (m.matches()) numberOfValidMessages++;
}
System.out.println("Number of messages: " + numberOfMessages);
System.out.println("Part 1: " + numberOfValidMessages);

rw.toggleToPart2Mode();
final Pattern p2 = rw.getMasterPattern(0);
final MessageReader mr2 = new FileMessageReader(FILE);
int numberOfValidMessages2 = 0;
while (mr2.isMoreInput())
{
  final String message = mr2.getNextMessage();
  final Matcher m = p2.matcher(message);
  if (m.matches()) numberOfValidMessages2++;
}
System.out.println("Part 2: " + numberOfValidMessages2);
 
Last edited:

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
Yowza Day 20 was a lot of work and I had some insidious bugs while getting it done. I don’t know if there is much implementation spoilers on this one, it’s just a lot of work. I guess I did use a trick to save some effort on the map matching/assembly.

What I did was convert the map edges to binary. I stored resulting 10 bit numbers in a HashMap so I could find the map with that specific edge quickly. There should only be a matching set of two edges with the “correct” values, and the corners are easier to find this way also. When building my map, I tried each of the four identified corners in each of the 8 possible orientations for loctation 0,0 and the solved for the rest of the map with that. The bug I had, and that took me a long time to figure out, is that the map pieces that abut each other don’t have the same binary value, you need to flip the bits end for end on one because they fit together when they’re mirrored. After I got that bug squashed, the map was solved in seconds and I could start on the next phase of hunting sea monsters.

I also had a bug in my monster hunter. It was finding them, but wasn’t breaking out of the loop properly when it did, so it reported none found :( I must have been getting pretty tired by then, but I finally got a clue and decided to input his provided example as a unit test and I needed the debugger to see my stupidity.

Nearly 7 and a half hours and I came in 2000th or so… pity those poor people still struggling on this long one.

Here’s my main:
Java:
final TileMatcher tm = new TileMatcher(12,12);
final TileReader tr = new TileFileReader(FILE);
int numberOfTiles = 0;
while (tr.isMoreInput())
{
  final Tile t = tr.getNextTile();
  tm.addTile(t);
  numberOfTiles++;
}
System.out.println("Number of tiles: " + numberOfTiles);
final Set<Integer> corners = tm.findCornerTiles();
long part1 = 1;
for (final int tileNumber : corners)
{
  part1 *= tileNumber;
}
System.out.println("Part 1: " + part1);

tm.buildMap();
final MonsterMap mm = new MonsterMap(12*8, 12*8);
tm.populateMonsterMap(mm);
mm.findAndHighlightSeaMonsters();
mm.dumpMap();
final int part2 = mm.countChar('#');
System.out.println("Part 2: " + part2);
 
  • Like
Reactions: Barry Wallis

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
Day 21… and it took me a bit to even understand the problem. Then it took me an even longer time to understand the example answer. Then it took me even longer to figure out how the answer was produced.

Spoiler: it’s a process of elimination, so you’ll need a loop along the lines of:

Code:
somethingWasEliminated=true;
while(somethingWasEliminated)
{
  somethingWasEliminated=false;
  ...
  if (condition) somethingWasEliminated=true;
}

Here’s a good portion of the method that does the part 1 work, the comments explain the process a bit, I think:

Java:
public int resolveAllergens()
{
  boolean madeAnEntry = true;
  // keep making passes until we have eliminated all we can
  while (madeAnEntry)
  {
    madeAnEntry = false;
    for (final Allergen a : Allergen.getAllAllergens())
    {
      // Find all foods that list this allergen
      final Set<FoodItem> foodItemsWithAllergen = allergenToFoodItemMapping.get(a);
      // find any ingredient(s) in common with all those foods
      final Set<Ingredient> ingredientsInCommon = getIngredientsInCommon(foodItemsWithAllergen);
      // One of the ingredients in common MUST be the allergen
      // See if any of the ingredients are already known to be another allergen
      final Set<Ingredient> ingredientsNotEliminated = new HashSet<>();
      for (final Ingredient i : ingredientsInCommon)
      {
        if (!mappingOfIngredientToAllergen.containsKey(i))
        {
          ingredientsNotEliminated.add(i);
        }
      }
      if (ingredientsNotEliminated.size() == 1)
      {
        // this must be the allergen
        for (final Ingredient i: ingredientsNotEliminated)
        {
          mappingOfIngredientToAllergen.put(i, a);
        }
        madeAnEntry = true;
      }
    }
  }

  final Set<Ingredient> ingredientsNotEliminated = new HashSet<>();
  for (final FoodItem fi: foodItemList)
  {
    for (final Ingredient i : fi.getIngredientList())
    {
      if (!mappingOfIngredientToAllergen.containsKey(i))
      {
        ingredientsNotEliminated.add(i);
      }
    }
  }

Part 2 wasn’t much of a challenge for me, because I collected the necessary data to answer part 1, so just had to restructure and sort that data to generate the answer for part 2.

Here’s my main method:

Java:
final Food food = new Food();
final FoodItemReader fir = new FoodItemReader(FILE);
while (fir.isMoreInput())
{
  final FoodItem fi = fir.getNextFoodItem();
  food.addItem(fi);
}
System.out.println("Number of food items: " + food.getNumberOfFoodItems());
System.out.println("Number of unique ingredients: " + Ingredient.getNumberOfUniqueIngredients());
System.out.println("Number of unique allergens: " + Allergen.getNumberOfUniqueAllergens());
final int part1 = food.resolveAllergens();
System.out.println("Part 1: " + part1);
final String part2 = food.getDangerousIngredients();
System.out.println("Part 2: " + part2);
 
  • Like
Reactions: Barry Wallis

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
For Day 22, part 1 is mostly just brute force coding. If you already had “Decks” ready to do the types of things needed, or if your language makes it easy to manage lists of numbers, then part 1 should be easy.

Here’s the key code for part 1:
Java:
public Hand playToEnd()
{
  while (hand1.getNumberOfCards()>0 && hand2.getNumberOfCards()>0)
  {
    final int p1c = hand1.getTopCard();
    final int p2c = hand2.getTopCard();
    if (p1c > p2c)
    {
      hand1.putOnBottom(p1c);
      hand1.putOnBottom(p2c);
    }
    else
    {
      hand2.putOnBottom(p2c);
      hand2.putOnBottom(p1c);
    }
  }

  return returnWinner();
}

Part 2 is a little more tricky. Part of it is just understanding precisely what is being asked. You should pay particular attention to the previous hand detection because the small example (unit test) given does not contain an example of this. My first attempted part 2 answer misunderstood what was expected for this previous hand detection. Also, the previous hand detection will be the slowest part of the code, so you should find a good approach or be prepared to wait, my input went for over 25000 games (of multiple rounds, all of which ended up in the previous hand detector.)

Here’s my code for part 2:
Java:
private static int _recurse(final Hand hand1, final Hand hand2, final Set<String> previousHands)
{
  while (hand1.getNumberOfCards()>0 && hand2.getNumberOfCards()>0)
  {
    if (isPreviousHand(previousHands, hand1, hand2))
    {
      return 1;
    }

    final int p1c = hand1.getTopCard();
    final int p2c = hand2.getTopCard();
    int p1nc = hand1.getNumberOfCards();
    int p2nc = hand2.getNumberOfCards();

    if ((p1nc>=p1c) && (p2nc>=p2c))
    {
      final int roundWinner = makeHandAndRecurse(p1c, p2c, hand1, hand2);
      doWinner(roundWinner, hand1, hand2, p1c, p2c);
    }
    else if (p1c > p2c)
    {
      doWinner(1, hand1, hand2, p1c, p2c);
    }
    else
    {
      doWinner(2, hand1, hand2, p1c, p2c);
    }
  }
  if (hand1.getNumberOfCards() == 0) return 2;
  return 1;
}

private static int makeHandAndRecurse(final int p1nc, final int p2nc, final Hand hand1in, final Hand hand2in)
{
  final Set<String> previousHands = new HashSet<>();
  final Hand newHand1 = hand1in.newSubHand(p1nc);
  final Hand newHand2 = hand2in.newSubHand(p2nc);
  return _recurse(newHand1, newHand2, previousHands);
}

And of course some main code:
Java:
// I chose to just copy the supplied input into String arrays in my main code
final Hand hand1 = new Hand(HAND1);
final Hand hand2 = new Hand(HAND2);
final Game game = new Game(hand1,hand2);
final Hand winningHand = game.playToEnd();
final long part1 = winningHand.calculateHandSum();
System.out.println("Part 1: " + part1);

final Hand hand1b = new Hand(HAND1);
final Hand hand2b = new Hand(HAND2);
final Game game2 = new Game(hand1b,hand2b);
final Hand winningHand2 = game2.recursivePlayToEnd();
final long part2 = winningHand2.calculateHandSum();
winningHand2.dump();
System.out.println("Part 2: " + part2);
 
  • Like
Reactions: Barry Wallis

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
Day 23… getting near the end. The trick with this one is to not implement the solution they way you’re going to instinctively want to do so. If you read the instructions in the right way, he kind of gives you a hint on an approach to take. Especially when he says to start at the next number after 1. He’s hinting that you need an arrangement that lets you easily connect the numbers so you can find them, but can also easily change what they connect to.

I initially did it the “wrong way” for part 1, and it worked fine (after a little debugging to eliminate a one off.) Although this won’t help you for part 2, here is the “wrong way” to do part 1:

Java:
public void playRounds(final int numberOfRounds)
{
  final int[] pickedup = new int[3];
  for (int i=0; i<numberOfRounds; i++)
  {
    pickedup[0]=cups[(currentCupPos+1)%cups.length];
    pickedup[1]=cups[(currentCupPos+2)%cups.length];
    pickedup[2]=cups[(currentCupPos+3)%cups.length];

    int destination=cups[currentCupPos]-1;
    if (destination <1) destination = cups.length;
    while(destination==pickedup[0] || destination==pickedup[1] || destination==pickedup[2])
    {
      destination--;
      if (destination <1) destination = cups.length;
    }
    int destLocation=-1;
    int j=(currentCupPos+4)%cups.length;
    while (destLocation<0)
    {
      if (cups[j] == destination)
        destLocation=(j+1)%cups.length;
      else
        j=(j+1)%cups.length;
    }
    int to=(currentCupPos+1)%cups.length;
    int from=(currentCupPos+4)%cups.length;
    while (from != destLocation)
    {
      cups[to]=cups[from];
      to=(to+1)%cups.length;
      from=(from+1)%cups.length;
    }
    cups[(to)%cups.length]=pickedup[0];
    cups[(to+1)%cups.length]=pickedup[1];
    cups[(to+2)%cups.length]=pickedup[2];
    currentCupPos=(currentCupPos+1)%cups.length;
  }
}

This won’t work for part 2 because it involves too much linear searching and moving of data for that many rounds. You need a design that can eliminate most of that overhead. You could use a linked list easily, except that finding a specific element in the linked list is still going to be slow. Instead I used a HashMap and the key is a cup and the value is the next cup (the cup beside it.) This way you can pull out three cups and rejoin the loop, and then quickly find the destination to hook them back in. Each iteration you’re only updating a couple of pointers and doing a 5 or so hash table lookups.

Here’s the code for part 2, and interestingly it’s shorter and simpler (in a way) that the code above for part 1:

Java:
public void playRounds2(final int numberOfRounds)
{
  final int[] pickedup = new int[3];
  for(int i=0; i<cups.length-1; i++)
  {
    nextNumber.put(cups[i], cups[i+1]);
  }
  prevValue = cups[cups.length-1];
  nextNumber.put(prevValue, cups[0]);

  for (int i=0; i<numberOfRounds; i++)
  {
    if (i%1_000_000==0)System.out.format("Round #%,d%n",i);
    int nextPrev = nextNumber.get(prevValue);
    pickedup[0]=nextNumber.get(nextPrev);
    pickedup[1]=nextNumber.get(pickedup[0]);
    pickedup[2]=nextNumber.get(pickedup[1]);

    int destination=nextNumber.get(prevValue)-1;
    nextNumber.put(nextNumber.get(prevValue), nextNumber.get(pickedup[2]));
    prevValue = nextPrev;

    if (destination <1) destination = cups.length;
    while(destination==pickedup[0] || destination==pickedup[1] || destination==pickedup[2])
    {
      destination--;
      if (destination <1) destination = cups.length;
    }
    int hold=nextNumber.get(destination);
    nextNumber.put(destination, pickedup[0]);
    nextNumber.put(pickedup[2], hold);
  }
}

Using this code, getting the part 2 answer is just a couple of lines of code. Here’s the main:

Java:
// cups is a hard coded int[] with the supplied input
public static void main(final String[] args)
{
  final CupGame game = new CupGame(cups);
  game.playRounds(100);
  final String part1 = game.collectResult();
  System.out.println("Part 1: " + part1);

  final int[] newCups = makeNewCups(cups, 1_000_000);
  final CupGame game2 = new CupGame(newCups);
  game2.playRounds2(10_000_000);
  final long part2 = game2.collectPart2Result();
  System.out.println("Part 2: " + part2);
}

private static int[] makeNewCups(final int[] firstCups, final int numberOfCups)
{
  final int[] newCups = new int[numberOfCups];
  for (int i=0; i<firstCups.length; i++)
  {
    newCups[i]=firstCups[i];
  }
  for (int i=firstCups.length; i<numberOfCups; i++)
  {
    newCups[i]=i+1;
  }
  return newCups;
}

EDIT: Someone suggested an approach that would be faster, just using arrays. Here's that code:

Java:
// Using an array named nextNumberArray of cups.length+1 (not using the zeroth element)
public void playRounds3(final int numberOfRounds)
{
  final int[] pickedup = new int[3];
  for(int i=0; i<cups.length-1; i++)
  {
    nextNumberArray[cups[i]] = cups[i+1];
  }
  prevValue = cups[cups.length-1];
  nextNumberArray[prevValue] = cups[0];

  for (int i=0; i<numberOfRounds; i++)
  {
    if (i%1_000_000==0)System.out.format("Round #%,d%n",i);
    int nextPrev = nextNumberArray[prevValue];
    pickedup[0]=nextNumberArray[nextPrev];
    pickedup[1]=nextNumberArray[pickedup[0]];
    pickedup[2]=nextNumberArray[pickedup[1]];
         
    int destination=nextNumberArray[prevValue]-1;
    nextNumberArray[nextNumberArray[prevValue]] = nextNumberArray[pickedup[2]];
    prevValue = nextPrev;
         
    if (destination <1)  destination = cups.length;
    while(destination==pickedup[0] || destination==pickedup[1] || destination==pickedup[2])
    {
      destination--;
      if (destination <1)  destination = cups.length;
    }
    int hold=nextNumberArray[destination];
    nextNumberArray[destination]= pickedup[0];
    nextNumberArray[pickedup[2]] = hold;
  }
}
 
Last edited:
  • Like
Reactions: Barry Wallis

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
Penultimate day… Day 24. Game of life on hex tiles. I spent way too much time debugging a stupid bug… my reader was skipping the first input line and adding a blank line. This gave me the correct number for part 1 but made part 2 not work right. (A blank line was interpreted as a black tile at 0,0 :( )

The trick here is how to represent hex tiles. This is “common” in hex tile based games, so you may need to learn the co-ordinate system. There are two general ways to orient the tiles, one with the points facing north/south and one with them facing east/west. The tiles in the problem set are point facing north/south. Accordingly when navigating east/west along tiles, x needs to increase or decrease by 2. For the other four directions, x and y will increase or decrease by 1. This site may be useful https://www.redblobgames.com/grids/hexagons/

Here’s the tile path calculation code:

Java:
public static TileAddress convertTilePathToAddress(final String tilePath)
{
  int x = 0;
  int y = 0;
  int i = 0;
  while (i < tilePath.length())
  {
    final char c1 = tilePath.charAt(i++);
    if ((c1 == 'n') || (c1 == 's'))
    {
      final char c2 = tilePath.charAt(i++);
      if (c1 == 'n')
      {
        y--;
        if (c2 == 'w')
        {
          x--;
        }
        else if (c2 == 'e')
        {
          x++;
        }
        else throw new IllegalStateException();
      }
      else if (c1 == 's')
      {
        y++;
        if (c2 == 'w')
        {
          x--;
        }
        else if (c2 == 'e')
        {
          x++;
        }
        else throw new IllegalStateException();
      }
      else throw new IllegalStateException();
    }
    else
    {
      if (c1 == 'w')
      {
        x -= 2;
      }
      else if (c1 == 'e')
      {
        x += 2;
      }
      else throw new IllegalStateException();
    }
  }
  return new TileAddress(x, y);
}

For part 2, it’s just the normal game of life semantics. There are a number of ways to represent the “infinite” tiles (that aren’t actually infinite, of course, as as you’ve done a game of line of an infinite space previously in this years problems (day 11) there is not much new to add here.

Here’s my main code:

Java:
final TilePathReader tpr = new TilePathReader(FILE);
final TileTracker tt = new TileTracker();
while(tpr.isMoreInput())
{
  final String tilePath = tpr.getNextTilePath();
  final TileAddress ta = TileAddress.convertTilePathToAddress(tilePath);
  tt.flipTileAtAddress(ta);
}
final int part1 = tt.getNumberOfBlackTiles();
System.out.println("Part 1: " + part1);

tt.flipTilesForDays(100);
final int part2 = tt.getNumberOfBlackTiles();
System.out.println("Part 2: " + part2);
 

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
Yay, all 25 days done, and all 50 stars collected. Merry Christmas Everyone!
Some more modular math… The RFID cards doing Diffie-Hellman-Merkle https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange

Here’s my main:

Java:
private static final long v1 = __INPUT#1_not_shown__;
private static final long v2 = __INPUT#2_not_shown__;

public static void main(final String[] args)
{
  final int loopSize1 = LoopFinder.findLoop(1, 7, 20201227, v1);
  System.out.println(loopSize1);
  final int loopSize2 = LoopFinder.findLoop(1, 7, 20201227, v2);
  System.out.println(loopSize2);
  final long key1 = LoopFinder.findKey(1, v1, loopSize2, 20201227);
  System.out.println(key1);
  final long key2 = LoopFinder.findKey(1, v2, loopSize1, 20201227);
  System.out.println(key2);
}
 
  • Love
Reactions: Barry Wallis

Paul F

Member
Sep 17, 2020
23
11
Toronto
I fell behind for about a week but managed to catch up and finish before New Year's. I'm not a fast programmer and not about to win any speed records. I'm more interested in taking my time and just enjoying the programming. It is, however, annoying when you miss something that you later realize was obvious.

Ironically, Day 19 which @PHolder excelled at, was the one I had the most difficulty with. First of all I only knew of regular expressions by name. I've had no experience working with them and certainly had no idea they could be recursive. Nor did I know how to go about implementing a recursive algorithm to solve this particular problem. I ended up implementing my own binary tree and traversing algorithm, which I spend a great deal of time trying to debug only to discover it was working correctly and the problem was a careless oversight in my input parsing code which misread (just) one input rule. After solving part 1 I couldn't get my head around part 2 and looked for help, not on how to solve it but to understand the instructions. It was then, that I finally understood the significance of 42 and 31 and everything fell into place - a very clever puzzle.

Day 21 was interesting. I "solved" the example by inspection then wondered what algorithm my brain used to analyze it. I figured that out and implemented it to find the matching ingredients and allergens which left the ingredients with no allergen. It turned out that matching the ingredients and allergens was part 2. I assume there is some more obvious(?) way to answer part 1.

Day 23 part 2 took me more time than it should have. The instructions are worded in a way to mislead you. If you work out a few steps by hand, you can see what's really happening. After a few failed attempts I decided a linked list was the way to go. I had already forgotten that I implemented such a list in previous problem as an array. For this problem you don't need to link backwards to delete and insert cups. An array works perfectly. The array index is the cup label and the contents of the array is the next cup in the sequence (this may be the method @PHolder mentioned). You immediately know where the destination cup is. It provides a very elegent and satisfying solution.

Day 24 is fairly straightforward once to decide how to store the tile pattern. I used a 2-D array where every vertical index is used and every second horizontal index is used. This makes it easy to place hexagonal tiles. East is two index steps to the right, south-east is one index step to the right and one index step down, etc.

Overall the puzzles were very entertaining. I've already started on the 2019 series.
 

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
I've already started on the 2019 series.
I did the first 17 parts of 2019, but in early 2020. I got stumped on #18, I didn't know the necessary algorithm, and literally spent 3 days working on it to no end. I think my approach is probably correct, but I have a bug I just couldn't find/eliminate. I got busy, and never bothered to go back, but I may yet one day.

I really enjoyed the IntCode aspects of the 2019 puzzles. I will recommend you spend some time making your IntCode parser robust and easily extendable, because you will keep reusing it every other day or so, with new twists and turns. If you need any help or suggestions for any of the first 17 days, feel free to hit me up, although I am sure there are also details on Reddit.