Year2015::Day01
Part 1
gives a final result
Part 2
gives a final result
Results
correctly answers part 1
correctly answers part 2
Ruby's String class is very well-furnished, even without all of Rail's ActiveSupport goodness. In that case, just using #count() is enough to get us out of trouble quickly.
I am pretty sure there must be an algorithm that doesn't include iterating through the whole string, but so far, the only idea I got would be to use bisecting until I get to the proper index, which just felt like a hassle.
Year2015::Day02
Part 1
gives a final result
Part 2
gives a final result
Results
correctly answers part 1
correctly answers part 2
I..am not even sure this one was complicated in any way.
Year2015::Day03
Part 1
gives a final result
Part 2
gives a final result
Results
correctly answers part 1
correctly answers part 2
The only thing to be wary of is on line 16: without the call to #dup, all of Santa's and Robo-Santa's positions will be overwritten, since Ruby's object model has a tendancy to pass references when you expect to pass values.
Passing by value or reference is a really wonky subject, but this blog post got nice examples that will get you started.
Year2015::Day04
when Part 1
gives a final result
when Results
correctly answers part 1
correctly answers part 2 (PENDING: Test is too slow for CI)
Not gonna lie, brute-forcing MD5 hashes is not something interesting.
Year2015::Day05
Part 1
finds nice lines
finds naughty lines
Part 2
finds nice lines
finds naughty lines
Results
correctly answers part 1
correctly answers part 2
Again, Regexp really are one of the best tools in your developer arsenal. In this specific exercise, we can look for repetition by using \1, which will reference a previously-captured group. Nothing specifically hard beyond that.
Year2015::Day06
Part 1
gives a final result
Part 2
gives a final result
Results
correctly answers part 1
correctly answers part 2
This one actually gave me SOME trouble. My first solution was iterating on each element one by one and was clearly too long. Thanksfully, Ruby is really smart when it comes to replacing slices of an array.
There is an even more beautiful solution for part 2 that consist of only tracking the total numbers of flicks on/off/toggle, but in the off chance that a light already off is turned off again, the results would become false.
Also of note: remember what was discussed earlier about references? Well, the documentation covers that too. Quote:
Note that the second argument populates the array with references to the same object. Therefore, it is only recommended in cases when you need to instantiate arrays with natively immutable objects such as Symbols, numbers, true or false.
To create an array with separate objects a block can be passed instead. This method is safe to use with mutable objects such as hashes, strings or other arrays:
Year2015::Day07
Part 1
assigns values to wires
Results
correctly answers part 1
correctly answers part 2
We already discovered bitwise operators in the previous exercises, so that shouldn't be too hard. The complication comes from building the wires.
The naive implementation, that works very well with the sample input, consists of interpreting each line one by one, storing the value of each wire every time. Unfortunately, not all inputs are indicated in a linear way.
The answer lies in to store all wires, setting up operations with lazy evaluation, and letting intepretation work itself all the way back.
Year2015::Day08
Part 1
calculates data length of code
calculates data length in memory
gives a final result
Part 2
calculates data length of dump
gives a final result
Results
correctly answers part 1
correctly answers part 2
Understanding how characters escaping works is a massive PAIN, and misunderstand the concept is a reason why PHP MySQL injections were so infamous. Things get even more hairy when you have to work with MULTIPLE type of injections (paths, web, sql,...), or even multiple types of string that don't escape the same way,
In that case, we are lucky, since Ruby already implements dump and undump, which happens to work exactly as the exercise require. But since we're here to learn, the methods will alternate at runtime between the Ruby methods and the manual implementation.
Year2015::Day09
Part 1
gives a final result
Part 2
gives a final result
Results
correctly answers part 1
correctly answers part 2
Any programming school worth its salt will one day ask of you the shortest path between many points. Often, the idea is that you'll use graph theory and implement Dijkstra's algorithm. Sometimes, the school wants your brain for dinner and you'll be asked to further solve the Travelling Salesman Problem. Both are very interested concepts in themselves, and a good first approach to PathFinding.
If you're not fond of graph transversal, the best answer is often to start using the A* (A-Star) algorithm to iterate through all possible paths.
You can then optimize it, for instance instructing the algorithm to stop searching once it's on a path longer than a previously explored one.
As for finding the "longest path"...just imagine you're not looking for a "shortest" or "longest" path, but a "best" path, and change how that path is selected among others.
Year2015::Day10
Part 1
iterates each look-and-say
Results
correctly answers part 1
correctly answers part 2
This exercise is based on John H. Conway's Look-and-say sequences, you probably know him for the Game of Life, but the mathematician provided us with lot of science.
Nothing really hard in this exercise, except complexity quickly running high, it becomes important to use the best algorithm to generate the next sequence.
Year2015::Day11
Part 1
checks first criteria (three straight letters)
checks second criteria (no i/o/l)
checks third criteria (two different pairs)
gives a final result
Results
correctly answers part 1
correctly answers part 2
Another exercise that is actually quite simple when you don't have to account for PERFORMANCE: the complexity in this exercise can quickly become huge and it's important that each of your iterations is as fast as you can. A good tool for that is using Ruby's built-in Benchmark class to compare which of two implementations is the fastest.
Another thing to do is to use heuristics and pre-sanitization: in this exercise, you don't need to iterate and test from iaaaaaaa to izzzzzzz.
Year2015::Day12
Part 1
counts the value of the JSON data
Part 2
counts the value of the JSON data
Results
correctly answers part 1
correctly answers part 2
That day looked so easy that I could not believe my eyes when I solved it in a simple one-liner: 3.0.0 :001 > pbpaste.scan(/-?\d+/).map(&:to_i).inject(&:+).
The second part is a bit more convoluted, but navigating JSON nodes isn't really a pain, you either have a Hash (explore), an Array (explore), or a value (return). Nothing too hard so far.
Year2015::Day13
when Part 1
gives a final result
when Results
correctly answers part 1
correctly answers part 2
Again, refer to Day 09 because we are in a similar configuration, with the exception that we must rejoin our starting point at the end. Nothing too complicated.
Second part is just adding another node with a 0 relationship to all nodes. Surprisingly, it seems our presence lowered the general happiness...
Year2015::Day14
when Part 1
gives a final result
when Part 2
gives a final result
when Results
correctly answers part 1
correctly answers part 2
This day doesn't have complicated concepts. If you want to dig, you can think of each reindeer as a finite-state machine, which is one of the concepts that are best solved thanks to Object-oriented programming.
Year2015::Day15
when Part 1
gives a final result
when Part 2
gives a final result
when Results
correctly answers part 1
correctly answers part 2
Is there a day where you don't have to iterate through all possible solutions?
I am (partly) joking. I am pretty sure there must be a way to solve n-sided equations, but quite frankly, there's a reason I've always thought of programming as "languages" and not "mathematics". Again, the best thing we can do to avoid an O(n*n) complexity is finding ways to avoid calculations we know will result in a 0 anywhere.
So far, I mainly used loops and other control flow structures, but I decided to go with an Enumerator for this one. No specific change or speedup, but it's the kind of structure we should think of building more often, as Enumerable is the class that made me fall in love with Ruby.
Year2015::Day16
when Results
correctly answers part 1
correctly answers part 2
See, when I say Ruby's Enumerable is the perfect, this is the kind of problems I'm talking about.
Year2015::Day17
when Results
correctly answers part 1
correctly answers part 2
Nothing really complicated here, or that we haven't seen yet.
Year2015::Day18
when Part 1
is correct after one step
is correct after two steps
is correct after three steps
is correct after four steps
gives a final result
when Part 2
is correct after one step
is correct after two steps
is correct after three steps
is correct after four steps
is correct after five steps
gives a final result
when Results
correctly answers part 1
correctly answers part 2
I already touched upon Conway's Game of Life earlier, and this exercise is a good example of it.
I thought I was being smart by only keeping track of positions of only ON lights, which was a good implementation for a six-by-six data set, but proved UTTERLY SLOW on the final data set. Using an array of strings (as is the most naive implementation) is indeed the fastest way to do it. I still kept the old code commented.
Year2015::Day19
when Part 1
calculates all permutations
gives a final result
when Part 2
gives a final result
when Results
correctly answers part 1
correctly answers part 2
Part one is nothing to write home about. However, part two... First idea was the good ol' bruteforce approach, but when searching if there was an algorithm I didn't know, I stumbled upon a very interesting Reddit comment...
Year2015::Day20
when Part 1
gives a final result
when Results
correctly answers part 1
correctly answers part 2
I've had to calculate list of primes and divisors in the past, and it always sucked. My previous algorithms were correct but always too long (but what is "long" when you're nearing infinity?).
Again, outside help is a great resource to find algorithms better than yours.
Year2015::Day21
when Results
correctly answers part 1
correctly answers part 2
...really nothing to say here.
Year2015::Day22
when Results
correctly answers part 1
correctly answers part 2 (PENDING: Does not work properly)
"Any sufficiently advanced bruteforce is indistinguishable from Dijkstra's algorithm"
As for this exercise, a key lesson is: make commits BEFORE you rewrite your code. In that occasion, rewriting my code made it unworkable, no matter how many times I tried, and I must have made the same input mistake many times because my second day results were always off by twenty, even when carefully copying an algorithm that works. In the end, it all boiled down to an off-by-one error.
Year2015::Day23
when Part 1
gives a final result
when Results
correctly answers part 1
correctly answers part 2
We are not Turing complete yet, but learning to write a virtual machine is always a fun exercise to understand how computers work.
As a small bonus on this exercise, instead of re-interpreting each instruction as they come, which can be costly on the long term, I used an approach similar to Ahead-of-time compilation to have all my instructions in machine code Ruby code and ready to reuse as needed.
That said: make sure you ALWAYS read the exercise WORD. BY. WORD. Because if jie means "jump-if-even", it does not mean jio will mean "jump-if-odd".
Year2015::Day24
when Part 1
gives a final result
when Part 2
gives a final result
when Results
correctly answers part 1
correctly answers part 2
While this looks like YABA (Yet Another Bruteforce Algorithm), Ruby's got a very useful #combination method that will generate permutations around for you. And of course, knowing when to exit the loop at the best time is half the battle.
Year2015::Day25
when Part 1
gives a final result
when Results
correctly answers part 1
You could solve this one by calculating each number one-by-one, cell-by-cell,... Or you could use modular exponentiation.
If you're careful, you will quickly understand that your operation will at some point look like STARTER * MULT % MODULO * MULT % MODULO etc..., and that once you know how many cells you need to iterate through, you can just repeat the * MULT % MODULO part.
Not being a math nerd at all (I've learned to talk to machines, not to numbers), the subject was completely lost on me, but here is some help: the modulo operation itself is very funny: once you apply it once, you don't need to repeat it, since it would just end up on the same number. So you can just repeat the multiply operation many times (isn't that a "power" operation?) and apply the modulo only once.
How about this:
> 9999 * 18 % 7 * 18 % 7 * 18 % 7 * 18 % 7 * 18 % 7 * 18 % 7 * 18 % 7 * 18 % 7
=> 6
> 9999 * 18 * 18 * 18 * 18 * 18 * 18 * 18 * 18 % 7 % 7 % 7 % 7 % 7 % 7 % 7 % 7
=> 6
> 9999 * 18 * 18 * 18 * 18 * 18 * 18 * 18 * 18 % 7
=> 6
> 9999 * 18**8 % 7
=> 6
Now, I got it, and so do you. Merry Xmas!