Loop Divisi Integer

8

Tantangan

Diberikan bilangan bulat positif yang didukung oleh bahasa Anda:

  1. Ambil input dan bagi menjadi dua. Untuk semua divisi dalam program ini, jika inputnya ganjil, bulatkan setengah ke atas dan setengah ke bawah (mis:, 7 -> 3,4tidak 7 -> 3.5,3.5).
  2. Bagi kedua nomor menjadi dua, kemudian ambil yang lebih besar dari dua bagian baru ini dan tambahkan kembali ke nomor yang tidak terpecah. Mis .: 3,4 -> (1,2),4 -> 1,6atau 3,4 -> 3,(2,2) -> 5,2.
  3. Ulangi langkah 2 hingga Anda mencapai set yang telah Anda lihat sebelumnya. Ex: 5 -> 3,2 -> (1,2),2 -> 1,4 -> 1,(2,2) -> 3,2. Karena kita telah melihat 3,2sebelumnya, kita mungkin berhenti mengulangi. Anda mungkin benar-benar menghabiskan tumpukan dalam proses melakukan ini. Ex: 5 -> 3,2 -> (1,2),2 -> 1,4 -> (0,1),4 -> 0,5.
  4. Keluarkan setiap pasangan dalam loop (yaitu yang di atas tanpa langkah-langkah menengah, dari penampilan pertama dari pasangan sampai yang kedua, tetapi tidak termasuk yang kedua). Ex: 3,2 -> 1,4. Jika input disertakan, jangan output a 0dengan itu - 5 -> 3,2 -> 1,4, tidak 0,5 -> 3,2 -> 1,4.
  5. Ulangi langkah 1-4 dengan memisahkan pasangan secara berbeda.

I / O

Input bilangan bulat positif lebih besar dari 1dan lebih kecil daripada bilangan bulat maksimum yang didukung oleh bahasa Anda atau bilangan bulat maksimum yang tidak akan membuat crash komputer, mana yang lebih kecil.

Output adalah loop dari atas dalam format apa pun yang Anda inginkan (string, daftar, array, dll.). Trailing white space diperbolehkan.

Jangan output loop yang sama dua kali, atau versi berbeda dari loop yang sama. Contoh: 2 -> 1,1dan 1,1 -> 2keduanya merupakan loop yang valid, tetapi mereka menggambarkan loop yang sama, dimulai pada titik yang berbeda pada loop. Demikian juga, dua loop yang identik tetapi berjalan dalam urutan terbalik tidak boleh di-output. Mis: 3 -> 1,2 -> 2,1dan 3 -> 2,1 -> 1,2adalah loop yang sama, tetapi mereka pergi ke arah yang berlawanan satu sama lain.

Anda dapat menggunakan pembatas apa pun untuk membedakan antara pasangan, antara setiap angka dalam pasangan, dan antara setiap loop, asalkan mereka adalah tiga karakter atau string yang berbeda. Di atas, saya membagi angka menggunakan koma, pasangan menggunakan ->'s, dan loop menggunakan instruksi yang membosankan. Dalam contoh saya di bawah ini, saya akan menggunakan tanda kurung di sekitar setiap pasangan, koma di antara setiap angka dalam pasangan, dan baris baru di antara setiap loop.

Contohnya

Kredit ke kode @ WheatWizard untuk memperbaiki daftar contoh saya. Seperti yang saya katakan di draft sebelumnya, saya yakin saya kehilangan beberapa karena saya melakukannya dengan tangan, tetapi anak laki-laki saya kehilangan beberapa.

Input: 2
Keluaran:(2)(1,1)

Input: 3
Keluaran:

(3)(1,2)
(1,2)(2,1)
(3)(1,2)(2,1)

Input: 4
Keluaran:

(4)(2,2)(1,3)
(1,3)(3,1)
(4)(2,2)(1,3)(3,1)
(4)(2,2)(3,1)(1,3)
(3,1)(1,3)
(4)(2,2)(3,1)

Memasukkan: 5

Keluaran:

(5)(2,3)(1,4)
(1,4)(3,2)
(2,3)(1,4)(3,2)(4,1)
(5)(2,3)(1,4)(3,2)(4,1)
(2,3)(4,1)
(5)(2,3)(4,1)

Memasukkan: 6

Keluaran:

(6)(3,3)(1,5)
(1,5)(4,2)(2,4)
(4,2)(2,4)
(1,5)(4,2)(5,1)(2,4)
(4,2)(5,1)(2,4)
(6)(3,3)(1,5)(4,2)(5,1)
(6)(3,3)(5,1)(2,4)(1,5)
(2,4)(1,5)(4,2)
(5,1)(2,4)(1,5)(4,2)
(2,4)(4,2)
(5,1)(2,4)(4,2)
(6)(3,3)(5,1)

Memasukkan: 7

Keluaran:

(7)(3,4)(1,6)
(1,6)(4,3)(2,5)
(2,5)(5,2)
(3,4)(1,6)(4,3)(2,5)(5,2)(6,1)
(7)(3,4)(1,6)(4,3)(2,5)(5,2)(6,1)
(3,4)(1,6)(4,3)(6,1)
(7)(3,4)(1,6)(4,3)(6,1)
(7)(3,4)(5,2)(2,5)(1,6)
(2,5)(1,6)(4,3)
(3,4)(5,2)(2,5)(1,6)(4,3)(6,1)
(7)(3,4)(5,2)(2,5)(1,6)(4,3)(6,1)
(5,2)(2,5)
(3,4)(5,2)(6,1)
(7)(3,4)(5,2)(6,1)

Mencetak gol

Ini adalah , sehingga jumlah byte terendah menang.


Ini adalah tantangan pertama saya di sini, jadi umpan balik apa pun akan sangat dihargai. Tautan ke kotak pasir di sini .

Fakta yang menyenangkan: Suatu hari saya bosan dan bermain dengan potongan-potongan kecil pensil secara acak dengan cara ini dan akhirnya menyadari bahwa saya bisa terus melakukan loop jenis ini. Untuk beberapa alasan reaksi pertama saya adalah "hei, ini akan menjadi tantangan besar untuk golf kode."

DonielF
sumber
4
Selamat datang di PPCG, tantangan pertama yang menyenangkan!
FlipTack
Bisakah kita mencetak (a,0)di tempat (a)? Ini cenderung masuk akal dalam bahasa yang sangat diketik.
Ad Hoc Garf Hunter
@WheatWizard Tidak. Saat mencetak input Anda hanya mencetak input tanpa nol. Saya belum melihat tantangan di sini di mana ia datang ke hanya satu atau dua byte.
DonielF
Ok, itu cukup adil. Tetapi sebagai catatan, saya tentu tidak akan menyebutnya satu atau dua byte. Bagi saya sepertinya sekitar 30% dari jumlah byte saya adalah menghapus nol.
Ad Hoc Garf Hunter
Karena loop yang sama secara terbalik adalah sama, dapatkah kita mengeluarkan loop secara terbalik?
Kamis

Jawaban:

2

Bersih , 267 ... 167 byte

import StdEnv
f s l|any((==)s)l=[dropWhile((<>)s)l]#[h,t:_]=s
|1>h*t=f[max h t]l=f[h/2,(h+1)/2+t](l++[s])++(f[(t+1)/2+h,t/2](l++[s]))
@n=removeDup(f[n/2,(n+1)/2][[n]])

Cobalah online!

Tidak Disatukan:

loops num
    = removeDup (half (divide num) [[num]])
where
    divide num
        = [num/2, (num+1)/2]
    half [_, 0] list
        = list
    half [0, _] list
        = list
    half [a, b] list
        | isMember [a, b] list
            = [dropWhile ((<>) [a, b]) list]
        # [u, v: _]
            = divide a
        # [x, y: _]
            = divide b
        = (half [u, v+b] (list ++ [a, b])) ++ (half [a+y, x] (list ++ [a, b]))
Suram
sumber
2

Haskell , 227 203 byte

17 byte disimpan berkat Οurous

(%)=div
u x|odd x=x%2+1|1>0=x%2
[0,b]!l=[b]!l
[b,0]!l=[b]!l
t!l|elem t l=[dropWhile(/=t)l]
t@[a,b]!l|q<-l++[t]=[a%2,u a+b]!q++[u b+a,b%2]!q
f x|q<-[x%2,u x]![[x]]=[a|(a,b)<-zip q[0..],notElem a$take b q]

Cobalah online!

Ad Hoc Garf Hunter
sumber
Tidak akan menggunakan daftar lebih pendek dari tupel, karena Anda bisa menangani kasus elemen 1 dan 2 dengan yang sama show?
Kamis
@ Οurous Sebenarnya Anda benar itu lebih pendek hanya membutuhkan beberapa pekerjaan.
Ad Hoc Garf Hunter