有谁知道以下骰子问题的更好解决方案?

Question

有许多骰子，输入数组包含骰子正面朝上的数字。骰子是6面的。计算骰子的最小旋转总数，使所有面都相同。1 只需要旋转一次即可使 2、3、4 和 5 朝上，但至少需要旋转两次才能使其成为面 6，因为 6 是 1 的对面。2 的对面是 5,3 是 4。

我已经提出了一个解决方案，但我认为应该有一个更好的解决方案。

例如：

1. A = {1,1,6}，答案 = 2。旋转 6 两次得到 1。
2. A = {1,2,3}，答案 = 2。旋转 1 和 2 并使它们成为 3。

3. A = {1,6,2,3}，答案 = 3。旋转 1、6 和 3 使它们全部为 2。

   import java.util.*;
   public class DiceProblem {
   public static void main(String args[]){
   int[] A = {3,4,1,2,4,2,3,5,1,2,3,4,6,2,4,1,5,2};
   Map<Integer, Integer> countMap = new HashMap<>();
   int rotation = 0;
   int diceCount;
   int maxDiceNumber = A[0];
   int OppositeOfMaxDiceNumber;
   int max = 1;
   for(int i = 1; i <= 6 ; i++){
   diceCount = 0;
   for (int value : A) {
   if(i == value){
   diceCount++;
   }
   }
   countMap.put(i, diceCount);
   if(diceCount > max){
   max = diceCount;
   maxDiceNumber = i;
   }
   }
   if(max == 1){
   if(countMap.get(1).equals(countMap.get(6)) && countMap.get(1) != 0 && countMap.get(2) != 0){
   maxDiceNumber = 2;
   }else if(countMap.get(2).equals(countMap.get(5))  && countMap.get(2) != 0 && countMap.get(3) != 0){
   maxDiceNumber = 3;
   }else if(countMap.get(3).equals(countMap.get(4)) && countMap.get(1) != 0){
   maxDiceNumber = 1;
   }else if(countMap.get(2) != 0){
   maxDiceNumber = 2;
   }else if(countMap.get(5) != 0){
   maxDiceNumber = 5;
   }else if(countMap.get(6) != 0){
   maxDiceNumber = 6;
   }
   }
   System.out.println("Max Dice Number: "+ maxDiceNumber);
   OppositeOfMaxDiceNumber = createOpposite(maxDiceNumber);
   System.out.println("Opposite Dice Number: "+ OppositeOfMaxDiceNumber);
   Iterator it2 = countMap.entrySet().iterator();
   while (it2.hasNext()) {
   Map.Entry pair = (Map.Entry)it2.next();
   System.out.println(pair.getKey() + " = " + pair.getValue());
   if((int)(pair.getValue()) > 0 && (int)(pair.getKey()) != maxDiceNumber){
   if((int)(pair.getKey()) == OppositeOfMaxDiceNumber){
   rotation = rotation + (2  * (int)(pair.getValue()));
   }else {
   rotation = rotation + ((int)(pair.getValue()));
   }
   }
   it2.remove(); // avoids a ConcurrentModificationException
   }
   System.out.println("Number of Minimum Rotations: "+ rotation);
   }
   private static int createOpposite(int key){
   switch (key) {
   case 1:
   return 6;
   case 2:
   return 5;
   case 3:
   return 4;
   case 4:
   return 3;
   case 5:
   return 2;
   case 6:
   return 1;
   }
   return 0;
   }}
   

Answer 1

public class DiceProblem {
public static void main(String args[]){
int[] A = {3,4,1,2,4,2,3,5,1,2,3,4,6,2,4,1,5,2};
int flip_count;
int min_flip_count = 9999999;
for (int value : A) {
flip_count = 0;
for (int i : A) {
if (value == i) {
flip_count += 0;
} else if (value + i == 7) {
flip_count += 2;
} else {
flip_count += 1;
}
}
if (flip_count < min_flip_count) {
min_flip_count = flip_count;
}
}
System.out.println("Minimum Flip Count:" + min_flip_count);
}
}

Answer 2

我想了一会儿，试图想出一个比蛮力更好的解决方案;也就是说，不要只考虑将所有骰子送到6个潜在位置中的每一个需要什么。 我敢打赌有一些聪明的方法可以做到这一点，但我无法想出它。

所以我写了我自己的蛮力解决方案版本，试图简化你的代码。 第一个观察结果是，骰子的两边总是加起来为 7，因此给定一个骰子值，总是通过从 7 中减去该值来找到相反的值。 不需要一堆if语句，或查找或任何东西。 一个简单的减法就可以完成。如果你想看看两个位置是否相反，看看它们加起来是否等于 7。

然后我只是写代码做最直接的事情...考虑每个骰子位置，计算翻转次数以使所有骰子到达该位置，并在我们进行时跟踪最小翻转位置。

更新：可以完成的一项优化是在每个位置创建一次模具计数。 然后，我们不必每次都通过外循环处理每个骰子，而是处理每个骰子的位置计数。 我更新了之前发布的代码的第一个版本以使用此优化。 这意味着无论您的列表中有多少骰子，您都将有 6 * 6 = 36 对位置需要考虑。

有了这一切，这就是我想出的代码：

public class DiceProblem {
public static void main(String args[]) {
int[] A = {3,4,1,2,4,2,3,5,1,2,3,4,6,2,4,1,5,2};
// Figure out how many dice we have in each position
int[] pos_counts = {0, 0, 0, 0, 0, 0, 0};
for (int start_pos : A)
pos_counts[start_pos] += 1;
// Initilize our accumulators for minimum flips and which position that was
int min_flips = Integer.MAX_VALUE;
int min_flip_pos = 0;
// Consider each of the 6 dice positions...
for (int position = 1 ; position <= 6 ; position++) {
// initialize the number of flips
int flips = 0;
// Go through all the dice starting positions and tally up the flips necessary to get all dice to the position
// we are considering
for (int start_pos = 1 ;  start_pos <= 6 ; start_pos++) {
if (start_pos + position == 7)  // opposite sides of a dice always add up to 7
flips += 2 * pos_counts[start_pos];
else if (start_pos != position)
flips += pos_counts[start_pos];
}
// If this is a smaller number of flips than we've seen before, record it as the new best choice
if (flips < min_flips) {
min_flips = flips;
min_flip_pos = position;
}
}
System.out.println(String.format("%d flips to die position %d", min_flips, min_flip_pos));
}
}

结果：

15 flips to die position 2

这与你的代码想出的答案相同。

Answer 3

对于一个好的解决方案，请考虑每边需要多少圈。

• 对于已经朝上的骰子，需要 0 圈。
• 对于对面朝上的骰子(例如 3 对 4)，需要 2 圈。
• 对于所有其他骰子，它需要 1 圈。

您可以使用它来编写如下函数：

int turnsForSide(int side, Map<Integer, Long> sideCount);

side是你要找的那一面;Map<Integer, Long> sideCount的键表示骰子的一面，而骰子的值是你在那边的骰子数量。

现在你所要做的就是得到每一边的计数;这是相当微不足道的。编写如下函数：

Map<Integer, Long> getSideCounts(int[] sidesUp);

如果你有这两个函数，你可以只迭代地图并找到具有最小值的边。

int[] A = {3,4,1,2,4,2,3,5,1,2,3,4,6,2,4,1,5,2};
Map<Integer, Long> counts = getSideCounts(A);
Map<Integer,Integer> turns = new HashMap<Integer, Integer>();
for (int i = 1; i < 7; i++) {
turns.put(i, turnsForSide(i, counts));
}
// you could also retain the minimum in the loop above to avoid another iteration
turns.entrySet().stream().min(Comparator.comparing(Map.Entry::getValue))
.map(entry -> String.format("minimum amount: %d for side %d", entry.getValue(), entry.getKey()))
.ifPresent(System.out::println);

这是相当有效的，因为你只需要迭代一次原始数组，然后是边的映射是固定的迭代量(6)，所以如果我没记错复杂性理论，总的来说，这应该是O(n)。

我确实有函数的代码，但由于它似乎是家庭作业，我认为如果您先尝试编写它会更有帮助。