Wednesday, July 30, 2008

Brain De-Freezing

Today's new song touches a topic close to everyone's heart: postponing #2 as long as humanly possible. Everyone's knows those painful moments in their lives where #2 is all but poking out, but you just can't put down what you're doing, or you're too lazy to walk over to the bathroom, and so you clench everything and swallow hard with your butt. Later of course, your sphincter has to stretch like a cannon barrel, but as Russians say: "art demands sacrifice."

In any case, the lyrics are before you:
Verse 1
Sometimes it hits you you're lying in bed,
your bladder says i'm ready, let me go or i'm dead
your colon's screaming i've been due for a while
and your intestines now measure in mi-iles
you're thinking


Chorus:
oh God
i got to go
but no, i can hold it
just a little longer
if i just squeeze and squeeze and squeeze those mighty cheeks
i know i can hold it just one more week


Verse 2
Two hours later you're blue in the face
but you never give up, this is a long distance race
you chant your strongest mantras and pray for success
and hold that sphincter tight so you don't make a me-ess


Chorus
...

That's as far as I've gotten so far, I'm afraid if I continue, things aren't going to go well for the protagonist. Here's the MIDI: Week #2 The melody is unambiguous, each note represents a syllable.

Got some puzzles secondhand from friends that are doing interviews. My brain wasn't exactly ready for any strain, so even reading them in the IM window was a struggle. Here they are, there's two of them:

1. Find the smallest number x such that any number above it can be obtained by a linear combination of 6's, 9's and 20's. (For example 127 can be obtained with five 20's and three 9's)

2. You have 2 glass balls and a 100 story building. You need to find the smallest numbered floor such that a glass ball will break if dropped from it. Minimize the number of floors tried.

WARNING: Don't read on if you don't want to hear hints or solutions

I didn't manage to find an elegant solution to the first problem before succumbing to the temptation of using brute force. Basically I tried numbers almost consecutively until I found six consecutive integers that held the requisite property. From there it is trivial to prove that any number higher will also hold the property. I won't say the answer in case someone has extremely well-developed peripheral vision and spots it while reading the spoiler warning.

I have no idea what the best answer is to the second problem. There are a handful of strategies that all have the same worst case scenario, but I'm too lazy to delve into calculating the average case scenario. The basic idea though, is to pick some interval, say n, and try every nth floor until ball 1 breaks. Then use ball 2 to go through the yielded interval. So say n = 15, try 15th, 30nd, 45th, etc. Worst case scenario is if ball 1 breaks on the 90th floor. Then you use ball 2 to try floors 76 through 89.

In any case, the best thing to do first would be to estimate the terminal velocity of the ball. Perhaps it will reach it after falling fewer than 100 floors, narrowing the testing range.

No comments: