Números confidentes

14

Números confidentes

Deje xser un número entero de una base arbitraria, tal que Des una matriz de sus dígitos. xes un Número de Confidente si, para todo nentre 1y la longitud de D:

D[n+1] = D[n] + D[n-1] + ... + D[1] + n

Tomemos, por ejemplo, el número 349en la base 10. Si etiquetamos los índices para este número, tenemos lo siguiente.

Index    Digit
-----    -----
1        3
2        4
3        9

A partir del primer dígito, tenemos 1 + 3 = 4, que produce el siguiente dígito. Luego, con el segundo dígito que tenemos 3 + 4 + 2 = 9, que, nuevamente, produce el siguiente dígito. Por lo tanto, este número es un número de confianza.


Dado un número entero con una base entre 1 y 62, calcule todos los Números de Confianza para esa base y genere una lista de ellos, separados por nuevas líneas. Puede suponer que hay una cantidad finita de números de confianza para una base determinada.

Para dígitos mayores que 9, use los caracteres alfabéticos A-Zy para dígitos mayores que Zuse los caracteres alfabéticos a-z. No tendrá que preocuparse por los dígitos más allá z.

No tienen que salir en ningún orden en particular.


Entrada de muestra:

16

Salida de muestra:

0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
12
23
34
45
56
67
78
89
9A
AB
BC
CD
DE
EF
125
237
349
45B
56D
67F
125B
237F

Este es el código de golf, por lo que gana el código más corto. ¡Buena suerte!

(Gracias a Zach por ayudar con el formato y señalar algunos problemas).

un espagueti
fuente
Lo siento, poca confusión entre Zach y yo sobre la pregunta. Todo debería estar formateado en este momento.
un spaghetto
Una observación útil: en un número confidente, cada dígito es uno más el doble del dígito anterior, excepto que el segundo dígito es uno más el primer dígito.
xnor
Ir en columna revela otro (posiblemente) patrón útil;)
Geobits
1
En el ejemplo, ¿por qué CDno está en la lista? Como todas las otras combinaciones en las que el segundo dígito es uno más que el primer dígito están en la lista, no entiendo por qué CDno califica.
Reto Koradi
Eso fue un accidente: P Corregido, gracias por señalarlo.
un spaghetto

Respuestas:

2

Pyth, 38 bytes

0jms@L+s`MT+rG1Gdf<eTQsm.u+N+lNsNQ]dSQ

Pruébelo en línea: demostración

Explicación:

0jms@L+s`MT+rG1Gdf<eTQsm.u+N+lNsNQ]dSQ  implicit: Q = input base
0                                       print 0
                       m            SQ  map each d of [1, 2, ..., Q] to:
                        .u       Q]d      start with N=[d], apply v Q times
                          +N+lNsN           add (len(N) + sum(N)) to N
                                          gives all intermediate results
                      s                 join to one list of candidates
                 f<eTQ                  filter those, where every digit < Q
  ms@L+s`MT+rG1Gd                       convert numbers to letters 0-9A-Za-z
 j                                      print each on separate line
Jakube
fuente
9

Python 2, 104 bytes

n=input()
for i in range(n):
 s=''
 while i<n:s+=chr(48+i+(i>9)*7+i/36*6);print s;i+=n**0**i+i*(s>s[:1])

Esto utiliza la siguiente observación: en un número confidente, el dígito ies seguido por 2*i+1, excepto que es i+1el segundo dígito. Al probar todos los primeros dígitos posibles y agregar más dígitos hasta que sean demasiado grandes, podemos generar todos los números confidentes.

Calculamos el carácter que corresponde al número icomo chr(48+i+(i>9)*7+i/36*6), lo que lo cambia al número, letra mayúscula o rango de letra mayúscula para los intervalos 0-9, 10-35, 36-61.

Luego, aumentamos ivía i+=i+1con dos ajustes. Para hacer esto en i+=1su lugar después del primer dígito, agregamos icondicional que stenga más de 1caracteres. Además, debemos evitar que se impriman números que comienzan con 0, mientras que al mismo tiempo lo permitimos 0. Para hacer esto, hacemos un truco que hace i=0que falle la condición i<nen el siguiente ciclo al agregarlo n. Esto se hace reemplazando 1con n**0**i, qué derecho se asocia a n**(0**i), qué es igual a n**(i==0)o n if i==0 else 1.

xnor
fuente
Wow, Dang. ¡Casi la mitad del tamaño en comparación con Python 3! Hmm Me pregunto cuántos bytes puedo ahorrar si uso algunos de tus trucos ...
El'endia Starman
4

Python 3, 201 200 bytes

n=int(input())
X=[[i]for i in range(1,n)]
for x in X:
 y=sum(x)+len(x)
 if y<n:X.append(x+[y])
X=[[0]]+X
print('\n'.join(''.join(map(lambda x:[str(x),chr(x+55),chr(x+61)][(x>9)+(x>35)],x))for x in X))

Explicación

La idea clave aquí es que, dada una secuencia x(como, por ejemplo, [1,2,5]), puede obtener el siguiente término en la secuencia con sum(x)+len(x), que da 11en este caso ( B). Verifique si esto es menor que n, y si es así, agregue la secuencia extendida a la lista de todas esas secuencias (sembradas por todos los dígitos individuales).

[str(x),chr(x+55),chr(x+61)][(x>9)+(x>35)]

Así es como mapeo los elementos de secuencia a los personajes. Estos se ''.joineditan juntos y luego se imprimen, separados por nuevas líneas.

El'endia Starman
fuente
Puede guardar un byte cambiando su última línea a print('\n'.join(''.join(map(lambda x:[str(x),chr(x+55),chr(x+61)][(x>9)+(x>35)],x))for x in X)). Además, actualmente son 201 bytes; no 200.
Zach Gates
@ZachGates: Pensé en eso, pero no me di cuenta de que podía dejar de lado los corchetes. ¡Gracias!
El'endia Starman
4

GS2, 44 bytes

26 c8 2f 08 4d 08 40 64 45 2e 30 42 67 40 24 d0
75 d3 20 e1 35 09 cb 20 23 78 22 09 34 30 e0 32
08 86 84 30 85 30 92 58 09 34 10

Produce los números en un orden diferente, pero la descripción del problema no especifica, ¡así que voy por ello! Aquí está la salida para la entrada de 16.

1
12
125
125B
2
23
237
237F
3
34
349
4
45
45B
5
56
56D
6
67
67F
7
78
8
89
9
9A
A
AB
B
BC
C
CD
D
DE
E
EF
F
0

Aquí están los equivalentes mnemotécnicos para los bytes:

read-num dec save-a
range1
{
    itemize
    {
        dup 
        sum
        over length
        add

        swap right-cons

        dup last push-a le

            push-d eval
        block2 when
    }
    save-d eval
    init inits tail
} map

+ ' fold 

{
    ascii-digits
    uppercase-alphabet catenate
    lowercase-alphabet catenate
    select 
    show-line
} map

0
recursivo
fuente
Oh hombre, esto es asombroso. He estado tratando de aprender GS2 pero lo he pasado muy mal con eso: P
un espagueti el
3

CJam, 46 42 40 bytes

ri:R,{Q{+_A,s'[,_el^+f=oNo__,+:+_R<}g&}*

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

ri:R            e# Read an integer from STDIN and save it in R.
,               e# Push [0 ... R-1].
{               e# Fold; For each element but the first:
                e#   Push the element.
  Q             e#   Push an empty array (accumulator for base-R digits).
  {             e#   Do:
    +           e#     Concatenate the integer and the array on the stack.
    _           e#     Push a copy of the result.
    A,s'[,_el^+ e#     Push "0...0A...Za...z".
                e#     See: http://codegolf.stackexchange.com/a/54348
    f=          e#     Replace each base-R digit with the corresponding character.
    oNo         e#     Print the resulting string and a linefeed.
    _           e#     Push another copy of the accumulator.
    _,+         e#     Append its length to it.
    :+          e#     Add all digits (including the length).
    _R<         e#     Push a copy of the result and compare it with R.
  }g            e#   If the sum is less than R, it is a valid base-R digit,
                e#   the comparison pushes 1, and the loop is repeated.
  &             e#   Intersect the accumulator with an integer that is greater
                e#   or equal to R. This pushes an empty array.
}*              e#

Al final, quedan 0 conjuntos vacíos en la pila, por lo que el intérprete imprime 0.

Dennis
fuente
1

gawk, 111 bytes

{for(n=$0;n>c=++i;)for(j=0;n>$++j=c+=j;print"")for(c=k=0;k++<j;c+=$k)printf"%c",$k+($k>9?$k>35?61:55:48)}$0="0"

Para cada dígito inicial de 1a base-1, calcula los siguientes dígitos, y aunque estos son más bajos que la base, todavía tenemos un número confidente. Cálculo del siguiente dígito durante la impresión. Finalmente imprime 0.

Cabbie407
fuente