java - 将两个给定数组配对并赢得大部分比较的最佳策略

Question

我正在做以下编程练习:Can you win the codewar? 。声明如下:

Two kingdoms are at war ⚔️ and, thanks to your codewarrior prowesses, you have been named general by one of the warring states. Your opponent's armies are larger than yours, but maybe you can reach a stalemate or even win the conflict if you are a good strategist.

You control the same number of armies as the rival state, but theirs are generally larger. You have to send a single army to fight each of your opponent's ones.
(It implies there will be as many battles as armies).
There are no possible David-and-Goliath surprises : the outcome of a battle is always the victory of the larger army (or a standoff if both are of the same size).
The winning side is the one which wins the most battles.
The outcome can be a stalemate if both win the same number.

You have to write a function

codewarResult(codewarrior, opponent)

that takes as input each side's armies as arrays of positive integers which represent their sizes. The function returns the strings "Defeat" , "Stalemate" or "Victory" depending on the outcome of the war for your side with an optimal strategy on your behalf.

For example, if you have 3 armies of sizes [1,4,1] and the rival state has armies of sizes [1,5,3] , despite you having on average smaller forces, it is possible to reach a stalemate :

1-1 : standoff
4-3 : victory for you
1-5 : victory for the opposing army

when the dust settles, you have won one battle, lost one, and one was indecisive so

codewarResult([1,4,1],[1,5,3])

should return "Stalemate".
More examples :

codewarResult([2,4,3,1],[4,5,1,2])

should return "Victory" because it is possible to win by disposing your amies this way :

2-1
4-4
3-2
1-5

thus winning two battles, deadlocking one and losing one.

codewarResult([1,2,2,1],[3,1,2,3])

should return "Defeat" because even with an optimal strategy it is not possible to win. The best you can do is one victory and one tie :

1-3
2-1
2-2
1-3

我尝试过以下算法:

import java.util.*;
public class Kata {
  public static String codewarResult(int[] codewarrior, int[] opponent) {
    System.out.println("codewarrior: "+Arrays.toString(codewarrior));
    System.out.println("opponent: "+Arrays.toString(opponent));

    List<Integer> opponentMatchedIndexes = new ArrayList<Integer>();
    int closestTo1 = Integer.MIN_VALUE;
    int indexInCodewarrior = 0;
    int indexInOpponent = 0;
    int score = 0;
    int battleResult = 0;

    for(int i = 0; i < codewarrior.length; i++){
      closestTo1 = Integer.MIN_VALUE;
      indexInCodewarrior = 0;
      indexInOpponent = 0;
      for(int j = 0; j < opponent.length; j++){
        battleResult = codewarrior[i]-opponent[j];
        if(!opponentMatchedIndexes.contains(j) && battleResult>closestTo1 && battleResult<=1){
          closestTo1 = battleResult;
          indexInCodewarrior = i;
          indexInOpponent = j;
        }
      }
      score+=closestTo1 < 0 ? -1 : closestTo1 == 0 ? 0 : 1;
      opponentMatchedIndexes.add(indexInOpponent);

      System.out.println("closesTo1: "+closestTo1);
      System.out.println("indexInCodewarrior: "+indexInCodewarrior);
      System.out.println("indexInOpponent: "+indexInOpponent);
      System.out.println("NumberInCodewarrior: "+codewarrior[indexInCodewarrior]);
      System.out.println("NumberInOpponent: "+opponent[indexInOpponent]);
      System.out.println("opponentMatchedIndexes: "+opponentMatchedIndexes);
      System.out.println("score: "+score);
    }

    return score<0?"Defeat":score==0?"Stalemate":"Victory";
  }
}

我们发现了一个测试，当它应该输出“Victory”时，它会输出“Stalemate”:

@Test
public void testRandom() {
        int[] codewarrior = {2,5,1,4,1};
        int[] opponent =    {2,4,1,1,8};
    System.out.println(Arrays.toString(codewarrior)+" vs "+Arrays.toString(opponent));
    assertEquals("Victory", Kata.codewarResult(codewarrior, opponent));
}

我们已经写了应该做什么的代码:

2-1 = 1 --> score = 1; 5-4 = 1 --> score = 2; 1-1 = 0 --> score = 2; 4-2 = 2 --> score = 3; 1-8 = -7 --> score = 2

我们已经输入了现在正在执行的代码:

2-1 = 1 --> score = 1; 5-4 = 1 --> score = 2; 1-1 = 0 --> score = 2; 4-8 = -4 --> score = 1; 1-8=-7 --> score = 0

正如您在第 4 步中注意到的那样，它应该执行 4-2 = 2 --> 分数 = 3；然而它确实是 4-8=-4 --> 分数 = 1。

我们已经找到了应该更改代码的行，并且我们也考虑了需要更改的内容，但是我们很难弄清楚到底需要如何更改它!

特别是我们需要更改以下代码行:

if(!opponentMatchedIndexes.contains(j) && battleResult>closestTo1 && battleResult<=1){

因为battleResult<=1限制了我们的算法需要取4-2 = 2的时候，解释是由于battleResult = 2 > 1，它只是跳过了保存数字的指令，里面如果。

此外我们还读到:

Math.max and Math.min outputting highest and lowest values allowed get closest value to a number in array

此外，我们如何调试更大的测试？我的意思是，以下测试也失败了，但是由于其输入数组的大小较大，因此很难弄清楚发生了什么:

@Test
public void testNumerousArmies() {
        int[] codewarrior = {2,1,3,1,1,3,3,2,3,1,1,1,3,1,3,1,3,3,1,2,3,3,1,3};
        int[] opponent =    {4,4,1,4,3,1,4,4,3,2,1,2,1,3,3,1,4,4,3,2,3,2,4,1};
    System.out.println(Arrays.toString(codewarrior)+" vs "+Arrays.toString(opponent));
    assertEquals("Stalemate", Kata.codewarResult(codewarrior, opponent));
}

如果您好奇完整的测试套件是:

import java.util.Arrays;
import org.junit.Test;
import static org.junit.Assert.assertEquals;

// TODO: Replace examples and use TDD development by writing your own tests

public class SolutionTest {
    @Test
    public void testStalemate() {
            int[] codewarrior = {1,4,1};
            int[] opponent =    {1,5,3};
        System.out.println(Arrays.toString(codewarrior)+" vs "+Arrays.toString(opponent));
        assertEquals("Stalemate", Kata.codewarResult(codewarrior, opponent));
    }

    @Test
    public void testVictory() {
            int[] codewarrior = {2,4,3,1};
            int[] opponent =    {4,5,1,2};
        System.out.println(Arrays.toString(codewarrior)+" vs "+Arrays.toString(opponent));
        assertEquals("Victory", Kata.codewarResult(codewarrior, opponent));
    }

    @Test
    public void testDefeat() {
            int[] codewarrior = {1,2,2,1};
            int[] opponent =    {3,1,2,3};
        System.out.println(Arrays.toString(codewarrior)+" vs "+Arrays.toString(opponent));
        assertEquals("Defeat", Kata.codewarResult(codewarrior, opponent));
    }

    @Test
    public void testEqualArmies() {
            int[] codewarrior = {1,1,1,1};
            int[] opponent =    {1,1,1,1};
        System.out.println(Arrays.toString(codewarrior)+" vs "+Arrays.toString(opponent));
        assertEquals("Stalemate", Kata.codewarResult(codewarrior, opponent));
    }

    @Test
    public void testSingleArmy() {
            int[] codewarrior = {5};
            int[] opponent =    {6};
        System.out.println(Arrays.toString(codewarrior)+" vs "+Arrays.toString(opponent));
        assertEquals("Defeat", Kata.codewarResult(codewarrior, opponent));
    }

    @Test
    public void testNumerousArmies() {
            int[] codewarrior = {2,1,3,1,1,3,3,2,3,1,1,1,3,1,3,1,3,3,1,2,3,3,1,3};
            int[] opponent =    {4,4,1,4,3,1,4,4,3,2,1,2,1,3,3,1,4,4,3,2,3,2,4,1};
        System.out.println(Arrays.toString(codewarrior)+" vs "+Arrays.toString(opponent));
        assertEquals("Stalemate", Kata.codewarResult(codewarrior, opponent));
    }


    @Test
    public void testRandom() {
            int[] codewarrior = {2,5,1,4,1};
            int[] opponent =    {2,4,1,1,8};
        System.out.println(Arrays.toString(codewarrior)+" vs "+Arrays.toString(opponent));
        assertEquals("Victory", Kata.codewarResult(codewarrior, opponent));
    }
}

我们如何编写最佳策略来配对两个给定数组，并赢得大部分比较？

Answer 1

首先你需要根据战斗力对数组进行排序。从您比较的最高值开始。

1. 如果你无法赢得战斗，你就会用最低的力量来对抗。
2. 如果是对峙。您现在有 2 个选择。要么让它成为僵局，要么在赢得别人的战斗中失败。所以现在您要更深入地测试结果，看看您在哪里获胜最多。

示例:

codewarChallenge([2,4,3,1],[4,5,1,2])

按顺序排列:([1,2,3,4],[1,2,4,5])

4-5 你会输，所以玩 1-5。现在你已经离开了 ([2,3,4],[1,2,4])

4-4对峙。两个选项 4-4 或 2-4。

当您玩 4-4 时，您还剩下 ([2,3],[1,2])，您将同时获胜

当您玩剩下的 2-4 ([3,4],[1,2]) 时，您将同时获胜

所以 4-4 是更好的选择。

您将需要采用递归模式。创建一个接受两个数组的函数，并给出分数作为返回值。 0 代表失败，1 代表对峙，2 代表胜利。现在，当您遇到僵局时，递归调用该函数以获得两个选项的其余分数。得分最高者获胜..