Seqindignot-Sequenz

27

Der Titel setzt sich aus 'Sequence Index Digit Not' zusammen.

Herausforderung:

Bei einer gegebenen ganzen Zahl nwird >= 0die n'te Zahl der folgenden Sequenz ausgegeben .
Hier sind die ersten 50 Elemente, über denen sich der (0-indizierte) Index befindet:

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

Wie funktioniert diese Sequenz?

Die Zahl am Index nmuss die erste sein, mit der keine Ziffern gemeinsam sind n, und ist für frühere Indizes noch nicht aufgetreten. Wenn wir also eine normale Sequenz wie diese betrachten, von 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

Wir definieren die n'ten Werte wie folgt:

  • 0: Die erste Ziffer ( 0) enthält dieselbe Ziffer, daher suchen wir nach der nächsten Ziffer ( 1), die nicht dieselbe Ziffer enthält. Also n=0Ausgänge 1.
  • 1: Die erste Ziffer ( 0) enthält nicht dieselbe Ziffer, wird also n=1ausgegeben 0.
  • 2: Wir sind bereits auf 0und gestoßen 1, und die nächste Ziffer ( 2) enthält dieselbe Ziffer. Deshalb suchen wir nach der nächsten Ziffer ( 3), die nicht dieselbe Ziffer enthält. Also n=2Ausgänge 3.
  • ...
  • 10: Wir sind bereits darauf gestoßen 0-9, also ist die nächste in der Reihe 10. Enthält 10-19die übereinstimmende Ziffer 1, 20enthält die übereinstimmende Ziffer 0, 21enthält die übereinstimmende Ziffer 1erneut, 22ist gültig, n=10gibt also aus 22.
  • etc.

Herausforderungsregeln:

  • Wenn Ihre Sprache 1-indiziert ist (oder Sie dies wünschen), können Sie die Sequenz um 3 2 5 4 7 ...(Überspringen des 1at n=0und des 0at n=1) beginnen.
  • Der kleinste Index, den Sie unterstützen sollten, ist 25,000. HINWEIS: Die Sequenz stoppt am Index 1,023,456,788, da der nächste Index in der Zeile alle 10 Ziffern enthält.
  • Sie können auch ein Array / eine Liste der gesamten Sequenz bis einschließlich Index ausgeben / zurückgeben, nwenn Sie dies möchten.

Allgemeine Regeln:

  • Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes.
    Lassen Sie sich von Code-Golf-Sprachen nicht davon abhalten, Antworten mit Nicht-Codegolf-Sprachen zu veröffentlichen. Versuchen Sie, für jede Programmiersprache eine möglichst kurze Antwort zu finden.
  • Für Ihre Antwort gelten Standardregeln. Daher dürfen Sie STDIN / STDOUT, Funktionen / Methoden mit den richtigen Parametern und vollständige Programme vom Rückgabetyp verwenden. Ihr Anruf.
  • Standardlücken sind verboten.
  • Fügen Sie nach Möglichkeit einen Link mit einem Test für Ihren Code hinzu.
  • Fügen Sie ggf. auch eine Erklärung hinzu.

Testfälle:

Diese Sequenz erzeugte tatsächlich Paare in Bezug auf Index und Ausgaben. Wenn nIndexausgaben o, oIndexausgaben n. Sie können also entweder links oder rechts eingeben, und die Ausgabe erfolgt auf der anderen Seite:

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

Hier ist ein Pastebin der ersten 25.001 Testfälle, wenn Sie andere ausprobieren möchten.

code-golf number sequence integer Kevin Cruijssen
quelle
Verwandt, aber kein Betrüger.
Kevin Cruijssen
3
Wie bei der damit verbundenen Herausforderung macht auch das Streudiagramm Spaß . :)
Martin Ender
@MartinEnder Als ich das Streudiagramm der damit verbundenen Herausforderung sah, dachte ich tatsächlich, dass dieses ähnlich sein würde. Es stellt sich zwar heraus, dass es ziemlich ähnlich ist, aber immer noch anders. :)
Kevin Cruijssen
Wie kommt es, dass eine so wichtige Sequenz nicht auf OEIS läuft?
Stewie Griffin
@ StewieGriffin Gute Frage. Eigentlich glaube ich, dass alle meine Sequence-Challenges (noch) nicht in OEIS waren, als ich sie gepostet habe. ;)
Kevin Cruijssen

Antworten:

3

Pyth , 18 Bytes

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

Probieren Sie es hier aus! oder Weitere Testfälle prüfen!

Beachten Sie, dass dies die gesamte Sequenz bis zum Index N zurückgibt, der Link jedoch nur die letzte Zahl zurückgibt, indem ein e(Ende) vorangestellt wird . Wenn Sie den von diesem Programm zurückgegebenen Rohwert sehen möchten, entfernen Sie ihn einfach .

Wie es funktioniert

u + Gf! |} TG @ `H`T0hQY - Volles Programm.

u ... hQY - Reduzieren Sie hQ (die Eingabe wird inkrementiert) von links nach rechts mit
                       Funktion ... (G, H), mit Startwert Y (die leere Liste).
                       G ist der aktuelle Wert und H ist der Iterationsindex.
   f 0 - Erste Ganzzahl ab 0, die die folgenden Anforderungen erfüllt:
      } TG - Erscheint in ...
     | @ `H`T - Oder sein (String-) Schnittpunkt mit dem aktuellen Index (H) ist
                        nicht leer.
    ! - Logisches NICHT (Boolesche Negation).
 + G - Hänge den oben erhaltenen Wert an den aktuellen Wert an (G).
                      Dies wird der angegebene Wert für die nächste Iteration.
                    - Drucken Sie implizit alle Zwischenergebnisse aus oder fügen Sie e zum Druck hinzu 
                      der Letzte.
Mr. Xcoder
quelle
6

Python 2 , 92 91 89 88 Bytes

a=()
i=0
exec"x=0\nwhile set(`x`)&set(`i`)or x in a:x+=1\na+=x,;i+=1;"*-~input()
print a

Probieren Sie es online!

Druckt eine Liste der ersten n+1Nummern

Anderer Ansatz, der viel schneller ist:

Python 2 , 96 Bytes

n=input()
r=range(9*n)
i=0
exec"x=0\nwhile set(`r[x]`)&set(`i`):x+=1\nprint r.pop(x),;i+=1;"*-~n

Probieren Sie es online!

TFeld
quelle
1
88 Bytes mit einem Tupel
Mr. Xcoder
3

Haskell, 80 69 Bytes

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

Probieren Sie es online!

Sehr langsam für groß 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]

Edit: @Laikoni hat 10 Bytes gespeichert. Vielen Dank!

nimi
quelle
Das direkte Berechnen des n-ten Terms anstelle des Indizierens in der Sequenz ist kürzer: Probieren Sie es online aus!
Laikoni
2

APL (Dyalog) , 39 Bytes

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

Verwendet ⎕IO←0 .

Probieren Sie es online!

Wie?

Rekursion.

0=⍵:1 - Raten Sie mal.

~⍺∊0∇¨⍳⍵ - linkes arg (akku) ist noch nicht in vorigen ergebnissen enthalten

∧⊃∧/≠/⍕¨⍺⍵- und die Stringdarstellung des Akkus nsind unterschiedlich

:⍺ - dann den Akku zurückgeben.

⍵∇⍨⍺+1 - Andernfalls Akkumulator inkrementieren und erneut verwenden.

Uriel
quelle
Wow .. Ich weiß, die Standardregel lautet "Beliebig viel Speicher und Zeit", aber Ihr Code hat n=10in TIO bereits eine Zeitüberschreitung.: S Das muss eine sehr leistungsintensive Operation sein, die Sie dort ausführen. Ist es die Rekursion, die dies verursacht, oder ist etwas anderes der Engpass?
Kevin Cruijssen
2
@ KevinCruijssen die zweite Bedingung im Grunde die Funktion auf den Bereich von 0..n-1 anwenden, und unter Berücksichtigung der gleichen gelten für jeden Aufruf, die ungefähr bei einem riesigen O (2 ^ n) kommen würde. Natürlich wäre es mit einem vernünftigeren Code niedriger, aber hier liegt der Engpass
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)

Probieren Sie es online!

Dies gibt alle Begriffe bis zum N- ten aus. Danke an Dennis für  -4  -5 Bytes!

Mr. Xcoder
quelle
2

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

Ich kann nicht glauben, dass ich die kganze Zeit nicht zurückgekehrt bin ...

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;}

Probieren Sie es online!

Roberto Graham
quelle
Hmm, das ist ein ganz anderer Ansatz als bei der Erstellung des Pastebins mit meinem Java-Programm. Und es scheint , können Sie Golf for(char f:(""+k).toCharArray())auf for(int f:(""+k).getBytes()), r.substring(-~r.trim().lastIndexOf(32));und zu r.substring(r.lastIndexOf(32)-1).
Kevin Cruijssen
Muss vor lastIndexOf gekürzt werden, da am Ende ein Leerzeichen steht
Roberto Graham
Ah, ich habe in der Tat einen Fehler gemacht. Ich wusste, dass die Zeichenfolge sowohl ein führendes als auch ein nachfolgendes Leerzeichen enthält, aber meine fälschlicherweise vorgeschlagene Änderung funktioniert nur für die ersten 10 einstelligen Zahlen. Meine schlechte
Kevin Cruijssen
2

Los , 217 205 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));}

Alternate Version (Programm statt ein Paket): Versuchen Sie es online!

Verbesserungen:

  • Leerzeichen nach Outer fordurch Mehrfachbelegung für entfernti,k
  • importieren "fmt";+ fmt.Printist kürzer als os.Stdout.WriteString(Holdover ab package mainwann os.Args benötigt wurde)
Riking
quelle
Schön, Ihre Antwort ist die erste, bei der nach 1 Minute keine Zeitüberschreitung eintritt, wenn ich den 25000Testfall ausprobiere . :) Also nicht nur eine gültige Lösung, sondern auch eine relativ gute Leistung. +1 von mir! (PS: In Ihrem TIO-Link ist es das Argument, das Sie verwenden, Eingaben können entfernt / nicht verwendet werden.)
Kevin Cruijssen
2

JavaScript (ES6), 103 88 81

Bearbeiten überarbeitet einschließlich viele cleveren Ideen von @Neil

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

Startpunkt

Grundidee: Eine Schleife von 0 bis n und eine innere Schleife, die Werte überprüft, die immer noch nicht verwendet werden

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
}

Aktuelle Version besser lesbar

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

Prüfung

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>
Erweitern Sie das Snippet

edc65
quelle
Würde ersetzen ~s.search(d)mit der s.match(d)Arbeit?
Neil
Ich denke , dass Sie ein anderes Byte speichern kann , indem 0auf j++, das Entfernen der ++von dem jes am vor und dann ausgehend jvon 0statt -1.
Neil
Ich glaube, ich konnte zu einer einzigen Schleife wechseln: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 eine einzelne Schleife wäre wunderbar
edc65
@ Neil die einzelne Schleife ist großartig, danke
edc65
2

Oktave , 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]

Probieren Sie es online!

Vielen Dank an Kevin Cruijssen und Dlosc für den Charaktervergleich beim Golfen.

Ungolfed

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]

Grundlegende Erklärung:

  • Äußere und innere Schleife, eine für den Index iund eine für den hinzuzufügenden Wertj

  • iInkrementieren Sie jedes Mal weiter, jwenn eine der folgenden Bedingungen erfüllt ist:

    1. Beliebige jwurde zuvor verwendet
    2. Dieser bekommt Spaß. Teilen Sie zuerst jeden numerischen Wert in einen Vektor von Ziffern (z. B. 10wird [1 0]) mit int2str. Vergleichen Sie dann die beiden Zahlen mit ismember(z. B. [1 0]und [2 1]würden zurückgeben [1 0]) und prüfen Sie nnz, ob Spalten übereinstimmen.

  • Wenn keine der oben genannten Bedingungen erfüllt ist, haben Sie die nächste Nummer! An odie Ausgabematrix anhängen

  • Drucken Sie Originalindizes mit Ausgabematrix
Alan
quelle
Schöne Antwort, +1 von mir. Und @DLosc scheint zu stimmen, es funktioniert auch ohne beides -'0'. Aber wenn es einen Randfall gibt, an den wir beide nicht gedacht haben, -48wäre dies eine kürzere Alternative. Auch beides sprintf('%d',...)kann sein int2str(...).
Kevin Cruijssen
1

Perl 5 , 60 Bytes

59 Byte Code + 1 für -p .

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

Probieren Sie es online! (Beinhaltet -lfür visuelle Zwecke und $-=0;zum Zurücksetzen jeder Iteration)

Dom Hastings
quelle
1

Pip , 30 Bytes

29 Byte Code, +1 für -pFlag.

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

Probieren Sie es online!

Gibt die gesamte Liste aus. Warnung: sehr ineffizient; das2231 Eingabefall läuft seit über 35 Minuten auf meinem Laptop und ist immer noch nicht fertig.

Erläuterung

                               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
quelle
1

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

-1 Byte dank 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

Durchläuft die Sequenz und generiert frühere Terme, um sie später zu vergleichen. Dann iteriert die Zahl als Zeichenfolge und sucht nach Übereinstimmungen.

Missbrauch des VB.NET-Eingabesystems. Ist beispielsweise jeine Zeichenfolge, aber das Hinzufügen einer wird für mich in eine Ganzzahl umgewandelt. Ganzzahlen werden in Boolesche Werte konvertiert, wobei 0sich Falseund der Rest in Booleschen Werten befindet True.

Probieren Sie es online!

Brian J
quelle
Ich habe noch nie in Visual Basic programmiert, aber es scheint, dass Sie den Raum If Not p.Contains(j)Thengenauso entfernen können, wie Sie es If j.Contains(c)Then g=0unten getan haben . Auch 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 Ifkann verkürzt werden durch Entfernen gund mit Exit Whiledirekt in der for-Schleife: 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 If, die werden werden 241 Bytes von den Blicken von ihm.
Kevin Cruijssen
@ KevinCruijssen Kann definitiv den Raum entfernen, um es zu machen Contains(c)Then, ich habe es einfach verpasst. Ich mag, was Sie denken, aber ich benutze gals Sentinel, um zu sehen, ob die Zeichenfolge die Nummer enthält oder nicht. Ihr Link gibt die falschen Antworten, aber ich werde sehen, ob ich einen Teil der inneren Logik nach Ihren Vorstellungen überarbeiten kann.
Brian J
Hoppla. Es schlägt in der Tat fehl. Jetzt wird nur noch die Eingabe ausgegeben. Mein Fehler. Sollte diese Kommentare nicht machen, wenn es Abend ist und ich von der Arbeit müde bin. ;)
Kevin Cruijssen
1

Gelee , 20 Bytes

Pyth schlägt Jelly. Gehen Sie Herr Xcoder!

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

Ein vollständiges Programm, das die Eingabe von STDIN und die Ausgabe im Listenformat mithilfe der Listendarstellung von Jelly * vornimmt. Verwendet die standardmäßige 0-basierte Indizierung.

* Listen mit einzelnen Elementen haben keine Umgebung [], also 0Ausgänge 1, während 1Ausgänge [1, 0]usw.

Probieren Sie es online!

Wie?

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
quelle