Export thread

  • 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.

Advent of Code

#1

Barry Wallis

Barry Wallis

@leolaporte mentioned this on the show this week and it looks like fun. Is anyone else planning on participating in the Advent of Code?

Oh! Finally there is a web site that looks older than @Steve's. ;-)


#2

P

PHolder

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


#3

Barry Wallis

Barry Wallis

Thanks for the info @PHolder. My comment about the site looking old was only about the look (which being a text RPG guy, I love). I'm prepared to see how far I get. The good news is that I am retired and have plenty of time and I'm not compulsive so if I need to put it down for a few days and come back to it (or not), I can do that too. We'll see how it goes.


#4

danlock

danlock

The site is very simple, but fairly advanced.
That's... profound. Or a contradiction in terms. Or... an answer to a question which has not yet been asked. :unsure:


#5

P

PHolder

I did day 1's problem in less than 30 minutes. It wasn't too tricky as long as you found a non-combinatorial way to do it. Usually the problems are tuned so if you take a good approach, the answer can be calculated quickly, but if you try to brute force it, you will quickly run out of time (or patience) to find an answer. Even more frequently part one of the problem could be brute forced, but part two will combinatorically blow up if you try to brute force it.


#6

Paul F

Paul F

Is anyone else planning on participating in the Advent of Code?
Yes, I'll give it a try. Thanks to @PHolder for mentioning the start of a new series. I'm ready to advance to day 2.


#7

P

PHXdNelson

@PHolder -

By chance did you watch the video after you completed today's task?

I was surprised to see the spoilers in the video! This is not the case for last years original "Advent of Cyber". I recently started working on those while waiting for this years to launch.


#8

P

PHolder

did you watch the video
I've watched no videos, no. I have seen one in the past where the author of Advent of Code talked about his process and methods... I think that talk was given at Google.


#9

Barry Wallis

Barry Wallis

@PHolder -

By chance did you watch the video after you completed today's task?
Nope. I didn't even know there was one. I completed the first of today's tasks. Actually, I was up after midnight last night and looked at it before I went to sleep. I came up with a design before my brain shut down, remembered and refined it this morning. Now I'm going to practice for my magic class and try not to think about the second half until I am done.


#10

P

PHXdNelson

As a novice, I love watching or reading other solutions to these challenges after I completed them. It is another great way to learn. As for this specific challenge, John Hammond was today's creator. I like a lot of his ctf walkthroughs. One of the other contributors I like is TCM (The Cyber Mentor). He is a great instructor!


#11

Barry Wallis

Barry Wallis

@PHXdNelson You can find my C# answers here. I just completed both halves of Day 1.


#12

P

PHXdNelson

I was thinking of something completely different! LOL No wonder why I was confused by your postings (and I am sure you were equally confused by my post)!

I started working on AoC today also, but mine is "Advent of Cyber 2". https://tryhackme.com/room/adventofcyber2


#13

Barry Wallis

Barry Wallis

That is very different. I may do the SANS Holiday Hack Challenge this year.


#14

P

PHolder

@Barry Wallis Day 2 starting soon, but I would encourage you to think of a less brute force solution for day 1. You will not be able to brute force solutions for every problem forthcoming, part of the challenge is to think outside the box. I will give you a hint, but wrap it in a spoiler:
Try thinking if there is a way to do a Big O of 1 O(1) way to tell if a number is in a list of numbers. Big O is a complexity indication, and the least complex (in general) would be O(1). Your nested loop solution is O(n*n) (n squared) because there are two loops to n, one nested in the other. A better solution is O( n ) which is one loop to n, doing a O(1) lookup inside. https://en.wikipedia.org/wiki/Big_O_notation


#15

Barry Wallis

Barry Wallis

I wasn't happy with my solution but I had several commitments today and just wanted to complete it.


#16

P

PHolder

Day 2 wasn't too bad. Mostly a parsing problem I suspect.
If your language of choice has regular expressions, and you know how to use them, that should make short work of it.


#17

miquelfire

miquelfire

I have been using Advent of Code to basically learn modern JavaScript. One of the sponsors had templates so I'm using it this year. You can see my code here.

I haven't looked at Day 2 yet. PHolder's hint tells me I'll be running RegexBuddy today.


#18

Barry Wallis

Barry Wallis

I did Day 2 part 1 last night (thankfully I'm on the west coast of the U.S.). I'm using C# and didn't need to dig into RegEx for part 1. I will be doing part2 this afternoon.


#19

P

PHolder

Day 3 isn't too tricky. I would say the biggest thing is to:
use mod to cause the horizontal repeat and to generalize your part 1 solver so it can be repurposed easily for part 2.


#20

Barry Wallis

Barry Wallis

I just started it.


#21

Barry Wallis

Barry Wallis

Day 3 complete. Part 2 was easy due to the way I coded part 1. I could make it more efficient by using parallelism if I had the time.


#22

Barry Wallis

Barry Wallis

Day 4 done and I designed part 1 with an eye towards what part 2 would be (and I was correct).


#23

P

PHolder

I started Day 4 late because I fell asleep before midnight. I found it kinda boring to do to be honest, this is just normal-ish data validation. Some say the weekends are when the questions get more challenging, so we'll see what happens tonight.


#24

miquelfire

miquelfire

With the template I'm using for this event, the code is basically solved with maps, reduce, and filters. The only bit that wasn't a one-liner of sorts, was the reduce function.

The filter for part 2 wasn't a "one-liner", but can be considered one if you don't care about readability.

And now for some RegEx abuse that I wrote today:
JavaScript:
/(?:(?:59|6[0-9]|7[1-6])in|1(?:[5-8][0-9]|9[0-3])cm)/


#25

P

PHolder

In Java you can capture groups from regex input using the round brackets. In fact you need to escape it if you don't want it to capture. So my code for that was:
I was a bit lazy by using input.contains when I could have just compared against the m.group(2), but I already had the contains code before I decided to use the regex.

Java:
  //hgt (Height) - a number followed by either cm or in:
  //  If cm, the number must be at least 150 and at most 193.
  //  If in, the number must be at least 59 and at most 76.
  private static final Pattern heightPattern = Pattern.compile("([0-9]+)(cm|in)");
  private boolean validateHeight(final String input)
  {
    final Matcher m = heightPattern.matcher(input);
    if (m.matches())
    {
      if (input.contains("cm"))
      {
        final int numcm = Integer.parseInt(m.group(1));
        if ((numcm < 150) || (numcm > 193)) return false;
        return true;
      }
      if (input.contains("in"))
      {
        final int numin = Integer.parseInt(m.group(1));
        if ((numin < 59) || (numin > 76)) return false;
        return true;
      }
    }

    return false;
  }


#26

Barry Wallis

Barry Wallis

I used C# range notation and was able to fit each validation function into a single line. I also stole your code to hide the spoiler. :)

Code:
        ///<summary>
        /// Validate height. 
        /// </summary>
        /// <param name="value">The height.</param>
        /// <returns><see langword="true"/> if <paramref name="value"/> contains a number followed by either cm or in:
        ///     If cm, the number must be at least 150 and at most 193.
        ///     If in, the number must be at least 59 and at most 76; 
        /// otherwise <see langword="false"/>.</returns>
        static bool ValidateHgt(string value)
            => int.TryParse(value[0..^2], out int height)
               && (value[^2..^0] == "cm" || value[^2..^0] == "in")
               && ((value[^2..^0] == "cm"
                    && height >= 150
                    && height <= 193) || (value[^2..^0] == "in" && height >= 59 && height <= 76));


#27

P

PHolder

Day 5 was very straightforward if you have experience with ...
... binary search.
Java:
  private static int calculateRow(final String boardingPass)
  {
    int min = 0;
    int max = 127;
    for(int i=0; i<6; i++)
    {
      final char c = boardingPass.charAt(i);
      if (c == 'F')
      {
        max = max-((max-min)/2)-1;
      }
      if (c == 'B')
      {
        min = min+((max-min)/2)+1;
      }
    }
    if (boardingPass.charAt(6) == 'F')
      return min;
    return max;
  }

  private static int calculateCol(final String boardingPass)
  {
    int min = 0;
    int max = 7;
    for(int i=7; i<9; i++)
    {
      final char c = boardingPass.charAt(i);
      if (c == 'L')
      {
        max = max-((max-min)/2)-1;
      }
      if (c == 'R')
      {
        min = min+((max-min)/2)+1;
      }
    }
    if (boardingPass.charAt(9) == 'L')
      return min;
    return max;
  }


#28

Barry Wallis

Barry Wallis

I just looked at part 1. It looks trivial.


#29

P

PHolder

Day 6 seems very much like day 4 or 5. This is getting kind of boring, to be honest. Last year I really enjoyed the IntCode parser and using it to solve problems, but this year they're just counting problems, really. Perhaps it will get more exciting in the upcoming questions... or at least a little more challenging.

I probably could have used an array instead of the Set or Map, but I felt this approach would be clearest since the most efficient code wasn't strictly necessary.

Java:
final class AnswerGroup
{
  private final int numberOfPeople;
  private final Set<Character> setOfQuestionsAnswered = new HashSet<>();
  private final Map<Character, Integer> numberOfTimesQuestionsAnswered = new HashMap<>();


  public AnswerGroup(final String[] lines)
  {
    numberOfPeople = lines.length;

    for(final char c: "abcdefghijklmnopqrstuvwxyz".toCharArray())
    {
      numberOfTimesQuestionsAnswered.put(c, 0);
    }

    for (final String line: lines)
    {
      for(final char c: line.toCharArray())
      {
        setOfQuestionsAnswered.add(c);
        numberOfTimesQuestionsAnswered.put(c, numberOfTimesQuestionsAnswered.get(c)+1);
      }
    }
  }

  public int getNumberOfQuestionsAnswered()
  {
    return setOfQuestionsAnswered.size();
  }


  public int getNumberOfQuestionsEveryoneAnswered()
  {
    int result = 0;
    for(final char c: setOfQuestionsAnswered)
    {
      if (numberOfTimesQuestionsAnswered.get(c) == numberOfPeople) result++;
    }

    return result;
  }
}


#30

Barry Wallis

Barry Wallis

I agree with you. @PHolder. It seems as though they are getting easier. I completed both parts this evening.


#31

Paul F

Paul F

I tried to make day 6 interesting by noting the symmetry:
For each group you can use an OR of yes answers for part 1 and an OR of no answers for part 2.


#32

Barry Wallis

Barry Wallis

That is what made it particularly trivial for me. :)
I changed union to intersection.


#33

miquelfire

miquelfire

Part 1 I basically made a one-liner. If I replaced the const data = with a return, it would be a one-liner.

Actually, I could have gotten rid of the braces because of how arrow functions work in modern Javascript.

d is the parameter to the function.
JavaScript:
d.split('\n\n').map(e => e.replace(/\n/g, '')).map(e => [...new Set(e.split('').sort())]).reduce((p, v) => p + v.length, 0)

Looking at it now, it seems before I figured out how Set would do some work for me, what I was going to do resulted in me leaving a pointless sort() call.

Part 2 I used map

I thought we would have been doing something like the IntCode from last year by now.


#34

P

PHolder

Okay, day 7 brought some challenge. You have string parsing to do, and then you need to do something meaningful with the strings once you have them parsed. I guess you can possibly do the parsing without regex, but I wouldn't want to have to.

You're going to need a tree data structure quite likely. You're going to need to recursively traverse it to answer the two different questions from part 1 and part 2. You need to be able to find a specific node in the middle of the tree too and then traverse upward or downward depending on the question asked. For my implementation I used a pair of HashMap's, one representing the tree as normal, and one that kind of built it in the inverse. I did this because it seemed about as easy as building a proper tree with a parent pointer and child pointers, as well as still having a HashMap to make finding certain nodes in the tree efficient. (I didn't want to have to walk the whole tree until I found the node of interest. I guess, since the searched item was specific and given in advance, you could avoid generalizing, and just remember the specific node of interest at time of creation for your later needs.)

The above spoiler discusses the solution in general, the code below is my key class for the actual implementation I did.

There are two other classes I used, but you can probably guess the basics of them from this code. There was a BagRule that contained the bag name and the allowed contents if any. The BagContentItem was a number and a bag name, and multiple different of these were the allowed contents for the BagRule. There is plenty of recursion here because the problem is pretty much defined by it. I returned the names of the bags for the parent bags, instead of just the count, but the reason for this is because I initially screwed up. I didn't fully comprehend what was being asked for part 1, and I actually initially built the answer for part 2 before realizing my mistake. I then assumed part 2 would use the code I had written, but I didn't finish it off fully when I realized I didn't need to.

Java:
final class BagRulesManager
{
  final Map<String, BagRule> rulesForWhatABagCanContain = new HashMap<>();
  final Map<String, Set<String>> rulesForWhatCanContainABag = new HashMap<>();

  public void addNewRule(final BagRule bagRuleToAdd)
  {
    final String bagName = bagRuleToAdd.getBagName();
    rulesForWhatABagCanContain.put(bagName, bagRuleToAdd);
    
    if (bagRuleToAdd.isAllowedContents())
    {
      final BagContentsItem[] allowedBagContents = bagRuleToAdd.getAllowedContents();
      for (int i=0; i<allowedBagContents.length; i++)
      {
        final String childName = allowedBagContents[i].getNameOfItem();
        if (!rulesForWhatCanContainABag.containsKey(childName))  rulesForWhatCanContainABag.put(childName, new HashSet<String>());
        
        final Set<String> bagsThatCanContain = rulesForWhatCanContainABag.get(childName);
        bagsThatCanContain.add(bagName);
      }
    }
  }
 
  public int getTotalNumberOfBagsABagCanContain(final String bagName)
  {
    final int result = _getTotalNumberOfBagsABagCanContain(bagName);
    if (result == 0) return 0;
    return result - 1;
  }

  private int _getTotalNumberOfBagsABagCanContain(final String bagName)
  {
    if (!rulesForWhatABagCanContain.containsKey(bagName)) throw new IllegalStateException("Asked to _getTotalNumberOfBagsABagCanContain() for a bagName that was not found: " + bagName);
    final BagRule br = rulesForWhatABagCanContain.get(bagName);
    if (!br.isAllowedContents()) return 0;

    int result = 1;
    final BagContentsItem[] allowedBagContents = br.getAllowedContents();
    for (int i=0; i<allowedBagContents.length; i++)
    {
      final int numSub = _getTotalNumberOfBagsABagCanContain(allowedBagContents[i].getNameOfItem());
      if (numSub == 0)
      {
        result += allowedBagContents[i].getNumberOfItem();
      }
      else
      {
        result += numSub * allowedBagContents[i].getNumberOfItem();
      }
    }
    return result;
  }
 
  public String[] getBagsThatCanContainABag(final String bagName)
  {
    if (!rulesForWhatCanContainABag.containsKey(bagName))  return new String[0];

    final Set<String> allPossibleContainingBags = new HashSet<>();
    final Set<String> parents = rulesForWhatCanContainABag.get(bagName);
    for (final String parentNames : parents)
    {
      allPossibleContainingBags.add(parentNames);
      final String[] grandParents = getBagsThatCanContainABag(parentNames);
      for (final String grandParentNames : grandParents)
      {
        allPossibleContainingBags.add(grandParentNames);
      }
    }
    
    return allPossibleContainingBags.toArray(new String[0]);
  }
}


#35

Barry Wallis

Barry Wallis

I spent more debugging time on part 1 than on any of the previous days. There was a defect I just couldn't see for a while. I finally found it with judicious use of the debugger. Again, if you find a good design for part 1, part 2 is just minor additions.


#36

P

PHolder

Day 8 feels like a revisit to the IntCode of last year. You need to construct a program to read and parse the input, presumably translating it into something you can run in a mini virtual machine. (A single accumulator and an instruction pointer, and three instruction types qualifies as "mini", right?)

Solving part 2 without brute force is apparently possible, but it's not intuitive to me and I wouldn't ever have come up with such a solution. The solution I did come up with seems elegant enough, even if it is brute force.

He basically tells you that an infinite loop is defined by any instruction in your program attempting to execute a second time. You need to design your parser so it can run a program and return a boolean indicating whether or not it would have gone into an infinite loop. (Would have attempted to run any instruction a second time.) My approach for this was to use a simple array for each instruction that counts the number of times that instruction executes... when you fetch the instruction you check the counter and return false (no normal termination) when the count is not zero. Then increment the count, and execute the instruction. Part 2 requires you to have a way to change one instruction, run it, and see if it still produces an infinite loop or not.

Java:
  public static void main(final String[] args)
  {
    final CodeReader     cr = new FileCodeReader(FILE);
    final Program        p  = Program.readProgram(cr, 1000);
    final ProgramRunner  pr = new ProgramRunner(p);

    pr.runProgramStopBeforeFirstInstructionRepeat();
    final int val = pr.getAccumVal();
    System.out.println("Part 1: " + val);
   
    // Iterate over the program instructions one by one, changing NOP->JMP or JMP->NOP then
    // test run the program to see if it terminates normally
    for (int i=0; i<p.getProgramSize(); i++)
    {
      final ProgramInstruction pi = p.getInstructionAt(i);
      final InstructionType it = pi.getInstructionType();

      final InstructionType newIT;
      switch (it)
      {
        case TERMINATE:  throw new IllegalStateException("Hit terminate");

        case JMP:  newIT = InstructionType.NOP;  break;
        case NOP:  newIT = InstructionType.JMP;  break;

        default:   newIT = InstructionType.UNDEFINED_INSTRUCTION; break;
      }
     
      if (newIT != InstructionType.UNDEFINED_INSTRUCTION)
      {
        final Program newP = p.newVersionWithChangedInstruction(i, newIT);
        final ProgramRunner newPR = new ProgramRunner(newP);
        if (newPR.runProgramStopBeforeFirstInstructionRepeat())
        {
          final int part2Val = newPR.getAccumVal();
          System.out.println("Part 2 (@" + i +"): " + part2Val);
          break;
        }
      }
    }
  }


#37

Paul F

Paul F

Day 8
Since only one instruction was wrong, it had to be one of the ones executed in part 1. I kept a history of those instructions, and for part 2 interchanged just the nops and jmps that were in the history (restricted brute force). The extra programming effort has negligible benefit but makes it a little more interesting.


#38

P

PHolder

@Paul F that's a nice little optimization. I went back and retrofitted that into mine.

Since I already maintained the array of instruction execution counts, it was easy enough to extract the instruction addresses that were executed and return them for further processing. I then changed my part two loop to use the result:
Java:
    // Only instructions run in part 1 could be affected for the answer to part 2
    // Iterate over the program instructions one by one, changing NOP->JMP or JMP->NOP then
    // test run the program to see if it terminates normally
    for(final int i : pr.getInstructionAddressesOfExecutedInstructions())


#39

miquelfire

miquelfire

I wonder if this will be a virtual machine we build throughout the month or not? There's no real sign we need to keep track of what we do.


#40

P

PHolder

Day 9 looked at first like it was daunting, but you just need to understand that you need a specific data structure to solve it. (Although my friend, working in Python, was able to use the built in arrays or slices or whatever they're called to save coding basic math operations over sets of numbers.)

I coded my own little variable sized FIFO. I had it keep a running total of the sum of the numbers in it. For part one it was a FIFO of size 25, and I needed to add a method to find any two numbers in the FIFO that summed to a specific sum. This is, in combinatorics, 25C2. For only two, it's find to code two nested loops that count from 1 to 25, making sure to ignore the times when the two loops have the same index. First preload the FIFO with the first 25 inputs, then for each new input, if it has a sum of two numbers in the FIFO you just add it to the FIFO. If there is no sum, you've found your part 1 answer, and your input to part 2.

For part 2, you need to try FIFOs of sizes 2 and upward, processing all the input through each until you find the sum of the numbers in the FIFO are equal to your answer from part 1. The process is the same as before, prefill the FIFO with the first inputs, then keep checking the sum as you add each new input. If you find the answer you're almost done, you just need a method to find the min and max and sum them. If you don't find the answer and reach the end of input, start over with a larger FIFO.

Java:
    final NumberReader nr = new NumberReader(FILE);
    final NumberFIFO   nf = new NumberFIFO(25);
    // fill preamble
    for (int i=0; i<25; i++) nf.addNumber(nr.getNextNumber());
   
    long soughtNumber = -1;  // For Part 2
    while (nr.isMoreInput())
    {
      final long val = nr.getNextNumber();
      if (nf.doesExistTwoNumbersThatSumTo(val))
      {
        nf.addNumber(val);
      }
      else
      {
        System.out.println("Part 1: " + val);
        soughtNumber = val;
        break;
      }
    }

Java:
    for(int i=2; i<1000; i++)
    {
      final NumberReader nri = new NumberReader(FILE);
      final NumberFIFO nfi = new NumberFIFO(i);
      for (int j=0; j<i; j++)  // fill preamble
      {
        nfi.addNumber(nri.getNextNumber());
      }
      boolean wasFound = false;
      while (nri.isMoreInput())
      {
        if (nfi.addAll() == soughtNumber)
        {
          wasFound = true;
          break;
        }
        nfi.addNumber(nri.getNextNumber());
      }
     
      if (wasFound)
      {
        System.out.println("Part 2: " + nfi.findMinAndMaxAndSumThem() + " (found in FIFO of size " + i + ")");
        break;
      }
    }


#41

Barry Wallis

Barry Wallis

I just finished Day 8. I'm a little late as I have magic class on Tuesdays. This was the most fun so far (although still not terribly difficult). I wonder if part 2 will always be simple if you designed part 1 appropriately. I'll tackle Day 9 tomorrow morning.


#42

Paul F

Paul F

Day 9
Using an array for the input data, step through each number (N) and its 25 preceding numbers (PN). Subtract the first number in PN from N (to get D) and check to see if any of the following numbers in PN equals D. If found, advance to the next N in the array. If not found, repeat for each number in PN. If no pair of numbers is found in PN, N is the number for part 1.

Using N from part 1, and all the preceding numbers in the array (PN), start a sum with the first number in PN and add the following numbers in PN one by one, checking the sum each time, and keeping track of the smallest and largest numbers encountered. Continue while the sum is less than N. If the sum equals N we have found the contiguous set. Otherwise repeat starting a new sum with the next number in PN.


#43

Barry Wallis

Barry Wallis

Day 9 may have been the easiest one yet. I made up for lost time today.


#44

P

PHolder

Well now isn't day 10 a pickle. I got the first part working in straight order, I spent time unit testing my approach on the small examples before trying the larger input. My natural approach to tackling the part 2 was recursive, and it worked fine on the toy example. On the big input, there wasn't enough time left in the universe for a recursive solution, but at least I knew I understood the problem. I thought I saw an approach using combinatorics, but I wasn't sure. There was clearly some pattern there. I coded something up based on my intuition, and the answer was too large. In the end I admitted defeat, assuming the trick was something I just didn't know about. It also turns out I was testing my approach with some made up data that didn't have the same restrictions as the actual input data, so that was really what kept me from seeing the pattern. In the end, when looking on Reddit, I found the piece I was missing, that I was indeed unaware of.

When I was looking at the small example, I saw there were two sub-sequences with numbers in sequence. One was size 4 and one was size 3 and to me it felt significant that the expected answer was 8 and (4-2)^2 * (3-2)^2 = 8. This was what I coded up that gave me too large of an answer... Still it felt like I was close. I was thinking it must be some special value nCr and that got me thinking of the binomial coefficients. Turns out I was in the right ballpark, but it wasn't until I looked on Reddit I learned about the Tribonacci Sequence--I had never heard of it before. I retrofitted it into what I had, and it worked for the given example, and for many of the examples I had crafted. It didn't work for all of them, because I had not noticed that there were no differences of 2 in the supplied input, and I had mistakenly created examples with differences of 2. If you allow differences of two, the Tribonacci Sequence will not work for the input. As there are no differences of two, the Tribonacci Sequence works. I'm a bit ashamed to say I don't understand what's going on here... :-/

Java:
  public void doPart1Calculations()
  {
    int currentJoltage = 0;
    int currentAdapterJoltage = -1;
    while (joltageAdapterEnumerator.canGetNextJoltageAdapter())
    {
      currentAdapterJoltage = joltageAdapterEnumerator.getNextJoltageAdapter();
      final int diff = currentAdapterJoltage-currentJoltage;
      switch(diff)
      {
        case 1: num1Diffs++; break;
        case 3: num3Diffs++; break;
        default: throw new IllegalStateException("Couldn't work with joltage diff:" + diff);
      }
      currentJoltage = currentAdapterJoltage;
    }
    num3Diffs++;  // For the device
  }

Java:
  private static final int[] tribonacci = {0, 1, 1, 2, 4, 7, 13, 24, 44};

  public long doPart2Calculations()
  {
    joltageAdapterEnumerator.reset();
    long result = 1;
    int currentJoltage = 0;
    int count = 1;
    while (joltageAdapterEnumerator.canGetNextJoltageAdapter())
    {
      final int nextJoltage = joltageAdapterEnumerator.getNextJoltageAdapter();
      if (currentJoltage+1 == nextJoltage)
      {
        count++;
      }
      else
      {
        result*=tribonacci[count];
        count = 1;
      }
      currentJoltage = nextJoltage;
    }
    return result;
  }


#45

Paul F

Paul F

Day 10
I used an array of adapters containing the rating of an adapter, sorted in ascending order, and the number of paths to that adapter. For a given adapter the number of paths is the sum of the paths to the previous adapters which exist with ratings 1, 2, or 3 jolts less that the rating of the given adapter. Working from the beginning to the end of the array the last number of paths calculated is the answer.


#46

P

PHolder

@Paul F I didn't understand your solution at first, but I get it now. I implemented the same thing in Java using a HashMap and it runs as fast as my other solution and gives the same results.

Java:
  public long doPart2CalculationsB()
  {
    final Map<Integer, Long> pathsToPoint = new HashMap<>();
    joltageAdapterEnumerator.reset();
    pathsToPoint.put(0, 1L);
    int adapterJoltage=0;
    while (joltageAdapterEnumerator.canGetNextJoltageAdapter())
    {
      adapterJoltage = joltageAdapterEnumerator.getNextJoltageAdapter();
      final long result =
          pathsToPoint.getOrDefault(adapterJoltage-1, 0L) +
          pathsToPoint.getOrDefault(adapterJoltage-2, 0L) +
          pathsToPoint.getOrDefault(adapterJoltage-3, 0L);
      pathsToPoint.put(adapterJoltage, result);
    }
    return pathsToPoint.get(adapterJoltage);
  }


#47

Paul F

Paul F

@Paul F I didn't understand your solution at first, but I get it now. I implemented the same thing in Java using a HashMap and it runs as fast as my other solution and gives the same results.
Yes, my description was rather brief. I had to mull over the problem for a while before I really understood what we were dealing with, and considered various approaches before I hit upon that one. I was a bit surprised that the gigantic number it produced on its first run was the right answer.

I'm not that familiar with containers. I prefer my own arrays or linked lists so I can see what's going on, and for these one-off programs I'm not concerned about hard-coded numbers or lack of generalization. I recently installed the free version of Visual Studio 2019 C++ and am using it for these puzzles.


#48

Barry Wallis

Barry Wallis

I was a bit surprised that the gigantic number it produced on its first run was the right answer.
I'm about to start part 2 (once again part 1 was trivial). There was a hint that made me think 64-bit ints would be needed (" there must be more than a trillion valid ways to arrange them!").

I just got back from running errands this afternoon and think I hit on a way to complete part 2 efficiently.


#49

P

PHolder

Day 11 was very straight forward. Basically a re-implementation of a version of The Game of Life. Not really much of a point giving implementation hints or code samples… just load the data, iterate it following the rules, and process it to produce a count. It took me almost an hour and a half to do it because it’s mostly tedium… especially when implementing it for unit testing. (I also made the mistake of assuming the input would be square like the sample, but it was not, but that was a quick 5 minute fix.)

On second thought, here’s my main loop:
Java:
final SeatingStateProvider ssp = new FileSeatingStateProvider(FILE);
final SeatingState ss = new SeatingState(ssp.getWidth(), ssp.getHeight());

ss.initialize(ssp);
while (ss.evolve()) ;
System.out.println("Part 1: " + ss.getNumberOfOccupiedSeats());

ss.initialize(ssp);
while (ss.evolve2()) ;
System.out.println("Part 2: " + ss.getNumberOfOccupiedSeats());


#50

Barry Wallis

Barry Wallis

I'm behind and still working on Day 10 part 2. I will hopefully finish it tomorrow morning.


#51

miquelfire

miquelfire

I'll work on day 11 then return to part 2 of day 10 later. I had a busy day yesterday can couldn't really attempt to try anything.


#52

Paul F

Paul F

Day 11 was very straight forward ... (I also made the mistake of assuming the input would be square ... )
Agreed, but the input layout is square (98x98), which interestingly becomes 100x100 if you add a floor border.


#53

P

PHolder

input layout is square (98x98),
Remember that everyone gets a unique input. Mine is:
Width=96, Height=98


#54

Paul F

Paul F

Remember that everyone gets a unique input. Mine is:
Width=96, Height=98
Oh! I didn't know that. That's really interesting. I guess that's to stop people from posting just the answers. Each person probably gets input data randomly from a pre-generated set . It explains a message I got for an incorrect answer saying that it matched a different person's answer.


#55

Barry Wallis

Barry Wallis

I'm way behind. I just finished day 10. <sigh>


#56

P

PHolder

Day 12 was interesting. Some minor parsing again, and dispatching to functions to implement the instructions. Part 1 was very straightforward once you built your code to handle each instruction. Part 2 was a little more challenging, because it twisted the situation enough that you had to decide how much of your previous part 1 code was reusable.

In the end, I copied my BoatControl class to BoatControl1, extracted an interface and then copied BoatControl1 to BoatControl2 and made the changes necessary to implement the waypoint and the new translations to it. I took a lot longer than I should have, because I tried to move the waypoint with the boat, but that made the rotations hell. Once I realized I could just leave the waypoint based on the origin, then the rotations were easy and everything fell in place.

Java:
    final NavigationInstructionReader nir = new FileNavigationInstructionReader(FILE);
    final BoatControl bc = new BoatControl1(0, 0, Direction.EAST);
    while (nir.isMoreInput())
    {
      final NavigationInstruction ni = nir.getNextNavigationInstruction();
      bc.navigate(ni);
    }
    System.out.println("Part 1: " + bc.getManhattanDistance());

    final NavigationInstructionReader nir2 = new FileNavigationInstructionReader(FILE);
    final BoatControl bc2 = new BoatControl2(0, 0, Direction.EAST, 10, -1);
    while (nir2.isMoreInput())
    {
      final NavigationInstruction ni = nir2.getNextNavigationInstruction();
      bc2.navigate(ni);
    }
    System.out.println("Part 2: " + bc2.getManhattanDistance());


#57

Paul F

Paul F

Day 12. This type of movement on a grid reminded me of this fascinating way to find the real roots of a polynomial:


#58

P

PHolder

Day 13 kinda makes me mad. He does these problems where you NEED to recognize some very specific thing, but he doesn’t give you any hints. That’s great if you’ve had the fortune to have encountered it in your past, but in this case, I doubt you could even know what to Google for without being told. I certainly didn’t.

The first part was pretty straight forward, if you’re competent with modular (as in mod based) math. You need to compute a minimum over a set of things. To compute when a bus on a fixed schedule will arrive after a specified time, you need to know that you use integer division, add one to the result and multiply by the fixed schedule amount.

So if you want to know when the next 8 minute bus will arrive after 1084 you do:
1084/8=135.5, but is 135 with integer math. That means you just missed a bus at 135*8 = 1080.
The next bus will be at 1080 + 8 which you can calculate by (135+1) * 8 = 1088
The time to wait for the next bus is 1088 minus 1084, or 4 minutes.

For my code, I kinda cheated–the input is so small I just copied it directly into my code, and massaged out the 'x’s I didn’t need for part 1. I replaced the 'x’s with 0’s for part 2, in my Part 2 solving class.

Java:
// See note above, I copied the supplied input directly into my code
// private static final int timestamp = removed my specific input timestamp;
// private static final int[] buses = {23,41, removed the rest of my specific inputs};

  public static void main(final String[] args)
  {
    int minimumWaitAnyNextBus = 10_000_000;
    int busNumber=0;
    for(int i=0; i<buses.length; i++)
    {
      final int tripNumberOfBusYouJustMissed = timestamp / buses[i];
      final int tripNumberOfNextBus = tripNumberOfBusYouJustMissed + 1;
      final int timestampOfNextBus = tripNumberOfNextBus * buses[i];
      final int waitForNextArrivalOfBus = timestampOfNextBus - timestamp;
      if (waitForNextArrivalOfBus < minimumWaitAnyNextBus)
      {
        minimumWaitAnyNextBus=waitForNextArrivalOfBus;
        busNumber=buses[i];
      }
    }
    System.out.format("Part 1: %d (You should catch bus %d in %d minutes)%n", (busNumber*minimumWaitAnyNextBus), busNumber, minimumWaitAnyNextBus);
    System.out.println("Part 2: " + Part2.doCalc());
  }

For part 2 you can brute force the small inputs, and I coded that quickly. But since you are warned the result will be HUGE, that is an indication that brute force is not going to work. What you need to know to solve it quickly is that it is an application of
the Chinese Remainder Theorem.
(I didn’t know this until I googled about the problem.)

Anyway, once you know that, it’s just a matter of massaging the input data to a form that works for the solver of the Chinese Remainder Theorem. I borrowed my implementation from https://rosettacode.org/wiki/Chinese_remainder_theorem#Java . The trick here is to recognize that the basic solution if you wanted the buses to all arrive at the SAME timestamp would be just to multiply all the primes together (i.e. to calculate the lowest common multiple of them.) But in this case, you need an offset, because the buses are arriving one after the other, so when you pass in your desired mod value for the CRT you need to subtract to allow time for the bus to arrive later than the previous one(s).

Here’s the key part of my part 2 code, I could have done the array filtering/processing better, but after banging my head for so long, I just wanted something quick and easy.

Java:
  public static long doCalcWith(final long[] schedule)
  {
    final List<Long> nVals = new ArrayList<>();
    final List<Long> aVals = new ArrayList<>();
    for (int i=0; i<schedule.length; i++)
    {
      if (schedule[i]!=0)
      {
        nVals.add(schedule[i]);
        aVals.add(schedule[i]-i);
      }
    }
    final long[] n = new long[nVals.size()];
    final long[] a = new long[nVals.size()];
    for(int i=0; i<nVals.size(); i++)
    {
      n[i]=nVals.get(i);
      a[i]=aVals.get(i);
    }
    return ChineseRemainderTheorem.chineseRemainder(n, a);
  }


#59

Paul F

Paul F

Day 13
This one was fun.


#60

P

PHolder

So day 14… it will either be a challenge or tedious. For me it was mostly tedious. Throwing away most of part 1 to do part 2 wasn’t my favourite decision, but it was faster and more efficient to just copy several of my classes and make the necessary changes to implement the completely different execution of the virtual machine. I did screw up using an int instead of a long, which gave me the wrong answer the first half dozen times I tried… oops! (My brain is practically hard coded to type int sum = 0 when adding sums… AoC is practically the only time I need to use longs.)

I predict part 2 is going to challenge many people who don’t figure out the trick for the addressing needs. You need to realize that
every X bit in the mask means you generate twice as many addresses, and the easiest way to do it is to build a list/set of addresses that you re-double for every X bit.

My main code:

Java:
    final InstructionReader ir = new FileInstructionReader(FILE);
    final InstructionDecoder id = new InstructionDecoder(ir);
    final ComputerEmulator ce = new ComputerEmulator(id);
    ce.runProgramToEnd();
    final long sum1 = ce.sumAllMemory();
    System.out.println("Part 1: " + sum1);

    ir.reset();
    final InstructionDecoder2 id2 = new InstructionDecoder2(ir);
    final ComputerEmulator2 ce2 = new ComputerEmulator2(id2);
    ce2.runProgramToEnd();
    final long sum2 = ce2.sumAllMemory();
    System.out.println("Part 2: " + sum2);

I guess the bit manipulation code could be a challenge for people who don’t usually do bitwise manipulations. Here’s some of that from part 1:

Java:
  public static ComputerInstruction makeSetMaskInstruction(final String mask)
  {
    final long andMask = Long.parseLong("0" + mask.replace('1', 'X').replace('X', '1'), 2);
    final long orMask  = Long.parseLong("0" + mask.replace('0', 'X').replace('X', '0'), 2);
    return new ComputerInstruction(ComputerInstructionType.SET_MASK, andMask, orMask, -1, -1);
  }



Java:
      case STORE_TO_MEMORY:
      {
        lastAddress = ci.getAddress();
        lastValue = ci.getValue() & currentAndMask | currentOrMask;
        computerMemory.put(lastAddress, lastValue);
      }
      break;

and from part 2:

Java:
  public static ComputerInstruction2 makeSetMaskInstruction(final String mask)
  {
    final long addressXMask  = Long.parseLong("0" + mask.replace('1', '0').replace('X', '1'), 2);
    final long addressOrMask = Long.parseLong("0" + mask.replace('0', 'X').replace('X', '0'), 2);
    return new ComputerInstruction2(ComputerInstructionType.SET_MASK, addressXMask, addressOrMask, -1, -1);
  }

And the tricky bit for part 2 addresses:

Java:
  private void putValueAtAllAddresses()
  {
    final Set<Long> addressesToAffect = new HashSet<>();
    long xPlacesFinder = 1;
    boolean first = true;
    int nummberOfXBits = 0;
    final long oredAddress = lastAddress | currentAddressOrMask;
    while (xPlacesFinder < 0b1_0000_0000_0000_0000_0000_0000_0000_0000_0000L)
    {
      if (xPlacesFinder == (currentAddressXMask & xPlacesFinder))
      {
        nummberOfXBits++;
        if (first)
        {
          first = false;
          addressesToAffect.add(oredAddress & ~xPlacesFinder);
          addressesToAffect.add(oredAddress |  xPlacesFinder);
        }
        else
        {
          final List<Long> newAddresses = new ArrayList<>();
          for (final long addr : addressesToAffect)
          {
            newAddresses.add(addr & ~xPlacesFinder);
            newAddresses.add(addr |  xPlacesFinder);
          }
          addressesToAffect.addAll(newAddresses);
        }
      }
      xPlacesFinder<<=1;
    }
    final int numberOfExpectedAddresses = (int)Math.pow(2, nummberOfXBits);
    lastNumberOfAddresses = addressesToAffect.size();
    if (lastNumberOfAddresses != numberOfExpectedAddresses)
    {
      throw new IllegalStateException(String.format("Didn't generate as many addresses(%d) as expected(%d)", lastNumberOfAddresses, numberOfExpectedAddresses));
    }


#61

P

PHolder

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


#62

Paul F

Paul F

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.


#63

P

PHolder

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”:
c93e85e8f14a1c23e3105eea10f7adc6f8d0abcc.jpeg

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


#64

Steve

Steve

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!


#65

P

PHolder

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


#66

Paul F

Paul F

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.


#67

P

PHolder

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.


#68

Paul F

Paul F

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.


#69

P

PHolder

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.


#70

Paul F

Paul F

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.


#71

P

PHolder

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


#72

Paul F

Paul F

OMG!! I ranked in the top 1000 for day 19:
Many congratulations!


#73

P

PHolder

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


#74

P

PHolder

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


#75

P

PHolder

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


#76

P

PHolder

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


#77

P

PHolder

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


#78

P

PHolder

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


#79

Paul F

Paul F

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.


#80

P

PHolder

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.