Solving Programming Puzzles Without Using Your Brain(doisinkidney.com)
doisinkidney.com
Solving Programming Puzzles Without Using Your Brain
https://doisinkidney.com/posts/2019-06-04-solving-puzzles-without-your-brain.html
17 comments
I love the idea of using OEIS to automate finding mathematical patterns in the solution. Also, plotting the search space immediately is something I know is often unreasonably effective, but I almost never take the time to do. This is a fantastic little article.
Given that I'm a bit of a moron mathematically, I have, more times than I cared to admit, made serious progress on a problem by (a) writing a Python or C++ program to spew out a highly non-scalable count of some entity whose nature I'm trying to understand and (b) taking that count and sticking it in OEIS.
This has led to some pretty major insights, which one can carefully 'launder' casually as something you knew all along. "Oh, of course the number of subtrees can be found by half-Catalan numbers", you say, with aplomb, as if you hadn't learned about half-Catalan numbers approximately 10 minutes ago.
This has led to some pretty major insights, which one can carefully 'launder' casually as something you knew all along. "Oh, of course the number of subtrees can be found by half-Catalan numbers", you say, with aplomb, as if you hadn't learned about half-Catalan numbers approximately 10 minutes ago.
Well haha still seems like a lot of brain was put into it.
Also, there's a simpler pattern to the sequence that is easily observable without even opening OEIS.
Also, there's a simpler pattern to the sequence that is easily observable without even opening OEIS.
Unfortunately, if you spot that pattern then you will not guess the correct generalization. It seems that this may be a puzzle that's easier to solve if you aren't good at spotting easy things.
Well tbh, it seems 2^k-1 does actually match the sequence as far as it is shown. Perhaps there is a proof that n=2^k-1 for the numbers where 2^n is divisible by (n+1). I'll have to see.
What's the simpler pattern?
Presumably multiplying by two and adding one? That's the pattern that jumped out to me, unless they're talking about something more subtle.
Transforming a problem into pattern recognition seems like a good way to use your brain natural inclinations.
Very neat little article.
Very neat little article.
I got lost at step 3. I wasn't super clear in how we went from line to memoization. Cool article though - I had never thought of plotting before to recognize patterns.
If you write out the coordinates for a straight line from the origin they look like this:
3, 5; 6, 10; 9, 15...
Google Foobar puzzles are amazing. Solving them was immensely fun and challenging. Best code I ever wrote.
"While Python is usually great for programming puzzles, this step in particular is crying out for something like QuickCheck: without it, we'll have to roll our own."
Instead of rolling his own, the author could have just used Python's Hypothesis package.[1][2]
[1] - https://github.com/HypothesisWorks/hypothesis
[2] - https://pypi.org/project/hypothesis/
Instead of rolling his own, the author could have just used Python's Hypothesis package.[1][2]
[1] - https://github.com/HypothesisWorks/hypothesis
[2] - https://pypi.org/project/hypothesis/
The bad thing about not using your brain is that you don't learn anything.
Do that in a face to face interview. Good luck with that.
Do you mean write the naive solution and explain how you'd turn it into a good solution? I think that would be well received.