22
\$\begingroup\$

Determine whether a given sequence could be a winning sequence for the game shut the box.

Background

There are a few variants to this game, so I'll clarify the rules here. Play begins with 12 tiles (1 through 12) face up. Each turn the player rolls two six sided dice, and must then flip over one or more tile(s) which sum to the given roll. The game ends when you roll a number that cannot be summed to with tiles that remain face up. Your score then is the sum of the values of the remaining face up tiles. If one manages to flip over all tiles (obtaining a score of 0), this is referred to as "shutting the box".

An example of a winning game may go as follows:

roll | sum | face up tiles remaining
4, 3   7     [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12]
1, 4   5     [1, 2, 3, 4, 6, 8, 9, 10, 11, 12]
6, 6   12    [1, 2, 3, 4, 6, 8, 9, 10, 11]
2, 2   4     [1, 2, 3, 6, 8, 9, 10, 11]
5, 1   6     [6, 8, 9, 10, 11]
3, 6   9     [6, 8, 10, 11]
5, 3   8     [6, 10, 11]
6, 5   11    [6, 10]
4, 2   6     [10]
5, 5   10    []

The challenge

For this challenge you will take a sequence of roll sums (ie. [7,5,12,4,6,9,8,11,6,10]) as input, and output a truthy value which will denote whether or not this sequence of rolls could be used to "shut the box" exactly (no extra rolls either).

Standard i/o rules apply, input can be taken in any reasonable form for a sequence, and output can be anything as long as truthy and falsy are distinct and consistent. You may assume that the input will consist only of integers 2-12.

This is , so the shortest answer in bytes wins.

Test cases

Truthy:

[2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 12]
[3, 4, 5, 6, 7, 8, 9, 12, 12, 12]
[12, 12, 12, 12, 12, 12, 6]
[12, 12, 12, 12, 12, 11, 7]
[7, 7, 7, 7, 8, 9, 10, 11, 12]
[12, 4, 5, 7, 8, 9, 10, 11, 12]
[2, 5, 7, 7, 7, 8, 9, 10, 11, 12]

Falsy:

[]
[2]
[12, 5, 6]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[3, 4, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8]
[3, 3, 4, 5, 6, 8, 9, 12, 12, 12, 4]
[2, 2, 5, 6, 6, 7, 8, 9, 10, 11, 12]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 12, 2, 2, 2]
[8, 8, 8, 10, 10, 10, 12, 12]
\$\endgroup\$
9
  • \$\begingroup\$ I bet someone will find a weird formula for this. \$\endgroup\$
    – naffetS
    Commented Oct 13, 2022 at 3:15
  • \$\begingroup\$ Two necessary conditions that are sufficient to eliminate the Falsy examples: the sum of the sequence must be 78. For every n>=6 there must be at least 13-n entries in the sequence >= n. I don't know if we are just missing another Falsy sequence, or if this is enough. \$\endgroup\$
    – David G.
    Commented Oct 13, 2022 at 19:40
  • 1
    \$\begingroup\$ For a sequence of rolls to be used to 'shut the box', does the box need to shut on the last roll, or could it be shut earlier in the sequence? In other words, is the sequence [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 2 ,2 ,2, 2, 2] truthy? (It could be used to 'shut the box' on the 11th roll, as in the example...) \$\endgroup\$ Commented Oct 13, 2022 at 20:43
  • 1
    \$\begingroup\$ @DominicvanEssen The box needs to be shut on the last roll, I'll add a test case for that and clarify in the post as well. \$\endgroup\$ Commented Oct 13, 2022 at 20:54
  • \$\begingroup\$ @DavidG. I added a falsy test case which breaks your rules (now second to last). I will say though that I believe that line of thinking is very close to something which is actually necessary and sufficient. \$\endgroup\$ Commented Oct 13, 2022 at 21:00

12 Answers 12

9
\$\begingroup\$

Vyxal, 10 bytes

vṄΠ'fs12ɾ⁼

Try it Online! Outputs an empty list for falsy, a non-empty list for truthy. Link is for a much smaller version as this is \$O\left(\prod_{i=0}{n_i}^2\right)\$, that is, takes time proportional to the square of the product of the inputs. -1 by stealing some ideas from Kevin Cruijssen's 05AB1E answer.

vṄ         # Take the integer partitions of each number
  Π        # Take the cartesian product of this
   '       # Filter all possible partitions by...
    fs     # Flattened and sorted
         ⁼ # Is the result equal to...
      12ɾ  # range(1, 12)?
\$\endgroup\$
0
6
\$\begingroup\$

Python3, 230 bytes:

def C(d,n,c=[]):
 if(K:=sum(c))==n:yield{*c};return
 for j in d:
  if K+j<=n:yield from C(d-{j},n,c+[j])
def f(d):
 q=[({*range(1,13)},d)]
 while q:
  s,d=q.pop(0)
  if not s:return 1
  if d:
   for r in C(s,d[0]):q+=[(s-r,d[1:])]

Try it online!

Outputs 1 for Truthy and None for Falsy.

\$\endgroup\$
0
6
\$\begingroup\$

Curry (PAKCS), 62 bytes

(!12)
[]!0=1
(0:a)!n=a!n
(a++b:c)!n|b>=n&&n>0=(a++b-n:c)!(n-1)

Try it online!

Returns 1 for truthy, and nothing otherwise. It might return the same 1 multiple times for truthy result.

\$\endgroup\$
5
\$\begingroup\$

JavaScript, 61 57 bytes

f=(s,k=12)=>s.some((v,i)=>k?f(t=[...s],k-1,t[i]-=k):v)^!k

Try it online!

Takes an Array.

k counts down from 12 to 1. Each number is tried at each position in the array; each time, spread syntax is used to make a copy of the array, in which k is subtracted from that position and the function is recursively called.

When k hits 0, the function passed to some instead returns each value in the array, and then some returns true if any of the values are nonzero and false otherwise. ^!k inverts the result for k=0, to be 1 if all the values are zero.

\$\endgroup\$
4
\$\begingroup\$

05AB1E, 12 bytes

Åœ.«âʒ˜ê12LQ

Outputs [] as falsey result; and a nested integer list as truthy result.

Port of emanresuA's Vyxal answer, so make sure to upvote him/her as well!

(Don't) try it online (try it with a smaller example, which won't time out).

Explanation:

Ŝ           # Map each integer in the (implicit) input-list to: all positive integer
             # lists that sum to that value
  .«         # (Right-)reduce this list of lists by:
    â        #  Taking the cartesian power between two lists
     ʒ       # Then filter this list of nested lists by:
      ˜      #  Flatten the nested list
       ê     #  Sorted-uniquify the list
           Q #  And check if it's now equal to
        12L  #  a list in the range [1,12]
             # (after which the filtered result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

Bash (+cureutils+bc), 145 160 fail bytes

f(){
test `echo 0 $@|sed -e s/\ /+/g|bc` = 78||return 1
y=12
echo $@|fmt -w1|sort -rn|while read x&&test $y -ge 6
do
[ $x -lt $y ]&&return 1
: $(( y-- ))
done
}

Try it online!

Based on my observation above:

Two necessary conditions that are sufficient to eliminate the Falsy examples: the sum of the sequence must be 78. For every n>=6 there must be at least 13-n entries in the sequence >= n. I don't know if we are just missing another Falsy sequence, or if this is enough.

And on my fondness for answers in bash, I decided to give it a try.

Input is function parameters. The function exits with either 0=truthy or 1=falsy. The test harness prints expected, actual, if it matched, and the input. It works for all the current test cases.

Previously I wrote

I'm not quite sure why.

Well, the problem was the lack of a stopping condition. Adding test case [2, 5, 7, 7, 7, 8, 9, 10, 11, 12] revealed this, and added 15 bytes to my solution.

And I haven't tried serious golfing yet.

Second Edit:

A couple more test cases:

[ 2, 5, 2, 5, 7, 7, 8, 9, 10, 11, 12]
[ 2, 2, 2, 12, 12, 12, 12, 12, 12]

Since no possible Truthy sequence can have two 2s, or three 3s, and probably some other combinations, my answer current fails. And I'm not sure how it can be fixed... or even if.

Third Edit:

I generated some complete lists. There are 636 distinct valid sorted sequences. There are 220295 distinct sorted sequences totaling to 78. If we discard the sequences before "12 11 10 9 8 7 6 5 4 3 2", which would not be able to remove all the numbers, and discard any sequence of more than 11, we are left with 6638 sequences.

My original 145 byte answer got 315 false negatives, and 124 false positives. My (first) 160 byte answer got no false negatives and 3075 false positives. My current 160 byte answer (test $x -ge 6 changed to test $y -ge 6) gives no false negatives and 1600 false positives. (I had been hoping for some simple special cases.)

\$\endgroup\$
2
\$\begingroup\$

C (GCC), 123 117 bytes

-6 bytes thanks to @ceilingcat

f(r,x,t,s,b,R)int*r;{for(R=0,t=8192;t--;R|=!x||s==*r&(t&x)==t&&f(r+1,x&~t))for(s=0,b=13;b--;)s+=t&1<<b?b:0;return R;}

Attempt This Online!

Note that it is exponentially slow; if you want it to run in a reasonable amount of time, add if(R)return R; after the x&~t);

\$\endgroup\$
0
2
\$\begingroup\$

Wolfram Language (Mathematica), 124 108 84 bytes

Max[Length/@Fold[Select[Join@@@Tuples@{##},0!=##&@@#&]&,IntegerPartitions/@#]]===12&

Try it online!

Thanks to @att!!

\$\endgroup\$
7
  • \$\begingroup\$ 108 bytes \$\endgroup\$
    – att
    Commented Apr 16, 2023 at 23:10
  • \$\begingroup\$ 87 \$\endgroup\$
    – att
    Commented Apr 17, 2023 at 6:52
  • 1
    \$\begingroup\$ 84 \$\endgroup\$
    – att
    Commented Apr 17, 2023 at 6:59
  • \$\begingroup\$ @att I’m trying to learn from your answers cool golfing in Mathematica but not very well yet ( \$\endgroup\$
    – lesobrod
    Commented Apr 17, 2023 at 7:32
  • \$\begingroup\$ 77 \$\endgroup\$
    – att
    Commented Apr 17, 2023 at 15:30
1
\$\begingroup\$

Charcoal, 41 bytes

⊞υ⊕…¹²FA≔∧υΣEυEΦEX²LκΦκ&μX²π⁼ιΣμ⁻κμυ∧υ¬Συ

Attempt This Online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for flipped, nothing if not. Explanation:

⊞υ⊕…¹²

Start with a list of the numbers 1 to 12.

FA

Loop through the input roll sums.

≔∧υΣEυEΦEX²LκΦκ&μX²π⁼ιΣμ⁻κμυ

For each position found so far, find all the subsets of unflipped tiles that sum to the current sum, remove them from the position, and save all of the resulting positions for the next iteration. Note that Sum doesn't know what to do with an empty list (which happens when the previous move was impossible) so there's a short-circuit for that case.

∧υ¬Συ

Check that we were able to flip over all of the tiles.

\$\endgroup\$
1
\$\begingroup\$

Husk, 13 11 13 bytes

Edit: +2 bytes to fix bug that failed to realise that incomplete 'shut the box' sequences can't themselves 'shut the box'.

¬€ṁö→½Ṗ∫Pḣ12∫

Try it online (using only 6 tiles to avoid timing out)

 €               # first index (or 0 if not found) of
              ∫  # cumulative sum of the input
                 # in
  ṁö             # list conctructed by mapping over
          P      # all permutations of 
           ḣ12   # 1..12
       Ṗ         # and taking all ordered sublists of
        ∫        # the cumulative sum of each permutation
                 # BUT: we need to include the last element
                 # to avoid matching incomplete seqeunces, so
     ½           # split it in half (longer half comes first)
    ←            # and take the second half, containing all the 
                 # sublists that contain the last element;
¬                # and finally return the logical NOT of this
\$\endgroup\$
1
\$\begingroup\$

Haskell, 129 bytes

p[]=[[]]
p(x:y)=[x:s|s<-p y]++p y
t#[]=null t
t#(r:q)=length t>0&&any(#q)[filter(`notElem`s)t|s<-p[1..12],sum s==r,all(`elem`t)s]

Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

Scala, 382 bytes

It can be golfed more.

Golfde version, try it online!

type S=Set[Int]
type L=List[Int]
def c1(d:S,n:Int,c:L=Nil):List[S]={val k = c.sum;if(k==n)List(c.toSet);else if(k>n)Nil;else d.toList.flatMap(j=>c1(d-j,n,j::c));}
def f(d:L):Int={val q=Queue[((S,L))]((1 to 12).toSet->d);while(q.nonEmpty){val (s,ds)=q.dequeue();if(s.isEmpty)return 1;if(ds.nonEmpty){val remaining= ds.tail;c1(s,ds.head).foreach(r=>q.enqueue((s--r,remaining)));}}
0;}

Ungolfed version

import scala.collection.mutable.Queue

object Main extends App {

  def combinations(d: Set[Int], n: Int, c: List[Int] = Nil): List[Set[Int]] = {
    val k = c.sum
    if (k == n) List(c.toSet)
    else if (k > n) Nil
    else d.toList.flatMap(j => combinations(d - j, n, j :: c))
  }

  def f(d: List[Int]): Int = {
    val q = Queue[((Set[Int], List[Int]))]((1 to 12).toSet -> d)
    while (q.nonEmpty) {
      val (s, ds) = q.dequeue()
      if (s.isEmpty) return 1
      if (ds.nonEmpty) {
        val remaining = ds.tail
        combinations(s, ds.head).foreach(r => q.enqueue((s -- r, remaining)))
      }
    }
    0
  }

  val truthy_tests = List(
    List(2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 12),
    List(3, 4, 5, 6, 7, 8, 9, 12, 12, 12),
    List(12, 12, 12, 12, 12, 12, 6),
    List(12, 12, 12, 12, 12, 11, 7),
    List(7, 7, 7, 7, 8, 9, 10, 11, 12),
    List(12, 4, 5, 7, 8, 9, 10, 11, 12)
  )
  val falsy_tests = List(
    List(),
    List(2),
    List(12, 5, 6),
    List(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12),
    List(3, 4, 4, 5, 6, 7, 8, 9, 10, 11, 12),
    List(7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8),
    List(3, 3, 4, 5, 6, 8, 9, 12, 12, 12, 4)
  )

  truthy_tests.foreach { t => println(f(t)) }
  println("-" * 30)
  falsy_tests.foreach { t => println(f(t)) }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.