Advent of Code

  • Be sure to checkout “Tips & Tricks”
    Dear Guest Visitor → Once you register and log-in please checkout the “Tips & Tricks” page for some very handy tips!

    /Steve.

  • BootAble – FreeDOS boot testing freeware

    To obtain direct, low-level access to a system's mass storage drives, SpinRite runs under a GRC-customized version of FreeDOS which has been modified to add compatibility with all file systems. In order to run SpinRite it must first be possible to boot FreeDOS.

    GRC's “BootAble” freeware allows anyone to easily create BIOS-bootable media in order to workout and confirm the details of getting a machine to boot FreeDOS through a BIOS. Once the means of doing that has been determined, the media created by SpinRite can be booted and run in the same way.

    The participants here, who have taken the time to share their knowledge and experience, their successes and some frustrations with booting their computers into FreeDOS, have created a valuable knowledgebase which will benefit everyone who follows.

    You may click on the image to the right to obtain your own copy of BootAble. Then use the knowledge and experience documented here to boot your computer(s) into FreeDOS. And please do not hesitate to ask questions – nowhere else can better answers be found.

    (You may permanently close this reminder with the 'X' in the upper right.)

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.
 
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.
 
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;
  }
 
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.
 
Last edited:
@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);
  }
 
PHolder said:
@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.
Click to expand...
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.
 
Paul F said:
I was a bit surprised that the gigantic number it produced on its first run was the right answer.
Click to expand...
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.
 
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());
 
PHolder said:
Remember that everyone gets a unique input. Mine is:
Width=96, Height=98
Click to expand...
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.
 
  • Wow
Reactions: Barry Wallis
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());
 
Day 12. This type of movement on a grid reminded me of this fascinating way to find the real roots of a polynomial:
 
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);
  }
 
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));
    }
 
You must log in or register to reply here.

Similar threads

P
Advent of Code 2022
Replies
0
Views
894
Coding
PHolder
P
P
Advent of Code 2021
Replies
48
Views
6K
Coding
PHolder
P
C
GitHub Copilot on low level code, C and MASM
Replies
0
Views
2K
Coding
coffeeprogrammer
C
C
Can some tell me what is wrong with this MASM code?
Replies
9
Views
3K
Coding
coffeeprogrammer
C
C
C++ straight Windows API Help github code
Replies
4
Views
2K
Coding
coffeeprogrammer
C
Top Bottom
Back