Solving Programming Puzzles Without Using Your Brain

https://doisinkidney.com/posts/2019-06-04-solving-puzzles-without-your-brain.html

by lelf • 7 years ago

119 17 7 years ago

doisinkidney.com

panzerklein• 7 years ago

Google Foobar puzzles are amazing. Solving them was immensely fun and challenging. Best code I ever wrote.

piterdevries• 7 years ago

Do that in a face to face interview. Good luck with that.

ALittleLight• 7 years ago

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.

mankeysee3• 7 years 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.

gjm11• 7 years ago

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.

mankeysee3• 7 years ago

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.

oisdk3• 7 years ago

What's the simpler pattern?

paideic• 7 years ago

Presumably multiplying by two and adding one? That's the pattern that jumped out to me, unless they're talking about something more subtle.

bspammer• 7 years ago

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.

glangdale• 7 years ago

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.

username90• 7 years ago

The bad thing about not using your brain is that you don't learn anything.

grive• 7 years ago

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

Very neat little article.

catchmeifyoucan• 7 years ago

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.

oisdk3• 7 years ago

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

pmoriarty• 7 years ago

"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/

Solving Programming Puzzles Without Using Your Brain

Related Stories