mahjong_shanten.c

filter: Statementstmt 100% 127 / 127 Branchbran 96.3% 158 / 164 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 97.9% 285 / 291 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« mahjong_decompose.c ↑ Summary blib/lib/Game/Mahjong.pm »
1 /* mahjong_shanten.c - the distance to ready.
2 *
3 * Per suit: a recursive grouping of the nine counts into sets, partials and
4 * at most one head, reduced to two 25-bit masks (sets 0..4 x partials 0..4,
5 * with and without a head) and memoised by the base-5 value of the counts.
6 * The honours group trivially. The hand is the best combination.
7 */
8  
9 #include <string.h>
10 #include "mahjong_abi.h"
11 #include "mahjong_shanten.h"
12  
13 #define BASE5_MAX 1953125 /* 5^9 */
14  
15 /* memo[head][index]: a 25-bit mask of reachable (sets, partials); 0 means
16 * unfilled (a filled entry always has at least the (0, 0) bit set) */
17 static unsigned int MEMO[2][BASE5_MAX];
18  
19 #define BIT(s, p) (1u << ((s) * 5 + (p)))
20  
21 struct suit_walk {
22 unsigned char c[9];
23 unsigned int mask[2];
24 };
25  
26 7196341 static void walk(struct suit_walk *w, int i, int sets, int partials, int head)
27 {
28 int c;
29 19097321 ▶ while (i < 9 && !w->c[i]) i++;
Branch: 2 branches
BranchTrueFalseTotal
while (i < 9 && !w->c[i]) i++; 15851656 3245665 19097321
while (i < 9 && !w->c[i]) i++; 11900980 3950676 15851656
30 7196341 ▶ if (i >= 9) {
Branch: 1 branch
BranchTrueFalseTotal
if (i >= 9) { 3245665 3950676 7196341
31 3245665 ▶ if (sets <= 4 && partials <= 4) w->mask[head] |= BIT(sets, partials);
Branch: 2 branches
BranchTrueFalseTotal
if (sets <= 4 && partials <= 4) w->mask[head] |= BIT(sets, partials); 3245665 0 3245665
if (sets <= 4 && partials <= 4) w->mask[head] |= BIT(sets, partials); 3190113 55552 3245665
32 3245665 return;
33 }
34 3950676 c = w->c[i];
35  
36 /* a pung of i */
37 3950676 ▶ if (c >= 3) {
Branch: 1 branch
BranchTrueFalseTotal
if (c >= 3) { 89097 3861579 3950676
38 89097 w->c[i] -= 3;
39 89097 walk(w, i, sets + 1, partials, head);
40 89097 w->c[i] += 3;
41 }
42 /* a chow from i */
43 3950676 ▶ if (i <= 6 && w->c[i + 1] && w->c[i + 2]) {
Branch: 3 branches
BranchTrueFalseTotal
if (i <= 6 && w->c[i + 1] && w->c[i + 2]) { 1980897 1969779 3950676
if (i <= 6 && w->c[i + 1] && w->c[i + 2]) { 695942 1284955 1980897
if (i <= 6 && w->c[i + 1] && w->c[i + 2]) { 278474 417468 695942
44 278474 w->c[i]--; w->c[i + 1]--; w->c[i + 2]--;
45 278474 walk(w, i, sets + 1, partials, head);
46 278474 w->c[i]++; w->c[i + 1]++; w->c[i + 2]++;
47 }
48 /* a pair of i as the head, once */
49 3950676 ▶ if (c >= 2 && !head) {
Branch: 2 branches
BranchTrueFalseTotal
if (c >= 2 && !head) { 641427 3309249 3950676
if (c >= 2 && !head) { 477866 163561 641427
50 477866 w->c[i] -= 2;
51 477866 walk(w, i, sets, partials, 1);
52 477866 w->c[i] += 2;
53 }
54 /* a pair of i as a partial */
55 3950676 ▶ if (c >= 2) {
Branch: 1 branch
BranchTrueFalseTotal
if (c >= 2) { 641427 3309249 3950676
56 641427 w->c[i] -= 2;
57 641427 walk(w, i, sets, partials + 1, head);
58 641427 w->c[i] += 2;
59 }
60 /* two adjacent */
61 3950676 ▶ if (i <= 7 && w->c[i + 1]) {
Branch: 2 branches
BranchTrueFalseTotal
if (i <= 7 && w->c[i + 1]) { 2964896 985780 3950676
if (i <= 7 && w->c[i + 1]) { 1021042 1943854 2964896
62 1021042 w->c[i]--; w->c[i + 1]--;
63 1021042 walk(w, i, sets, partials + 1, head);
64 1021042 w->c[i]++; w->c[i + 1]++;
65 }
66 /* two a gap apart */
67 3950676 ▶ if (i <= 6 && w->c[i + 2]) {
Branch: 2 branches
BranchTrueFalseTotal
if (i <= 6 && w->c[i + 2]) { 1980897 1969779 3950676
if (i <= 6 && w->c[i + 2]) { 717006 1263891 1980897
68 717006 w->c[i]--; w->c[i + 2]--;
69 717006 walk(w, i, sets, partials + 1, head);
70 717006 w->c[i]++; w->c[i + 2]++;
71 }
72 /* leave one i ungrouped */
73 3950676 w->c[i]--;
74 3950676 walk(w, i, sets, partials, head);
75 3950676 w->c[i]++;
76 }
77  
78 2586033 static void suit_masks(const unsigned char *nine, unsigned int *out)
79 {
80 2586033 unsigned int idx = 0;
81 int i;
82 25860330 ▶ for (i = 0; i < 9; i++) idx = idx * 5 + nine[i];
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 9; i++) idx = idx * 5 + nine[i]; 23274297 2586033 25860330
83 2586033 ▶ if (!MEMO[0][idx]) {
Branch: 1 branch
BranchTrueFalseTotal
if (!MEMO[0][idx]) { 20753 2565280 2586033
84 struct suit_walk w;
85 20753 memcpy(w.c, nine, 9);
86 20753 w.mask[0] = w.mask[1] = 0;
87 20753 walk(&w, 0, 0, 0, 0);
88 20753 MEMO[0][idx] = w.mask[0];
89 20753 MEMO[1][idx] = w.mask[1];
90 }
91 2586033 out[0] = MEMO[0][idx];
92 2586033 out[1] = MEMO[1][idx];
93 2586033 }
94  
95 /* the honours: every kind with three or more is a set, with two a partial
96 * or the head */
97 862011 static void honour_masks(const unsigned char *counts, unsigned int *out)
98 {
99 862011 int k, sets = 0, pairs = 0;
100 6896088 ▶ for (k = 28; k <= 34; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 28; k <= 34; k++) { 6034077 862011 6896088
101 6034077 ▶ if (counts[k] >= 3) sets++;
Branch: 1 branch
BranchTrueFalseTotal
if (counts[k] >= 3) sets++; 37043 5997034 6034077
102 5997034 ▶ else if (counts[k] == 2) pairs++;
Branch: 1 branch
BranchTrueFalseTotal
else if (counts[k] == 2) pairs++; 216439 5780595 5997034
103 }
104 862011 out[0] = out[1] = 0;
105 862011 ▶ if (sets <= 4 && pairs <= 4) out[0] |= BIT(sets, pairs);
Branch: 2 branches
BranchTrueFalseTotal
if (sets <= 4 && pairs <= 4) out[0] |= BIT(sets, pairs); 862011 0 862011
if (sets <= 4 && pairs <= 4) out[0] |= BIT(sets, pairs); 862011 0 862011
106 862011 ▶ if (pairs && sets <= 4) out[1] |= BIT(sets, pairs - 1);
Branch: 2 branches
BranchTrueFalseTotal
if (pairs && sets <= 4) out[1] |= BIT(sets, pairs - 1); 196433 665578 862011
if (pairs && sets <= 4) out[1] |= BIT(sets, pairs - 1); 196433 0 196433
107 862011 ▶ if (!out[0]) out[0] = BIT(0, 0);
Branch: 1 branch
BranchTrueFalseTotal
if (!out[0]) out[0] = BIT(0, 0); 0 862011 862011
108 862011 }
109  
110 862011 static int standard(const unsigned char *counts, int melds)
111 {
112 unsigned int m[4][2];
113 862011 int best = 99, g, s0, p0, s1, p1, s2, p2, s3, p3, h0, h1, h2, h3;
114 unsigned char nine[9];
115 3448044 ▶ for (g = 0; g < 3; g++) {
Branch: 1 branch
BranchTrueFalseTotal
for (g = 0; g < 3; g++) { 2586033 862011 3448044
116 2586033 memcpy(nine, counts + 1 + 9 * g, 9);
117 2586033 suit_masks(nine, m[g]);
118 }
119 862011 honour_masks(counts, m[3]);
120  
121 /* every combination of one (sets, partials) from each group, at most
122 * one head among them */
123 54306693 ▶ for (h0 = 0; h0 < 2; h0++) for (s0 = 0; s0 <= 4; s0++) for (p0 = 0; p0 <= 4; p0++) {
Branch: 3 branches
BranchTrueFalseTotal
for (h0 = 0; h0 < 2; h0++) for (s0 = 0; s0 <= 4; s0++) for (p0 = 0; p0 <= 4; p0++) { 43100550 8620110 51720660
for (h0 = 0; h0 < 2; h0++) for (s0 = 0; s0 <= 4; s0++) for (p0 = 0; p0 <= 4; p0++) { 8620110 1724022 10344132
for (h0 = 0; h0 < 2; h0++) for (s0 = 0; s0 <= 4; s0++) for (p0 = 0; p0 <= 4; p0++) { 1724022 862011 2586033
124 43100550 ▶ if (!(m[0][h0] & BIT(s0, p0))) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!(m[0][h0] & BIT(s0, p0))) continue; 39083691 4016859 43100550
125 12050577 ▶ for (h1 = 0; h1 < 2; h1++) { if (h1 && h0) continue;
Branch: 3 branches
BranchTrueFalseTotal
for (h1 = 0; h1 < 2; h1++) { if (h1 && h0) continue; 4016859 4016859 8033718
for (h1 = 0; h1 < 2; h1++) { if (h1 && h0) continue; 1115151 2901708 4016859
for (h1 = 0; h1 < 2; h1++) { if (h1 && h0) continue; 8033718 4016859 12050577
126 214475577 ▶ for (s1 = 0; s1 <= 4; s1++) for (p1 = 0; p1 <= 4; p1++) {
Branch: 2 branches
BranchTrueFalseTotal
for (s1 = 0; s1 <= 4; s1++) for (p1 = 0; p1 <= 4; p1++) { 172964175 34592835 207557010
for (s1 = 0; s1 <= 4; s1++) for (p1 = 0; p1 <= 4; p1++) { 34592835 6918567 41511402
127 172964175 ▶ if (!(m[1][h1] & BIT(s1, p1))) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!(m[1][h1] & BIT(s1, p1))) continue; 157894853 15069322 172964175
128 45207966 ▶ for (h2 = 0; h2 < 2; h2++) { if (h2 && (h0 || h1)) continue;
Branch: 4 branches
BranchTrueFalseTotal
for (h2 = 0; h2 < 2; h2++) { if (h2 && (h0 || h1)) continue; 15069322 15069322 30138644
for (h2 = 0; h2 < 2; h2++) { if (h2 && (h0 || h1)) continue; 12022774 3046548 15069322
for (h2 = 0; h2 < 2; h2++) { if (h2 && (h0 || h1)) continue; 3256472 8766302 12022774
for (h2 = 0; h2 < 2; h2++) { if (h2 && (h0 || h1)) continue; 30138644 15069322 45207966
129 738904344 ▶ for (s2 = 0; s2 <= 4; s2++) for (p2 = 0; p2 <= 4; p2++) {
Branch: 2 branches
BranchTrueFalseTotal
for (s2 = 0; s2 <= 4; s2++) for (p2 = 0; p2 <= 4; p2++) { 595890600 119178120 715068720
for (s2 = 0; s2 <= 4; s2++) for (p2 = 0; p2 <= 4; p2++) { 119178120 23835624 143013744
130 595890600 ▶ if (!(m[2][h2] & BIT(s2, p2))) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!(m[2][h2] & BIT(s2, p2))) continue; 548648148 47242452 595890600
131 141727356 ▶ for (h3 = 0; h3 < 2; h3++) { if (h3 && (h0 || h1 || h2)) continue;
Branch: 5 branches
BranchTrueFalseTotal
for (h3 = 0; h3 < 2; h3++) { if (h3 && (h0 || h1 || h2)) continue; 47242452 47242452 94484904
for (h3 = 0; h3 < 2; h3++) { if (h3 && (h0 || h1 || h2)) continue; 39369733 7872719 47242452
for (h3 = 0; h3 < 2; h3++) { if (h3 && (h0 || h1 || h2)) continue; 31254520 8115213 39369733
for (h3 = 0; h3 < 2; h3++) { if (h3 && (h0 || h1 || h2)) continue; 7098270 24156250 31254520
for (h3 = 0; h3 < 2; h3++) { if (h3 && (h0 || h1 || h2)) continue; 94484904 47242452 141727356
132 2213359762 ▶ for (s3 = 0; s3 <= 4; s3++) for (p3 = 0; p3 <= 4; p3++) {
Branch: 2 branches
BranchTrueFalseTotal
for (s3 = 0; s3 <= 4; s3++) for (p3 = 0; p3 <= 4; p3++) { 1784967550 356993510 2141961060
for (s3 = 0; s3 <= 4; s3++) for (p3 = 0; p3 <= 4; p3++) { 356993510 71398702 428392212
133 int S, P, head, d;
134 1784967550 ▶ if (!(m[3][h3] & BIT(s3, p3))) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!(m[3][h3] & BIT(s3, p3))) continue; 1734321958 50645592 1784967550
135 50645592 S = melds + s0 + s1 + s2 + s3;
136 50645592 P = p0 + p1 + p2 + p3;
137 50645592 ▶ head = h0 || h1 || h2 || h3;
Branch: 4 branches
BranchTrueFalseTotal
head = h0 || h1 || h2 || h3; 42772873 7872719 50645592
head = h0 || h1 || h2 || h3; 34657660 8115213 42772873
head = h0 || h1 || h2 || h3; 27559390 7098270 34657660
head = h0 || h1 || h2 || h3; 3403140 24156250 27559390
138 50645592 ▶ if (S > 4) S = 4;
Branch: 1 branch
BranchTrueFalseTotal
if (S > 4) S = 4; 0 50645592 50645592
139 50645592 ▶ if (S + P > 4) P = 4 - S;
Branch: 1 branch
BranchTrueFalseTotal
if (S + P > 4) P = 4 - S; 5059360 45586232 50645592
140 50645592 d = 8 - 2 * S - P - head;
141 50645592 ▶ if (d < best) best = d;
Branch: 1 branch
BranchTrueFalseTotal
if (d < best) best = d; 5398587 45247005 50645592
142 } }
143 } }
144 } }
145 }
146 862011 return best;
147 }
148  
149 862011 static int seven_pairs(const unsigned char *counts, int melds)
150 {
151 862011 int k, pairs = 0, kinds = 0;
152 862011 ▶ if (melds) return 99;
Branch: 1 branch
BranchTrueFalseTotal
if (melds) return 99; 137309 724702 862011
153 25364570 ▶ for (k = 1; k <= MJ_KINDS; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 1; k <= MJ_KINDS; k++) { 24639868 724702 25364570
154 24639868 ▶ if (counts[k]) kinds++;
Branch: 1 branch
BranchTrueFalseTotal
if (counts[k]) kinds++; 8119467 16520401 24639868
155 24639868 ▶ if (counts[k] >= 2) pairs++;
Branch: 1 branch
BranchTrueFalseTotal
if (counts[k] >= 2) pairs++; 1751155 22888713 24639868
156 }
157 724702 ▶ return 6 - pairs + (kinds < 7 ? 7 - kinds : 0);
Branch: 1 branch
BranchTrueFalseTotal
return 6 - pairs + (kinds < 7 ? 7 - kinds : 0); 48 724654 724702
158 }
159  
160 static const int ORPHAN[13] = { 1, 9, 10, 18, 19, 27, 28, 29, 30, 31, 32, 33, 34 };
161  
162 862011 static int thirteen_orphans(const unsigned char *counts, int melds)
163 {
164 862011 int i, have = 0, pair = 0;
165 862011 ▶ if (melds) return 99;
Branch: 1 branch
BranchTrueFalseTotal
if (melds) return 99; 137309 724702 862011
166 10145828 ▶ for (i = 0; i < 13; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 13; i++) { 9421126 724702 10145828
167 9421126 ▶ if (counts[ORPHAN[i]]) have++;
Branch: 1 branch
BranchTrueFalseTotal
if (counts[ORPHAN[i]]) have++; 2249081 7172045 9421126
168 9421126 ▶ if (counts[ORPHAN[i]] >= 2) pair = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (counts[ORPHAN[i]] >= 2) pair = 1; 536808 8884318 9421126
169 }
170 724702 return 13 - have - pair;
171 }
172  
173 static const int KNIT_BASE[3] = { 1, 2, 3 };
174 static const int PERM[6][3] = {
175 { 0, 1, 2 }, { 0, 2, 1 }, { 1, 0, 2 }, { 1, 2, 0 }, { 2, 0, 1 }, { 2, 1, 0 }
176 };
177  
178 862011 static int honours_knitted(const unsigned char *counts, int melds)
179 {
180 862011 int p, k, honours = 0, best = 0;
181 862011 ▶ if (melds) return 99;
Branch: 1 branch
BranchTrueFalseTotal
if (melds) return 99; 137309 724702 862011
182 5797616 ▶ for (k = 28; k <= 34; k++) if (counts[k]) honours++;
Branch: 2 branches
BranchTrueFalseTotal
for (k = 28; k <= 34; k++) if (counts[k]) honours++; 926958 4145956 5072914
for (k = 28; k <= 34; k++) if (counts[k]) honours++; 5072914 724702 5797616
183 5072914 ▶ for (p = 0; p < 6; p++) {
Branch: 1 branch
BranchTrueFalseTotal
for (p = 0; p < 6; p++) { 4348212 724702 5072914
184 4348212 int s, usable = honours;
185 17392848 ▶ for (s = 0; s < 3; s++) {
Branch: 1 branch
BranchTrueFalseTotal
for (s = 0; s < 3; s++) { 13044636 4348212 17392848
186 13044636 int base = KNIT_BASE[PERM[p][s]], r;
187 52178544 ▶ for (r = base; r <= 9; r += 3) if (counts[1 + 9 * s + r - 1]) usable++;
Branch: 2 branches
BranchTrueFalseTotal
for (r = base; r <= 9; r += 3) if (counts[1 + 9 * s + r - 1]) usable++; 14385018 24748890 39133908
for (r = base; r <= 9; r += 3) if (counts[1 + 9 * s + r - 1]) usable++; 39133908 13044636 52178544
188 }
189 4348212 ▶ if (usable > best) best = usable;
Branch: 1 branch
BranchTrueFalseTotal
if (usable > best) best = usable; 1430115 2918097 4348212
190 }
191 724702 return 13 - best;
192 }
193  
194 862011 int mj_shanten_forms(const unsigned char *counts, int melds, int *out)
195 {
196 int min;
197 862011 out[MJ_FORM_S_STANDARD] = standard(counts, melds);
198 862011 out[MJ_FORM_S_PAIRS] = seven_pairs(counts, melds);
199 862011 out[MJ_FORM_S_ORPHANS] = thirteen_orphans(counts, melds);
200 862011 out[MJ_FORM_S_KNITTED] = honours_knitted(counts, melds);
201 862011 min = out[0];
202 862011 ▶ if (out[1] < min) min = out[1];
Branch: 1 branch
BranchTrueFalseTotal
if (out[1] < min) min = out[1]; 103139 758872 862011
203 862011 ▶ if (out[2] < min) min = out[2];
Branch: 1 branch
BranchTrueFalseTotal
if (out[2] < min) min = out[2]; 3523 858488 862011
204 862011 ▶ if (out[3] < min) min = out[3];
Branch: 1 branch
BranchTrueFalseTotal
if (out[3] < min) min = out[3]; 35463 826548 862011
205 862011 return min;
206 }
207  
208 862009 int mj_shanten(const unsigned char *counts, int melds)
209 {
210 int forms[MJ_FORM_S_COUNT];
211 862009 return mj_shanten_forms(counts, melds, forms);
212 }
213  
214 22583 int mj_ukeire(const unsigned char *counts, int melds, unsigned char *out)
215 {
216 unsigned char c[MJ_KINDS + 1];
217 22583 int k, n = 0, now;
218 22583 memcpy(c, counts, MJ_KINDS + 1);
219 22583 now = mj_shanten(c, melds);
220 790405 ▶ for (k = 1; k <= MJ_KINDS; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 1; k <= MJ_KINDS; k++) { 767822 22583 790405
221 767822 ▶ if (c[k] >= MJ_PER_KIND) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (c[k] >= MJ_PER_KIND) continue; 100 767722 767822
222 767722 c[k]++;
223 767722 ▶ if (mj_shanten(c, melds) < now) out[n++] = (unsigned char)k;
Branch: 1 branch
BranchTrueFalseTotal
if (mj_shanten(c, melds) < now) out[n++] = (unsigned char)k; 169710 598012 767722
224 767722 c[k]--;
225 }
226 22583 return n;
227 }
« mahjong_decompose.c ↑ Summary blib/lib/Game/Mahjong.pm »