Untitled

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))));
          }
        }
        winners = winners.add(mergedPath);
      }
    }

    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))));
        }
        winners = winners.add(mergedPath);
      }
    }

    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<>();
    stateQueue.add(new State(position, 0));
    while (!stateQueue.isEmpty()) {
      State currState = stateQueue.poll();

      if (currState.score >= goal) {
        pathsTo21.add(currState.steps);
        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);
        nextState.addStep(step);
        stateQueue.add(nextState);
      }
    }


    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<>();
      stateQueue.add(new State(position, 0));
      while (!stateQueue.isEmpty()) {
        State currState = stateQueue.poll();

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

        if (currState.steps.size() == step) {
          pathsToNot21.add(currState.steps);
          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);
          nextState.addStep(diceStep);
          stateQueue.add(nextState);
        }
      }
    }

    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);
    }

    public void addStep(int step) {
      steps.add(step);
    }
  }
}