Problem Statement
Ash and Elsh invented a new variant of the game Rock-Paper-Scissors called DoubleRoshambo. In the normal game, each of the two players change their right hand into one of these gestures: rock, paper, or scissors. Rock beats scissors; scissors beat paper; paper beats rock. For example, if Ash plays rock and Elsh plays paper, then Elsh wins. In DoubleRoshambo, each player uses both hands. Each hand may play different gestures. A player scores: 2 points, if his right hand beats his opponent’s right hand, and his left hand beats his opponent’s left hand. 1 point, if his right hand beats his opponent’s right hand, and his left hand plays the same gesture as his opponent’s left hand. 0 points, in all other cases.
Ash and Elsh played DoubleRoshambo several rounds. You are given two String[]s A and E, representing the gestures that Ash and Elsh played, respectively. Each element of A and E will contain two characters. The first character is for their left hand and the second character is for their right hand. For each hand, the character will be one of ‘R’, ‘P’, or ‘S’, representing rock, paper, or scissors, respectively.
Tutorial
The problem is solved using greedy approach, we can greedily pick 2 points entries first and then solve for 1 points. I’ll prove this by mathematical induction.
Code
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
public class DoubleRoshambo {
int cost(char ash, char other)
{
if(ash == 'R' && other == 'S') return 1;
if(ash == 'S' && other == 'P') return 1;
if(ash == 'P' && other == 'R') return 1;
return 0;
}
public int maxScore(String[] A, String[] E) {
int lena, lenb, cost;
lena = A.length;
lenb = E.length;
cost = 0;
boolean[] visitA = new boolean[lena + 1];
boolean[] visitB = new boolean[lenb + 1];
for(int i = 0; i < lena ;i ++)
{
for(int j = 0 ;j < lenb ;j ++)
{
if(!visitA[i] && !visitB[j] )
{
if(cost(A[i].charAt(0), E[j].charAt(0)) == 1)
if(cost(A[i].charAt(1), E[j].charAt(1)) == 1)
{
cost += 2;
visitA[i] = true;
visitB[j] = true;
}
}
}
}
for(int i = 0; i < lena ;i ++)
{
for(int j = 0 ;j < lenb ;j ++)
{
if(!visitA[i] && !visitB[j] )
{
if(A[i].charAt(0) == E[j].charAt(0))
if(cost(A[i].charAt(1), E[j].charAt(1)) == 1)
{
cost += 1;
visitA[i] = true;
visitB[j] = true;
}
}
}
}
return cost;
}
}