20150503, 16:59  #12  
"Forget I exist"
Jul 2009
Dartmouth NS
2147_{16} Posts 
Quote:
Last fiddled with by science_man_88 on 20150503 at 17:04 

20150503, 19:02  #13 
May 2013
East. Always East.
11×157 Posts 
Yeah, okay. That makes sense.

20150503, 19:11  #14 
"Forget I exist"
Jul 2009
Dartmouth NS
7·1,217 Posts 
I have a script right now that has pari printing them ( I reduced to irreducible form since my known properties don't change if the same ratio is held) that can print all irreducible possibilities left in under 4 minutes ( wish their were less than 2 million left but I may have missed some checks and got them out of order to speed the code up). edit: part of my problem is using exclusive ORs but I don't know quite how to fix that as  is all I know I don't remember  ever working in pari, edit2:doh if using the switch case possibility might be worth trying
Last fiddled with by science_man_88 on 20150503 at 19:21 
20150503, 21:33  #15 
May 2013
East. Always East.
11×157 Posts 
I have a collection of points [x,y,z] which I call legal starting configurations, where x, y and z are all <= 255. I have a numbering scheme which uses a single integer to denote each point.
Each point is currently tagged as ending the following turn (because it contain duplicates) OR is tagged with the identifier of each of the three configurations it can potentially lead to. My goal is to check each of those ID's to see if they reference an ID tagged with ending on turn 1. If any of them does, then that config ends on turn 2. The hiccup I had is that some of the points which can be reached are not legal starting configs (like I discussed earlier) so I have a second set of points which I call reachable points. I have eliminated from them all legal starting configurations so that all legal points throughout the game are inside only one of the two sets. However, with some thinking, I have determined that a large number of my "reachable points" are not in fact reachable. I am working on a list of criteria for points which cannot be reached within the mechanics of the game. For example: The points x, y and z cannot all be odd, because one of the players had to double his money to get to where he is. I'm starting to do more thinking and less crunching and I think this line of thinking is what science_man_88 has been doing. Depending on how much work it is to trim the points list and start over, it might help to expand the list of criteria. This of course is assuming people are interested in helping. I think I'll go it alone for now because I finally feel like I have trimmed things down to a manageable amount (down to 7 million entries from 30some, and this is before removing the allodd cases). 
20150504, 00:13  #16  
"Forget I exist"
Jul 2009
Dartmouth NS
10000101000111_{2} Posts 
Quote:
I did some arithmetic using counter variables on the whole problem and my first check took 473477 of 2796152 (using forpart ( short for for partitions basically for those who don't know) I gave it preconditions of both minimum and maximum length of 3 and values of 1255) or 16.93 ..... % off that top that don't even see my second check for example. Last fiddled with by science_man_88 on 20150504 at 00:33 

20150504, 05:55  #17 
Jun 2003
2×7×17×23 Posts 
If I have done my programming correctly, there are 3 solutions that terminate in exactly 12 iterations (and none longer).
1_5,1_9,2_3 1_7,2_5,2_3 2_9,2_7,2__ Last fiddled with by Batalov on 20150504 at 16:45 Reason: (We don't want thousands of submissions from people who will simply copy this into IBM site, no?) 
20150504, 06:16  #18 
"Serge"
Mar 2008
San Diego, Calif.
2^{5}×5^{2}×13 Posts 
I think I see four solutions.

20150504, 07:20  #19 
Jun 2003
2×7×17×23 Posts 

20150504, 07:23  #20 
"Serge"
Mar 2008
San Diego, Calif.
2^{5}×5^{2}×13 Posts 
Some ideas:
1. Note that in each game the amount of coins is constant. 2. All possible game states can be split in 757 game families (from 6 to 762 coins total in all hands) 3. Always keep the game state sorted: a<b<c 4. In each game family (s=a+b+c), nodes can be enumerated by the two poorest players' hands (a,b). 5. Catch and prune cycles, especially the most trivial: where one player is exactly twice richer than another. 6. Prune useless paths early 7. Memoize visited nodes 
20150504, 08:25  #21 
Jun 2003
2·7·17·23 Posts 
I use a bruteforce approach. Pseudocode to follow.
1. Start with a length[763][763][763] 3D array. Set length[i][j][k] = 0 for invalid points (either 0 or sum > 763). set to 1 if at least two indexes are same. Everything else = infinity 2. For pass = 2, 3... Examing distinct i,j,k (i<j<k) where length[i][j][k] > pass. compute the three child nodes, and get the minimum of length of those three. set newlength = min child length +1. If that is an improvement ( newlength < currentlength), record it for all 6 combinations of i,j,k. 3. Exit when a particular pass doesn't improve any node. 
20150504, 11:08  #22  
"Forget I exist"
Jul 2009
Dartmouth NS
7·1,217 Posts 
Quote:
I did mess up my checks, but here's a list of incompatible formulations among the cash of two people the count of eliminated assumes you haven't gone to irreducible form: 1:3 > 84 such pairings eliminated 1:7> 36 such pairings eliminated 1:15> 17 such pairings eliminated 1:31> 8 such pairings eliminated 1:63> 4 such pairings eliminated 1:127> 2 such pairings eliminated 1:255> 1 such pairing eliminated 152 such pairings eliminated each that can be paired with 253 other numbers in theory which eliminates 38456 groupings before going to irreducible form ( 1771 from irreducible form). edit: of course by eliminating 1:2:4 we can disprove another 63 if not in irreducible form. edit2: sorry I read twice richer as twice as rich for some reason. Last fiddled with by science_man_88 on 20150504 at 11:40 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
December 2015  Xyzzy  Puzzles  15  20160106 10:23 
October 2015  LaurV  Puzzles  3  20151102 15:22 
September 2015  Xyzzy  Puzzles  12  20151007 14:43 
July 2015  Xyzzy  Puzzles  16  20150819 16:13 
June 2015  Batalov  Puzzles  10  20150707 14:59 