Develop a dynamic programming solution to the Crazy-8 game in java. Input: a seq

Question

Develop a dynamic programming solution to the Crazy-8 game in java.

Input: a sequence of cards c[0], c[1] … c[n-1]

Example: 7S 7H KD KC 8H (7 of Spades, 7 of Hearts, King of Diamonds, King of Clubs, 8 of Hearts)

Output: the longest “trick subsequence” c[i1] c[i2] … c[ik], where i1 < i2 . . .< ik

Definition of a Trick Subsequence: For it to be a trick subsequence, it must be that "j, c[ij] and c[ij+1] “match” that is

• they either have the same rank

• or they are from the same suit

• or one of them is an 8 For the above example (card sequence: 7S 7H KD KC 8H),

the longest trick subsequence is: KD KC 8H i = 1 i = 2 i = 3 i = 4 i = 5 C[i] 7S 7H KD KC 8H

Max Score[i] 1 2 1 2 3 Sub Pointer 0 1 0 3 4 For the above example (card sequence: 7C 7H KC KS 8D), the longest trick subsequence is: 7C KC KS 8D i = 1 i = 2 i = 3 i = 4 i = 5 C[i] 7C 7H KC KS 8D

Max Score[i] 1 2 2 3 4 Sub Pointer 0 1 1 3 4 The following main program will be used to create a random card sequence, and your program will print the trick sequence. The card sequence is a sequence of two characters – a single character rank followed by a single character for suit. The rank of 10 is omitted. Main Program: package cse361;

import java.util.*;

public class Main {

public static void main(String[] args) {

String[] ranks = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "J", "Q", "K", "A"};

String[] suits = {"C", "S", "H", "D"};

int seqLength = Integer.parseInt(args[0]);

String[] cardSeq = new String[seqLength];

int cntCards = ranks.length;

int cntSuite = suits.length;

for (int i = 0; i < seqLength; i++) {

// generate the first random number

int rand1 = (int)(Math.random()*cntCards);

int rand2 = (int)(Math.random()*cntSuite);

cardSeq[i] = ranks[rand1] + suits[rand2]; }

// Print card cardSeq

for (int i = 0; i < cardSeq.length; i++)

System.out.println (cardSeq[i]);

// Create Card Sequence

Crazy8 crazy8Seq = new Crazy8 (cardSeq);

crazy8Seq.findTrickSequence();

crazy8Seq.printTrickSeqeunce(); } }

Explanation / Answer

find the code below:

/*********************************** Crazy8.java **********************************/

import java.util.*;

public class Crazy8 {
String[] nCardSeq;       // Card Sequence
String[] nMaxTrick; // Maximum trick subsequence

public Crazy8(String[] cardSeq) {
nCardSeq = cardSeq;

}

/*
* This function generates mMaxSeq
*/
public void findTrickSequence() {
int[] my_trick = new int[nCardSeq.length];//memoization array, stores maximum trick length ending at i
int curMax; //current maximum trick while scanning previously calculated subarray
int MaxIndex; //keeps track of the index of the maximum of all of my_trick[]
int[] prevIndex = new int[nCardSeq.length]; //stores index of previous card in maximum trick ending at i

my_trick[0] = 1;
MaxIndex = 0;
prevIndex[0] = 0;
//generate rest of my_trick[]
for (int i = 1; i < my_trick.length; i++) {
curMax = 0;
for (int j = 0; j < i; j++) { //iterate through calculated subarray
if (my_trick[j] > curMax) {
if (cardMatch(nCardSeq[i], nCardSeq[j])) {
curMax = my_trick[j];
my_trick[i] = curMax + 1;
prevIndex[i] = j;
}
}
}
if(my_trick[i] > my_trick[MaxIndex])
MaxIndex = i;
}

//generate maximum trick subsequence by back-tracing through my_trick[]
nMaxTrick = new String[my_trick[MaxIndex]]; //size is the max trick sequence length
int curPrev = MaxIndex;
for (int i = nMaxTrick.length - 1; i >= 0; i--) {
nMaxTrick[i] = nCardSeq[curPrev];
curPrev = prevIndex[curPrev];
}
}

/*
* iterates mMaxSeq, prints the maximum trick subsequence
*/
public void printTrickSeqeunce() {
System.out.println("The length of trick sequence = " + nMaxTrick.length);
System.out.println("Trick Sequence");
for (int i = 0; i < nMaxTrick.length; i++) {
System.out.print(nMaxTrick[i] + " ");
}
System.out.println();
}

/*
* returns true if the cards match, false if they don't
*/
private boolean cardMatch (String c1, String c2) {
char irank = c1.charAt(0);
char isuit = c1.charAt(1);
char jrank = c2.charAt(0);
char jsuit = c2.charAt(1);

if(irank == jrank)
return true;
if(isuit == jsuit)
return true;
if(irank == '8' || jrank == '8')
return true;
return false;
}
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.