Friday Quiz Solution

Puzzle.java

/*
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;
    }
}

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

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 :)

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]] ...

That's interesting! I was hoping someone would end up porting totally to swift. I am curious to know how it would perform.