tag:blogger.com,1999:blog-8826059633697057288.post6334166299824038744..comments2015-02-26T13:18:29.825-08:00Comments on Craig Nevill-Manning: Three ContainersCraig Nevill-Manninghttp://www.blogger.com/profile/05177752241391591108noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-8826059633697057288.post-70190137674944716612014-02-21T19:10:02.842-08:002014-02-21T19:10:02.842-08:00This is similar to Towers of Hanoi, isn't it?
...This is similar to Towers of Hanoi, isn't it?<br /><br /> if isFull(C) then C->A<br /> else if isEmpty(B) then A->B<br /> else B->C<br /><br />Or, we can transfer the other direction<br /><br /> if isFull(B) then B->A<br /> else if isEmpty(C) then A->C<br /> else C->BTony Smithhttps://www.blogger.com/profile/00625709656671313524noreply@blogger.comtag:blogger.com,1999:blog-8826059633697057288.post-78889780290065146482012-08-09T23:03:14.281-07:002012-08-09T23:03:14.281-07:00Btw, here's the code for I used to output the ...Btw, here's the code for I used to output the BFS state transitions:<br /><br />http://pastebin.com/q4BBhCwx<br /><br />Cheers,<br />-Beckettbecketthttps://www.blogger.com/profile/02163994273113779789noreply@blogger.comtag:blogger.com,1999:blog-8826059633697057288.post-20414982037802352302012-07-28T05:59:59.084-07:002012-07-28T05:59:59.084-07:00Oops, I was wrong when I said every move is forced...Oops, I was wrong when I said every move is forced. There are two "first" reverse moves: (10,0) is accessible from (10, 7) but also from (3, 7). So there is a second path accessible by backtracking. But this leads to a slightly longer solution. (18 moves vs 15.)<br /><br />Looks like I have recreated the two states you both found. (Shows I didn't read the earlier posts carefully, I was avoiding spoilers myself...)<br /><br />And now I can enumerate all legal positions and the number of moves it takes to get there just by moving around the boundary of the rectangle (with corner cut off). There are two positions that take more moves to reach than (10, 0): they are (3, 7) and (3, 0). (16 moves each, vs 15 for (10, 0).) These correspond to (10, 3, 7) and (17, 3, 0) for the amount of water in (20, 15, 7) cups respectively. So (10, 10, 0) isn't quite the hardest puzzle possible given the constraints, but it has more aesthetic appeal than either of these.JMHLhttps://www.blogger.com/profile/08006455134993864135noreply@blogger.comtag:blogger.com,1999:blog-8826059633697057288.post-8494519332876747352012-07-28T05:39:17.597-07:002012-07-28T05:39:17.597-07:00This comment has been removed by the author.JMHLhttps://www.blogger.com/profile/08006455134993864135noreply@blogger.comtag:blogger.com,1999:blog-8826059633697057288.post-42188222733661294682012-07-27T21:15:58.687-07:002012-07-27T21:15:58.687-07:00Spoiler alert! Don't read on if you don't ...Spoiler alert! Don't read on if you don't want to see the solution.<br /><br />Here's how I solved the problem: <br /><br />Draw a grid of 15 x 7 squares. Every point in the grid corresponds to a state of all three glasses, with the contents of the 20 oz glass implied by the other two values. There are three infeasible points at (7, 14), (7, 15) and (6, 15), because you only have 20 oz of water, so the top right corner is cut off the rectangle.<br /><br />Now your starting point is (0, 0) and you want to get to (10, 0). Every pour is either an upward vertical move (20->7 pour), a horizontal move to the right (20->15 pour), a diagonal move up/left (15->7 pour), or the reverse of each of these. And every move has keep going in one of these directions until it hits a boundary. Then go backwards from the end point (10, 0) and every move is forced: (10, 7), (15, 2), (0, 2), (2, 0), ... etc. Eventually you have a nice cobweb picture and you hit the corner (15, 0) which is reachable from (0, 0).JMHLhttps://www.blogger.com/profile/08006455134993864135noreply@blogger.comtag:blogger.com,1999:blog-8826059633697057288.post-34495601247197544472012-07-26T16:49:35.233-07:002012-07-26T16:49:35.233-07:00Thanks, Beckett – I absolutely missed two states! ...Thanks, Beckett – I absolutely missed two states! I've updated the post.Craig Nevill-Manninghttps://www.blogger.com/profile/09693521670450230478noreply@blogger.comtag:blogger.com,1999:blog-8826059633697057288.post-24326893438797265762012-07-25T21:51:41.112-07:002012-07-25T21:51:41.112-07:00Nice!
I threw together some code, and got similar...Nice!<br /><br />I threw together some code, and got similar results:<br />http://moosers.org/glass-puzzle/bfs.png<br /><br />Though, I have some more nodes off the early (0, 15, 5) and so my overall tree is shallower than yours.<br /><br />Things get visually interesting if you draw in the edges to form cycles.<br />Here's where I wish I had better dot skills than I do...<br /><br />http://moosers.org/glass-puzzle/cycles.png (warning: large image)becketthttps://www.blogger.com/profile/02163994273113779789noreply@blogger.com