OK, the first day was awesome, I'm super excited about all of the solutions people posted. And I'm learning a lot! We've got a solid 20 people on...
For further actions, you may consider blocking this person and/or reporting abuse
Python solutions!
part 1
part 2 -- this one feels clunky to me.
My part one ended up looking super similar!
I ended up using
zip
to help with the comparison if the strings in part 2:Nice! Definitely think that's the easiest way to do number 1. Zip also makes sense for the second, though not using it allowed me to do the early return!
True!
10 points for the variable name βthrice!β
As a lispy thinker, my brain wants to tell you to make those for loops into comprehensions, but my work brain is telling me that my coworkers would have me drawn and quartered to make your "find-one-difference" a one-liner!
Kudos on how neat this looks. I find python and ruby to be difficult to make look "clean" when I write it.
Part 1
You can probably see my Python shining through as I implemented a custom Counter struct to help me out.
Part 2
Double for loop boooooooo! But it works and it's fast enough for now. I'm pretty happy with the mileage I got out of Iterators for this part.
This is very well documented and clear, easy-to-read code. This also makes me want to jump into Rust again (I've only hobbied around with it here and there).
Thanks! That really encouraging!
I love how you've used enumerate and skip together in your nested for loop. I struggled to find a clean solution like this.
Thanks! Yeah, I originally had a very manual nested for-loop set up, but after I got the tests passing, I decided to make an effort to do everything I could with iterators instead :) I've decided that the iterator module in Rust is where most of the magic that I'm missing from Python and Ruby lives.
This was still bothering me, but I found the
Itertools
crate and thetuple_combinations
method. Check out my updated solution in the thread.Itertools
makes iterators even more powerful.PHP
Ended up learning about a bunch of useful array functions like
array_values
,array_count_values
andarray_diff_assoc
for this one!Part 1:
Part 2:
Iβm trying to use a broader range of languages than I do usually, so I figured Iβd try not to use one Iβd already used before through the days. I use bash all the time, so I thought Iβd get it out of the way early.
This was not one of my better decisions, but worked fine!
Part 1 uses regular expressions; I could have used an associative array like some other people in the thread, but for some reason I went here first. The sort function wasnβt necessary, but helped with debugging.
Part 2 uses the same double
for
loop lamented elsewhere, but it gets the job done.Neither of these is what Iβd call βfastβ.
Woah, nice! It's always really cool to see bigger things done with Bash :)
P.S. Depending on your Bash version, you can save yourself some typing with
{a..z}
.Oh yes, good call, I missed that compaction.
Clojure (inefficient part 2)
Part 1:
Part 2:
I like the threaded use of
update
here in part 1 - my method used a transient map and returned a persistent copy at the end:Nice one. Is definitely faster than mine.
Javascript lazy solution
I don't have much time to solve the challenges :( So I'm just trying to get the stars.
part 1
Part 2
Thanks for hosting the private leaderboard! Never been on a leaderboard before lol so that'll be fun. :)
I am curious - how is everyone posting their code? Is there a code tag on here, like there is on Slack? Is everyone sharing screenshots? I haven't posted a whole lot on here yet, so I'm not sure of the best way to share code.
I'm using JS this year, so here's my day 2 solutions: not the prettiest / most succinct, but they work!
Part 1:
Part 2:
There's an enhanced form of markdown for code blocks: triple backticks for start and end, and if you immediately follow the opening backticks with the language you get syntax highlighting. Difficult to show raw markdown in markdown unfortunately.
Excellent, thank you! Much better than screenshots. :)
Enjoyed this one. My Kotlin solution:
Were you also annoyed that Kotlin has
.groupBy
but not.frequencies
?Have you thought about looking into
Sequence
? You could make your pairs function lazily? UsingList
means you're materializing the entirety of your double for-loop right away.The lack of
frequencies
didn't bother me - it's easy to add. And yes, I've been thinking for the rest of the day that I should use lazy sequences. In this case the execution time remains O(NΒ²) but as you say the memory footprint becomes more like constant. Definitely a good practice when you can't find a better algorithm.A little late, to the party. I tried really hard to think of a solution to part 2 that only involved iterating the list once, but no luck. Here is my solution in Elixir.
Part one:
Part 2:
So this was a pain. I also ended up with a double loop (O(n2)) and couldn't think of anything better.
One thing I discovered during part two was that Crystal has Levenshtein distance as part of the standard library. It might have been a bit heavy going for what I needed, but it did the trick!
Bring on day 3!
High five for a beefy standard library! Thatβs awesome π
My solution with Python, not sure about the second part, not the most fastest solution I think regarding of performance.
Nice! Donβt forget about collections.Counter for part 1! I didnβt know about difflib though. Cool!
Thanks for the hint! Will do that later!
My edited solution for part one with collections Counter
Part 1: C# + LINQ = one-liner
Part 2
Part 1
Part 2
And from the output, I just copied and pasted the necessary characters that matched. That was faster than comming up with a custom method to do so.
Nice! Did you implement editdistance yourself, or is that an external library?
It is external. I found it via a quick google search. The edit distance measures how many operations - insertion, deletion or substitution - it takes to get from one string to the other. Since all the strings in the puzzle input have the same length, insertion and deletion do not come into play and it works out perfectly.
Ok thatβs cool, just checking. Neat!
Terrible C++ solution for part 1 !
Terrible is better than never finished! And this looks pretty good to me, not knowing C++ if that makes you feel better π
I did my solutions at midnight last night, but I was surviving on very little sleep at the time, so the resulting code was below standard. I tried again this morning and felt better about it.
For anyone reading this, I'm still using the simple
lines
function from Day 1 which reads a file into a sequence of strings.Part 1
This was my solution last night:
This is embarrassing code. I totally forgot about the
frequencies
function, which is why I usedgroup-by
followed bycount
. But the 2filter
operations in the final calculation meant that the results of themap
get processed twice.My morning attempt fixed these:
This time I accumulated the 2/3 count values while processing the list, so it only goes through it once.
Part 2
Since each element needs to be compared to every other element, I can't see any way around the O(n2 ) complexity. Of course, each element should only be compared to the ones after it, so as to avoid comparing each one twice (since comparing A/B has the same result as comparing B/A).
When doing list processing, the only ways I know to refer to everything following an element are by using indexes (yuck) or with a
loop
. Unfortunately, I got fixated on the loop construct, and nested it:The other way you can tell that I wrote this on very little sleep was the use of ridiculously terse var names.
On reflection this morning, I realized that the inner loop should have been a
some
operation. This does a predicate test and terminates processing early, which is what I was doing manually with the innerloop
.Also, my
close
function has several issues. First is the name! I was thinking of "A is close to B", but when I saw it again this morning I realized that it's the same function name for closing a resource. Something else that bothers me is that it processes the entirety of each string before returning, when a false result can usuall terminate early. Finally, a minor issue is that the anonymous function#(when (= %1 %2) %1)
would be more idiomatic to use a singleton set on%1
to compare to%2
.The
nearly=
function now returns a string, rather than the array of characters, but hasn't changed much. I was still unsatisfied with it not terminating the test early, so I rewrote it to be faster. However, the resulting code lacks any kind of elegance, and I'm not convinced that it's worth the effort:Hopefully I'll get some sleep before attempting day 3. π
A bit late to the party, here are my solutions on Ruby:
Part 1:
Part 2:
I learnt about the combination method :)
My solution in JavaScript / Node 11, using the
readline
interface:readLines.js
02a.js
02b.js
My solutions for part 1
Python
Go
Benchmark difference
My solution to day 2, in Elixir. The double for-loop in part 2 is certainly not optimal, but it works. The available time was short today. :)
Part one:
Part two:
Common:
Giving it a go in good ol' JavaScript.
Part 1
First creates an Object to track the # of times a letter appears in a string. That gets converted to a Set to filter out any duplicate values to account for situations where 2 or more letters appeared twice (as the string only gets counted once for the check sum).
Part 2
I struggled with this one, so I'm sure there's a cleaner/more efficient way to do this. This takes each line of the input and compares it to the other lines, checking the characters and tracking the # of differences and the position of the last accounted for difference. The loops are set to break when a result with only 1 difference is found to prevent unnecessary looping.
Part 1 in Ruby:
I enjoyed playing around with the one liner
which produces a frequency chart something like this:
i.e. there are exactly 2 occurrences of the letter s in
str
Part 2 in Ruby
Not happy about the double loop through the input file... but also can't think of a way to avoid it! It occurred to me that sorting the list first might improve the chances of finding a match earlier in the loop since all similar strings would be together, but thinking about it, perhaps there's equal chance that the similar strings would end up being sorted to the bottom of the list and it wouldn't help at all :/
Another thought - many of the input strings are v. similar, maybe they could be grouped into sets early on (e.g. based on the first 4 chars or something) and then you only look for similar strings in the same set?
Going to read into hamming distances now!
I lost about 10 minutes to my son stalling getting into bed.
Kotlin Solution
Answer 1
Once again a fairly straightforward opener. Just run through, do some simple frequency checking and spit back the results. I think this is technically O(n2) but it moved fast enough for me. (And in a more lazy language, it ends up being closer to O(n) anyway)
Answer 2
As Ryan said, this is just Hamming distance with the added wrinkle that you need to throw away the differences while counting them. Lots of optimization room here, but once again, we shave off just under half the possibilities by only doing unique combinations and going from a raw
n^2
to(n*(n+1))/2
.At around 10 ms (calculated by shuffling my input 1000 times), I don't think there's an easy way to make this noticeably faster at this point without a more esoteric method.
Node.js
Common async generator. Read the file in chunk by chunk and yield each product ID based on new lines.
Part 1 was fun with some ES6 array -> Set -> Map to get the value counts
Part 2 got interesting. I needed to generate all pairs for every product ID. I made my Hamming Distance function also return the common letters. Then tied it all together by running each pair through the Hamming Distance function and getting the lowest.
Putting it all together:
Full code here: github.com/MattMorgis/Advent-Of-Co...
Making hamming distance return common letters is a slick way to go. I was looking at the duplication between the hamming distance and common letters functionality in my solution and was a little bummed about it, but I couldn't figure out a good way to do it.
I like this!
Rust
Part 1
Part 2
I'm still searching for a nice iterator adapter to replace the nested loop.I finally used theitertools
crate and it's AMAZING!!!I am using Advent of Code to learn Golang, and here is the solution I came up with. Suggestions for improvements are always welcome!
Part 1:
Part 2:
My idea was to use a dictionary and store the subnames and see if we encounter one we have already visited. Since there should only be one match we can immediately return it. I learned a lot about using maps in Golang!
I am also using Python that I have more experience with to cross check solutions. I have tried to implement it with readability in mind, not performance.
Part 1:
Part 2:
Late to the party!
Still digging F#, but I'm definitely hindered by my lack of familiarity with what's available in .NET
I'm not super thrilled with my Day 2 code, but I haven't really had the time to tweak it with everything going on at work currently.
Swift Solutions
Part 1
This one was fairly simple. Just count how many times each letter appears in each
String
and act appropriately. I do like the fact that a SwiftString
type is really anArray
ofCharacters
.Part 2
This one feels clunky, if I get a chance I'll revisit it.
I break on the first hit for a solution to short circuit everything and return the answer, this can help a lot with so many
Characters
to test.I use
zip(_:_:)
with a filter and count to quickly test how many differences there are in the same positions. When I see two strings that differ by one character in the same position I move to the next step.In the second part I cast the Arrays into
Set
types so that I can use the Collection Algebra features to quickly find the actual character to remove by subtracting one collection from the other. With that done I can just remove it from the sourceArray
and return what's left.Normally I would
import Foundation
here so that I could just useNSOrderedSet
and skip a few steps. I wanted to try and keep it all in the Swift Standard Library though, so I didn't!Here's my C# .Net solution:
I didn't see any C# glancing through:
(Note
AddIfNotNull
is from my extension methods package nuget.org/packages/Kritner.Extensi...Part 2:
I dunno how I'm gonna keep up during the week, but putting my solutions in the repo github.com/Kritner/Kritner.AdventO...
This one was difficult for me, but I eventually got it! I'm also not happy about that double for loop in part 2, but I think I sped it up by removing the elements as I compared them?
github.com/stevieoberg/advent-of-c...
Hosting my solutions on my github...
MustafaHaddara / advent-of-code-2018
Code for https://adventofcode.com/2018/
advent-of-code-2018
Code for adventofcode.com/2018/
I'm trying to learn Julia so I'm using AoC to force myself to learn.
I'm pretty sure part 2 has to be O(n2) but you can cut down on the total number of iterations by only looking forward...here's my solution (implemented in Julia)
Julia's a weird language...it's so close to python that I forget it does weird things like "Arrays are 1-indexed", and it spells
None
/null
asnothing
I agree that Julia is weird, but I actually love it because it adds some functional stuff that I miss in python like the pipe operator!
We need better cover images π
I was kind of hoping that the magical resizing was an automated resizing thing that happens and not one of you guys fixing it for me. I can actually put a background on it and scale it. What are the optimal dimensions? Is the white text on black ok or should I come up with something more fancy? I have very little aesthetic skill, so Iβd appreciate any suggestions you or anyone else has.
Ryan, do you want me to design something? The only hard part is that I probably won't be up at midnight most nights to add specifics. Do you have any design software? If so, I can transfer you a file! We could also use Canva.
That would be amazing! I have a Figma account, but thatβs it. Iβve never heard of Canva and pretty sure I donβt have any design software, but if you tell me the best way to handle it, Iβll happily do whatever you suggest. Iβm happy to learn.
Cool -- sending you a DM via /connect!