14
\$\begingroup\$

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 2nd row, 3 beads on the 3rd row and 4 beads on the 4th 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 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
\$\endgroup\$
6
  • \$\begingroup\$ Can I take the input without trailing zeros? \$\endgroup\$
    – xigoi
    Commented Jun 30, 2021 at 13:06
  • 1
    \$\begingroup\$ @xigoi Yes. That seems reasonable. \$\endgroup\$
    – Arnauld
    Commented Jun 30, 2021 at 13:12
  • \$\begingroup\$ Great challenge! Just out of curiosity, why did you add the constraint that at least one configuration can be found? (It's in the first rule specifying valid input.) \$\endgroup\$
    – AviFS
    Commented Jun 30, 2021 at 18:22
  • 2
    \$\begingroup\$ @AviFS It was just a way to elude several questions about how wrong the input can be. I suppose I could have removed it when I added the 2 other points about the range and the sum of the values. \$\endgroup\$
    – Arnauld
    Commented Jun 30, 2021 at 19:48
  • \$\begingroup\$ There certainly are configurations that satisfy the first 2 rules but not the 3rd, e.g.: 12304000, 00144100, etc. Maybe a related challenge would be to test whether a given configuration has a solution. Or you could put it in this one, just return 0 if there are none? \$\endgroup\$ Commented Jul 1, 2021 at 15:33

10 Answers 10

5
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ It really feels like there should be some way to inline the helper that saves a byte, but § isn't equivalent to S€ and ) won't give you the argument back for ċ... \$\endgroup\$ Commented Jun 30, 2021 at 15:51
4
\$\begingroup\$

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.

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

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.

\$\endgroup\$
4
  • \$\begingroup\$ Neat test in the TIO link! \$\endgroup\$
    – AviFS
    Commented Jun 30, 2021 at 18:40
  • 1
    \$\begingroup\$ Save 1 byte with: 1#.(1680+/@((#:~8&-)I.@,.1+])"{&i.4)e.,: \$\endgroup\$
    – Jonah
    Commented Jul 1, 2021 at 6:06
  • \$\begingroup\$ I don't know J, but will this save some bytes: Simply convert 0..4095 to base 8, and generate items with some garbage items included (which will never match input and harmless). \$\endgroup\$
    – tsh
    Commented Jul 1, 2021 at 8:28
  • \$\begingroup\$ @tsh Because the resulting items with length > 8 would pad the smaller ones, finding the input in them won't be that easy. Also base-converting without giving length is actually quite long in J 8#:inv]. But I might just haven't found the right combination yet. \$\endgroup\$
    – xash
    Commented Jul 1, 2021 at 8:51
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Could you please explain your I/O format? \$\endgroup\$
    – Arnauld
    Commented Jun 30, 2021 at 16:49
  • \$\begingroup\$ @Arnauld sum.(4#) is the function. Call it on a list of 8 integers. \$\endgroup\$
    – Wheat Wizard
    Commented Jun 30, 2021 at 17:03
3
\$\begingroup\$

Charcoal, 32 26 bytes

I№E׳φΣE⁴×Xχ﹪÷ιX⁸λ⁸÷Xχ⊕λ⁹N

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.

  E׳φ                      Consider 3,000 configurations
       E⁴                   Consider 4 rows
                   ÷Xχ⊕λ⁹   Row mask
         ×                  Multiplied by
          Xχ                Shift given by
            ﹪÷ιX⁸λ⁸         Current base 8 digit
      Σ                     Take the (column) sum
 №                          Count matches of
                         N  Input cast to integer
I                           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.

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

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)
\$\endgroup\$
1
  • \$\begingroup\$ Brilliant, as always! I don't know why I didn't think of using , it's so useful for this challenge… \$\endgroup\$
    – xigoi
    Commented Jun 30, 2021 at 21:55
2
\$\begingroup\$

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\$.

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

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!

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

Vyxal R, 23 bytes

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

Try it Online!

A messy attempted port of Lynn's answer.

\$\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.