{{ message }}

Instantly share code, notes, and snippets.

# boyter/Puzzle.java

Last active Apr 20, 2017
Friday Quiz Solution
 /* Three people are playing the following betting game. Every five minutes, a turn takes place in which a random player rests and the other two bet against one another with all of their money. The player with the smaller amount of money always wins, doubling his money by taking it from the loser. For example, if the initial amounts of money are 1, 4, and 6, then the result of the first turn can be either 2,3,6 (1 wins against 4); 1,8,2 (4 wins against 6); or 2,4,5 (1 wins against 6). If two players with the same amount of money play against one another, the game immediately ends for all three players. Find initial amounts of money for the three players, where none of the three has more than 255, and in such a way that the game cannot end in less than one hour. (So at least 12 turns) In the example above (1,4,6), there is no way to end the game in less than 15 minutes. All numbers must be positive integers. */ import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Puzzle { public static void main(String[] argv) { Puzzle puzzle = new Puzzle(); puzzle.run(); } private int DESIRED_TURNS = 11; private int MAX_MONEY = 256; private List matches = Collections.synchronizedList(new ArrayList()); public enum Wait { PLAYER1, PLAYER2, PLAYER3 } private void run() { long tic = System.currentTimeMillis(); Wait[] events = this.calcEvents(); System.out.println("Generate Events Time: " + (System.currentTimeMillis() - tic)); tic = System.currentTimeMillis(); List combinations = new ArrayList<>(2829056); for (int x = 1; x < MAX_MONEY; x++) { for (int y = x; y < MAX_MONEY; y++) { for (int z = y; z < MAX_MONEY; z++) { int[] intArray = {x, y, z}; combinations.add(intArray); } } } System.out.println("Generate Combinations Time: " + (System.currentTimeMillis() - tic)); tic = System.currentTimeMillis(); combinations.parallelStream().forEach(x -> this.playGames(x[0], x[1], x[2], events)); for (int[] matchReturn: matches) { System.out.println(matchReturn[0] + " " + matchReturn[1] + " " + matchReturn[2]); } System.out.println("Calculate Matches Time: " + (System.currentTimeMillis() - tic)); } private void playGames(int x, int y, int z, Wait[] events) { int player1 = x; int player2 = y; int player3 = z; int count = 0; for (Wait e: events) { if (player1 == player2 || player1 == player3 || player2 == player3) return; if (e == Wait.PLAYER1) { if (player2 > player3) { player2 = player2 - player3; player3 = player3 * 2; } else { player3 = player3 - player2; player2 = player2 * 2; } } else if (e == Wait.PLAYER2) { if (player1 > player3) { player1 = player1 - player3; player3 = player3 * 2; } else { player3 = player3 - player1; player1 = player1 * 2; } } else { if (player1 > player2) { player1 = player1 - player2; player2 = player2 * 2; } else { player2 = player2 - player1; player1 = player1 * 2; } } if (count == 11) { player1 = x; player2 = y; player3 = z; count = 0; } count++; } int[] match = {x, y, z}; this.matches.add(match); } private Wait[] calcEvents() { Wait[] flatEvents = new Wait[1948617]; List events = this.calcEvents(new Wait[this.DESIRED_TURNS], 0); int count = 0; for (Wait[] event: events) { for (int i = event.length - 1; i != 0; i--) { flatEvents[count] = event[i]; count++; } } return flatEvents; } private List calcEvents(Wait[] current, int turn) { if (turn == this.DESIRED_TURNS) { return new ArrayList() {{ add(current); }}; } Wait[] one = new Wait[this.DESIRED_TURNS]; System.arraycopy(current, 0, one, 0, current.length); one[turn] = Wait.PLAYER1; Wait[] two = new Wait[this.DESIRED_TURNS]; System.arraycopy(current, 0, two, 0, current.length); two[turn] = Wait.PLAYER2; Wait[] three = new Wait[this.DESIRED_TURNS]; System.arraycopy(current, 0, three, 0, current.length); three[turn] = Wait.PLAYER3; turn++; List ints1 = calcEvents(one, turn); List ints2 = calcEvents(two, turn); List ints3 = calcEvents(three, turn); ArrayList toReturn = new ArrayList<>(); toReturn.addAll(ints2); toReturn.addAll(ints1); toReturn.addAll(ints3); return toReturn; } }

### boyter commented Mar 28, 2017 • edited

 ``````org133902:lambda boyter\$ time java Puzzle Generate Events Time: 88 Generate Combinations Time: 565 175 199 223 197 205 213 209 217 225 Calculate Matches Time: 6591 real 0m7.411s user 0m23.670s sys 0m0.367s ``````

### boyter commented Mar 30, 2017

 ``````root@temp:~# time java Puzzle Generate Events Time: 133 Generate Combinations Time: 173 197 205 213 175 199 223 209 217 225 Calculate Matches Time: 2938 real 0m3.394s user 0m32.864s sys 0m0.908s `````` Running on a 16 core machine :)

### proyb6 commented Apr 1, 2017 • edited

 Interesting, I tried a small test on Swift and Java on Macbook Pro. Generate combinations time in Java 1.8 - 530ms Generate combinations time in Swift 3.1 - 300ms Swift code: ``````let MAX_MONEY:Int = 256 var combinations = [[Int]]() for x in 1..

### boyter commented Apr 2, 2017

 That's interesting! I was hoping someone would end up porting totally to swift. I am curious to know how it would perform.
to join this conversation on GitHub. Already have an account? Sign in to comment