Urutan seqindignot

27

Judul dibuat, dari 'Sequence Index Digit Not'.

Tantangan:

Mengingat integer nyang >= 0, output n'th jumlah urutan berikut.
Inilah 50 item pertama, dengan indeks (0-indeks) di atasnya:

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

Bagaimana cara kerja urutan ini?

Angka pada indeks nharus menjadi yang pertama agar tidak memiliki angka yang sama n, dan belum terjadi untuk indeks sebelumnya. Jadi ketika kita melihat urutan normal seperti ini dari 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

Kami mendefinisikan nilai nth seperti ini:

  • 0: Angka pertama ( 0) berisi digit yang sama, jadi kami mencari yang berikutnya ( 1), yang tidak mengandung digit yang sama. Jadi n=0keluaran 1.
  • 1: Angka pertama ( 0) tidak mengandung digit yang sama, jadi n=1hasilnya 0.
  • 2: Kami telah menemukan 0dan 1, dan digit berikutnya ( 2) berisi digit yang sama, jadi kami mencari berikutnya ( 3), yang tidak mengandung digit yang sama. Jadi n=2keluaran 3.
  • ...
  • 10: Kami sudah menemukan 0-9, jadi baris berikutnya adalah 10. 10-19berisi digit yang cocok 1, 20berisi digit yang cocok 0, 21berisi digit yang cocok 1lagi, 22valid, jadi n=10hasilnya 22.
  • dll.

Aturan tantangan:

  • Jika bahasa Anda diindeks 1 (atau Anda pilih), Anda diizinkan untuk memulai urutan di 3 2 5 4 7 ...(melewatkan 1at n=0dan 0at n=1).
  • Indeks minimum minimum yang harus Anda dukung adalah 25,000. CATATAN: Urutan berhenti pada indeks 1,023,456,788, karena indeks berikutnya dalam baris berisi semua 10 digit.
  • Anda juga diizinkan untuk menampilkan / mengembalikan array / daftar seluruh urutan hingga dan termasuk indeks njika Anda mau.

Aturan umum:

  • Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang.
    Jangan biarkan bahasa kode-golf mencegah Anda memposting jawaban dengan bahasa non-codegolf. Cobalah untuk memberikan jawaban sesingkat mungkin untuk bahasa pemrograman 'apa saja'.
  • Aturan standar berlaku untuk jawaban Anda, jadi Anda diperbolehkan menggunakan STDIN / STDOUT, fungsi / metode dengan parameter yang tepat dan tipe pengembalian, program lengkap. Panggilanmu.
  • Celah default tidak diperbolehkan.
  • Jika memungkinkan, silakan tambahkan tautan dengan tes untuk kode Anda.
  • Juga, silakan tambahkan penjelasan jika perlu.

Kasus uji:

Urutan ini sebenarnya membuat pasangan mengenai indeks dan output. Jika indeks nmenghasilkan o, indeks omenghasilkan n. Jadi, Anda dapat memasukkan kiri atau kanan, dan hasilnya adalah sisi lain:

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

Berikut adalah pastebin dari 25.001 kasus uji pertama jika Anda ingin mencoba yang lain.

code-golf number sequence integer Kevin Cruijssen
sumber
Terkait, tetapi bukan korban penipuan.
Kevin Cruijssen
3
Seperti halnya tantangan terkait, sebar cukup menyenangkan . :)
Martin Ender
@ MartinEnder Ketika saya melihat scatterplot dari tantangan terkait, saya pikir ini akan serupa. Ternyata memang agak mirip, tapi masih beda. :)
Kevin Cruijssen
Kenapa urutan yang begitu penting tidak ada pada OEIS?
Stewie Griffin
@StewieGriffin Pertanyaan bagus. Sebenarnya, saya pikir semua tantangan urutan saya sejauh ini tidak di OEIS (belum) ketika saya mempostingnya. ;)
Kevin Cruijssen

Jawaban:

3

Pyth , 18 byte

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

Coba di sini! atau Periksa lebih banyak test case!

Perhatikan bahwa ini mengembalikan seluruh urutan hingga indeks N , tetapi tautan hanya mengembalikan nomor terakhir, dengan menambahkan e(akhir). Jika Anda ingin melihat nilai mentah yang dikembalikan oleh program ini, hapus saja .

Bagaimana itu bekerja

u + Gf! |} TG @ `H`T0hQY - Program lengkap.

u ... hQY - Mengurangi hQ (input bertambah) dari kiri ke kanan, dengan
                       berfungsi ... (G, H), dengan nilai awal Y (daftar kosong).
                       G adalah nilai saat ini dan H adalah indeks iterasi.
   f 0 - Bilangan bulat pertama mulai dari 0, yang memenuhi yang berikut:
      } TG - Muncul di G ...
     | @ `H`T - Atau persimpangan (string) dengan indeks saat ini (H) adalah
                        tidak kosong.
    ! - TIDAK logis (negasi boolean).
 + G - Tambahkan nilai yang diperoleh di atas ke nilai saat ini (G).
                      Ini menjadi nilai yang diberikan untuk iterasi berikutnya.
                    - Secara implisit mencetak semua hasil antara, atau menambahkan e untuk dicetak 
                      yang terakhir.
Tuan Xcoder
sumber
6

Python 2 , 92 91 89 88 byte

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

Cobalah online!

Mencetak daftar n+1angka pertama

Pendekatan berbeda, yang jauh lebih cepat:

Python 2 , 96 byte

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

Cobalah online!

TFeld
sumber
1
88 byte menggunakan tuple
Tn. Xcoder
3

Haskell, 80 69 byte

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

Cobalah online!

Sangat lambat untuk ukuran besar 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]

Sunting: @Laikoni menyimpan 10 byte. Terima kasih!

nimi
sumber
Menghitung istilah ke-n secara langsung alih-alih mengindeks ke dalam urutan lebih pendek: Coba online!
Laikoni
2

APL (Dyalog) , 39 byte

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

Penggunaan ⎕IO←0.

Cobalah online!

Bagaimana?

Rekursi.

0=⍵:1 - coba tebak.

~⍺∊0∇¨⍳⍵ - arg kiri (akumulator) belum ada di hasil sebelumnya

∧⊃∧/≠/⍕¨⍺⍵ - dan representasi string dari akumulator dan n berbeda

:⍺ - lalu kembalikan akumulator.

⍵∇⍨⍺+1 - jika tidak, akumulator tambahan dan berulang.

Uriel
sumber
Wow .. Saya tahu aturan default adalah "mengingat jumlah memori dan waktu", tetapi kode Anda sudah habis untuk n=10TIO ..: S Itu pasti operasi yang sangat berat yang Anda lakukan di sana. Apakah rekursi yang menyebabkan ini, atau ada hal lain yang menjadi hambatan?
Kevin Cruijssen
2
@KevinCruijssen kondisi kedua pada dasarnya menerapkan fungsi pada kisaran 0..n-1, dan mempertimbangkan penerapan yang sama untuk setiap panggilan, yang kira-kira akan muncul pada O besar (2 ^ n). tentu saja itu akan lebih rendah dengan kode yang lebih masuk akal, tapi di situlah letak kemacetan
Uriel
2

Python 3 , 92 byte

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

Cobalah online!

Ini mencetak semua persyaratan hingga yang ke- N . Terima kasih kepada Dennis untuk  -4  -5 byte!

Tuan Xcoder
sumber
2

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

Saya tidak percaya bahwa saya tidak hanya kembali kselama ini ...

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

Cobalah online!

Roberto Graham
sumber
Hmm, itu pendekatan yang sangat berbeda dari yang saya gunakan ketika saya membuat pastebin dengan program Java saya. Dan tampaknya Anda dapat golf for(char f:(""+k).toCharArray())untuk for(int f:(""+k).getBytes()), r.substring(-~r.trim().lastIndexOf(32));dan untuk r.substring(r.lastIndexOf(32)-1).
Kevin Cruijssen
Harus dipangkas sebelum lastIndexOf karena ada ruang pada akhirnya
Roberto Graham
Ah, saya memang melakukan kesalahan .. Saya tahu String berisi ruang terdepan dan tambahan, tetapi perubahan saya yang salah menyarankan hanya berfungsi untuk 10 angka pertama. Angka buruk saya
Kevin Cruijssen
2

Pergi , 217 205 byte

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 alternatif (program alih-alih sebuah paket): Cobalah secara online!

Perbaikan:

  • ruang dihapus setelah luar fordengan menggunakan beberapa penugasan untuki,k
  • mengimpor "fmt";+ fmt.Printlebih pendek dari os.Stdout.WriteString(peninggalan sejak package mainos.Args diperlukan)
Bersepeda
sumber
Bagus, jawaban Anda adalah yang pertama yang tidak habis setelah 1 menit ketika saya mencoba 25000test case. :) Jadi bukan hanya solusi yang valid, tetapi dengan kinerja yang relatif baik juga. +1 dari saya! (PS: Dalam TIO-link Anda, itulah argumen yang Anda gunakan, input dapat dihapus / tidak digunakan.)
Kevin Cruijssen
2

JavaScript (ES6), 103 88 81

Sunting Direvisi termasuk banyak ide pintar oleh @Neil

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

Titik pangkal

Ide dasar: loop dari 0 ke n, dan nilai-nilai pengecekan loop dalam masih belum digunakan

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 saat ini lebih mudah dibaca

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

Uji

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>
Luaskan cuplikan

edc65
sumber
Apakah penggantian ~s.search(d)dengan s.match(d)pekerjaan?
Neil
Saya pikir Anda dapat menyimpan byte lain dengan mengubah 0ke j++, menghapus ++dari jitu sebelum dan kemudian mulai jdari 0bukan -1.
Neil
Saya pikir saya bisa beralih ke satu loop: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 satu loop akan menjadi luar biasa
edc65
@Neil loop tunggal hebat, terima kasih
edc65
2

Oktaf , 114 byte

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]

Cobalah online!

Terima kasih kepada Kevin Cruijssen dan Dlosc untuk golf perbandingan karakter.

Tidak disatukan

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]

Penjelasan dasar:

  • Loop luar dan loop dalam, satu untuk indeks i, dan satu lagi untuk nilai yang ditambahkanj

  • Untuk masing-masing i, lanjutkan kenaikan jjika salah satu dari yang berikut dipenuhi:

    1. Apa saja jsudah pernah digunakan sebelumnya
    2. Yang ini jadi menyenangkan. Pertama, bagi setiap nilai numerik menjadi vektor digit (misalnya, 10menjadi [1 0]) menggunakan int2str. Kemudian, bandingkan dua angka menggunakan ismember(misalnya, [1 0]dan [2 1]akan kembali [1 0]) dan kemudian nnzuntuk melihat apakah ada kolom yang cocok.

  • Jika tidak ada yang di atas terpenuhi, Anda memiliki nomor berikutnya! Tambahkan ke o, matriks keluaran

  • Cetak indeks asli dengan matriks keluaran
Alan
sumber
Jawaban yang bagus, +1 dari saya. Dan tampaknya @DLosc benar, ia berfungsi bahkan tanpa keduanya -'0'. Tetapi jika ada beberapa kasus tepi yang kami berdua belum pikirkan, -48akan menjadi alternatif yang lebih pendek. Juga, keduanya sprintf('%d',...)bisa int2str(...).
Kevin Cruijssen
1

Perl 5 , 60 byte

59 byte kode +1 untuk -p.

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

Cobalah online! (Termasuk -luntuk tujuan visual dan $-=0;untuk mengatur ulang setiap iterasi)

Dom Hastings
sumber
1

Pip , 30 byte

29 byte kode, +1 untuk -pbendera.

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

Cobalah online!

Keluarkan seluruh daftar. Peringatan: sangat tidak efisien; itu2231 kasus masukan baru berjalan 35 + menit di laptop saya dan masih belum selesai.

Penjelasan

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

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

-1 byte terima kasih kepada 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

Loop melalui, menghasilkan istilah sebelumnya dalam urutan untuk kemudian membandingkan nanti. Kemudian iterasi angka sebagai string yang mencari kecocokan.

Menyalahgunakan sistem pengetikan VB.NET. Misalnya, jadalah string, tetapi menambahkan satu yang dikonversi ke integer untuk saya. Integer dikonversi ke Boolean di mana 0ada Falsedan sisanyaTrue .

Cobalah online!

Brian J
sumber
Saya tidak pernah diprogram dalam Visual Basic, tetapi sepertinya Anda dapat menghapus ruang di If Not p.Contains(j)Then sama seperti yang Anda lakukan di If j.Contains(c)Then g=0bawah. Juga, 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 Ifdapat dipersingkat dengan menghapus gdan menggunakan Exit Whilelangsung di for-loop:, 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 Ifyang akan menjadi 241 byte dengan tampilannya.
Kevin Cruijssen
@KevinCruijssen Pasti bisa menghilangkan ruang untuk membuatnya Contains(c)Then, saya baru saja melewatkannya. Saya suka apa yang Anda pikirkan, tetapi saya menggunakan gsebagai penjaga untuk melihat apakah string berisi nomor atau tidak. Tautan Anda memberikan jawaban yang salah, tetapi saya akan melihat apakah saya dapat mengerjakan ulang beberapa logika batin sepanjang apa yang Anda pikirkan.
Brian J
Ah oops .. Memang gagal .. Sekarang hanya mengeluarkan input. Salahku. Seharusnya tidak membuat komentar ini ketika malam hari dan saya lelah dari pekerjaan. ;)
Kevin Cruijssen
1

Jelly , 20 byte

Pyth mengalahkan Jelly. Tn. Tn. Xcoder!

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

Program lengkap yang mengambil input dari STDIN dan mengeluarkan dalam opsi format daftar menggunakan representasi daftar Jelly *. Menggunakan pengindeksan berbasis 0 standar.

* daftar elemen tunggal tidak memiliki sekitarnya [], jadi 0output 1, sedangkan 1output [1, 0]dll

Cobalah online!

Bagaimana?

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
sumber