Solving Programming Puzzles Without Using Your Brain | Hacker News Reader

Solving Programming Puzzles Without Using Your Brain

doisinkidney.com

119 pointslelf17 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.

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.

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.

Oh, of course! Looking at it now that's pretty obvious, lol.

Although I think even if I had spotted that I still would have put it into oeis to see if there was a quick membership test.

Which is to say, 2^n-1.

Transforming a problem into pattern recognition seems like a good way to use your brain natural inclinations.

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...

So now, instead of having to test 6, 10 and 9, 15 when we see it, we can just test 3, 5 once and we'll know the answer to all of the points on that line. Then, to answer the question "which line is this point on?" we simplify the fraction (i.e. 2, 6 -> 1, 3).

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/

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.

Reply on news.ycombinator.com