Ask HN: What is the most complicated Algorithm you came up with yourself? Hi HN, what was the most complex and sophisticated algorithm you came up with yourself while working on a problem? |
Ask HN: What is the most complicated Algorithm you came up with yourself? Hi HN, what was the most complex and sophisticated algorithm you came up with yourself while working on a problem? |
Portable Two-Way Translator, Handheld
Portable Handheld Translator
Handheld Two-Way Translator
Electronic Two-Way Portable Instant Voice Translator, 40 Languages, Handheld
Based on previous experience with centroid-based algos, the function I wrote does a first pass throwing all words from all product titles into one big bag, then computing a centroid (frequency histogram with low-frequency words removed). The second pass is to compute a cosine similarity score for each product title (its own frequency histogram against the centroid). Whichever product title is the most similar to the centroid wins.
That algo may have existed already in some academic paper somewhere, but I came up with it independently.
One really fun algorithm involved optimizing an n^2 naive tree algorithm to O(n), ignoring logs.
For me, the way I reasoned about it was expanding the number of objects to consider (n^3), then there were observations you could apply to bring it down to O(n).
If you asked me what exactly the correspondence was between the final reduction and the original problem statement, I couldn't tell you. Maybe there was a more direct way to get to the solution.
But that style of thinking carries on with me to real tasks too. Sometimes it's easier to simplify, other times it might actually be easier to complexify, as long as you trust that you're not going down "arbitrary" complexity.
code: https://github.com/aleda145/product_allocation_aframe/blob/m...
I'm not proud of this code, but it yielded 0.2% better result than the naive approach!
Basically I precomputed a table of masks and used the XLAT instruction in a very tight loop to fly though all the product descriptions for everything IBM offered back around 1983. I could accommodate case insensitivity and single character wildcards.
The test search was always "dos tech ref" to find the IBM DOS Technical reference manual.
A thing for storing and comparing schedules
a weekly schedule is turned into a run-length list (the week is in minutes 0 to 10079 - so 540,1020,1980,2460 would be 9am to 5pm on Sunday and Monday). Makes it easy to unpack the list into an array and do basic math comparison can determine whether schedule A is within schedule B or get the difference in minutes that schedule A falls outside of schedule B etc.
I would say the most complicated ones I've done are some SQL queries where I had to break it into stages to reduce the amount of grinding it did on a query that was combining many tables.
A = [2, 7, 1, 8, 28, 18]
sort = A => A.reduce((B, x) => (B[x] = x, B), []).filter(x => x)