3 ms·
you could solve this with a simple state machine; there's no reason to resort to parlour tricks... https://gist.github.com/igor47/7228586 https://gist.github.c
by igor47 13y ago
you could solve this with a simple state machine; there's no reason to resort to parlour tricks...
https://gist.github.com/igor47/7228586 https://gist.github.com/igor47/7228586
- igor47 13y agooops, sorry! i meant the "parlour tricks" part in response to this comment: https://news.ycombinator.com/item?id=6640033 https://news.ycombinator.com/item?id=6640033 not in response to the author!
- huhalu 13y agotry this test case ([5,1,0,1],1)
- igor47 13y agothanks! i updated the gist (https://gist.github.com/igor47/7228586/revisions https://gist.github.com/igor47/7228586/revisions), but the solution is not nearly as simple as before.
- lelf 13y agoFails for [3,0,1,0,2]
- ledave123 13y agoTry the list(reversed()) of the cases and this finds more bugs: MISMATCH: [6, 7, 7, 4, 3, 2, 1, 5, 2] holds 10 (got 0) MISMATCH: [5, 3, 6, 7, 7, 4, 3, 2, 1, 5, 2] holds 12 (got 2) Another mismatch: MISMATCH: [2, 0, 1] holds 1 (got 0) TRUE: [1, 0, 2] holds 1
- acchow 13y agoYour solution doesn't work when there is more than one "puddle": https://gist.github.com/alexchow/7228746 https://gist.github.com/alexchow/7228746 Try the case: ([2,5,1,2,3,4,7,7,6,3,5], 12)
- igor47 13y agoit's not "more than one puddle"; it's that i don't count the second puddle because i don't ever "close" it by encountering it's level again. if i go off the edge, i should close it as best i can.
- acchow 13y agoAh, right. Now that I actually read your code, that's the real bug :p The issue with this "state machine" approach is you don't have "lookahead". In the two pass approach (approach from one side, then the other), you essentially have two machines, one implicitly serving as the "lookahead" for the other.