¿Cuántos dígitos de cartón necesito?

32

Necesito preparar dígitos hechos de cartón para mostrar algún número ( ejemplo ). No sé de antemano qué número debo mostrar, lo único que sé es que no es mayor que n.

¿Cuántos dígitos de cartón debo preparar?

Ejemplo: n = 50

Para mostrar cualquier número en el rango 0 ... 50, necesito los siguientes dígitos:

  1. Un cero, para mostrar el número 0, o cualquier otro número redondo
  2. Dos copias de los dígitos 1, 2, 3 y 4, para mostrar los números correspondientes.
  3. Una copia de los dígitos 5, 6, 7 y 8, para el caso aparecen como dígitos menos significativos en el número
  4. El dígito 9 nunca es necesario, porque puedo usar el dígito invertido 6 en su lugar

Total: 13 dígitos

Casos de prueba (cada línea es un caso de prueba en el formato "entrada; salida")

0 1
1 2
9 9
11 10
50 13
99 17
100 18
135 19
531 22
1000 27
8192 34
32767 38
anatolyg
fuente
2
¿Se puede girar cualquier otro dígito además de 6/9?
feersum
No (ver ejemplo)
anatolyg
Entonces, dos 1 no se pueden superponer para hacer un 7 entonces
user253751
2
... y dos ceros no pueden hacer un 8. Eso sería feo.
anatolyg
Probablemente sea una pregunta incómoda, pero como se trata de dígitos de 'cartón', ¿pueden imprimirse a doble cara para ahorrar en el total requerido? En el ejemplo, nunca necesitaría 6 y 0 juntos, por ejemplo.
Weckar E.

Respuestas:

16

Jalea , 9 bytes

‘ḶDœ|/ḟ9L

Pruébalo en línea!

Cómo funciona

‘ḶDœ|/ḟ9L
‘Ḷ         [0,1,...,n]
  D        convert each to list of its digits
   œ|/     fold by multiset union
      ḟ9   remove 9
        L  length
Monja permeable
fuente
14
Demasiado rápido>. <Lo juro, tienes una respuesta Jelly para cada desafío conocido en el universo y solo tienes un bot para publicarlos justo después del desafío. : P Buena respuesta.
HyperNeutrino
10
@HyperNeutrino Creo que el bot extrae casos de prueba del desafío y prueba todos los posibles programas de gelatina utilizando una supercomputadora.
NieDzejkob
1
@HyperNeutrino Conoces la sensación ... especialmente si tu solución es 0rDŒr€ẎQṪÞẎḟ9ĠẎL.
Erik the Outgolfer
Dudé de la validez de part9 parte por un momento, luego me di cuenta de que 6 <9, por lo que el número de 6s no puede ser menor que el número total posible de 6s y 9s combinados en cada combinación.
Nader Ghanbari
7

Python 2 , 49 bytes

lambda n:9*len(`n`)-9+(n*9+8)/10**len(`n`)+(n<10)

Pruébalo en línea!

Una fórmula aritmética torpe. Suponga que nencaja dentro de un intpara que Lno se agregue un.

Gracias a Neil por guardar 5 bytes al señalar que los 9 que no se usan podrían manejarse haciendo en n*9+8lugar de n*9+9, por lo que, por ejemplo, 999*9+8=8999no se transfiere a 9000.

xnor
fuente
@ovs Eso no funciona del todo, no es suficiente saber el primer dígito. Por ejemplo, 33333requiere cinco 3 pero 22222solo cuatro. n*9[0] es tentador, pero falla para los números que comienzan con 1y menos 111...
xnor
Según mis cálculos (vea mi respuesta de Lote), probablemente pueda usar (n*9+8)/10**len(`n`)para evitar usar min.
Neil
7

Haskell , 117 114 108 95 89 88 87 84 82 63 bytes

6 bytes guardados gracias a Laikoni

1 4 6 bytes guardados gracias a nimi

g x=sum[maximum[sum[1|u<-show y,d==u]|y<-[0..x]]|d<-['0'..'8']]

Pruébalo en línea!

Asistente de trigo
fuente
3
1.) maximum[a,b]es lo mismo que max a b. 2.) Las comprensiones de la lista son a menudo más cortas que filter:max d$sum[1|x<-show a,x==b]
Laikoni
1
Se puede reemplazar gcon un literal de la función pointfree: sum.(#[-9..]).
nimi
@nimi No sé qué es una función literal de punto libre, pero creo que veo lo que estás sugiriendo. Dime si me equivoco.
Wheat Wizard
1
... y lo length[x|x<-...]es sum[1|x<-...].
nimi
1
Las funciones pueden no tener nombre, por lo que no es necesario g=(pero tal vez desee incluirlo en la versión TIO).
nimi
5

Mathematica, 49 bytes

Tr@Delete[Max~MapThread~DigitCount@Range[0,#],9]&
alephalpha
fuente
¡bonito! ¿Se basa esto en mi respuesta?
J42161217
5

JavaScript (ES6), 60 53 bytes

f=(n,i=9)=>n>(i%9+1+"e"+(i/9|0))/9-1?1+f(n,-~i):n>9^1

Una especie de solución recursiva hacky. Esto genera los números que requieren agregar un dígito:

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 22, 33, 44, 55, 66, 77, 88, 100, 111, 222, ...

y luego cuenta cuántos son menos que la entrada. Por un milagro feliz, eliminar el dígito en 9realidad elimina varios bytes de la función, porque la secuencia se puede generar así (suponiendo una división de enteros):

1e1 / 9 = 1, 2e1 / 9 = 2, ..., 8e1 / 9 = 8, 9e1 / 9 = 10, 1e2 / 9 = 11, 2e2 / 9 = 22, ...

Tenemos que tener en cuenta el hecho de que los números menores de 10 todavía requieren el cero, pero esto es tan simple como sumar n > 9 ? 0 : 1al resultado.

Casos de prueba

ETHproducciones
fuente
n>9^1probablemente puede sern<10
CalculatorFeline
@CalculatorFeline Bueno, eso da trueinformación 0, así que dudo un poco en hacerlo.
ETHproductions
0>9es falso, false^1es 1 ...?
CalculatorFeline
@CalculatorFeline Sí, estoy diciendo que dudo en generar el booleano trueen lugar del número 1.
ETHproductions
4

Lote, 67 bytes

@if %1 geq 10%2 %0 %1 0%2 -~%3
@cmd/cset/a(%1*9+8)/10%2+9*%30+!%30

En la formulación estándar de este problema, necesita separar 6y 9dígitos, pero no es necesario que lo muestre 0. A medida nque aumenta el valor máximo requerido, la cantidad de números requeridos aumenta cada vez que alcanza un repdigit (porque no tiene suficiente de ese número) y cada vez que alcanza una potencia de 10(cuando necesita un cero adicional). En total, cada potencia 10necesita 10más números que la anterior, que se pueden calcular como floor(log10(n))*10. Para valores de nentre potencias de 10, el número de dígitos intermedios intermedios se puede calcular como floor(n/((10**floor(log10(n))*10-1)/9))o alternativamente floor(n*9/(10**floor(log10(n))*10-1)).

Calculo floor(log10(n))por medio del bucle en la primera línea. Cada vez, %2gana un extra 0y %3gana un extra -~. Esto significa que 10%2es 10*10**floor(log10(n))y %30es floor(log10(n)).

La duplicación de 6y 9tiene dos efectos: en primer lugar, solo se 9requieren números para cada potencia 10y, en segundo lugar, la detección de repdigits debe ignorar los 9repdigits. Afortunadamente, como son menos de una potencia de 10, esto se puede lograr ajustando la fórmula para obtener floor((n*9+8)/(10**floor(log10(n))*10)).

Tratar con el cero es razonablemente simple: esto solo requiere un número adicional cuando n<10, es decir floor(log10(n))==0.

Neil
fuente
2

Mathematica, 83 bytes

v=DigitCount;s=v@0;(Table[s[[i]]=v[j][[i]]~Max~s[[i]],{i,10},{j,#}];s[[9]]=0;Tr@s)&
J42161217
fuente