Just a few short hours before Advent of Code 2020 opens up. Time to get out your copy of The Art of Computer Programming and read up! (Kidding, that’s a massive amount of reading, but they are great books.)
Well this is an inauspicious start… the site went through 502 Bad Gateway, 504 Gateway Timeout and finally 503 Service Temporarily Unavailable right at the start… I guess interest is very high!
I bet there are a lot of programmers who have extra time this year!
1 Like
Finished Day 1! 
Not too bad of a problem, but they, as usual, have designed the problem to prevent you from wanting to brute force it (using combinatorics.) For part one I simplified the problem by using a hashset. For part two I had to refactor part one and then have the solution finder for part two use part one.
I brute forced it, I confess. Pretty easy using recursion. And, like you, I repurposed part one in part two. I’m not getting my hopes up, though. It always starts easy!!
This is not a complete solution, because I encapsulated the reading of the numbers and whatnot, but in case you were curious to see my Java solution, here’s the bulk of it (missing the number manager and the unit tests.)
final class FindNumbers
{
public static boolean findTwoNumbersThatSumTo(final ListOfNumbers listOfNumbers, final int desiredSum, final int[] result)
{
final int[] nums = listOfNumbers.getNumbers();
for (final int n: nums)
{
final int diff = desiredSum - n;
if (listOfNumbers.doesListContain(diff))
{
result[0] = n;
result[1] = diff;
return true;
}
}
return false;
}
public static boolean findThreeNumbersThatSumTo(final ListOfNumbers listOfNumbers, final int desiredSum, final int[] result)
{
final int[] nums = listOfNumbers.getNumbers();
for (final int n: nums)
{
final int diff = desiredSum - n;
if (findTwoNumbersThatSumTo(listOfNumbers, diff, result))
{
// result[0] and result[1] filled in by findTwoNumbersThatSumTo()
result[2] = n;
return true;
}
}
return false;
}
}
Mine’s almost exactly the same - except using recursion instead of iteration. Same idea though.
#lang racket
; --- Day 1: Report Repair ---
;
; Before you leave, the Elves in accounting just need you to fix your expense report (your puzzle input); apparently, something isn't quite adding up.
;
; Specifically, they need you to find the two entries that sum to 2020 and then multiply those two numbers together.
;
; For example, suppose your expense report contained the following:
;
; 1721
; 979
; 366
; 299
; 675
; 1456
;
; In this list, the two entries that sum to 2020 are 1721 and 299. Multiplying them together produces 1721 * 299 = 514579, so the correct answer is 514579.
;
; Of course, your expense report is much larger. Find the two entries that sum to 2020; what do you get if you multiply them together?
;
;
;; provided by AOC:
(define list-of-entries (file->list "input1.txt"))
(define LOE1 (list 1721 979 366 299 675 1456)) ; example given
(define LOE2 (list 1 2 3 2010 5 5 10))
;; Integer (list-of Integer) -> (list-of Integer)
;; produces the first pair of Integers in a list of Integers that add up to the base value
;; if no such pair exists, return #false
(define (find-pair base loe)
(cond [(empty? loe) #false]
[else
(local [(define testnum (- base (first loe)))
(define testres (member testnum (rest loe)))]
(if testres
(list (first loe) (first testres))
(find-pair base (rest loe))))]))
(module+ test
(require rackunit)
(check-equal? (find-pair 2020 LOE1) (list 1721 299))
(check-equal? (find-pair 2020 LOE2) (list 2010 10)))
(define pair-of-entries (find-pair 2020 list-of-entries))
(printf "AOC Problem 1.1 = ~a\n"
(* (first pair-of-entries) (second pair-of-entries)))
; The Elves in accounting are thankful for your help; one of them even offers you a starfish coin they had left over from a past vacation. They offer you a second one if you can find three numbers in your expense report that meet the same criteria.
;
; Using the above example again, the three entries that sum to 2020 are 979, 366, and 675. Multiplying them together produces the answer, 241861950.
;
; In your expense report, what is the product of the three entries that sum to 2020?
;; Integer (list-of Integer) -> (list-of Integer)
;; Given a list of Integers, produces the first triplet that adds up to the base
(define (find-triplet base loe)
(cond [(empty? loe) #false]
[else
(local [(define newbase (- base (first loe)))
(define testres (find-pair newbase (rest loe)))]
(if testres
(list (first loe) (first testres) (second testres))
(find-triplet base (rest loe))))]))
(module+ test
(check-equal? (find-triplet 2020 LOE1) (list 979 366 675))
(check-equal? (find-triplet 2020 LOE2) (list 2010 5 5)))
(define triplets (find-triplet 2020 list-of-entries))
(printf "AOC Problem 1.2 = ~a\n"
(* (first triplets) (second triplets) (third triplets)))
Day 2 now done. It wasn’t too bad really. The biggest effort for me was parsing the input, the rest is quite straightforward I would say.
Yeah just finished it myself. I’m pretty comfortable with regular expressions so the solution seemed obvious.
I think I get bogged down when the solution requires patterns and techniques I’m less familiar with. Then I have to do a lot of research to figure out how to do it. Of course that’s why I’m tackling AoC: to broaden my knowledge of coding patterns. Each year I get a little better!
Knowing Eric Wastl uses perl is a bit of a help - the problems tend to focus on perl’s strengths (like regex).
Waiting for Day 3 in 30 minutes - I’ll probably be up late again!
And day 3 done! It was straightforward read the data, represent it in an addressable way and remember to use a mod on the horizontal “address” so that you can treat the base map as repeating horizontally. And of course having a good design (the least hard coding) in part 1 so you could easily reuse it for part 2.
The high level structure of my solution:
final TreeField tf = new TreeField(FILE);
final TreeFieldTraverser tft = new TreeFieldTraverser(tf, 3, 1);
final int count = tft.getNumberOfTreesEncounteredWhenStartingAt(0);
System.out.println("Number of trees in path: " + count);
final TreeFieldTraverser tft1 = new TreeFieldTraverser(tf, 1, 1);
final TreeFieldTraverser tft2 = new TreeFieldTraverser(tf, 3, 1);
final TreeFieldTraverser tft3 = new TreeFieldTraverser(tf, 5, 1);
final TreeFieldTraverser tft4 = new TreeFieldTraverser(tf, 7, 1);
final TreeFieldTraverser tft5 = new TreeFieldTraverser(tf, 1, 2);
...
Wow, you’re fast. Just looked at the problem. Oh boy. Not going to look at your solution yet! I think I can represent it with a series of lists (in Racket everything is a list! In Java, everything is an array!)
UPDATE: I went to bed thinking about the problem and realized it was pretty simple. If I were using Python I’d be long done, but I’ve seldom used Racket’s iterators (generally preferring recursion) and so I’ve spent some time struggling with it. I’m being stubborn. I should probably just write it in Python!
Wrestled the iterators to the ground! And I’m pleased to say I guessed right about the changes in part two so it was easy to adjust.
Total CPU time to solve both: less than one tick!
;; AoC 2020 - Problem 3
;; Leo Laporte, 12/3/2020
;; racket 7.9
#lang racket
;; provided by AoC:
(define INPUT (file->lines "input3.txt"))
(define X-SLOPE 3)
(define Y-SLOPE 1)
(define RUN0 (list
"..##......."
"#...#...#.."
".#....#..#."
"..#.#...#.#"
".#...##..#."
"..#.##....."
".#.#.#....#"
".#........#"
"#.##...#..."
"#...##....#"
".#..#...#.#")) ; example given
;; List Integer Integer -> Integer
;; Given a run and slope returns the number of tree hits
(define (go-sledding run x y)
(local [(define slope-width (string-length (list-ref run 1)))
(define slope-height (length run))
(define max-width (* slope-width slope-height))]
(for/sum ([row (in-range y slope-height y)]
[col (in-range x max-width x)])
(if (tree? (list-ref run row) (modulo col slope-width))
1
0))))
(module+ test
(require rackunit)
(check-equal? (go-sledding RUN0 X-SLOPE Y-SLOPE) 7))
;; String -> Boolean
;; Produces true if the string at position p contains a tree ("#")
(define (tree? str p)
(equal? "#" (substring str p (add1 p))))
(module+ test
(check-equal? (tree? ".###...#.#.##..###..#...#...#.." 4) #false)
(check-equal? (tree? ".###...#.#.##..###..#...#...#.." 3) #true))
(time (printf "AOC Problem 3.1 = ~a\n" (go-sledding INPUT X-SLOPE Y-SLOPE)))
; --- Part Two ---
(time (printf "AOC Problem 3.2 = ~a\n" (* (go-sledding INPUT 1 1)
(go-sledding INPUT 3 1)
(go-sledding INPUT 5 1)
(go-sledding INPUT 7 1)
(go-sledding INPUT 1 2))))
;; Welcome to DrRacket, version 7.9 [3m].
;; (on Dell XPS 9300 i7/16 GB running Manjaro Linux 5.9.11)
;; Language: racket, with debugging; memory limit: 128 MB.
; AOC Problem 3.1 = 280
; cpu time: 1 real time: 1 gc time: 0
; AOC Problem 3.2 = 4355551200
; cpu time: 1 real time: 1 gc time: 0
Done day 4. I fell asleep waiting for midnight, and woke up at like 4am. It is mostly just data validation. Hopefully you design part 1 to allow part 2 to be grafted in easily.
Here’s my highest level code:
final PassportDataReader pdr = new PassportDataReader(FILE);
int numberOfPassports = 0;
int numberOfValidPassports1 = 0;
int numberOfValidPassports2 = 0;
while (pdr.isMoreInput())
{
final PassportData pd = pdr.readNextPassportDataGroup();
numberOfPassports++;
if (pd.areAllRequiredFieldsPresent())
{
numberOfValidPassports1++;
if (pd.isValidPassport())
{
numberOfValidPassports2++;
}
}
}
System.out.println("Number of passports: " + numberOfPassports);
System.out.println("Number of valid passports 1: " + numberOfValidPassports1);
System.out.println("Number of valid passports 2: " + numberOfValidPassports2);
I haven’t started Day 4 but it looks pretty simple. I feel like this year has started out a little easier than previous years. I’m actually optimistic I might get past Day 5 this time!
Day 5 is done. It’s basically a little binary search disguised as a boarding pass “parsing” problem. For the 2nd part, I didn’t do anything fancy, I just used a simple array of the size of the part 1 answer, and then just dumped out the empty spots, there was only one high one, and that was the answer.
Key Code:
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;
}
I’m still stuck on 4. It would be easy in Python, but I’m trying to stay with idiomatic Racket and even just the loading of the data is baffling me. fold and map aren’t cooperating.
Day 6 felt very much like day 4 or day 5. I reused my reader from day 4 and then just used a set for part 1 and a hashmap for part 2. Based on last year, I really expected these to be harder than they’ve turned out to be so far… in fact they’re kind of boring so far this year.
Here’s the key class I built to do the work:
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)
{
for(final char c: "abcdefghijklmnopqrstuvwxyz".toCharArray())
{
numberOfTimesQuestionsAnswered.put(c, 0);
}
numberOfPeople = lines.length;
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;
}
}
@Leo I don’t think you’re going to like Day 7 much. It needs string parsing, and then you need to build some structure with the parsed data that can help you answer the two questions for the two parts. You’ll probably want some sort of a tree data structure to represent the rules. The answers will be a couple of different ways to walk the tree recursively.
As it happened for me, I didn’t initially fully absorb the question asked in part one, and designed the answer for part two before I realized it wasn’t the answer I needed. I just assumed it would be the part two answer, and let it be. Turns out I made a lucky (and probably somewhat obvious) guess, and doing part 2 didn’t take me more than a minute as I did a minor reconfiguration of my code.
I spent more time than I should have on the regex parsing of the input rules. I wanted Java to collect all the various parts into different group()s but that’s not how it works with you have a repeat (plus sign or star.) In the end I just split the parts out on the commas and then re-parsed them with a much simplified regex. Lesson learned for next time, I guess. (That is why we’re doing these after all, is to learn for next time, right?)
Anyway, here’s my key class:
I could have built a “proper” tree with parent and child pointers and all that, but I figured I could be more efficient for this problem if I just used Map and Set. I used a class to represent a rule from the file, that contains the outer bag name and the allowed contents, if any. The allowed contents is represented by another class that stores the number of bags and the bag name. There is plenty of recursion here, of course, because the problem is pretty much defined by it.
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]);
}
}
Ugh I’m way in the back of the pack. I just finished the first star on day 4(!) and I’m not proud to admit that I had to get some help. Having said that I’m definitely learning some great new techniques in Racket! See you in a few weeks!!
Day 8 brings back IntCode from last year, more or less. Part 2 poses an interesting challenge, which I brute forced, but there exist solutions that don’t have to, apparently. I would say that overall it’s fairly straightforward to do part one, he basically guides you to use an array for each instruction counting the number of times that instruction gets executed. You know you have an infinite loop as soon as any instruction would be executed a second time, so you just need a method to run the program and return a boolean indicating whether the program terminates or goes into an infinite loop (i.e. starts to execute any instruction for the second time.)
Here’s my main method, which uses classes that should have fairly obvious implementations:
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;
}
}
}
}
Day 9 is number processing in the guise of a secret code or something.
For part one you need to craft a FIFO of size 25. Then you need to iterate over the values within the FIFO to find two of them that sum to the next data from the input. A simple double nested loop, that makes sure to exclude the case were the indexes are same for the inner and outer loop will suffice.
For part 2 you will need the ability to make FIFOs of various sizes that have the ability to sum all the numbers in the FIFO. (You can do a minor optimization to keep this value up to date as you add to the FIFO (and kick the oldest value out.)) Start with a FIFO of size 2, which is the minimum according to the instructions, and iterate it larger until you find the sum in the FIFO that matches the value from part 1. You then need to run a loop over all the values in the FIFO to find the min and the max and add them as the answer for part 2.
This is my key code for part 1:
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;
}
}
and this is the add-on for part 2:
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());
break;
}
}