ftw!
Home Blog Archives RSS
¶ totally useless
gah. It's 4:30 am, and I can't sleep. i hate it when i can't shut my brain off.

stacy was telling me about her interviews in new york today, and told me a brain teaser she and eugene were joking about. It goes like this: You have two jugs. Jug A can hold 3 gallons of water, and jug B can hold 5. Using just these two jugs and a running faucet, how do you measure out 4 gallons?

So it's a pretty simple one, and the answer is:
  1. fill B (A: 0, B: 5)
  2. fill A with B (A: 3, B: 2)
  3. empty A (A: 0, B: 2)
  4. fill A with B (A: 2, B: 0)
  5. fill B (A: 2, B: 5)
  6. fill A with B (A: 3, B: 4)


Then I couldn't sleep, and started thinking about generalizing the problem and came up with the following generalization:

Problem:Given n jugs with capacities c1, ..., cn, find the shortest sequence of actions that allow you to measure out k gallons of water.

Solution:This is a classic example of uninformed search.
state space:a vector [j1, ..., jn], where ji is the current amount of water, in gallons, in jug i
actions:
  • fill jug i
  • empty jug i
  • fill jug i with jug j
transition function:
  • [j1, ..., ji-1, ji, ji+1, ..., jn], fill i → [j1, ..., ji-1, ci, ji+1, ...,jn]
  • [j1, ..., ji-1, ji, ji+1, ..., jn], empty i → [j1, ..., ji-1, 0, ji+1, ...,jn]
  • [j1, ..., , ji, ..., jj, ..., jn], fill i with j → [j1, ..., p, ..., r, ..., jn], where p = min( ci, ji + jj ) and r = max(0, jj - (ci - ji))
start state:[ 0, ..., 0 ]
goal states:any state [j1, ..., jn] such that there is some jug i such that ji = k
Given that formalization, you can apply a simple search algorithm like breadth first search to find the shortest sequence of actions that will give you your desired measurement. This search is complete, so if BFS finishes without entering a goal state, then you can conclude that the task is impossible.

So there you have it, a generalization of one of those totally useless brain teasers that you might get in a job interview. Damnit, why can't I come up with a useful insight for once???



Re: totally useless
Posted 17 years, 9 months ago by Sonic • • Reply
Jeez. Frickin' smart people *mumble mumble* Yeah, if it makes you feel any better, I get insomnia all the time and my thoughts are way more useless than that. Well, my entire field of study is arguably more useless than your algorithm but that's a discussion for another day...
Re: totally useless
Posted 17 years, 9 months ago by amandine • • Reply
and THIS is what you do instead of coming over for crepe night?! i'm offended.
Re: totally useless
Posted 17 years, 9 months ago by albert • • Reply
but i told you why i couldn't come! *ducks and hides*
Re: totally useless
Posted 17 years, 9 months ago by Jeremy • • Reply
They did the 3/5 gallon jug thing in "Die Hard: With a Vengeance" -- Willis and Samuel L.J. had to fill one with four gallons to disarm a bomb. After we saw it, my Dad and I spent a half hour figuring out how it worked. Just remember that the next time you're questioning whether you have a decent social life.



Comments disabled until the spammers go away. I hope you comment spammers all die horrible deaths and are forced to delete endless streams of comment spam in your days in purgatory.
• Powered by bBlog