For me, CP-SAT is the "dumb" solution that works in a lot of situations. Whenever a hackathon has a problem definable in constraints, that tends to be the first path I take and generally scores top 5
Ask HN: When has a "dumb" solution beaten a sophisticated one for you?
11–20 of 73 posts
Re: Ask HN: When has a "dumb" solution beaten a sophisticated one for you?
#12I recently wrote a command-line full-text search engine [1]. I needed to implement an inverted index. I choose what seems like the "dumb" solution at first glance: a trie (prefix tree). There are "smarter" solutions like radix tries, hash tables, or even skip lists, but for any design choice, you also have to examine the tradeoffs. A goal of my project is to make the code simpler to understand and less of a black box…
What body of knowledge (books, tutorials etc) did you use while developing it?
Re: Ask HN: When has a "dumb" solution beaten a sophisticated one for you?
#13I recently wrote a command-line full-text search engine [1]. I needed to implement an inverted index. I choose what seems like the "dumb" solution at first glance: a trie (prefix tree). There are "smarter" solutions like radix tries, hash tables, or even skip lists, but for any design choice, you also have to examine the tradeoffs. A goal of my project is to make the code simpler to understand and less of a black box…
What body of knowledge (books, tutorials etc) did you use while developing it?
Before I started the project, I was already vaguely familiar with the notion of an inverted index [1]. That small bit of knowledge meant that I knew where to start looking for more information and saved me a ton of time. Inverted indices form the bulk of many search engines, with the big unknown being how you implement it. I just had to find an adequate data structure for my application.
To figure that out, I remember searching for articles on how to implement inverted indices. Once I had a list of candidate strategies and data structures, I used Wikipedia supplemented by some textbooks like Skiena's [2] and occasionally some (somewhat outdated) information from NIST [3]. I found Wikipedia quite detailed for all of the data structures for this problem, so it was pretty easy to compare the tradeoffs between different design choices here. I originally wanted to implement the inverted index as a hash table but decided to use a trie because it makes wildcard search easier to implement.
After I developed most of the backend, I looked for books on "information retrieval" in general. I found a history book (Bourne and Hahn 2003) on the development of these kind of search systems [4]. I read some portions of this book, and that helped confirm many of the design choices that I made. I actually was just doing what people traditionally did when they first built these systems in the 1960s and 1970s, albeit with more modern tools and much more information on hand.
The harder part of this project for me was writing the interpreter. I actually found YouTube videos on how to write recursive descent parsers to be the most helpful there, particular this one [5]. Textbooks were too theoretical and not concrete enough, though Crafting Interpreters was sometimes helpful [6].
[1] https://en.wikipedia.org/wiki/Inverted_index
[2] https://doi.org/10.1007/978-3-030-54256-6
[3] https://xlinux.nist.gov/dads/
[4] https://doi.org/10.7551/mitpress/3543.001.0001
Re: Ask HN: When has a "dumb" solution beaten a sophisticated one for you?
#14Earlier quoted context omitted.
What body of knowledge (books, tutorials etc) did you use while developing it?
Before I started the project, I was already vaguely familiar with the notion of an inverted index [1]. That small bit of knowledge meant that I knew where to start looking for more information and saved me a ton of time. Inverted indices form the bulk of many search engines, with the big unknown being how you implement it. I just had to find an adequate data structure for my application. To figure that out, I remembe…
Thanks for detailing, how much time you invested in it?
Re: Ask HN: When has a "dumb" solution beaten a sophisticated one for you?
#15Earlier quoted context omitted.
Before I started the project, I was already vaguely familiar with the notion of an inverted index [1]. That small bit of knowledge meant that I knew where to start looking for more information and saved me a ton of time. Inverted indices form the bulk of many search engines, with the big unknown being how you implement it. I just had to find an adequate data structure for my application. To figure that out, I remembe…
Thanks for detailing, how much time you invested in it?
I spent around 170 hours on this so far, with only 60% of that being coding. The rest was mostly research or writing.
Re: Ask HN: When has a "dumb" solution beaten a sophisticated one for you?
#16I remember Scalyr, at least before they were bought by SentinelOne basically did parallel / SIMD grep for each search query and consistently beat data that was continually indexed by the likes of Splunk and ElasticSearch.
They had a great article on this too.
Re: Ask HN: When has a "dumb" solution beaten a sophisticated one for you?
#17When I was on Google Docs, I watched the Google Forms team build a sophisticated ML model that attempted to detect when people were using it for nefarious purposes.
It underperformed banning the word "password" from a Google Form.
So that's what they went with.
Re: Ask HN: When has a "dumb" solution beaten a sophisticated one for you?
#18It was a very long time ago, but during a programming competition one of the warm-up questions was something to do with a modified sudoku puzzle. The naive algorithmic solution was too slow, the fancy algorithm took quite a bit of effort... and then there were people who realised that the threshold for max points was higher than you needed for a brute force check of all possible boards. (I wasn't one of them)
This generalises to a few situations where going faster just doesn't matter. For example for many cli tools it matters if they finish in 1s or 10s. But once you get to 10ms vs 100ms, you can ask "is anyone ever likely to run this in a loop on a massive amount of data?" And if the answer is yes, "should they write their own optimised version then?"
Re: Ask HN: When has a "dumb" solution beaten a sophisticated one for you?
#19Great question, I could answer with many stories but here are two:
The (deliberately) very limited analytics software I wrote for my personal website[0] could have used database but I didn't want to add a dependency to what was a very simple project so I hacked up an in-memory datastructure that periodically dumps itself to disk as a json file. This gives persistence across reboots and at a pinch I can just edit the file with a text editor.
Game design is filled with "stupid" ideas that work well. I wrote a text-based game[1] that includes Trek-style starship combat. I played around with a bunch of different ideas for enemy AI before just reverting to a simple action drawn off the top of a small deck. It's a very easy system to balance and expand, and just as fun for the player.
Re: Ask HN: When has a "dumb" solution beaten a sophisticated one for you?
#20I wrote a clone of battle zone the old Atari tank game. For the enemy tank “AI” I just used a simple state machine with some basic heuristics. This gave a great impression of an intelligent adversary with very minimal code and low CPU overhead.
Game design is filled with simple ideas that interact in fun ways. Every time I have tried to come up with complex AIs I ended up scrapping them in favor of "stupid" solutions that turned out to be more enjoyable and easier to tune.