Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- 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 (Wait e: event) {
- flatEvents[count] = e;
- 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(ints1);
- toReturn.addAll(ints2);
- toReturn.addAll(ints3);
- return toReturn;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement