# Untitled

unknown
plain_text
2 years ago
5.6 kB
108
Indexable
Never
```import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;

public class Dice {
public static void main(String[] args) {
int player1Position = 1;
int player2Position = 10;

Map<Integer, Integer> sums = new HashMap<>();

for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
for (int k = 1; k <= 3; k++) {
sums.compute(i + j + k, (key, value) -> (value == null) ? 1 : value + 1);
}
}
}
int goal = 21;

Set<List<Integer>> pathsTo21A = getWinPaths(player1Position, sums, goal);
Set<List<Integer>> pathsTo21B = getWinPaths(player2Position, sums, goal);

int maxStep1 = pathsTo21A.stream().mapToInt(List::size).max().orElse(0);
int maxStep2 = pathsTo21B.stream().mapToInt(List::size).max().orElse(0);

Set<List<Integer>> inverseStepsToPaths1 = getLossPaths(player1Position, sums, goal, maxStep2);
Set<List<Integer>> inverseStepsToPaths2 = getLossPaths(player2Position, sums, goal, maxStep1);

BigInteger aWinners = mergeFirstWinners(pathsTo21A, inverseStepsToPaths2, sums);
System.out.println(aWinners);
BigInteger bWinners = mergeSecondWinners(pathsTo21B, inverseStepsToPaths1, sums);
System.out.println(bWinners);

System.out.println(bWinners.max(aWinners));
}

private static BigInteger mergeFirstWinners(Set<List<Integer>> first, Set<List<Integer>> second, Map<Integer, Integer> splitsForStep) {
Map<Integer, List<List<Integer>>> sizeToPathMap = second.stream().collect(Collectors.groupingBy(List::size, Collectors.toList()));

BigInteger winners = new BigInteger("0");
for (List<Integer> path : first) {
for (List<Integer> secondPath : sizeToPathMap.getOrDefault(path.size() - 1, Collections.emptyList())) {
BigInteger mergedPath = new BigInteger("1");
for (int i = 0; i < path.size(); i++) {
mergedPath = mergedPath.multiply(new BigInteger("" + splitsForStep.get(path.get(i))));
if (i != path.size() - 1) {
mergedPath = mergedPath.multiply(new BigInteger("" + splitsForStep.get(secondPath.get(i))));
}
}
}
}

return winners;
}

private static BigInteger mergeSecondWinners(Set<List<Integer>> second, Set<List<Integer>> firstInverse, Map<Integer, Integer> splitsForStep) {
Map<Integer, List<List<Integer>>> sizeToPathMap = firstInverse.stream().collect(Collectors.groupingBy(List::size, Collectors.toList()));

BigInteger winners = new BigInteger("0");
for (List<Integer> path : second) {
for (List<Integer> firstPath : sizeToPathMap.getOrDefault(path.size(), Collections.emptyList())) {
BigInteger mergedPath = new BigInteger("1");
for (int i = 0; i < path.size(); i++) {
mergedPath = mergedPath.multiply(new BigInteger("" + splitsForStep.get(firstPath.get(i))));
mergedPath = mergedPath.multiply(new BigInteger("" + splitsForStep.get(path.get(i))));
}
}
}

return winners;
}

private static Set<List<Integer>> getWinPaths(int position, Map<Integer, Integer> sums, int goal) {
Set<List<Integer>> pathsTo21 = new HashSet<>();

Queue<State> stateQueue = new ArrayDeque<>();
while (!stateQueue.isEmpty()) {
State currState = stateQueue.poll();

if (currState.score >= goal) {
continue;
}

for (Integer step : sums.keySet()) {
int nextPosition = currState.position + step;
if (nextPosition > 10) {
nextPosition -= 10;
}

State nextState = new State(nextPosition, currState.score + nextPosition, currState.steps);
}
}

return pathsTo21;
}

private static Set<List<Integer>> getLossPaths(int position, Map<Integer, Integer> sums, int goal, int maxSteps) {
Set<List<Integer>> pathsToNot21 = new HashSet<>();
for (int step = 1; step <= maxSteps; step++) {
Queue<State> stateQueue = new ArrayDeque<>();
while (!stateQueue.isEmpty()) {
State currState = stateQueue.poll();

if (currState.score >= goal) {
continue;
}

if (currState.steps.size() == step) {
continue;
}

for (Integer diceStep : sums.keySet()) {
int nextPosition = currState.position + diceStep;
if (nextPosition > 10) {
nextPosition -= 10;
}

State nextState = new State(nextPosition, currState.score + nextPosition, currState.steps);
}
}
}

return pathsToNot21;
}

public static class State {
int position;
int score;
List<Integer> steps;

public State(int position, int score) {
this.position = position;
this.score = score;
steps = new ArrayList<>();
}

public State(int position, int score, List<Integer> steps) {
this.position = position;
this.score = score;
this.steps = new ArrayList<>(steps);
}