Uneven Fight Solution
I was working on a Codewars problem not too long ago, and I wanted to write about my solution to it. Partly because it was an interesting problem, but also because it reminded me of a puzzle I once did in a Professor Layton game.
Here’s the original prompt:
The biggest problem is that accumulative strength of the gray forces is greater than the accumulative strength of the red forces. So, when the forces are lined up against each other in descending order, the red forces lose every match up. It seems like a pretty hopeless fight, but read the prompt carefully: Arrange your forces so that the red side avoids defeat. Your goal isn’t to win, just to not lose, and that may be more manageable. Let’s try this line-up:
Because you’re able to dictate who fights who, you can make red’s weakest forces fight gray’s strongest, and completely waste gray’s advantage. Then, red’s strongest forces can win a few narrow victories. And then the final fight can end in a stalemate, making the final score two wins, two loses, and one stalemate, and a stalemate overall. And with that, red has avoided defeat!
Skip forward to a few weeks ago, and I run into this kata on Codewars: https://www.codewars.com/kata/5e3f043faf934e0024a941d7
This is the same problem/puzzle, but minus all the charm of Professor Layton. That, and instead of taking your time, and flipping the forces around by hand until you find a winning solution, you know need to prepare some code to do it for you. The goal is also to win as many battles as possible, but also admit defeat when it can’t win, or settle for stalemates. I think it’s a fun little kata, and I suggest giving it a shot before reading ahead.
Algorithmic Solution
The same tricks we used in Layton’s puzzle to get a stalemate can used again, but it needs to be translated into some conditional statements. There’s two things we need to be aiming for:
- Our forces smallest values need to be matched against the opposing forces’ largest values. The lowest possible value will be 1, and it will lose every fight except against another 1. So, while they can’t win any fights, they can control how our forces lose. By matching our lowest values against their highest, we hopefully eliminate their biggest strengths, and leave room for our highest values to score easy wins.
- When we do field our biggest forces, we want them to facing the largest force they can beat. Again, the goal is to whittle down the opposing forces largest values. But unlike with our lowest values, these match-ups will end in victory.
As a flowchart, it should look something like this:
Simply follow this pattern until every force has been paired up, and this should provide the most possible victories. Let’s try it with one of the example cases: [2, 4, 3, 1] vs. [4, 5, 2, 1].
On the first pass, our largest values on each side are 4 and 5, and the smallest are 1 and 1. 4 can’t beat 5, and 1 and 1 are equal, so the first match will be between 1 and 5, a loss.
On the second pass, the largest values are 4 and 4, and the smallest are 2 and 1. 4 can’t beat 4, and 2 is greater than 1, so the second match will be 2 and 1, a win.
On the third pass, the largest values are 4 and 4, and the smallest are 3 and 2. 4 can’t beat 4, and 3 is greater than 2, so the third match will be 3 and 2, a win.
The final pass means that the remaining values are the largest and smallest values. 4 can’t beat 4, and 4 is equal to 4, so they are matched up for a stalemate.
In the end, that’s two wins, one loss, and a stalemate, which makes an overall victory. I did a few things differently in my full solution, https://github.com/CarlKarlQarl/Codewars/blob/master/CanYouWinTheCodewar.js, but in the end, the focus needs to be on the largest and smallest values at any given time, and pairing them up accordingly.
