Saturday, November 15, 2014

the Lazy Hobo Riddle

The other week, somebody mentioned this funny coding problem on the ifMUD:
There once were 4 hoboes travelling across the country. During their journey, they ran short on funds, so they stopped at a farm to look for some work. The farmer said there were 200 hours of work that could be done over the next several weeks. The farmer went on to say that how they divided up the work was up to them. The hoboes agreed to start the next day.
The following morning, one of the hoboes - who was markedly smarter and lazier than the other 3 - said there was no reason for them all to do the same amount of work. This hobo went on to suggest the following scheme:
  • The hoboes would all draw straws.
  • A straw would be marked with a number.
  • The number would indicate both the number of days the drawer must work and the number of hours to be worked on each of those days. For example, if the straw was marked with a 3, the hobo who drew it would work 3 hours a day for 3 days.
It goes without saying that the lazy hobo convinced the others to agree to this scheme and that through sleight of hand, the lazy hobo drew the best straw.
The riddle is to determine the possible ways to divide up the work according to the preceding scheme.
I thought it'd be cute to code it up in Hugo.

Now, that version allows for straws being the same length.  If we can assume that every straw is a different length, we can make each inside loop start at a higher value from the outside one.  We can also break out of the loops if the length on the first straw is incremented to the point that it shares a value with the first possible second straw.

No comments:

Post a Comment