Howdy, Stranger!
It looks like you're new here. If you want to get involved, click one of these buttons!
This forum is in permanent archive mode. Our new active community can be found here.
GeekNights 20111004 - Rock of Ages
Tonight on GeekNights, we review the surprising and interesting Rock of Ages. In the news, id releases Rage, Xenonauts might be X-Com, and Risk Legacy brings statefulness to boardgames (for good or ill, we cannot yet say).
- Rym's Thing - Cool Cool Considerate Men
- Scott's Thing - MCã‚³ãƒŸãƒ¤ã€€å€¦æ€ æœŸã§ã™
Comments
Without going into too much detail
1. Run the Extended Euclidean Algorithm on m and n yielding an equation of the form xm + yn = 1
2. Multiply the equation by the desired quantity, k, yielding: kxm+kyn = k.
3. Now this linear combination describes the fact that the bucket of size m is filled kx times, poured into the bucket of size n when full, and the bucket of size n is emptied ky times (when full).
4. However, filling the m bucket n times and the n bucket m times yields nothing, so we are going to reduce the equation by subtracting n from (kx) and m from (ky) until kx is between 0 and n and ky is between 0 and m.
5. note, this will actually leave two solutions because in one, bucket m will be filled and bucket n will be emptied while in the other the roles will be switched.
2(5)-2(3)=4
3(3)-1(5)=4
the first of these corresponds to the solution
0,0
5,0
2,3
2,0
0,2
5,2
4,3
4,0
the second corresponds to:
0,0
3,0
0,3
3,3
1,5
1,0
0,1
3,1
0,4
the algorithm extends pretty well out to much larger numbers, though I credit that more to Euclid than to myself.
Having looked at the idea of a linear combination as a solution, which suggests that one bucket must be the fill bucket and on must be the draining bucket, the brute force algorithm as follows becomes reasonable.
fill bucket 1
pour it into bucket 2
repeat until bucket 2 is full
empty bucket 2
pour the leftovers of bucket 1 into bucket 2
repeat all above steps until you have the desired quantity of water.
Wait, this episode isn't about the musical? Damn it, I got excited for a second there.
My problem with slowing the game down for more build time is that I was already pretty bored with the 5 minute level model. There would need to be more escalation in the game somehow to keep me going. Perhaps the boulders get bigger and bigger and bigger to start as the map goes on? So your first boulder is say a 7, then a 14 ,then a 21, 28, and then max out at 35. So if you played well, the 5th boulder is the kill shot and you can take a little beating, but if any of your boulders get shot down a degree you're going to need 6. If you lost about a degree per boulder, you'll need 7.
... or, if it wasn't (maybe you're right, and I'm the one who misunderstood), consider this a new math problem for you to solve in your spare time.
For a sample problem:
buckets are 30, 42,70 and 105 liters (or ounces if you prefer) in volume. You can fill a bucket, empty a bucket, or pour from one bucket to another until one of them becomes either empty or full.
a) get 23 liters into any bucket
b) get a total of 143 liters in the buckets, or show why it's impossible. (Edit: it said 100, which was an obvious typo- we want more than the biggest bucket in this exercise. Nevertheless, I apologize for the inconvinience)
c) for any set of 3 buckets devise a rule to determine which volumes are possible.
Some initial dicking around gave me that:
23 = 1(105)+2(70)-6(42)+1(30)
143 = 3(105)+2(70)-6(42)-2(30)
make a list of the four bucket sizes and the 6 greatest common factors of every subset of two. Then I tried to construct 23 and 143 from those 10 (in this case only 9) values. Then I reduced by just adding coefficients to get the above.
problem c is the most interesting of the lot. I'll be thinking about that next time I'm bored in class. It feels to me like a cross between linear algrebra and discrete math.
I admit though, problems a and b were far from trivial. With good number choice, it may be possible to make a fun bucket-water game that is neither trivial to solve, nor impossibly difficult without paper and/or a calculator.
to clarify what I meant by the above linear combinations, the buckets are listed in size order
[105][70][42][30]
0,0,0,0
105,0,0,0
63,0,42,0
63,0,0,0
21,0,42,0
21,0,0,0
0,0,21,0
0,70,21,0
0,49,42,0
0,49,0,0
0,7,42,0
0,7,0,0
0,0,7,0
0,70,7,0
0,35,42,0
0,35,0,0
0,0,35,0
0,0,35,30
0,0,42,23
0,0,0,23
The entire rules are already online if you want to read more about the game. I wrote a quick news piece for MTV that basically just previewed the rules and posed the question "is this crap or is this awesome?" Can't answer that Q since the game doesn't actually release until November. Rob Daviau actually reached out to me and sent a pre-release copy to my house. It shipped yesterday, and if for some reason he paid for pricy next day shipping, I can bring it to Recess on Sat if you're coming and want to check it out in person.
Foxton
To do so, just Extended Euclidean Algorithm the first two. Then EEU that number with the third one and replace that number with the linear combination of the first two you got from the initial calculations. Continue until you are out of numbers, or you find a linear combination that equals one. Now multiply all coefficients by the desired quantity of water. If you feel like it, you can reduce by subtracting x uses of the bucket with size y and y uses of the bucket with size x. That is up to you though.
My math professor/advisor thought my logic was sound.
One small note is that sometimes you need to keep the result of your labors so far in some bucket, even as you need it for the linear combination. I'm pretty sure this resolves itself during optimization (adding and subtracting XY liters, like you said), but even if it doesn't, you can always just pick several buckets (f.e. the biggest buckets) to be filled and work only to put the remainder in one bucket, then fill them (f.e. if in the example bucket set you needed 200 liters, you'd first get 0,25,0,0 and then 0,25,70,105).
It works! It determines how many buckets the user wants, takes in the sizes of those buckets, takes in the desired quantity of water, determines if it is possible, and if so, prints a linear combination of the bucket sizes equal to the desired quantity. It could be made for efficient, but it tends to be extremely fast, even for unrealistically large numbers of buckets and sizes of buckets.