Ah, BFS my old friend. I must resist booting up a gremlin database to solve this one.
Day 6 - The Problem
Cool as cucumbers we descend ...
For further actions, you may consider blocking this person and/or reporting abuse
Finally a nice and short one.
My solutions aren't particularly efficient as they involve recursive functions, but still run pretty fast so whatever. ¯\_(ツ)_/¯
Part 1
Part 2
You can find my solutions on GitHub.
Maybe a future node version will add tail call optimization, and Javascript could have efficient recursion again.
Tail recursive functions are so much clearer to me than a while loop... something about walking down to a trivial solution just makes sense. 🤷♀️
I long the day they will tackle the problem once and for all. It's the last thing missing from ES2015! (Only Safari supports it.)
There's got to be some better way to go about it, as even with memoisation it takes about half a minute to sort through part one, but hey, memoisation is cool.
JavaScript
Unsolicited hints from a fellow 2+ minute initial runtime maker:
You're absolutely right. I've changed the approach and with this I managed to reduce the processing time from 43.3 seconds to 2.6:
Part 1 was a no-brainer in clojure:
I kinda got stuck on part 2, so the solution for this isn't really optimal (takes around half a second):
Fun one nonetheless!
(Full code: github.com/jkoenig134/AdventOfCode...)
I am fake upset you didn't break out the clojure zipper library for this! (it's like using a cannon for flies in this case)
Oh, I will definitely look into that, thanks for the suggestion.
I only knew about (tree-seq),
I'm still a newbie in clj.
Zipper is extremely powerful for navigating trees efficiently.
It’s also as easy to read as overly point free Haskell.
I vastly improved it without using zippers now.
I just fetch the first common center of both objects and add the steps it takes to get there for both.
Back to Prolog today but rather than battle with reading the input file in Prolog and turning it into relations, which I have no idea where to begin with, I used a Perl one-liner to turn it into Prolog source code. That's not cheating is it?
Part 1 boiled down to finding all possible paths in the graph and counting them.
Part 2 was more involved but is ultimately a similar algorithm in Prolog, filtering the possible solutions down to a single path between the start and end which does not visit any location twice.
Shortest code for the day?
Since I solved one based on the Josephus Problem by hand once because I had just seen a numberphile video based upon it, it's only cheating (in my book) if someone else figured it out for you.
I don't think it's even cheating looking at someone else's solution, as long as you write your own version instead of copying it. (renaming doesn't count!)
Honestly, Advent of Code is so much fun. This stuff makes me fall back in love with programming.
After a weekend of flu, I'm back in action--albeit about four days behind the pace now. I'll catch up. Here's today's solution in Rust. No BFS for me. Just a hashtable of children, and a (likely inefficient, but good enough) reverse lookup to do some ancestor math.
Interesting and challenging problem today. I went for a parent-to-children map for the first part and a tree for the second. Runs within a couple of milliseconds.
Part 1:
Part 2:
Without embarrassment, I show this code to you. Part 1 takes a few minutes to complete. I will respond with an optimized version later.
Part 2 was my old friend "Djikstra's Algorithm". It wasn't enough data to warrant breaking out A*Search, but if previous years are any indication we will probably need it at some point.
Ahhh... much better. This runs in msecs.
I liked that the explanation was much easier to understand today. I'm pretty happy with this one.
Solution for part two, in Elixir.
Here's part one
Javascript solution w/ Graph implementation
Day dusted with swift
A Python solution (also see github.com/devChad/advent_of_code)
Lots of recursive functions...
Bit late to the party on this one. With good reason, but also I kept making mistakes with how to add up the jumps.
Got there eventually.
Part 2 first:
Part 1 had the following code in place of the number of jumps calculation:
Late here, but as I am doing 2019 AOC now (yes, nearly 3 years later), and I noticed there was no
C
solution for this one here, I have one here.Nothing special there, as the two parts are trivial after the tree has been built, and you get a way to find existing nodes by name (mainly to build tree). For that, instead of an usual hash-table, I decided to go for a
trie
structure. Don't ask me why ;-)A javascript walkthrough. I was happy to have coded the part 1 in a clean way because it helped me a ton for the part 2!