This week I am going to write about the game “Ma-Jan”. I was told about this by takamura-san, inagaki-san and sugawara-san. Thanks to them for explaining me the rules.Firstly I will describe the rules and then the algorithm.
Disclaimer: The rules listed are my interpretation of the game. They might be incorrect. Similarly the algorithm looks correct to me, but it might have some flaws on some corner cases. Please excuse me if you find any mistakes and report it in comments.
Objective
There are 14 digits (0-9) given to you. You need to form matchings as given by the rules. The code assumes you know the 13 digits in advance and tries to find all possibilities to complete the game for you.
Rules for matchings
- From the 14 digits, you have to form 4 triplets( 3) and 1 pair (2). So 3*4 +1 *2 =14
- The triplets can be of the form, (xxx) all same numbers, or (x, x+1, x+2); i.e three consecutive numbers. So (333) and (567) is correct but (568) and (112) are incorrect.
- The pair has to be of the form (xx) same digits.So (22) is correct but not (45)
- You know the 13 digits, and want to figure out all possibilities to finish the game. So you have to write within square brackets ‘[ ]’ the matching which is expected to complete by the 14th digit. So if the 13 digits are 1112233444555, then you need to output (111)(33)(444)(555)[22] meaning that the square bracket is where the 14th card is going to be placed and according to rules it must be a 2. Note that there are other possibilities as well. The code has to report all such possibilities.
Algorithm
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
<ul> Method main()</p> <li> Read the input string s</li> <li> Check for validity of s, it must have 13 digits and the count of any digit must not exceed 4</li> <li>Make a global HashSet which will hold all the answers. Note that the hashset reomves all duplicates from the set </li> <li> Make an array <i>a</i> to store the count of each of digit in the input string.</li> <li>//There are 10 possibilties for the 14th digit (0-9), so assume that the 14th digit is each of the digit using a for loop.<br /> for( i= 0 ;i<=9; i++)<br /> {<br /> add digit <i>i</i> to array <i>a</i>;<br /> call recursive function <i>recur(a, 0,new ArrayList(), false,i);</i><br /> remove digit <i>i</i> from array <i>a</i><br /> }</li> <li>print all possibilties from the hashset</li> <p>end main</p> <p> //A Recursive function which has parameters :<br /> /*<br /> #array a containing the count of all the remianing digits<br /> #int pointer ; indicates the number of digits parsed<br /> #Arraylist array; contaning the result for the current pass<br /> #boolean numTwo; tells if the current solution has seen a two length (xx) pair.<br /> # int number; the digit which we have added to make it 14.<br /> */<br /> function recur(a,pointer,array,numTwo,number)<br /> {</p> <ul> <li>if(pointer ==14) // means that we have made 1 possibilty<br /> {<br /> make a solution from the ArrayList. //This is a bit difficult but see my code attached for clarity.<br /> add the solution made to the hashset<br /> return;<br /> }</li> <li> if(!numTwo) // we have not made any pairs, so look if its possible<br /> {<br /> for(i=0;i <= 9; i++)<br /> {<br /> clone the array a with x making x[i]-=2;<br /> make a new arraylist array1 adding (i i) to the current arraylist<br /> //call the recursive fucntion to see if the current configs can make a solution<br /> recur(x,pointer+2,array1,true,number);<br /> }<br /> }</p> </li> <p>//Similarly try 2 more recursive calls;</p> <li> To add (xxx) , if possible</li> <li>To add(x,x+1,x+2) , if possible</li> </ul> <p>//See my code for details.</p> <p>end recur<br /> } |
I have attached my code along. It is not clean and not refactored properly. But you can take a reference if you want.
Link to source code link
Thats all , thank you for reading.
最近のコメント