Skip to content

Instantly share code, notes, and snippets.

@boyter
Last active October 15, 2021 07:36
  • Star 8 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save boyter/42df7f203c0932e37980f7974c017ec5 to your computer and use it in GitHub Desktop.
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<int[]> matches = Collections.synchronizedList(new ArrayList<int[]>());
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<int[]> 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<Wait[]> 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<Wait[]> calcEvents(Wait[] current, int turn) {
if (turn == this.DESIRED_TURNS) {
return new ArrayList<Wait[]>() {{
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<Wait[]> ints1 = calcEvents(one, turn);
List<Wait[]> ints2 = calcEvents(two, turn);
List<Wait[]> ints3 = calcEvents(three, turn);
ArrayList<Wait[]> toReturn = new ArrayList<>();
toReturn.addAll(ints2);
toReturn.addAll(ints1);
toReturn.addAll(ints3);
return toReturn;
}
}
@boyter
Copy link
Author

boyter commented Mar 28, 2017

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
Copy link
Author

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
Copy link

proyb6 commented Apr 1, 2017

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..<MAX_MONEY {
	for y in x..<MAX_MONEY {
		for z in y..<MAX_MONEY {
			combinations.append([x, y, z])
		}
	}
}

Output:

[[1, 1, 1], [1, 1, 2], [1, 2, 2], [2, 2, 2]] ...

@boyter
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment