Struggling to keep an algorithm to order players by dice roll tidy
|
12:19 AM |
No comments |
Struggling to keep an algorithm to order players by dice roll tidy
I am writing a Java algorithm which gets each of six players in a game to roll a dice and the highest roll takes the first turn and so on. I have already written the dice rolling method which takes in a map of players in the form of
The problem I am having trouble overcoming when ordering the players is that if two players roll the same number, they then roll again in order to see who goes ahead of the other. Here is an example scenario:
Position: Player (number rolled)
1: Tom (5)
2: Jerry (4)
=3: Jack (3)
=3: Jill (3)
5: Harry (2)
6: Ron (1)
So Jack and Jill roll again. Jack rolls a 6 and Jill rolls a 3. Jack is now in 3rd position and Jill in 4th.
Any strategy I have began to write quickly becomes seemingly overly complicated and very untidy and difficult to read. This is due to having to check if there are any duplicate rolls at any number, all while storing every roll in the correct order, allowing for two or more positions if there is a duplicate roll. Can anyone come up with a neat structure in which this order can be determined and stored?
Each instance of Player, has a nextPlayer variable that will point to the player in the position after them. It would probably be best to also store numberRolled in the class too. Any players who roll the same number can be stored in a new map and then passed into the rollDice method again.
EDIT
Thanks to Andy Turner, here is my solution:
private Player[] playerOrder = new Player[ModelConstants.NUM_PLAYERS_PLUS_NEUTRALS]; playerOrder = getPlayerOrder(); Player[] getPlayerOrder() { Player[] players = ModelConstants.PLAYERS.values().toArray(new Player[ModelConstants.PLAYERS.size()]); String[] playerNames = ModelConstants.PLAYERS.keySet().toArray(new String[ModelConstants.PLAYERS.size()]); getPlayerOrder(playerNames, players, 0, players.length); return players; } void getPlayerOrder(String[] playerNames, Player[] players, int start, int end) { // Get all players between players[start] (inclusive) and // players[end] (exclusive) to re-roll the dice. for (int i = start; i < end; ++i) { players[i].setDiceNumberRolled(rollDice(playerNames[i], players[i])); } // Sort this portion of the array according to the number rolled. Arrays.sort(players, start, end, new Comparator() { @Override public int compare(Player a, Player b) { return Integer.compare(a.getDiceNumberRolled(), b.getDiceNumberRolled()); } }); for (int i = 0; i < playerNames.length; i++) { playerNames[i] = HashMapUtilities.getKeyFromValue(ModelConstants.PLAYERS, players[i]); } // Look for players who rolled the same number. int i = start; while (i < end) { // Try to find a "run" of players with the same number. int runStart = i; int diceNumberRolled = players[runStart].getDiceNumberRolled(); i++; while (i < end && players[i].getDiceNumberRolled() == diceNumberRolled) { i++; } if (i - runStart > 1) { // We have found more than one player with the same dice number. // Get all of the players with that dice number to roll again. addMessageToLog(MessageType.INFO, "There has been a tie." , 2000); tiedPlayers = true; getPlayerOrder(playerNames, players, runStart, i); tiedPlayers = false; } } } private int rollDice(String playerName, Player player) { int numberRolled = 0; if (player.getPlayerType().equals(PlayerType.HUMAN)) { boolean diceRolled = false; while (!diceRolled) { String message = ", roll the dice"; if (tiedPlayers == true) { message += " again."; } else { message += "."; } String userInput = getCommand(playerName + message, "Invlaid command. Type \"Roll Dice\" or something similar.", 2000); if (userInput.equalsIgnoreCase("Roll Dice") || userInput.equalsIgnoreCase("roll the dice") || userInput.equalsIgnoreCase("Roll")) { numberRolled = dice.rollDice(); diceRolled = true; } else { addMessageToLog(MessageType.ERROR, "Invlaid command. Type \"Roll Dice\" or something similar.", 0); } } } else { String message = " is now rolling the dice"; if (tiedPlayers == true) { message += " again..."; } else { message += "..."; } addMessageToLog(MessageType.INFO, playerName + message, 2000); numberRolled = dice.rollDice(); } player.setDiceNumberRolled(numberRolled); addMessageToLog(MessageType.SUCCESS, playerName + " rolled a " + numberRolled, 1000); addDicePanel(numberRolled); return numberRolled; } private void setPlayerOrder() { for (int i = 0; i < playerOrder.length; i++) { if (i == (playerOrder.length - 1)) { playerOrder[i].setNextPlayer(playerOrder[0]); } else { playerOrder[i].setNextPlayer(playerOrder[i + 1]); } } activePlayer = playerOrder[0]; } private void changePlayer() { activePlayer = activePlayer.getNextPlayer(); } Answer by Valentin Bauer for Struggling to keep an algorithm to order players by dice roll tidy
My attemp would be to let everyone roll the dice and just store it without any sort. Then check for duplicates and let the players who got the same numbers roll again. Afterwards when every Player rolled and nothig duplicate anymore just use some Sort Algorithm. Simplest one for that would be BubbleSort since you have no time issue when sorting. Check out this enter link description here
Answer by Sorin for Struggling to keep an algorithm to order players by dice roll tidy
There are 2 ways to deal with this.
1) The simple thing is to forget the "dice-roll". Generate 32 random (one int) bits for each player and use that for ordering. If they happen to match pick whatever player you want. It's going to be so rare that it doesn't really matter (1 in 4 billion that you get 2 numbers to be the same).
2) If you want to stick to dice-roll. Create a function that takes a list of players, rolls the dice internally and returns the correctly ordered one. Whenever you have equal rolls call create a smaller list with the players that are equals and call the function recursively to give you the ordering of those players. When it returns copy it in the result and continue. You can prove mathematically that it's highly unlikely(read impossible) that this will result in an infinite loop.
Answer by Andy Turner for Struggling to keep an algorithm to order players by dice roll tidy
You can put all of the players into an array - the order of the players in an array can be used to indicate the order of play.
Get them all to pick a dice roll; then sort them by the number they rolled (using a custom comparator).
Now, look for 2 or more players that rolled the same number - these are next to each other because the array is sorted. Now, you can recursively call the same logic to get just those players to re-roll, but only on the portion of the array where those players had the same dice roll.
For example:
Player[] getPlayerOrder() { Player[] players = playerMap.values().toArray(new Player[playerMap.size()]); getPlayerOrder(players, 0, players.length); return players; } void getPlayerOrder(Player[] players, int start, int end) { // Get all players between players[start] (inclusive) and // players[end] (exclusive) to re-roll the dice. for (int i = start; i < end; ++i) { // Logic to roll dice... players[i].setDiceNumberRolled(...); } // Sort this portion of the array according to the number rolled. Arrays.sort(players, start, end, new Comparator() { @Override public int compare(Player a, Player b) { return Integer.compare(b.getDiceNumberRolled(), a.getDiceNumberRolled()); } }); // Look for players who rolled the same number. int i = start; while (i < end) { // Try to find a "run" of players with the same number. int runStart = i; int diceNumberRolled = players[runStart].getDiceNumberRolled(); ++i; while (i < end && players[i].getDiceNumberRolled() == diceNumberRolled) { ++i; } if (i - runStart > 1) { // We have found more than one player with the same dice number. // Get all of the players with that dice number to roll again. getPlayerOrder(players, runStart, i); } } } Answer by jmcg for Struggling to keep an algorithm to order players by dice roll tidy
To organize stuff, try to create a separate method for each "action" you need - one method for rolling the dice, another to find duplicates, and another to sort. here are the steps:
- Roll dice for all players, store in a
List - Find duplicates
- For all duplicates, repeat step 1 and 2 until no duplicates are found.
- Sort the players.
3 methods. 4 steps. logically executed to do what you need.
public int rolldice(Player player); public List findDuplicates (List players); public void sortPlayers(List players); you can already work with these 3 methods. Hope this helps
Answer by Trunk for Struggling to keep an algorithm to order players by dice roll tidy
EDITED
Iterative solution not as simple as first thought !
But best way is to simply manipulate the start and end indices of the original play order and dice rolls arrays. The Java sort-within-limits method for arrays handles these well. Have to keep the end markers (ends) for present roll-off when this produces another dice-tie lest present dice-roll order gets lost. This also means keeping track of the order of play-off rounds (r). Single player rounds skipped.
A lot simpler to code recursively as each instance takes care of its own start and end markers. But still handleable using int arrays for 99% of data manipulation and this would mesh well if int arrays are used in board game display and moves.
import java.util.Arrays; import java.util.Comparator; public class PlayOrderTest4 { private final static int players = 8; /** Main method basically runs the getPlayOrder(.) method for the number of players involved in this game, i.e. the attribute players. */ public static void main(String[] args) { int[] playerOrder = getPlayOrder(); System.out.println(); System.out.println("Final Player Order is : " + Arrays.toString(playerOrder)); } /** Method to decide the player order based on who gets the highest dice roll. If two or more players get the same dice, they run against each other. This method is wholly iterative and calls other methods for specific operations : (1) rollDice(...) : to simulate a dice-roll for an array of players. (2) sortByDice(....) : to determine player order by respective dice value descending. (3) sortDescending(...) : to order an int array according to value descending. (4) sameDice(...) : to determine those players rolling the same dice. (5) firstIndexOf(....) : to determine the first index of a value in an int array range. (6) lastIndexOf(....) : to determine the last index of a value in an int array range. @return Returns an int array the same size as the number of players and giving the order in descending order of initial dice rolling by each player. Players on tied dice roll again to decide the play order between them. */ public static int[] getPlayOrder() { int[] playOrder = new int[players], // Final play order rolls = new int[players], // Play-off dice rolls ends = new int[players]; // Array holding end markers for play-off rounds. int start = 0, // Entry range start index. end = players - 1, // Entry range end index. r = 0, // Roll-off round index. sdStart; // Indicator for start marker of tied players. // Starting dice roll order gives no advantage, so set it arbitrarily : for(int p = 0; p < players; p++) playOrder[p] = p + 1; // Players #1, #2, #3, etc. System.out.println("Initial Play Order: " + Arrays.toString(playOrder)); System.out.println(); ends[0] = end; // Original end marker saved in ends array. /* Repeatedly roll dice, sort play order by dice number, sort dice descending, find tied players and roll dice again for these till all players sorted. */ do { rollDice(rolls, start, end); System.out.println("Dice Rolls: " + Arrays.toString(rolls)); sortByDice(playOrder, rolls, start, end); // Sort players range by dice number sortDescending(rolls, start, end); // Sort dice rolls range descending System.out.println("Sorted Dice Roll-Off (Round #" + r + "): " + Arrays.toString(rolls)); System.out.println("Player Order (Round #" + r + "): " + Arrays.toString(playOrder)); // Check for two or more players tying the same dice number : sdStart = sameDice(rolls, start, end); if (sdStart == -1) // If no ties this round... { // Until a tie found or all sorted ... while (end < players - 1 && sdStart == -1) { r--; //... move to previous round, if any... start = end + 1; // ... reset start ... end = ends[r]; //... and end marks. if (start < end) // If > one unsorted player in round ... sdStart = sameDice(rolls, start, end); // ... check for tie } } if (sdStart != -1) // When ties found ... { ends[r] = end; // ... save end marker of previous roll-off start = sdStart; // ... reset start ... end = lastIndexOf(rolls, rolls[start], start, end); //... and end markers ... r++; // ... and increment roll-off round index System.out.println("Start (Round #" + r + "): " + start); System.out.println("End (Round #" + r + "): " + end); } } while (sdStart != -1); return playOrder; } /** Method to generate dice rolls for a set of players in a board game whose previous roll resulted in their tying on the same dice number. All players within a contiguous index range roll dice again. @param rolls : An int array holding the previous dice rolls sorted descending. Since rolls is a referenced object it is also effectively a return parameter. @param start : An int value holding the index of the first tied player. @param end : An int value holding the index of the last tied player. */ private static void rollDice(int[] rolls, int start, int end) { if (rolls == null || start < 0 || end > rolls.length - 1 || end < start) System.out.println("Error in rollDice(...) method ! " + "\nInvalid input parameter(s)."); else for(int i = start; i < end + 1; i++) rolls[i] = (int)(6 * Math.random() + 1); } /** Method to sort a given contiguous range of an int array in descending order. All entries between and including two given indices are sorted. Sorting is first done in ascending order. Then the resulting entries are reflected about the array centre. @param ints : The int array to be sorted in descending order. This parameter also serves as a return parameter. @param start : The start index of the range of ints to be sorted. @param end : The end index of the range of ints to be sorted. */ private static void sortDescending(int[] ints, int start, int end) { if (ints == null || start < 0 || end > ints.length - 1 || end < start ) System.out.println("Error in sortDescending(...) method ! " + "\nInvalid input parameter(s)."); else { int copy; // Use Arrays.sort(.) method to put in ascending order : Arrays.sort(ints, start, end + 1); // INCLUSIVE lower- & EXCLUSIVE upper index // Reflect ascending sorted values about the array centre : for(int i = start; i < (start + end + 1)/2; i++) { copy = ints[i]; ints[i] = ints[end - i + start]; ints[end - i + start] = copy; } } } /** Method to sort a contiguous index range of an int array holding player order according to the dice value rolled by the respective players. @param players : An int array holding the player numbers, entries lying between one and the maximum number of players. This also serves as a return parameter. @param rolls : An int array holding players' dice numbers; entries in range 1 .. 6. @param start : The start index (inclusive) for the range of players to be sorted. @param end : The end index (inclusive) for the range of players to be sorted. */ private static void sortByDice(int[] players, int[] diceNums, int start, int end) { if (players == null || diceNums == null || start < 0 || end < start || end > players.length - 1) System.out.println("Error in sortByDice(....) method ! " + "\nInvalid input parameter(s)."); else { Integer[] playersI = new Integer[players.length]; // Copy int[] players to Integer[] playersI, as needed by Comparator interface: for(int i = 0; i < players.length; i++) playersI[i] = players[i]; Arrays.sort(playersI, start, end + 1, new Comparator() { @Override public int compare(Integer x, Integer y) { return ( diceNums[firstIndexOf(players, y, start, end)] - diceNums[firstIndexOf(players, x, start, end)] ); } }); // Convert players Integer[] back into int[] : for(int i = 0; i < players.length; i++) players[i] = playersI[i]; } } /** Method to find the first group of players on tied dice after a roll-off. Only players in the index range [start .. end] inclusive are checked for tied dice. The method returns the start index for the first tied group; or -1 if no ties exist. @param rolls : An int array holding the sorted-descending dice values obtained at the dice-roll for play order. @param start : An int value holding the index of the first element in the range. @param end : An int value holding the index of the last element in the range. @return : An int value holding the start index for the first tied player or else -1 to indicate absence of tied players or -9 to indicate parameter error. */ private static int sameDice(int[] rolls, int start, int end) { if (rolls == null || start < 0 || end < start || end > rolls.length - 1) { System.out.println("Error in sameDice(...) method ! " + "\nInvalid input parameter(s)."); return -9; // Input error indicator } else { int i, istart = -1; // Default index for start marker is fail indicator, -1 for(i = start; i < end && rolls[i] != rolls[i + 1]; i++); if (i < end) istart = i; // Record index of first tied player. // Return first tied player's index or else fail indicator : return istart; } } /** Method to find the first index of an int value within a range of an int array. @param ints : An int array holding the values to check x against. @param x : An int value believed to be present in the ints array. @param start : An int value holding the first index of the range checked. @param end : An int value holding the last index of the range checked. @return : Returns either the first index of ints that holds x; -1 to indicate absence of x from ints; and -9 to indicate error invalid data. */ private static int firstIndexOf(int[] a, int x, int start, int end) { if (a == null || x < 1 || x > a.length || start < 0 || end < start || end > a.length - 1) { System.out.println("Error in sameDice(...) method ! " + "\nInvalid input parameter(s)."); return -9; // Input error indicator } else { int i = 0; for(i = start; i < end + 1 && a[i] != x; i++); if (i < a.length) return i; else return -1; // Search fail indicator } } /** Method to find the last index of an int value in a range of an int array. @param ints : An int array holding the values to check x against. @param x : An int value believed to be present in the ints array. @param start : An int value holding the first index of the range checked. @param end : An int value holding the last index of the range checked. @return : Returns either the last index of ints that holds x; -1 to indicate absence of x from ints; and -9 to indicate invalid input. */ private static int lastIndexOf(int[] a, int x, int start, int end) { if (a == null || x < 1 || x > 6 || start < 0 || end < start || end > a.length - 1) { System.out.println("Error in lastIndexOf(...) method ! " + "\nInvalid input parameter(s)."); return -9; } else { int i; for(i = end; i > start - 1 && a[i] != x; i--); if (i > -1) return i; else return -1; // Search fail indicator } } }
SAMPLE OUTPUT: ============= Initial Play Order: [1, 2, 3, 4, 5, 6, 7, 8] Dice Rolls: [3, 6, 6, 2, 1, 1, 2, 1] Sorted Dice Roll-Off (Round #0): [6, 6, 3, 2, 2, 1, 1, 1] Player Order (Round #0): [2, 3, 1, 4, 7, 5, 6, 8] Start (Round #1): 0 End (Round #1): 1 Dice Rolls: [4, 2, 3, 2, 2, 1, 1, 1] Sorted Dice Roll-Off (Round #1): [4, 2, 3, 2, 2, 1, 1, 1] Player Order (Round #1): [2, 3, 1, 4, 7, 5, 6, 8] Start (Round #1): 3 End (Round #1): 4 Dice Rolls: [4, 2, 3, 3, 4, 1, 1, 1] Sorted Dice Roll-Off (Round #1): [4, 2, 3, 4, 3, 1, 1, 1] Player Order (Round #1): [2, 3, 1, 7, 4, 5, 6, 8] Start (Round #1): 5 End (Round #1): 7 Dice Rolls: [4, 2, 3, 4, 3, 1, 3, 3] Sorted Dice Roll-Off (Round #1): [4, 2, 3, 4, 3, 3, 3, 1] Player Order (Round #1): [2, 3, 1, 7, 4, 6, 8, 5] Start (Round #2): 5 End (Round #2): 6 Dice Rolls: [4, 2, 3, 4, 3, 4, 3, 1] Sorted Dice Roll-Off (Round #2): [4, 2, 3, 4, 3, 4, 3, 1] Player Order (Round #2): [2, 3, 1, 7, 4, 6, 8, 5] Final Player Order is : [2, 3, 1, 7, 4, 6, 8, 5] Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72
0 comments:
Post a Comment