How many bead arrangements on the abacus?

Question

Your toy in this challenge is a special abacus of 4 rows and 8 positions per row. There's one bead on the first row, 2 beads on the 2^nd row, 3 beads on the 3^rd row and 4 beads on the 4^th row. Beads on a same row are glued together, which means that they can only be moved as a block.

Below is a valid configuration of the abacus:

---O----
------OO
-OOO----
---OOOO-

Of course, a block cannot be moved beyond the edges of the abacus. So there are 8 possible positions for the block on the first row and only 5 for the block on the last row.

Task

You'll be given a list of 8 non-negative integers representing the total number of beads in each column of the abacus. Your task is to output the number of configurations that lead to this result.

Examples

If the input is \$[4,3,2,1,0,0,0,0]\$, the only possible way is to put all blocks at the leftmost position:

O-------
OO------
OOO-----
OOOO----
________
43210000

If the input is \$[1,0,0,1,2,3,2,1]\$, there are 2 possible configurations:

O-------    O-------
----OO--    -----OO-
-----OOO    ---OOO--
---OOOO-    ----OOOO
________    ________
10012321    10012321

If the input is \$[1,1,1,2,2,2,1,0]\$, there are 13 possible configurations. Below are just 4 of them:

O-------    ---O----    ---O----    ------O-
-OO-----    ----OO--    ----OO--    OO------
---OOO--    OOO-----    ----OOO-    ---OOO--
---OOOO-    ---OOOO-    OOOO----    --OOOO--
________    ________    ________    ________
11122210    11122210    11122210    11122210

Rules

• You can assume that the input is valid: all values are in \$[0\dots4]\$, their sum is \$10\$ and at least one configuration can be found.
• You can take the input list in any reasonable format (array, string of digits, etc.).
• Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

[4,3,2,1,0,0,0,0] -> 1
[1,1,1,2,0,2,2,1] -> 1
[1,0,0,1,2,3,2,1] -> 2
[1,1,2,2,2,1,0,1] -> 3
[0,2,2,2,2,2,0,0] -> 4
[0,0,0,1,2,2,3,2] -> 5
[1,1,1,1,1,1,2,2] -> 6
[0,2,2,2,2,1,1,0] -> 8
[1,1,1,2,2,1,1,1] -> 10
[1,1,2,2,2,1,1,0] -> 12
[1,1,1,2,2,2,1,0] -> 13

Answer 1

Jelly, 15 bytes

żJØ.xⱮS
8Ḷṗ4Ç€ċ

Try it online!

Takes input without trailing zeros.

Explanation

żJØ.xⱮS Auxiliary monadic link, taking a list of 4 integers
ż       Zip with
 J        indices: [1,2,3,4]
    x   Repeat
  Ø.      [0,1]
          [a,b] times respectively
     Ɱ    for each [a,b] in the list
      S Sum

8Ḷṗ4Ç€ċ Main monadic link, taking a list of integers
8       8
 Ḷ      Lowered range: [0,1,2,3,4,5,6,7]
  ṗ4    Cartesian 4th power
    Ç   Apply the auxiliary link
     €    to each
      ċ Count the occurences of the input

Answer 2

MATL, 33 32 31 25 bytes

8:KZ^!"8:@<1M-K:!<<sGX=vs

Try it online! (but it takes around 50 seconds, and it sometimes times out).

Explanation

The code 8: generates the vector [1 2 ··· 8]. K pushes 4, Z^ computes the Cartesian power, and ! transposes. So this gives the following matrix, of size 4×4096:

[1 1 ··· 8 8;
 1 1 ··· 8 8;
 1 1 ··· 8 8;
 1 2 ··· 7 8]

Each column represents a possible abacus configuration, defined by the position of the leftmost bead in each row. Some configurations are impossible (for example, values above 5 in the last row are not allowed), but this isn't a problem because the result computed from these configurations will never coincide with the input.

The loop " takes each column of this matrix. 8: pushes [1 2 ··· 8] onto the stack, and @ pushes the current column, say [1; 1; 1; 1] in the first iteration. < compares these two vectors, of sizes 1×8 and 4×1, element-wise with singleton expansion. This gives a 4×8 matrix with all the comparisons, in this case (*)

[0 0 0 0 0 0 0 0;
 0 0 0 0 0 0 0 0;
 0 0 0 0 0 0 0 0;
 0 0 0 0 0 0 0 0]

Then, 1M pushes the two vectors again and - subtracts them element-wise with singleton expansion. This gives, in this case

[0 1 2 3 4 5 6 7;
 0 1 2 3 4 5 6 7;
 0 1 2 3 4 5 6 7;
 0 1 2 3 4 5 6 7]

K:! pushes the column vector [1; 2; 3; 4], and < compares the previous matrix with this vector, again element-wise with singleton expansion. The result is (**)

[1 0 0 0 0 0 0 0;
 1 1 0 0 0 0 0 0;
 1 1 1 0 0 0 0 0;
 1 1 1 1 0 0 0 0]

Now < compares matrices (*) and (**) element-wise. The result will give 1 at entries where the first matrix has a 0 and the second has a 1. The result represents the beads in the abacus for the current configuration:

[1 0 0 0 0 0 0 0;
 1 1 0 0 0 0 0 0;
 1 1 1 0 0 0 0 0;
 1 1 1 1 0 0 0 0]

s computes the sum of each column: [4 3 2 1 0 0 0 0]. Then GX= compares this with the input vector. (Note that non-valid abacus configurations such as [8; 8; 8; 8] will produce less then 10 entries equal to 1 in the matrix above, and so will never give a result matching the input.) The result is 1 if both vectors are equal or 0 otherwise. vs adds this to the accumulated sum of previous iterations.

The final sum is implicitly printed at the end.

Answer 3

J, ^{42 41} 40 bytes

-1 thanks to Jonah!

1#.(1680+/@((#:~8&-)I.@,.1+])"{&i.4)e.,:

Try it online!

• 1680 f"{&i. 4 for each i in 0…1679 and 0 1 2 3 run …

• (#:~8&-) i mixed-base-converted with bases 8 - 0 1 2 3 = 8 7 6 5 so we get every possible configuration, f.e. 2 1 0 1.

• ,.1+] append item-wise 1 + 0 1 2 3 = 1 2 3 4: 2 1, 2 2, 0 3, 1 4.

• I.@ for each pair, take that many 0s and 1s (_ filled with 0s):

  2 1: 0 0 1 _ _
  2 2: 0 0 1 1 _
  0 3: 1 1 1 _ _
  1 4: 0 1 1 1 1
  

• +/@ sum 1 2 4 2 1 – because we get every possible configuration, J automatically pads the arrays to length of 8.

• 1#. … e.,: count the occurrences of the input.

Answer 4

Python 3, 72 bytes

f=lambda a,n=4:n==a or sum(f(a-int(n*"1"+i*"0"),n-1)for i in range(n*8))

Try it online!

---

Python 2, 75 bytes

[sum(int(-~j*"1"+n/8**j%8*"0")for j in range(4))for n in range(8**4)].count

Try it online!

This is an expression evaluated to an unnamed function. You can assign it to f by prepend f=, and then use it as f(43210000). It takes input as a single integer. For example, [4,3,2,1,0,0,0,0] becomes 43210000 while [0,0,0,1,2,2,3,2] becomes 12232.

It is interesting that you don't need lambda nor def to define a function in Python.

Answer 5

Haskell, 88 bytes

0#t=[1|all(==0)t]
m#t=do k<-[0..7];(m-1)#[r-sum[1|j>k,j<=k+m]|(j,r)<-zip[1..]t]
sum.(4#)

Try it online!

Answer 6

Charcoal, 32 26 bytes

Ｉ№Ｅ׳φΣＥ⁴×Ｘχ﹪÷ιＸ⁸λ⁸÷Ｘχ⊕λ⁹Ｎ

Try it online! Link is to verbose version of code. Takes input as a string of 8 digits. Explanation: Simply generates the column sums of all configurations and counts the number that match.

  Ｅ׳φ                      Consider 3,000 configurations
       Ｅ⁴                   Consider 4 rows
                   ÷Ｘχ⊕λ⁹   Row mask
         ×                  Multiplied by
          Ｘχ                Shift given by
            ﹪÷ιＸ⁸λ⁸         Current base 8 digit
      Σ                     Take the (column) sum
 №                          Count matches of
                         Ｎ  Input cast to integer
Ｉ                           Cast to string
                            Implicitly print

There are only 1680 true configurations but without mixed base conversion they won't be consecutive; in base 8 the last configuration is 2423 but obviously 3000 is golfier (any value up to 4096 would work). The row mask is simply a string of 1s representing the Os, with a shift that represents the number of trailing 0s representing the -s (the leading -s are implied). Since the column sums won't be higher than 4 the masks can simply be added as decimal integers (golfier than base 5 of course). False configurations will result in a value greater than 43,210,000 so they which will never match a legal input value.

Answer 7

Jelly, 13 bytes

Started looking for ways to golf xigoi's great Jelly answer but it took a fair bit of effort so thought I'd post instead.

8ṗ4+"JḶ$ṬSƲ€ċ

A monadic Link that accepts the list (using the no-trailing zeros option) and yields the count.

Try it online!

How?

8ṗ4+"JḶ$ṬSƲ€ċ - Link: list of non-negative integers, Totals
8             - eight
  4           - four
 ṗ            - ([1..8]) Cartesian power (4) -> all length 4 lists using [1..8]
           €  - for each (list of four "start indices", I, in that):
          Ʋ   -   last four links as a monad - f(I):
       $      -     last two links as a monad - g(I):
     J        -       range of length -> [1,2,3,4]
      Ḷ       -       lowered range -> [[0],[0,1],[0,1,2],[0,1,2,3]]
    "         -     (I) zip (that) with:
   +          -       addition -> [[0+i1],[0+i2,1+i2],[0+i3,1+i3,2+i3],[0+i4,1+i4,2+i4,3+i4]]
        Ṭ     -     un-truth -> [[0...0,1],[0...0,1,1],[0...0,1,1,1],[0...0,1,1,1,1]]
                                (number of zeros being i1-1, i2-1, i3-1, and i4-1 respectively)
         S    -     sum (column-wise)
            ċ - count occurrences (of the input list, Totals)

Answer 8

Haskell, 58 bytes

(1111%)
0%0=1
0%_=0
k%n=sum[div k 10%(n-k*10^i)|i<-[0..7]]

Try it online!

(1111%) is the main function. It takes input as an integer, e.g. (1111%) 11122210 == 13.

This essentially counts solutions to $$1111a+111b+11c+d=n$$ where \$a,b,c,d\$ range over \$10^0, 10^1 \dots 10^7\$.

Answer 9

Python 3, 136 bytes

Takes input as an integer (i.e. no leading zeroes). Generates all possible configurations of the abacus, filters down to only those matching the input, returns the count. Loses 23 byes on the itertools import.

lambda n:sum([x==n for x in map(sum,product(*([int('1'*i+'0'*(8-j-i))for j in range(9-i)]for i in range(1,5))))])
from itertools import*

Try it online!

Answer 10

Vyxal R, 23 bytes

8:Ẋ:Ẋvfƛ‹↵\1dd¦vI*∑⁰=;∑

Try it Online!

A messy attempted port of Lynn's answer.