Cube calendar numbers

Question

^{Credit: Marco Verch CC BY 2.0}

A two-cube calendar, as shown in the picture, uses two cubes with digits painted on the faces to display the date. For dates in the range 1-9, a leading zero is used ("01", "02", ..., "09").

Now, if you do the math, you might come to the conclusion that these calendars should be impossible. After all, the numbers "0","1" and "2" must appear on both cubes (proof left to the reader). This means that there are only six faces remaining for the other seven numbers.

Two-cube calendars use a trick where the face with a "6" can be rotated upside down to look like a "9". For example, one cube may have faces "012345" and the other one "012678" where the "6" can also be a nine. For the purposes of this challenge these kind of font-dependent tricks are banned.

With these restrictions we can only display the numbers from 0 to 21 for a total of 22 numbers. We can display some other numbers too, but we are only interested in the longest possible sequence of numbers displayable (no gaps), starting from 0.

If, instead of using base 10, we would have used base 6, we could display \$0-55_6\$ for a total of 36 numbers. (\$55_6=35_{10}\$)

If, instead of using cubes, we would have used octahedrons (8 faces), we could display 0-65 (using base 10).

And finally, with three cubes we can get 0-76 for a total of 77 numbers (using base 10).

The maximal amount of numbers we can get in the initial range is called the cube calendar number. It depends on the number of faces, on the number of dice ("cubes") and on the base of the numbers.

Task

Given a base b, the number of faces f and the number of dice d, return the cube calendar number for those parameters.

b, f and d are natural numbers guaranteed to satisfy:

\$b\ge 2\$

\$b\ge f \ge 1\$

\$d\ge 1\$

Test cases

d f b result
1 1 2 1
1 1 3 1
1 1 4 1
1 2 2 2
1 2 3 2
1 2 4 2
1 3 3 3
1 3 4 3
1 4 4 4
2 1 2 1
2 1 3 1
2 1 4 1
2 2 2 4
2 2 3 4
2 2 4 3
2 3 3 9
2 3 4 10
2 4 4 16
3 1 2 1
3 1 3 1
3 1 4 1
3 2 2 8
3 2 3 8
3 2 4 5
3 3 3 27
3 3 4 21
3 4 4 64
4 1 2 1
4 1 3 1
4 1 4 1
4 2 2 16
4 2 3 13
4 2 4 10
4 3 3 81
4 3 4 63
4 4 4 256
2 6 10 22
2 6 6 36
2 8 10 66
3 6 10 77

Answer 1

Python, 57 bytes (-8 thanks to @xnor)

lambda D,F,B:B**(D*~-F//~-B+1)//(B-(F<B>2))*(1+D*~-F%~-B)

Attempt This Online!

Previous Python, 65 bytes

lambda D,F,B:F//B*B**D or(B**(D*~-F//~-B+1)-1)//~-B*(1+D*~-F%~-B)

Attempt This Online!

Obsolete Python, 69 bytes

lambda D,F,B:(B**-(D*~-F//-~-B)-1)//~-B*((x:=B+D*~-F%-~-B)-F//B)+x//B

Attempt This Online!

How?

Given D,F,B a best set of dice has a zero on every die because 0 (with leading zeros) must be representable. The remaining D(F-1) faces should evenly split between the B-1 non-zero digits. Indeed, if we write

\$(1)\qquad M:=\lfloor D(F-1)/(B-1)\rfloor\$

then to get up to at least \$10_{(B)}^M\$ we need \$11..11_{(B)}, 22..22_{(B)}, 33..33_{(B)}\$ etc. (M digits each).

How much farther can we go? If the division in (1) splits cleanly (no remainder) then we top out at \$11..110_{(B)}\$ (M+1 digits). This also shows that if the split was not clean then the first excess face should be a 1. If that is the only excess face it will carry us up to \$22..221_{(B)}\$. The next excess face if it exists should therefore be a 2. Etc. Since we start at 0, the corresponding cube calendar numbers are \$11..11_{(B)}=(10_{(B)}^{M+1}-1)/(B-1),22..22_{(B)},...\$

It remains to special case B=F and that's it.

Answer 2

Charcoal, 36 bytes

ＮθＮηＮζＩ×⊕﹪×θ⊖η⊖ζ÷Ｘζ⊕÷×θ⊖η⊖ζ⁻ζ∧‹ηζ›ζ²

Try it online! Link is to verbose version of code. Explanation: Now uses @xnor's correction F<B>2 (my previous correction F<B didn't work in some cases) which is still a byte golfier than special-casing F=B; this now makes my answer equivalent to a port of his golf to @loopywalt's answer.

Ｎθ                                      Input `d` as a number
  Ｎη                                    Input `f` as a number
    Ｎζ                                  Input `b` as a number
                  ζ                     Input `b`
                 Ｘ                      Raised to power
                      θ                 Input `d`
                     ×                  Multiplied by
                        η               Input `f`
                       ⊖                Decremented
                    ÷                   Integer divided by
                          ζ             Input `b`
                         ⊖              Decremented
                   ⊕                    Incremented
                ÷                       Integer divided by
                            ζ           Input `b`
                           ⁻            Subtract
                               η        Input `f`
                              ‹         Is less than
                                ζ       Input `b`
                             ∧          Logical And
                                  ζ     Input `b`
                                 ›      Is greater than
                                   ²    Literal integer `2`
       ×                                Multiplied by
           θ                            Input `d`
          ×                             Multiplied by
             η                          Input `f`
            ⊖                           Decremented
         ﹪                              Modulo
               ζ                        Input `b`
              ⊖                         Decremented
        ⊕                               Incremented
      Ｉ                                 Cast to string
                                        Implicitly print

Answer 3

JavaScript (ES7), 54 bytes

A port of loopy walt's xnor-optimized answer.

(d,f,b)=>~~(b**-~(d*--f/--b)/(b+(b<=f|b<2)))*(d*f%b+1)

Try it online!

---

JavaScript (ES11), 50 bytes

An alternate version taking Bigints as input.

We have to use a ternary operator because we can't add a Boolean to a Bigint. This is however an opportunity to invert the sign of the division which allows to save one byte on the multiplication by just using ~. And more importantly, we don't have to round the result of the division anymore.

(d,f,b)=>b**-~(d*--f/--b)/(b>f&b>1?-b:~b)*~(d*f%b)

Try it online!

Answer 4

Haskell, 235 bytes

import Data.Bits
import Data.List
import Data.List.Ordered
o=0::Int
c d f b=length$fst$span(>[])$tail$scanl(\p n->nubSort$filter(all$(f>=).popCount)[sort$zipWith(.|.)q$bit<$>m|m<-permutations n,q<-p])[repeat o]$mapM id$[o..b-1]<$[1..d]

Try it online!

Haskell, 251 bytes

import Data.Bits
import Data.List
import Data.List.Ordered
o=0::Int
c d f b=length$fst$break null$tail$scanl(\p n->nubSort$map sort$filter(all$(f>=).popCount)[zipWith(.|.)m q|m<-map(map bit)$permutations n,q<-p])[repeat o]$sequence$replicate d[o..b-1]

Try it online!

Answer 5

Python3, 877 bytes

from numpy import*
from itertools import*
U=lambda D:[''.join(j)for k in permutations(D,len(D))for j in product(*k)]
I=lambda P,n,b:sorted({int(i,b)for i in P})[:n+1]==[*range(n+1)]
def F(d,f,b):
 q,R,S=[([['0']],0,[])],[0],[]
 while q:
  D,n,C=q.pop(0)
  if len(D)==d and all([f==len(i)for i in D]):R+=[n]
  N=base_repr(n+1,base=b).zfill(len(D))
  if N in C:q+=[(D,n+1,C)]
  else:
   if len(N)>len(D)and len(D)<d:D+=[['E']]
   p=U(D)
   for P in p:
    if P!=N and(P[:-1]==N[:-1]or P[1:]==N[1:]):
     V=N[0]if P[1:]==N[1:]else N[-1]
     D=[[j for j in i if j!='E']for i in D]
     if len(D[-1])<f:
      if(Y:=[*D[:-1],D[-1]+[V]])not in S and I(u:=U(Y),n+1,b):q+=[(Y,n+1,u)];S+=[Y]
     elif len(D)<d:
      if f>1 and(Y:=D+[['0',V]])not in S and I(u:=U(Y),n+1,b):q+=[(Y,n+1,u)];S+=[Y]
      if(Y:=D+[[V]])not in S and I(u:=U(Y),n+1,b):q+=[(Y,n+1,u)];S+=[Y]
 return max(R)+1

Try it online!

Answer 6

05AB1E, 19 bytes

<*I<‰>`ŠmID¹2‚›P-÷*

Inputs in the order \$f,d,b\$.

Port of @Neil's Charcoal answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

Formula: (d*(f-1)%(b-1)+1)*((b**(d*(f-1)//(b-1)+1))//(b-(b>f)*(b>2)))

<                   # Decrease the first (implicit) input `f` by 1
                    #  STACK: f-1
 *                  # Multiply it to the second (implicit) input `d`
                    #  STACK: d*(f-1)
    ‰               # Divmod it by
  I<                # the third input `b` minus 1
                    #  STACK: [d*(f-1)//(b-1), d*(f-1)%(b-1)]
     >              # Increase both values in the pair by 1 (let's call them [A,B])
                    #  STACK: [d*(f-1)//(b-1)+1, d*(f-1)%(b-1)+1]
      `             # Pop and push them separated to the stack
                    #  STACK: d*(f-1)//(b-1)+1, d*(f-1)%(b-1)+1
       Š            # Tripleswap the stack using the implicit third input `b`
                    #  STACK: d*(f-1)%(b-1)+1, b, d*(f-1)//(b-1)+1
        m           # Take `b` to the power `A`
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1)
         I          # Push the third input `b` again
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1), b
          D         # And again
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1), b, b
           ¹2‚      # Push pair [f,2]
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1), b, b, [f,2]
              ›     # Pop the copy of `b`, and check [b>f, b>2]
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1), b, [b>f,b>2]
               P    # Check if both are truthy by taking the product
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1), b, (b>f)*(b>2)
                -   # Decrease the other `b` by this 0 or 1
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1), b-(b>f)*(b>2)
                 ÷  # Integer-divide `b to the power A` by this
                    #  STACK: d*(f-1)%(b-1)+1, (b**(d*(f-1)//(b-1)+1))//(b-(b>f)*(b>2))
                  * # Multiply it to `B`
                    #  STACK: (d*(f-1)%(b-1)+1)*((b**(d*(f-1)//(b-1)+1))//(b-(b>f)*(b>2)))
                    # (after which the result is output implicitly)