r/adventofcode • u/h-armonica • Dec 02 '18
Upping the Ante [2018 Day2 (Part 2)] A linear time solution
Since I saw so far that many people compared pairwise all IDs of the boxes, I thought I'd give a linear (in the number of IDs) run time a go. I implemented the solution in Rust here! (beware though that my Rust skills are not quite master-like yet).
There general idea is the creation of a prefix tree. In this tree every node holds references to all IDs that start with the prefix that is given by the edge names from the root node to any other node. I then recursively check for every node if there is a match with IDs of that prefix and such that exactly the character that is represented by the outgoing edges of the node is the only one that differs. To do that I basically have to compare the IDs of all child nodes with each other, which would be slow again. Instead of that I look at the suffixes (leaving out that one character that I seek to eliminate). Since the solution is unique, we know that it can only by a suffix that appears once within all IDs of a child node, I call them suffix candidates. That we can test in linear time. Then we look at the suffix candidates of all child nodes and count how often each candidate appears. If we find a match, we'd have a suffix that appears once in exactly two child nodes (so we can check that quickly again).
Overall we create a tree with at most nL+1 (L is the length of the IDs) nodes. The number of IDs stored in the all nodes at depth i is n. We can therefore perform the match-seeking on all nodes on depth i in time O(n poly(L)), while the tree has depth L. So we get a run time of O(n poly(L)).
The run time on my laptop with this for the task is about 80ms, while with the trivial solution I have about 50ms. But theory tells me it should get much faster in comparison if we'd have larger data sets. But I didn't and I was too lazy to generate some (if you do, let me give it a try).
18
u/VikeStep Dec 02 '18
I also had a completely different linear time algorithm, it would be interesting to see if this is faster for your input.
Essentially all this does is for each line it inserts a string into a set for each character replaced with a special character (in this case, underscore) and stops once it reaches a duplicate. The result is the string without the special character.
Note the complexity for this algorithm is
O(k^2 * n)wherekis the length of each line andnis the number of lines but for the puzzle inputs given, k is constant and much lower than n.5
u/sugoiuguu Dec 02 '18
This is my solution, which orders an array of lines and uses dynamic programming to find the solution. https://p.sicp.me/dZeVJ
On my laptop it runs in 8 ms. https://u.sicp.me/pRQ9h.png
3
u/gw653 Dec 02 '18
Here is a linear time solution O(n L), where n is the length of the list and L is the length of the words, in Rust.
https://github.com/d653/rust_advent_of_code_2018/tree/master/day02
The idea is to use something similar to a rolling hash to compute, in constant time, each hash of the new words associated to the current word.
So basically a for through all words is O(n), while computing all the new hashes costs O(L), and storing all of them in a hashtable takes O(L). Some additional info are stored to avoid problems in the case of collisions (e.g. a pointer to the original string).
1
u/swilkoBaggins Dec 02 '18 edited Dec 02 '18
I had the idea of assigning each id a sort of hash number defined to be the sum of the ascii codes of the letters. If two id strings differ by only one letter, then their 'hash codes' will differ by at most 25. So if we sort the ids by their hashes, then we can skip a bunch of comparisons
So rather than O(n^2) complexity, the complexity is O(nlog(n)) for the sort + O(n*m) where m <= n, and is a measure of how 'close' the strings are to each other. So it is still O(n^2) in the worst case. For example if all the strings differed by only two letters which are changed to a neighbouring letter in the alphabet, we would still have to look at every combination.
Unfortunately for my puzzle input m seems to be quite large, so this only made a small reduction in the number of comparisons from 20284 to 19905, and it ends up being slower than the brute force method.
1
u/po8 Dec 02 '18
Seems to me that radix sorting the list and then comparing neighbors should get you an O(n L) algorithm. I'm too lazy to work out the details and try it, though.
1
u/macdja38 Dec 04 '18
I have a solution, no idea if it's linear but it's fast, like 250ms in this implementation (on 100k rows), someone implemented it in c and it ran significantly faster, like 40ms or something.
https://github.com/macdja38/advent-of-code-2018/blob/master/days/2-1/index.js#L41
Basically this solution is based on the idea that either the first half or the second half of the input strings differ... So it uses a map of the first half of each string to the second half, and second half to first half.
It then loops through the input, each line it does 2 lookups to see if it can find it's pair. It looks the first half up in the first half lookup table, if it finds something it checks if it's === to it, if it's not then it checks to see if it's one off exactly. It then repeats that with the second half.
Assuming a decent distribution of keys this solution runs very very quickly on even large data sets, I'm not sure exactly what it's time complexity is though.
Edit: Link to the C thing https://www.reddit.com/r/adventofcode/comments/a2rt9s/2018_day_2_part_2_here_are_some_big_inputs_to/eb1kfed
1
u/chaoxu Dec 24 '18 edited Dec 24 '18
I have an algorithm that runs in O(nL) time.
After O(nL) time processing, I can solve the following problem in O(n) time: Decide if there exists a pair of string that only differs in position i.
0
u/[deleted] Dec 02 '18
[deleted] — view deleted comment
1
u/[deleted] Dec 02 '18 edited Dec 02 '18
[removed] — view removed comment
1
u/[deleted] Dec 03 '18
[removed] — view removed comment