Secuencia Seqindignot

27

El título está compuesto por 'Índice de secuencia de dígitos no'.

Reto:

Dado un número entero nque es >= 0, genera el nnúmero 'th de la siguiente secuencia.
Aquí están los primeros 50 elementos, con su índice (indexado 0) encima:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
1 0 3 2 5 4 7 6 9 8 22 20 30 24 23 26 25 28 27 32 11 33 10 14 13 16 15 18 17 31 12 29 19 21 50 40 41 42 44 45 35 36 37 51 38 39 52 53 55 56 34

¿Cómo funciona esta secuencia?

El número en el índice ndebe ser el primero para que no tenga ningún dígito en común ny no haya aparecido aún para índices anteriores. Entonces, cuando miramos una secuencia normal como esta de 0-60:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

Definimos los n'th valores como este:

  • 0: El primer número ( 0) contiene el mismo dígito, por lo que buscamos el siguiente ( 1), que no contiene el mismo dígito. Así n=0salidas 1.
  • 1: El primer número ( 0) no contiene el mismo dígito, por lo que se n=1genera 0.
  • 2: Ya hemos encontrado 0y 1, y el siguiente dígito ( 2) contiene el mismo dígito, por lo que buscamos el siguiente ( 3), que no contiene el mismo dígito. Así n=2salidas 3.
  • ...
  • 10: Ya nos hemos encontrado 0-9, así que el siguiente en la línea es 10. 10-19contener el dígito correspondiente 1, 20contiene el dígito de juego 0, 21contiene el dígito de juego 1de nuevo, 22es válido, por lo que n=10las salidas 22.
  • etc.

Reglas de desafío:

  • Si su idioma está indexado en 1 (o lo elige), puede comenzar la secuencia en 3 2 5 4 7 ...(omitiendo el 1at n=0y el 0at n=1).
  • El índice mínimo más grande que debe admitir es 25,000. NOTA: La secuencia se detiene en el índice 1,023,456,788, porque el siguiente índice en línea contiene los 10 dígitos.
  • También puede generar / devolver una matriz / lista de toda la secuencia hasta el índice incluido, nsi lo desea.

Reglas generales:

  • Este es el código de golf , por lo que la respuesta más corta en bytes gana.
    No permita que los lenguajes de code-golf lo desanimen a publicar respuestas con lenguajes que no sean codegolf. Trate de encontrar una respuesta lo más breve posible para 'cualquier' lenguaje de programación.
  • Se aplican reglas estándar para su respuesta, por lo que puede usar STDIN / STDOUT, funciones / método con los parámetros adecuados y programas completos de tipo retorno. Tu llamada.
  • Las lagunas predeterminadas están prohibidas.
  • Si es posible, agregue un enlace con una prueba para su código.
  • Además, agregue una explicación si es necesario.

Casos de prueba:

Esta secuencia realmente creó pares con respecto al índice y las salidas. Si las nsalidas de oíndice, las osalidas de índice n. Entonces puede ingresar a la izquierda o la derecha, y la salida será el otro lado:

0      <->  1       (this test case is optional)
2      <->  3
10     <->  22
12     <->  30
34     <->  50
89     <->  100
111    <->  200
112    <->  300
199    <->  322
2231   <->  4456
9605   <->  11118
19235  <->  46000
23451  <->  60668
25000  <->  13674

Aquí hay un pastebin de los primeros 25.001 casos de prueba si desea probar otros.

code-golf number sequence integer Kevin Cruijssen
fuente
Relacionado, pero no un tonto.
Kevin Cruijssen
3
Al igual que con el desafío relacionado, el diagrama de dispersión es bastante divertido . :)
Martin Ender
@MartinEnder Cuando vi el diagrama de dispersión del desafío relacionado, de hecho pensé que este sería similar. Resulta que de hecho es bastante similar, pero aún diferente. :)
Kevin Cruijssen
¿Cómo es que una secuencia tan importante no está en OEIS?
Stewie Griffin
@StewieGriffin Buena pregunta. En realidad, creo que todos mis desafíos de secuencia hasta ahora no estaban en OEIS (todavía) cuando los publiqué. ;)
Kevin Cruijssen

Respuestas:

3

Pyth , 18 bytes

u+Gf!|}TG@`H`T0hQY

Pruébalo aquí! o ¡ Verifique más casos de prueba!

Tenga en cuenta que esto devuelve toda la secuencia hasta el índice N , pero el enlace devuelve solo el último número, anteponiendo un e(final). Si desea ver el valor bruto devuelto por este programa, simplemente elimínelo .

Cómo funciona

u + Gf! |} TG @ `H`T0hQY - Programa completo.

u ... hQY - Reduce hQ (la entrada incrementada) de izquierda a derecha, con el
                       función ... (G, H), con el valor inicial Y (la lista vacía).
                       G es el valor actual y H es el índice de iteración.
   f 0: primer entero a partir de 0, que satisface lo siguiente:
      } TG - Aparece en G ...
     El | @ `H`T - O su intersección (cadena) con el índice actual (H) es
                        no vacio
    ! - NO lógico (negación booleana).
 + G: añade el valor obtenido anteriormente al valor actual (G).
                      Esto se convierte en el valor dado para la próxima iteración.
                    - Imprima implícitamente todos los resultados intermedios, o agregue e para imprimir 
                      el último.
Sr. Xcoder
fuente
3

Haskell, 80 69 bytes

f n=[x|x<-[0..],all(`notElem`show n)$show x,all(/=x)$f<$>[0..n-1]]!!0

Pruébalo en línea!

Muy lento para grandes n.

f n=
    [x|x<-[0..]     ] !!0          -- pick the first of all 'x' from [0..]
                                   -- where
      all(`notElem`show n)$show x  -- no digit of 'n' appears in 'x', and
      all(/=x)                     -- 'x' is not seen before, i.e. not in the list
               f<$>[0..n-1]        -- 'f' mapped to [0..n-1]

Editar: @Laikoni guardó 10 bytes. ¡Gracias!

nimi
fuente
Calcular el enésimo término directamente en lugar de indexarlo en la secuencia es más corto: ¡ Pruébelo en línea!
Laikoni
2

APL (Dyalog) , 39 bytes

0∘{0=⍵:1⋄(~⍺∊0∇¨⍳⍵)∧⊃∧/≠/⍕¨⍺⍵:⍺⋄⍵∇⍨⍺+1}

Usos ⎕IO←0.

Pruébalo en línea!

¿Cómo?

Recursividad

0=⍵:1 - Adivina.

~⍺∊0∇¨⍳⍵ - left arg (acumulador) no está ya en resultados anteriores

∧⊃∧/≠/⍕¨⍺⍵- y la representación de cadena del acumulador y nson diferentes

:⍺ - luego devuelva el acumulador.

⍵∇⍨⍺+1 - de lo contrario, incremente el acumulador y recurse.

Uriel
fuente
Wow ... Sé que la regla predeterminada es "dada cualquier cantidad de memoria y tiempo", pero su código ya se agota n=10en TIO ...: S Esa debe ser una operación de alto rendimiento que está haciendo allí. ¿Es la recursión lo que causa esto, o es algo más el cuello de botella?
Kevin Cruijssen
2
@KevinCruijssen, la segunda condición básicamente aplica la función en el rango de 0..n-1, y teniendo en cuenta la misma aplicación para cada llamada, eso vendría aproximadamente en un gran O (2 ^ n). por supuesto, sería más bajo con un código más razonable, pero ahí es donde se encuentra el cuello de botella
Uriel
2

Python 3 , 92 bytes

o=1,
for i in range(int(input())):
 x=0
 while{*str(x),x}&{*str(~i),*o}:x+=1
 o+=x,
print(o)

Pruébalo en línea!

Todo esto impresiones de los plazos de hasta el N º uno. Gracias a Dennis para  -4  -5 bytes!

Sr. Xcoder
fuente
2

Java (OpenJDK 8) , 218 217 213 210 202 200 172 171 170 168 167 bytes

No puedo creer que no haya regresado ktodo este tiempo ...

i->{int j=-1,k=0,y=1;for(String r=" ",e=r;j++<i;r+=~-k+e,y=1)for(k=0;y>0;k++)for(int f:(k+(y=0)+"").getBytes())y+=(e+j).indexOf(f)<0&!r.contains(e+k+e)?0:1;return~-k;}

Pruébalo en línea!

Roberto Graham
fuente
Hmm, ese es un enfoque bastante diferente al que estaba usando cuando hice el pastebin con mi programa Java. Y parece que se puede jugar golf for(char f:(""+k).toCharArray())a for(int f:(""+k).getBytes()), r.substring(-~r.trim().lastIndexOf(32));y a r.substring(r.lastIndexOf(32)-1).
Kevin Cruijssen
Debe recortarse antes de lastIndexOf ya que hay un espacio al final
Roberto Graham
Ah, de hecho cometí un error ... Sabía que la Cadena contenía tanto un espacio inicial como uno posterior, pero mi cambio sugerido incorrectamente solo funciona para los primeros 10 números de un solo dígito ... Lo malo
Kevin Cruijssen
2

Ir , 217205 bytes

package g;import("fmt";"strconv";"strings");var(
d=make(map[int]int)
a=strconv.Itoa)
func G(L int){k,i:=0,0;for;i<=L;i++{s:=a(i);k=0;for d[k]>0||strings.ContainsAny(a(k),s){k++;}
d[k]=1;}
fmt.Print(a(k));}

Versión alternativa (programa en lugar de paquete): ¡ Pruébelo en línea!

Mejoras:

  • espacio eliminado después del exterior formediante el uso de asignación múltiple parai,k
  • importar "fmt";+ fmt.Printes más corto que os.Stdout.WriteString(remanente de package maincuando se necesitaban Args os)
Riking
fuente
Bien, tu respuesta es la primera que no se agota después de 1 minuto cuando pruebo el 25000caso de prueba. :) Así que no solo es una solución válida, sino también con un rendimiento relativamente bueno. +1 de mi parte! (PD: en su enlace TIO es el argumento que usa, la entrada se puede eliminar / no se usa.)
Kevin Cruijssen
2

JavaScript (ES6), 103 88 81

Editar Revisado incluyendo muchas ideas inteligentes por @Neil

n=>eval("for(r=[j=i=0];i<=n;)j=r[j]||(i+'').match(`[${j}]`)?j+1:!(r[k=j]=++i);k")

Punto de partida

Idea básica: un bucle de 0 a n, y los valores de comprobación de un bucle interno aún no se utilizan

n=>{
  var r=[]
  for(i=0;i<=n;i++)
  {
    s=new Set(i+'')
    for(j=-1;s;)
    {
      if (!r[++j] && ![...j+''].some(d=>s.has(d)))
      {
        r[j]=1
        console.log(i,j)
        s=0
      }
    }
  }
  return j
}

Versión actual más legible

n=>{
  for(r = [j=i=0]; i <= n; )
    if (r[j] || (i+'').match(`[${j}]`))
      ++j
    else
      r [k=j] = ++i,
      j = 0;
  return k
}

Prueba

var f=
n=>eval("for(r=[j=i=0];i<=n;)j=r[j]||(i+'').match(`[${j}]`)?j+1:!(r[k=j]=++i);k")

update=_=>{
  var i=+I.value
  if (i < 1e4 || confirm("Really?")) {
    O.textContent=i + ' -> ...'
    setTimeout(_=>O.textContent=i + ' -> ' + f(i), 100)
  }
}  

update()
<input id=I value=100 type=number max=1023456788>
<button onclick='update()'>Go</button>
(slow when input > 1000)
<pre id=O></pre>
Expandir fragmento

edc65
fuente
¿Reemplazar ~s.search(d)con s.match(d)trabajo?
Neil
Creo que puede guardar otro byte cambiando 0a j++, quitando el ++de jantes y luego comenzando jdesde en 0lugar de -1.
Neil
Creo que pude cambiar a un solo ciclo:n=>eval("for(r=[j=i='0'];i<=n;)r[j]|[...''+j].some(d=>i.match(d))?j++:(i=++i+'',r[k=j]=1,j=0);k")
Neil
@Neil un solo bucle sería maravilloso
edc65
@Neil the single loop es genial, gracias
edc65
2

Octava , 114 bytes

N=input("");o=[1];for i=1:N;j=0;while(any(o==j)||nnz(ismember(int2str(i),int2str(j))));j++;end;o=[o,j];end;[0:N;o]

Pruébalo en línea!

Gracias a Kevin Cruijssen y Dlosc por la comparación de personajes de golf.

Sin golf

N=input("");o=[1];

for i=1:N;
    j=0;
    while(any(o==j)||nnz(ismember(int2str(i),int2str(j))));
        j++;
    end;
    o=[o,j];
end;
[0:N;o]

Explicación básica:

  • Bucle externo y bucle interno, uno para índice iy otro para agregar valorj

  • Para cada uno i, continúe aumentando jsi se cumple cualquiera de los siguientes:

    1. Alguno jha sido usado antes
    2. Este se pone divertido. Primero, divida cada valor numérico en un vector de dígitos (por ejemplo, se 10convierte [1 0]) usando int2str. Luego, compare los dos números usando ismember(por ejemplo, [1 0]y [2 1]volvería [1 0]) y luego nnzpara ver si alguna columna coincidía.

  • Si no se cumple ninguno de los anteriores, ¡tiene el siguiente número! Anexar a o, la matriz de salida

  • Imprima índices originales con matriz de salida
Alan
fuente
Buena respuesta, +1 de mi parte. Y parece que @DLosc tiene razón, funciona incluso sin ambos -'0'. Pero si hay algún caso marginal en el que ambos no hayamos pensado, -48sería una alternativa más corta. Además, ambos sprintf('%d',...)pueden ser int2str(...).
Kevin Cruijssen
1

Perl 5 , 60 bytes

Código de 59 bytes + 1 para -p.

$_="@{[0..($;=++$_)*9]}";$_=eval's/\b[^ $-]+ //;$-++;$&;'x$

Pruébalo en línea! (Incluye -lpara fines visuales y $-=0;para restablecer cada iteración)

Dom Hastings
fuente
1

Pip , 30 bytes

29 bytes de código, +1 para -pbandera.

Fn,a+1{Y0WyNl|_NyMSn++ylPBy}l

Pruébalo en línea!

Emite la lista completa. Advertencia: altamente ineficiente; el 2231caso de entrada ha estado funcionando durante más de 35 minutos en mi computadora portátil y aún no ha terminado.

Explicación

                               a is cmdline arg, l is [] (implicit)
Fn,a+1{                    }   For each n in range(a+1):
       Y0                       Yank 0 into y
         W                      While...
          yNl|                  y is in l, or...
              _Ny               lambda function: arg is in y
                 MSn            mapped to digits of n and result list summed
                                (i.e., any digit of n is in y):
                    ++y          Increment y
                       lPBy     Once we have a y that meets the criteria, push it to
                                the back of l
                            l  Output l (formatted with -p flag)
DLosc
fuente
1

Visual Basic .NET (.NET 4.5) , 260 259 bytes

-1 byte gracias a Kevin Cruijssen

Function A(n)
Dim p=New System.Collections.Generic.List(Of Long),j="0",g=0
For i=0To n
j=0
While 1
If Not p.Contains(j)Then
g=1
For Each c In i.ToString
If j.Contains(c)Then g=0
Next
If g Then Exit While
End If
j+=1
End While
p.Add(j)
Next
A=p(n)
End Function

Recorre en bucle, generando términos anteriores en la secuencia para luego compararlos. Luego itera el número como una cadena en busca de coincidencias.

Abusa del sistema de mecanografía de VB.NET. Por ejemplo, jes una cadena, pero agregar uno se convierte en un entero para mí. Los enteros se convierten en booleanos donde 0está Falsey el resto lo están True.

Pruébalo en línea!

Brian J
fuente
Nunca programé en Visual Basic, pero parece que puedes eliminar el espacio al If Not p.Contains(j)Thenmismo tiempo que hiciste a If j.Contains(c)Then g=0continuación. Además, If Not p.Contains(j)Then \n g=1 \n For Each c In i.ToString \n If j.Contains(c)Then g=0 \n Next \n If g Then Exit While \n End Ifpuede acortarse eliminando gy utilizando Exit Whiledirectamente en el bucle for: If Not p.Contains(j)Then \n For Each c In i.ToString \n If j.Contains(c)Then Exit While \n Next \n End Ifque, según parece , se convertirá en 241 bytes .
Kevin Cruijssen
@KevinCruijssen Definitivamente puede eliminar el espacio para hacerlo Contains(c)Then, simplemente lo perdí. Me gusta lo que estás pensando, pero lo estoy usando gcomo centinela para ver si la cadena contiene el número o no. Su enlace da las respuestas incorrectas, pero veré si puedo reelaborar parte de la lógica interna a lo largo de lo que está pensando.
Brian J
Ah, vaya ... De hecho, falla ... Ahora solo está emitiendo la entrada. Mi error. No debería hacer estos comentarios cuando es de noche y estoy cansado del trabajo. ;)
Kevin Cruijssen
1

Jalea , 20 bytes

Pyth le gana a Jelly. ¡Vamos, señor Xcoder!

Df⁹LD¤ȯeṆ
0ç1#ɓ;
1Ç¡

Un programa completo que toma la entrada de STDIN y sale en la opción de formato de lista usando la representación de lista de Jelly *. Utiliza la indexación basada en 0 estándar.

* Listas solo elemento no han rodea [], por lo que 0las salidas 1, mientras que 1las salidas [1, 0], etc.

Pruébalo en línea!

¿Cómo?

Df⁹LD¤ȯeṆ - Link 1, can append n to current? n, number; current, list
D         - convert n to decimal list
     ¤    - nilad followed by link(s) as a nilad:
  ⁹       -   chain's right argument, current
   L      -   length
    D     -   convert to a decimal list
 f        - filter discard from left if not in right
       e  - n exists in current?
      ȯ   - left logical OR right (empty lists are falsey)
        Ṇ - logical NOT

0ç1#ɓ; - Link 2, append next number: current, List
   #   - n find (count up finding first n matches):
  1    - ...finding: 1 match
0      - ...stating at: n=0
 ç     - ...doing: the last link as a dyad (left=n, right=current)
    ɓ  - new swapped-arg-dyadic chain (left = current, right = list of the found n)
     ; - concatenate

1Ç¡ - Main link: no arguments
1   - initialise the return value to 1
  ¡ - repeat input() times:
 Ç  -   last link (2) as a monad
    - implicit print
Jonathan Allan
fuente