Do you win a Numeric Mahjong?

Question

Background

Numeric Mahjong is a hypothetical variation of Japanese Mahjong, played with nonnegative integers instead of Mahjong tiles. Given a list of nonnegative integers, it is a winning hand if it satisfies the following:

• its length is \$3n+2\$ for some nonnegative integer \$n\$, and
• it can be partitioned into \$n\$ triples and a pair so that
  • each triple consists of three identical numbers \$(x,x,x)\$ or three consecutive numbers \$(x,x+1,x+2)\$, and
  • the pair consists of two identical numbers \$(x,x)\$.

Challenge

Write a program or function that tests if a given a list of nonnegative integers is a winning hand in Numeric Mahjong. As this is a self-validating challenge, your source code (when converted to a list of integers) must be a winning hand. For example, print(1) is not a valid answer even if it implements the task, but the following may be:

print(1)###*11ios

whose ASCII values in sorted order is [35, 35, 35, 40, 41, 42, 49, 49, 49, 105, 105, 110, 111, 112, 114, 115, 116], which can be partitioned to five triples [35, 35, 35], [40, 41, 42], [49, 49, 49], [110, 111, 112], [114, 115, 116] and a pair [105, 105].

When converting the source code to integers, you may choose between

• Unicode codepoints of each char (when the source code is a sequence of Unicode characters),
• one of your language's fixed-width encodings, or
• a raw byte sequence (when the source code has an integral number of bytes).

If there are other sensible conversions, please leave a comment.

For output, you can choose to

• output truthy/falsy using your language's convention (swapping is allowed), or
• use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

Truthy

[0, 0]
[999, 999, 999, 1234, 1234]
[1, 2, 2, 2, 3]
[1, 4, 7, 2, 5, 5, 5, 8, 3, 6, 9]
[1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 7, 7]
[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3]
[0, 0, 0, 0, 0, 0, 0, 0]

Falsy

[]
[1]
[1, 3, 5, 7, 9]
[1, 1, 2, 2, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64]

Answer 1

05AB1E, 47 47 44 41 38 bytes

œʒ3ôʒ¥J>}gy3ôʒ¥T>SQ}g+3*Ig>Q}ćQ,¥›HUyy

Try it online!, or try all test cases (this code can handle in under a minute).

See the codepoints

Returns 0 for true and [] for false.

Explanation

The general approach is this: Test for the existence of a permutation such that if we split it to parts of length 3, and then keep all the valid ones and count them, and multiply by 3, we should get 1 plus the length of the original input.

œ       # all permutations
ʒ       # keep those such that:
 3ô      # split to parts of length 3
 ʒ       # keep parts where:
  ¥       # their differences
  J       # joined to a string
  >       # plus one
 }       # (is equal to 1)
 g       # find the length
 y       # push the input again
 3ô      # and split to parts of length 3
 ʒ       # keep parts such that:
  ¥      # their differences
  T>     # 11
  S      # [1, 1]
  Q      # [1, 1] is equal to the differences
 }
 g       # take their lengths
 +       # sum the lengths of the two types of parts
 3*      # times 3
 I       # input
 g       # length
 >       # plus one
 Q       # is equal to the number of valid parts times 3
}
ćQ      # test whether the array is empty, by comparing arr[0] == arr[1:]
,        # output - this suppresses implicit output, so the rest of the code doesn't matter
¥›HUyy  # filler to satisfy the self validation requirement

Answer 2

JavaScript (ES6),  143 122  119 bytes

-24 bytes thanks to @tsh!

Expects an Uint32Array. Returns a Boolean value.

n=>(q=([v,...f],e)=>6/v?[e,4,4.5].some(t=>q(f.filter(i=>p>t|v+t%1*p-i||0%[p*=2],p=2),t<p?4>t?4:e:1%0)):e>3)(n.sort(),3)

Try it online!

The above function is too slow to validate itself on TIO, so this is using my original answer with an additional optimization:

Try it online!

Answer 3

K (ngn/k), 71 bytes

oo::{*0-0!=|/{:[&/0=x;1;|/^%x;0;o@@[1_x;!2;-;3!*x]]}'+@[-2*=3+/x;x;1+]}

Try it online!

Based on a polynomial-time algorithm with respect to the maximal element, so it can test all test cases and itself in a second.

Let's call (x,x,x) an x-triplet and (x,x+1,x+2) an x-sequence.

• Count the occurrence of each number in [0, 1, 2, ...] up to the maximal element that appears in the input. Let's call it C.
• For i from 0 to the maximum index of C,
  • Construct a copy of C where i-th element is subtracted by 2. (i.e., Assume a pair is (i,i).)
  • Repeat until one of the halting condition is met:
    • If the remaining array is all zeros, return true.
    • If the remaining array contains a negative value, return false.
    • Otherwise, pop x from the front, and subtract x%3 from the first two elements. (i.e., Maximally create j-triplets and try creating j-sequences for the remaining js.)
• If any choice of i gives true, return true. Otherwise return false.

If a partition exists and it contains three or more j-sequences for some j, three copies of j-sequences can be replaced with j-, j+1-, and j+2-triplets to get another valid partition. Also, when considering all possible partitions where the minimum value is j, choosing to have three j-sequences (compared to one j-triplet) has the effect of fixing a j+1- and j+2-triplet from the remaining numbers, leaving a strict subset of choices afterwards. Therefore, it suffices to check if a greedy partitioning (favoring triplets) leads to a valid one.

{|/{:[&/0=x;1;|/^%x;0;o@@[1_x;!2;-;3!*x]]}'+@[-2*=3+/x;x;1+]}

+@[-2*=3+/x;x;1+]  construct number-count arrays with all choices of pairs
      =3+/x        identity matrix of size `sum of x + 3`
   -2*             change 1s on the diagonal to -2
 @[        ;x;1+]  for each number i in x, add 1 to i-th row of the above
+                  transpose

{:[...]}'  test if each number-count array is partitionable
&/0=x;1;   if all elements are 0, return 1
|/^%x;0;   if any element is negative, return 0
           (monadic % is square root, which gives 0n for negatives;
            monadic ^ is null-check, which gives 1 for 0n)
o@@[1_x;!2;-;3!*x]  otherwise, update the array and do recursive call
    1_x             remove first element k
        !2          and update 0th and 1st elements by
           - 3!*x   subtracting k%3
o@                  recursive call

|/  return 1 if any is true

*0-0!=  filler that preserves truthiness
oo::    globally assign function to the name oo

Answer 4

Charcoal, 128 125 122 95 bytes

≔∧θＥ⌈⁺³θ№θιθＦＥθ⮌Ｅθ⁻λ∧⁼κ첫Ｗ∧›Ｌ鲬‹⌊ι⁰«≔﹪⊟ι³θＦ²§≔ι±⊕λ⁻§ι±⊕λθ»Ｐ↔¬⌈↔ι»Ｗ⁰«⊟⊟⌊≡↔⊕¬§﹪﹪⁺⁺⁻⁰³ＦＬＬＰＰＷιλθ»

Try it online! Uses the Charcoal code page. Add the -x argument to show the hex dump which you can compare against the input. Outputs a Charcoal boolean, i.e. - for a winning hand, nothing if not. Explanation: Now a port of @Bubbler's algorithm.

≔Ｅ⁺³⌈θ№θιθ

Count the number of times each integer appears in the array, plus some extra dummy values.

ＦＥθ⮌Ｅθ⁻λ∧⁼κ첫

Try each integer in case it's the pair.

Ｗ∧›Ｌ鲬‹⌊ι⁰«

Repeat until a count becomes negative or the length is reduced to 2.

≔﹪⊟ι³θ

Get the number of runs needed to satisfy the next integer.

Ｆ²§≔ι±⊕λ⁻§ι±⊕λθ

Subtract them from the next two integers.

»Ｐ↔¬⌊↔ι

Output a - if this reduced all the integers to zero (but not negative).

»Ｗ⁰«⊟⊟⌊≡↔⊕¬§﹪﹪⁺⁺⁻⁰³ＦＬＬＰＰＷιλθ»

Filler bytes to satisfy the source layout, wrapped in a while loop whose condition is false.

Original verbose code (without padding): Try it online!

Answer 5

JavaScript (Node.js), 122 bytes

f=(A,e,k,n)=>1/n&&!{'1,1':1,'0,0':'B\():'|1}[[e-k,k-n]]?!!0:A+A?A.some((C,j)=>f(A.filter(B=>j--),C,...1/n?[]:[e,k])):e==+k

Try it online!

Besides tuplets: && ++,,-- --..// AABBCC [\] ijjkkl mno rst {|}

Answer 6

Jelly, 50 bytes

°þþ&&,@ƑƒWß»Ȥ
WÞW+þ@3’œ&ƑƇœ-@€Ʋ€Ẏ$ƬẎŒɠ%¹Ƈɗ€3‘œ&ƑƇ3

Try it online!

The main part is a monadic link that takes a list of integers and returns an empty list for false and a list containing one or more items for truthy. To meet the challenge rules, the program includes another link above the main one which is just filler.

Completes all test cases including itself in about 17 seconds on TIO. Full explanation to follow. Note the footer turns the falsy and truthy outcomes to 0 and 1 for more compact printing.

General explanation:

• Remove every possible combination of runs of three (including removing none)
• Check the remaining integers are in groups of length 0 mod 3, except for one that is of length 2 mod 3

Explanation

°þþ&&,@ƑƒWß»Ȥ | Filler to meet challenge requirements

WÞ                                   | Sort (technically with order based on that after wrapping each item in a list, but this doesn't affect sort order)
  W                                  | Wrap in a list
                   $Ƭ                | Repeat the following until no changes are made, gathering up intermediate results
                Ʋ€                   | - For each list in the lists of lists (example for e.g. [1, 2, 3, 4, 4])
   +þ@3                              |   - Outer addition using 1, 2, 3 e.g. [[[2, 3, 4], [3, 4, 5], [4, 5, 6], [5, 6, 7], [5, 6, 7]]
       ’                             |   - Decrease by 1 e.g. [[1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6], [4, 5, 6]]
        œ&ƑƇ                         |   - Filter, keeping only those lists that were seen in the original list e.g. [[1, 2, 3], [2, 3, 4]]
            œ-@€                     |   - Filter the original list removing each of these in turn [[4, 4], [1, 4]]
                  Ẏ                  | - Join inner lists together, leaving one list of lists
                     Ẏ               | Join all gathered intermediate results into one list of lists
                           ɗ€        | For each list within this list:
                      Œɠ             | - Run lengths
                        %    3       | - Mod 3
                         ¹Ƈ          | - Only keep those non-zero (i.e. those lists that were not a multiple of 3 in length)
                              ‘      | Increase by 1
                               œ&ƑƇ3 | Only keep those that consist of a single 3

Some of the code above (e.g. using WÞ rather than Ṣ) would be suboptimal in normal code-golf challenges, but here improve length by reducing the amount of filler required.

The runtime is sufficient to complete all the test cases, but as written becomes very inefficient as the number of runs of three consecutive numbers increases. This can be greatly improved by adding a uniquify step (TIO), reducing the run time for all test cases and my original code down to ~0.3 seconds total).

Answer 7

Raku, 121 116 bytes

{sub k(\u){u{*}~~[.2/.1]||?(u{*}:k).grep:{?grep {u (>)$_&&k u (-)$_},^3+$_,[$_,$_,$_]}}(bag |$_)}#%&//:>>?\`aabeqqss

Try it online!

The inner subroutine name k and its argument u were somewhat haphazardly chosen to try to produce more triples and runs.

• bag |$_ converts the argument list into a Bag (a set with multiplicity) which is then given to the inner recursive subroutine k.
• The subroutine returns true if u{*} ~~ [.2/.1], that is, if the bag contains a single element with multiplicity 2. This is the pair that a winning mah jong hand must contain.
• Otherwise, for the keys 𝑥 in the bag (u{*}:k), return true if the bag is a superset (u (>) $_) of either the run 𝑥, 𝑥 + 1, 𝑥 + 2 (^3 + $_) or the triple 𝑥, 𝑥, 𝑥 ([$_, $_, $_]), and the bag minus those elements (u (-) $_) produces a true result when passed to the inner recursive function k. (Normally I prefer using the Unicode characters for superset (⊃) and set minus (∖), which are the same number of bytes as the equivalent plain ASCII operators ((>) and (-) respectively), but then I'd have to repeat both of them twice in the trailing comment for a substantial byte penalty.)

Of course, the trailing comment #%&//:>>?\`aabeqqss makes the overall code snippet into a winning numerical mah jong hand. The function takes an infeasibly long time to validate itself; I constructed the comment by visual inspection of the function's character distribution.

The pair is: ~~

The runs are: #$%, ()*, ()*, +,-, 123, [\], [\], ^_ plus a backtick I can't figure out how to escape, pqr, pqr

The triples are: , , $$$, $$$, &&&, (((, ))), ,,,, ..., ///, :::, >>>, ???, ___, ___, aaa, bbb, eee, ggg, kkk, sss, uuu, uuu, {{{, {{{, |||, }}}, }}}

Answer 8

Ruby, 116 92 bytes

Brute force solution checking all permutations until it finds one that matches. Times out on medium inputs, so verification was done using the program below since it doesn't time out as easily.

Recursive approach saving 24 bytes by G B.

e=->a{a[2]?a.permutation.any?{_,o,z,*i=_1;_-o==(o-=z)&&o**2<2&&e[i]}:a!=a|a}#"')).11@@A[]ass

Attempt This Online!

Ruby, 137 bytes

Count the number of occurrences of each element. Then, for each element, removes a pair from the count (if possible), then checks if everything else is sequences or triplets.

->a{a.any?{t=a.tally;(t[_1]-=2)>=0&&a.sort.all?{|e|t[e]>=0&&((0...t[e]%=3).all?{(e..e+2).all?{|i|t[i]=t[i]&.-1}})}}}#$&*++3;;??\\__lmtty|

Attempt This Online!