Advent of Code 2020

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.

These are implementation notes for part 2:

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… :-/

Key code for part 1:

  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
  }

Key code for part 2:

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

Back here at Day 5. I was writing all this scaffolding for a brute force solution (not complicated but time-consuming - same as yours @PHolder) when I happened to see that the immortal Peter Norvig is solving these, too. When I saw his solution the clouds parted. So obvious!! Now I’m rethinking all my solutions! This Wastl fellow is a sly cove, indeed!

Hint: There’s a reason there are 128 rows and 8 columns. And the columns are in the least significant three places!

My final code was SO much cleaner!!


;; provided by AOC:
(define input (file->lines "input5.txt"))

;; String -> Seat
;; given a seat code return a Seat
;; big Peter Norvig insight: it's just binary!!
(define (find-seat code)
  (local [(define (convert-to-binary char)
            (case char
              [(#\F #\L) #\0]
              [(#\B #\R) #\1]))]
    (string->number
     (string-append "#b"
                    (list->string
                     (map convert-to-binary (string->list code))))))) 
 
(module+ test
  (require rackunit)
  (check-equal? (find-seat "BFFFBBFRRR") 567)
  (check-equal? (find-seat "FFFBBBFRRR") 119)
  (check-equal? (find-seat "BBFFBBFRLL") 820))

(time (printf "AOC Problem 5.1 = ~a\n" (apply max (map find-seat input))))
        

Yea, Day 5’s Part 1 took me longer than any other Part 1 this year so far (through Day 10); I immediately saw the binary search aspect of it, but wasted time trying to implement an actual binary search in the necessary manner before I realized the solution you ended up at. Part 2 was trivial after that; my submission time was a minute after Part 1.

Wasn’t that an epiphany. It blew my mind! What language are you doing it in @Cyphase?

Yeah part two was a simple iteration through the list…

(define seats (sort (map find-seat input) <)); ascending sorted list of seat IDs
(time (printf "AOC Problem 5.2 = ~a\n"
              (for/first ([i seats]
                          [j (rest seats)]
                          #:when (equal? 2 (- j i)))
                (sub1 j))
              ))

Now on to Day 6. (I’m slooooow.)

In thinking about day 10 part 2 some more, and talking with others, I found a different way to achieve the result, that is maybe more explainable.

The number of paths to a certain adapter is equal to the sum of any paths to the adapters that are 1,2 or 3 less in joltage than the current adapter. The final answer is the number of paths to the final adapter.

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

I’m doing it in Python initially since that’s what I’m fastest in, and I find the extra challenge of speed-coding and competing for the leaderboard adds some fun to it. :smiley: I plan to go through the puzzles with Haskell and Rust at some point, since I’ve had those on my list of languages to learn for a while.

I get the appeal of the speed aspect, but I am morally against making junk throw-away code, which frequently happens when speed is in the picture. I even make unit tests! :wink: Accordingly, I won’t ever be on the leader board, but I will at least be able to look at my code later and not feel disappointed in its quality.

I also don’t mind my results so far… they’re not special, but respectable given I am concerned with code quality and testing it before submitting:

10   00:43:05   8481         03:47:41   9505
 9   00:18:14   4661         00:38:26   5342
 8   00:46:48   8571         01:10:05   7105
 7   01:52:36   8453         01:57:46   6367
 6   00:16:45   5961         00:24:04   4513
 5   00:33:17   5909         00:38:19   4989
 4   04:44:50  25293         05:13:20  18830
 3   00:19:35   4706         00:25:19   4011 
 2   00:29:37   5654         00:36:05   5148 
 1   00:33:09   4460         00:42:02   4393

(I edited out all my 0 points… :wink: )

I agree @PHolder - you’re still a lot faster than me.

I’m just in it for the pleasure of coding, and learning how to do it better. I’m not trying to win a race. And I really want to keep the habits I learned from HtDP of test-driven, bottom-up programming.

I’m not just making something you can sit on, I’m making fine furniture. Or trying to anyway!

2 Likes

I totally get that, and I fully admit often writing bad code to get it done fast; but I can always do it again later from scratch with the intention of writing good code. Actually, sometimes I catch myself instinctively writing better code than I need to to get the job done, which I’m trying to not do as much. :laughing:

They’re two separate goals; get answer fast, and write good code to solve the problem. If I thought I could get an answer faster by using a pen and paper and notes that are unreadable five minutes later, I probably would, because that accomplishes the first goal. Then there’s the totally different goal of writing good, maintainable code, with tests. And the other different goal of using the puzzles to learn a new language.

I enjoy all aspects, but I do the speed-coding first because it’s not quite the same to start a clock running on your own later; whereas I can endeavour to write good code at any time. There’s a community aspect to it as well.

What I usually do after speed-coding is hang out in IRC while I clean up my code or solve it from scratch using a better method; also playing with performance optimizations and the like, etc. IRC is usually active for some hours after the puzzle release, depending on its complexity. Lots of smart discussion happens there.

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:

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

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.

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

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.

  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 = 10000000;
    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.

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

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:

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:

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

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

and from part 2:

  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:

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

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:

  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:

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

Now that I think of it. maybe I didn’t need to track the number of times spoken in it’s own hashmap, I might have been able to look to see if it were previously spoken… I will go try that as an improvement after I finish this post…

EDIT: nope, couldn’t figure out a way to make that work.

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”:

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. I’m going to go refactor my code, add unit tests, and then I’ll come back and edit this post with some example code.

EDIT: Well, after much refactoring and unit testing, I have a main() now that I like:

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

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

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:

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

I am so impressed by your mad skillz @PHolder!

Meanwhile, back here on Day 7! I recognized immediately that 6 was just a set union and intersection problem, but I had to learn about sets in Racket to implement it. I’m working fairly leisurely so it took a week or so.

I’m getting the impression that each day uses a well-known algorithm, well, well known to CompSci majors. I am utterly ignorant when it comes to anything past high school – Chinese Remainder Theorem? Really? – but it’s giving me a chance to learn a lot.

Onward to luggage processing!

Ah, you’re both inspiring me! I’m learning python at the moment - first time properly learning to code, though I’ve tried in the past. It’s great to see both @PHolder 's skills and @Leo 's determination to puzzle it out. Maybe next year (or the one after!) I’ll be able to join in…

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 totaly obvious:

  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:

  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:

  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.

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

FWIW, you don’t need the Chinese Remainder Theorem for Day 13. There’s a fairly simple way to do it without using that, which involves an optimization to the naive brute-force solution.