Angka senapan

45

The nomor Shotgun adalah urutan dengan definisi agak sederhana tapi beberapa struktur menarik. Mulai dengan bilangan asli:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

Sekarang ambil semua angka pada indeks yang dapat dibagi 2 , kelompokkan menjadi pasangan, dan tukar angka dalam setiap pasangan:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
   ^     ^     ^     ^      ^       ^       ^  
    <--->       <--->        <----->         <----
1, 4, 3, 2, 5, 8, 7, 6, 9, 12, 11, 10, 13, 16, ...

Sekarang lakukan hal yang sama dengan indeks yang dapat dibagi 3 :

1, 4, 3, 2, 5, 8, 7, 6, 9, 12, 11, 10, 13, 16, ...
      ^        ^        ^           ^          
       <------>          <--------->           
1, 4, 8, 2, 5, 3, 7, 6, 10, 12, 11, 9, 13, 16, ...

Dan kemudian untuk 4 , 5 , 6 , dan seterusnya:

1, 4, 8, 2, 5, 3, 7, 6, 10, 12, 11, 9, 13, 16, ...
1, 4, 8, 6, 5, 3, 7, 2, 10, 12, 11, 14, 13, 16, ...
1, 4, 8, 6, 12, 3, 7, 2, 10, 5, 11, 14, 13, 16, ...
1, 4, 8, 6, 12, 14, 7, 2, 10, 5, 11, 3, 13, 16, ...
...

Setelah k langkah tersebut, angka k +1 pertama akan diperbaiki. Jadi kita dapat mendefinisikan urutan tak terhingga dari angka-angka Shotgun sebagai batas membiarkan k pergi hingga tak terbatas. 66 angka pertama adalah:

1, 4, 8, 6, 12, 14, 16, 9, 18, 20, 24, 26, 28, 22, 39, 15, 36, 35, 40, 38, 57, 34, 48, 49, 51, 44,
46, 33, 60, 77, 64, 32, 75, 56, 81, 68, 76, 58, 100, 55, 84, 111, 88, 62, 125, 70, 96, 91, 98, 95,
134, 72, 108, 82, 141, 80, 140, 92, 120, 156, 124, 94, 121, 52, 152, 145, ...

Fakta menyenangkan: Meskipun diperoleh dengan hanya mengubah bilangan asli, urutan ini tidak mengandung bilangan prima.

Tantangan

Diberikan bilangan bulat n > 0, cari nnomor Shotgun. Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengembalikan output atau mencetaknya ke STDOUT (atau alternatif terdekat).

Ini adalah kode golf, jadi pengiriman terpendek (dalam byte) menang.

Papan peringkat

Ini mendapatkan lebih banyak jawaban daripada yang saya kira, juga beberapa orang bersaing dalam bahasa yang sama. Jadi di sini adalah Cuplikan Stack untuk menghasilkan leaderboard reguler dan tinjauan pemenang berdasarkan bahasa.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

# Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Misalnya:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Tampilkan cuplikan kode

code-golf number sequence permutations Martin Ender
sumber
1
Fakta menyenangkan itu gila, algoritma ini mengocok semua bilangan prima sampai akhir? Atau adakah bilangan alami lain yang juga tidak akan terjadi?
Devon Parsons
1
@DevonParsons Ya itu mengocok semua bilangan prima "sampai akhir". Tapi saya pikir ada nomor lain yang hilang juga. Sepertinya 10, 21, 25dan 30tidak muncul baik, misalnya.
Martin Ender
3
Ini terdengar seperti pertanyaan Project Euler. Saya tidak berpikir itu ... tapi mungkin seharusnya begitu.
Corey Ogburn
9
Secara umum, pada kiterasi th, kelemen th dalam array akan dipindahkan ke 2kposisi th, dan tidak akan disentuh lagi sampai 2kiterasi th, di mana saat itu akan dipindahkan ke 4kposisi th, ad infinitum. Perdana tidak dialihkan sampai gilirannya tiba, sehingga untuk berbicara, sehingga semua bilangan prima bisa dikocok ke depan. Tetapi kita dapat dengan mudah membuat daftar korban yang tidak bersalah hanya dengan mencetak elemen pertama yang akan ditransfer pada iterasi 2 dan setiap iterasi aneh. Daftarnya berbunyi: 2, 3, 5, 7, 10, 11, 13, 21, 17, 19, 30, 23, 27, 25, 29, 31, 45, 42, 37, 54, 54, 41, 43, 65, ...
Théophile
3
@ Sherlock9 Selesai! Jika disetujui, itu akan menjadi https://oeis.org/A266679 . Selamat Tahun Baru!
Théophile

Jawaban:

5

Pyth, 19 22

u-G*H^_!%GH/GHrhQ2Q

Implementasi jawaban golfscript @ PeterTaylor yang cukup naif .

Cobalah online di sini

Ini menggunakan trik yang sama untuk mengubah loop sementara menjadi lipatan seperti program Pyth lainnya di bawah ini.

u+G**H!%GHty%/GH2rhQ2Q

Salinan naif dari algoritma @ Sp3000 yang diterjemahkan ke Pyth.

Anda dapat mencobanya online di sini

Kurangi (nama python untuk lipatan) untuk meniru loop sementara. Ini menyebutkan tentang range(input, 2)yang di Pyth berhasil range(2, input)[::-1]. Golf yang berhubungan dengan Pyth lainnya melibatkan penggunaan notalih-alih <2dan menggunakan ymode tersembunyi untuk menggandakan nilai argumen numerik.

FryAmTheEggman
sumber
21

> <>, 52 45 byte

Halaman Esolang untuk> <>

i:&&:&1-?vn;
2*1-*+20.>:&:&%1(&:&*{:}&:1-&,2%

Ada banyak elemen penyalinan dan pemindahan, berkat beberapa modulo dan multiplikasi yang dibutuhkan. Logikanya persis sama dengan solusi Python saya .

Mengambil input melalui titik kode dari STDIN, mis "!" = 33 -> 75.

Sp3000
sumber
10
Dan Anda mendapatkan penghargaan untuk format input paling canggung yang pernah ada: P
Caridorc
Pokoknya +1, jangan khawatir :)
Caridorc
@ Sp3000 IMO seharusnya hanya dihitung sebagai satu
SuperJedi224
@ SuperJedi224 Sebenarnya, menurut meta ini rupanya -vdiperhitungkan sebagai tiga: /
Sp3000
17

Python 2, 58 byte

i=n=input()
while~-i:n+=(n%i<1)*i*(n/i%2*2-1);i-=1
print n

Seperti sebagian besar jawaban lainnya, idenya adalah untuk bekerja mundur.

Mari kita panggil langkah k+1langkah i, sehingga pada langkah isemua kelipatan iditukar. Kami membutuhkan dua pengamatan sederhana:

  • Posisi ndalam array hanya ditukar pada langkah ijika ndapat dibagi dengan i,
  • Untuk mengetahui apakah Anda nomor lebih rendah atau lebih tinggi dalam swap, lihat n/i mod 2. Jika ini adalah 1 Anda adalah angka yang lebih rendah (dan akan bertukar), jika tidak, Anda adalah angka yang lebih tinggi (dan akan bertukar ke bawah).

Ini memberi kita algoritma untuk bekerja mundur. Mari kita coba dengan 6, mulai dari langkah terakhir (langkah i = 6):

Step 6: Position 6 swaps with position 12 (6 is divisible by 6, 6/6 = 1 == 1 mod 2)

Jadi sekarang kita tahu nomornya berasal dari posisi 12. Lalu:

Step 5: No swap (12 not divisible by 5)
Step 4: Position 12 swaps with position 16 (12 is divisible by 4, 12/4 = 3 == 1 mod 2)

Jadi sekarang kita tahu itu berasal dari 16 sebelum itu. Akhirnya:

Step 3: No swap (16 not divisible by 3)
Step 2: Position 16 swaps with position 14 (16 divisible by 2, 16/2 = 8 == 0 mod 2)

Karena ini adalah langkah pertama (ingat, k+1), kita selesai dan angka yang berakhir di posisi 6 berasal dari posisi 14, yaitu angka senapan ke-6 adalah 14.

Jadi sekarang untuk penjelasan Python:

i=n=input()             Read input, and store into i (step) and n (position)
while~-i:               while i-1 != 0:, or since we're descending with i this is just while i>1:
  n+=                   Add to the current position...
    (n%i<1)*            1* whatever's next if n is divisible by i, otherwise 0* (i.e. nothing)
    i*                  How many positions n might go up/down
    (n/i%2*2-1)         n/i%2 tell us higher/lower, *2-1 maps 0 or 1 to -1 (down) or +1 (up)
  i-=1                  Decrement the step number
print n                 Output
Sp3000
sumber
cara yang menarik untuk menulis i-1sebagai~-i
mbomb007
6
@ mbomb007: Setuju. Meski pintar, karena memiliki makna yang sama tetapi menghilangkan kebutuhan akan ruang sesudahnya while. Kerja bagus, Sp3000.
Alex A.
Terpendek saya bisa mendapatkan ini dalam pyth adalah dengan menggunakan mengurangi:u+G**H!%GHty%/GH2rhQ2Q
FryAmTheEggman
1
@FryAmTheEggman, Sp3000, apakah Anda berdua tidak akan memposting itu?
Martin Ender
@ MartinBüttner Saya awalnya tidak memposting karena saya merasa itu terlalu banyak salinan. Saya akan mempostingnya sebagai jawaban CW untuk saat ini.
FryAmTheEggman
6

Haskell, 68 byte

n#k|mod k(2*n)<1=k-n|mod k n<1=k+n|k>0=k
s n=foldr((.).(#))id[2..n]n

Mungkin golf lebih jauh, terutama baris pertama. Ini mendefinisikan fungsi syang mengambil ndan mengembalikan nnomor senapan.

map s [1..66]
[1,4,8,6,12,14,16,9,18,20,24,26,28,22,39,15,36,35,40,38,57,34,48,49,51,44,46,33,60,77,64,32,75,56,81,68,76,58,100,55,84,111,88,62,125,70,96,91,98,95,134,72,108,82,141,80,140,92,120,156,124,94,121,52,152,145]

Penjelasan

Fungsi helper #mengambil dalam dua angka ndan k, dan mengembalikan knomor ke dalam daftar yang ditentukan dengan menerapkan operasi pertukaran pasangan ke setiap nnomor ke. Misalnya, menerapkannya ke 20 angka pertama dengan n = 4hasil ini:

map (4#) [1..20]
[1,2,3,8,5,6,7,4,9,10,11,16,13,14,15,12,17,18,19,24]

Hasil s ndiperoleh dengan mengurangi ("melipat") daftar [2..n]dengan fungsi urutan kedua (.).(#), yang mengambil angka mdan fungsi f(awalnya fungsi identitas id), dan mengembalikan fungsi yang mengambil kdan mengembalikan f (m # k). Misalnya, dalam kasus ini n = 4daftar [2,3,4]direduksi menjadi fungsi yang mengambil kdan mengembalikan id (4 # (3 # (2 # k))). The idhanya diperlukan untuk kasus dasar n = 1, di mana daftar kosong. Akhirnya, kami memberikan fungsi ini input k = n, memperoleh nnomor senapan.

Zgarb
sumber
6

CJam, 32 byte

Cukup mengikuti spek to the point. Menjalankan instruksi pada perangkat yang lebih besar sehingga tidak mempengaruhi angka ke- n .

ri:N)2#,:)N{))/2/{:)~\@}%:+}/N(=

Cobalah online di sini

Pengoptimal
sumber
5

Ruby, 92 byte

def s(d,n)
d==1?n:s(d-1,n%d==0?n+(n%(d*2)==0?-d :d):n)
end
n=ARGV[0].to_i
print s(n,n).to_s

Upaya golf kode pertama saya. Tidak berdasarkan jawaban lain.

Sekarang saya telah melihat beberapa yang lain, saya perhatikan bahwa kebanyakan hanya mendefinisikan fungsi, bukan program lengkap yang menerima input dan menghasilkan output. OP meminta program lengkap dengan input dan output. Apakah biasa mengabaikan persyaratan seperti itu?

84 Bytes

n=ARGV[0].to_i
d=n
while d>1
n+=(n%d==0?(n%(d*2)==0?-d :d):0)
d-=1
end
print n.to_s

Setelah melihat jawaban lain dan menyadari bahwa solusi berulang mungkin dilakukan.

Solomon Lambat
sumber
2
Beberapa perbaikan untuk solusi 84 byte Anda: 1. Ubah ARGVke dunia $*ajaib. 2. Tidak to_sperlu. 3. Alih-alih menugaskan duntuk npada baris terpisah, hanya melakukan d=n=...mencukur karakter. Kerja bagus untuk golf pertama Anda! :)
Gagang Pintu
1
Di mana saya meminta program lengkap? "Anda dapat menulis sebuah program atau fungsi ...";) (Ini juga merupakan standar untuk tantangan kode-golf , tetapi saya biasanya memasukkannya untuk kelengkapan.)
Martin Ender
Untuk menambah saran @ Doorknob, dua set tanda kurung pada n+=baris tidak diperlukan, dan kedua kemunculan ==0dapat dengan aman diubah <1.
Peter Taylor
5

Python 2, 97 79 karakter

g=lambda n,k:n>1and g(n-1,k-(k%n<1)*n*(-1)**(k/n%2))or k
n=input()
print g(n,n)

Ini menentukan untuk setiap indeks nilai yang benar dengan secara rekursif mengejar angka mundur. Algoritma itu ditemukan secara independen.

sunting: Sekarang hanya mencetak nnomor ke-empat dan bukan nnomor pertama . Tentu saja pendekatan berulang akan lebih pendek, tetapi saya tidak ingin menyalin kode Sp3000.

Jakube
sumber
Ya, saya pikir semua orang akan bertemu dalam hal ini. Saya menemukan g(i,i)bagian yang sangat mengganggu ...
Sp3000
2
Bahasa harus ditandai sebagai Python 2, karena printpernyataan itu.
mbomb007
@ mbomb007 Memperbaikinya.
Jakube
4

Haskell, 79 byte

1#i=i
s#i|i`mod`(2*s)==0=(s-1)#(i-s)|i`mod`s==0=(s-1)#(i+s)|1<2=(s-1)#i
p n=n#n

Penggunaan: p 66output mana145

Tidak banyak menjelaskan: Fungsi #secara rekursif menghitung jumlah senapan di posisi ilangkah s. p nmengembalikan angka pada posisi nlangkah n.

nimi
sumber
Oh, saya tidak melihat jawaban Anda sebelum mengirimkan jawaban saya. Sepertinya kami memiliki pendekatan yang sangat berbeda.
Zgarb
4

k, 41 byte

{{x+$[y!x;0;$[2!_x%y;y;-y]]}/[x;|2+!x-1]}

 / apply to an int
 {{x+$[y!x;0;$[2!_x%y;y;-y]]}/[x;|2+!x-1]} 42
111
 / apply to 1 through 66
 {{x+$[y!x;0;$[2!_x%y;y;-y]]}/[x;|2+!x-1]}'1+!66
1 4 8 6 12 14 16 9 18 20 24 26 28 22 39 15 36 35 40 38 57 34 48 49 51 44 46 33 60 77 64 32 75 56 81 68 76 58 100 55 84 111 88 62 125 70 96 91 98 95 134 72 108 82 141 80 140 92 120 156 124 94 121 52 152 145
  • {...} lambda, x dan y adalah argumen 1 dan 2 implisit
  • $[b;t;f] operator ternary, mengevaluasi b diikuti oleh t / f masing-masing
  • b!a a modulo b
  • _ lantai, melemparkan hasil pembagian ke int
  • % divisi
  • {...}/[x;y] prime {...} dengan x dan terapkan pada daftar y, sama dengan f [f [.. f [f [x; y0]; y1]; .. yn-1]; yn]
  • | membalikkan
  • ! fungsi iota, menghasilkan daftar 0 hingga n-1
Mollmerx
sumber
4

Common Lisp, 113 91

(berulang: 91)

(defun s(n)(do((r n(1- r)))((= r 1)n)(if(= 0(mod n r))(incf n(* r(if(oddp(/ n r))1 -1))))))

(asli, rekursif: 113)

(defun s(n &optional(r n))(cond((= r 1)n)((= 0(mod n r))(s(+ n(* r(if(oddp(/ n r))1 -1)))(1- r)))(t(s n(1- r)))))

Contoh

Dengan versi rekursif:

(trace s)
(s 10)

  0: (S 10)
    1: (S 20 9)
      2: (S 20 8)
        3: (S 20 7)
          4: (S 20 6)
            5: (S 20 5)
              6: (S 15 4)
                7: (S 15 3)
                  8: (S 18 2)
                    9: (S 20 1)
                    9: S returned 20
         ...
    1: S returned 20
  0: S returned 20

Tes

Cek dan langkah-langkah untuk versi berulang:

(let ((list '(1 4 8 6 12 14 16 9 18 20 24 26 28 22 39 15 36 35 40 38 57 34 48 49 51 44
              46 33 60 77 64 32 75 56 81 68 76 58 100 55 84 111 88 62 125 70 96 91 98 95
              134 72 108 82 141 80 140 92 120 156 124 94 121 52 152 145)))
  (time
   (loop for r in list
         for n from 1
         always (= r (s n)))))

 => T

Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  807,160 processor cycles
  32,768 bytes consed
coredump
sumber
4

Mathematica, 53 49 byte

(For[i=n=#,n>1,--n,If[n∣i,i+=Mod[i,2n]2-n]];i)&

Saya memutuskan untuk menerapkan implementasi referensi saya. Ini ∣adalah simbol Unicode untuk "membagi", dan menghitung selama 3 byte. Kalau tidak, ini menggunakan algoritma yang sama seperti orang lain.

Ini mendefinisikan fungsi yang tidak disebutkan namanya yang mengambil nsebagai parameter tunggal dan mengembalikan nnomor senapan.

Martin Ender
sumber
4

GolfScript, 27 karakter

~.,(~%{):i\.@%!~)1$i/?i*-}/

Penjelasan

Jika f(i, n)nilai pada posisi nsetelah i-1transformasi, kita miliki

f(1, n) = n
f(i, n) = f(i - 1, n % i == 0 ? (((n / i - 1) ^ 1) + 1) * i : n)  for i > 1

di mana ^menunjukkan bitor xor; diberi input n, kami ingin menghitung f(n, n).

Konversi dari fungsi rekursif ke loop tidak menarik; yang menarik adalah caranya

n % i == 0 ? (((n / i - 1) ^ 1) + 1) * i : n

dapat ditulis ulang. Pendekatan yang lebih jelas adalah mengatakan bahwa itu harus

n + (n % i == 0 ? i : 0) * g(n / i)

untuk beberapa orang g. Jelas gbergantian antara 1dan -1, karena posisi bertukar secara bergantian naik dan turun; sejak g(1) = 1(karena 1swap hingga 2), kita miliki

n + (n % i == 0 ? i : 0) * -1**(1 + n / i)

di mana **menunjukkan eksponensial. Penghematan akhir berasal dari penulisan ulang ini sebagai

n - i * (n % i == 0 ? -1 : 0)**(n / i)

Pembedahan

~             # Evaluate input to get n
.,(~%{        # For n-1 downto 1...
  ):i         #   Let i be that value + 1, so for i = n downto 2...
  \.@%!       #   Find n % i == 0 ? 1 : 0
  ~)          #   Negate
  1$i/?       #   Raise to the power of n/i
  i*-         #   Multiply by i and subtract
}/
Peter Taylor
sumber
Melihat Anda memiliki jawaban GS dan CJam terpendek, mengapa tidak juga memiliki jawaban Pyth terpendek? u-G*H^_!%GH/GHrhQ2QJika Anda tidak ingin memposting ini sendiri, beri tahu saya / tambahkan ke jawaban CW.
FryAmTheEggman
@FryAmTheEggman, saya mungkin tidak terlalu berlatih di CJam, tapi setidaknya saya bisa lebih atau kurang membacanya. Saya tidak tahu apa yang dikatakan Pyth dalam komentar Anda, meskipun dari konteks saya kira itu adalah jawaban dari jawaban ini. Jadi yang terbaik adalah Anda mempostingnya, karena Anda dapat menjawab pertanyaan tentang itu.
Peter Taylor
4

Julia, 61 57 byte

n->(i=n;while~-i!=0 n+=(n%i<1)*i*(n÷i%2*2-1);i-=1;end;n)

Ini menciptakan fungsi tanpa nama yang mengambil argumen tunggal ndan mengembalikan nnomor senapan. Untuk menyebutnya, berikan nama, mis f=n->(...).

Contoh:

julia> for i = 1:10 println(f(i)) end
1
4
8
6
12
14
16
9
18
20

Saat ini didasarkan pada jawaban Python @ Sp3000 yang mengagumkan . Saya akan meninjau kembali ini segera karena harus ada cara yang lebih pendek untuk melakukan ini di Julia daripada apa yang saya lakukan di sini. Masukan apa pun diterima, seperti biasa.

Alex A.
sumber
3

CJam, 28 27 byte

Jadi ini sedikit memalukan ... sebelum memposting ini, saya mencoba bermain golf ini sendiri dan mendapatkan 30 byte di CJam. Belum ada jawaban yang ada yang mengalahkan itu. Sementara itu saya juga berhasil mencukur tiga byte lagi. Ada adalah solusi Pyth pendek di komentar, tapi tidak ada yang lebih pendek telah diposting di sebuah jawaban, jadi di sini adalah. Mungkin itu mengilhami orang APL / J untuk mencoba sedikit lebih keras (atau seseorang benar-benar memposting solusi Pyth), sebelum saya harus menerima jawaban saya sendiri. ;)

l~__(,f-{_I_+%_+I-_zI=*+}fI

Uji di sini.

Penjelasan

l~                          "Read input N and eval.";
  __(,                      "Duplicate twice, create range [0 1 2 ... N-2].";
      f-                    "Subtract each from N, giving [N N-1 N-2 ... 2].";
        {               }fI "For each element, storing the element in I.";
         _I_+%_+I-          "Compute 2(N % 2I)-I - the shuffling offset";
                  _zI=      "Check that this offset is ±I.";
                      *+    "Multiply the offset by this boolean and update to N.";
Martin Ender
sumber
3

J, 34 32 byte

   (]+[*(1-~2*2|%~)*0=|)/@(_1}2+i.)

   ((]+[*(1-~2*2|%~)*0=|)/@(_1}2+i.)) every 1+i.20  NB. running with inputs 1..20
1 4 8 6 12 14 16 9 18 20 24 26 28 22 39 15 36 35 40 38

Akan mencoba golf sedikit lebih dan menambahkan penjelasan nanti.

Cobalah online di sini.

randomra
sumber
2

TI-Basic 83/84, 40 byte

Input A:For(I,A,2,~1:A+(AfPart(I/2)-1)I(1>IfPart(A/I->A:End:A

Informasi tentang TI-Basic

Timtech
sumber
1

Ruby, 57 47 byte

Ini pada dasarnya adalah solusi Python Sp3000 (dengan saran xnor ) yang diterjemahkan ke Ruby. Saya mungkin bisa bermain golf di beberapa tempat.

->n{n.downto(2).map{|i|n+=i*(n/i%2-~-n/i%2)};n}
Sherlock9
sumber