Advent of Code

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

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

    /Steve.
  • Larger Font Styles
    Guest:

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

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

    /Steve.

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
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.
 
Last edited:
  • Like
Reactions: Barry Wallis

miquelfire

I like red!
Sep 26, 2020
42
4
www.miquelfire.red
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)/
 
  • Like
Reactions: Barry Wallis

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
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;
  }
 

Barry Wallis

Magician in Training
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));
 

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
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;
  }
 
  • Like
Reactions: Barry Wallis

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
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;
  }
}
 

Paul F

Member
Sep 17, 2020
23
11
Toronto
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.
 
Last edited:

miquelfire

I like red!
Sep 26, 2020
42
4
www.miquelfire.red
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.
 

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
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]);
  }
}
 
  • Like
Reactions: Barry Wallis

Barry Wallis

Magician in Training
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.
 

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
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;
        }
      }
    }
  }
 
Last edited:

Paul F

Member
Sep 17, 2020
23
11
Toronto
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.
 

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
@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())
 
  • Like
Reactions: Paul F

PHolder

Well-known member
Sep 16, 2020
638
2
313
Ontario, Canada
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;
      }
    }