Diberikan urutan aritmatika terbatas bilangan bulat positif dengan beberapa istilah dihapus dari tengah, merekonstruksi seluruh urutan.
Tugas
Pertimbangkan urutan aritmatika: daftar bilangan bulat positif di mana perbedaan antara dua elemen berturut-turut adalah sama.
2 5 8 11 14 17
Sekarang anggaplah satu atau lebih bilangan bulat dihapus dari urutan, tunduk pada batasan berikut:
- Bilangan bulat yang dihapus akan merupakan urutan berurutan.
- Bilangan bulat pertama dan terakhir dalam urutan tidak akan dihapus.
- Setidaknya tiga bilangan bulat akan tetap berada dalam urutan.
Untuk urutan di atas, kemungkinan pemindahan meliputi:
2 5 8 14 17 (removed 11)
2 5 17 (removed 8 11 14)
2 14 17 (removed 5 8 11)
Tugas Anda: Diberikan salah satu dari sekuens parsial ini, merekonstruksi sekuens penuh asli.
Detail
Anda dapat menganggap input valid (memiliki solusi) dan tidak memiliki setidaknya satu istilah. Semua angka dalam urutan akan bilangan bulat positif (> 0). Urutan mungkin memiliki perbedaan positif atau negatif antara istilah (yaitu mungkin meningkat atau menurun). Itu tidak akan menjadi urutan konstan (misalnya 5 5 5
).
Solusi Anda mungkin merupakan program atau fungsi lengkap . Salah satu input dan output metode standar yang dapat diterima.
Input dan output Anda mungkin berupa string (dengan pembatas yang masuk akal), daftar string, atau daftar angka. Anda dapat mewakili angka-angka dalam basis apa pun yang nyaman untuk bahasa Anda.
Harap sebutkan metode / format I / O yang tidak biasa dalam kiriman Anda, sehingga orang lain akan dapat menguji kode Anda dengan lebih mudah.
Uji kasus
In: 2 5 8 14 17
Out: 2 5 8 11 14 17
In: 2 5 17
Out: 2 5 8 11 14 17
In: 2 14 17
Out: 2 5 8 11 14 17
In: 21 9 6 3
Out: 21 18 15 12 9 6 3
In: 10 9 5
Out: 10 9 8 7 6 5
In: 1 10 91 100
Out: 1 10 19 28 37 46 55 64 73 82 91 100
Ini adalah kode-golf ; jawaban terpendek di setiap bahasa menang.
2 5 ... 17
Jawaban:
Haskell , 63 byte
Cobalah online!
Pada dasarnya bekerja dengan mencoba membangun hasil dari depan dan, jika itu gagal, dari belakang. Ini menggunakan fakta bahwa anggota input pertama dan terakhir akan selalu benar, fakta bahwa anggota yang dihapus harus berturut-turut, dan fakta bahwa akan selalu ada setidaknya tiga item dalam input. Yang harus saya lakukan adalah mengasumsikan bahwa anggota kedua atau kedua hingga terakhir akurat dan memeriksa apakah itu berfungsi. Untungnya Haskell memiliki sintaks yang sangat indah untuk membuat seri aritmatika.
EDIT: terima kasih kepada @xnor karena telah menunjukkan bug dan memberikan solusi!
sumber
[1,3,4,5]
memberi[1,3,5]
.all(`elem`s)c
harus memperbaikinya dengan jumlah byte yang sama.05AB1E ,
98 byteCobalah online!
Penjelasan
Disimpan 1 byte menggunakan
gcd of deltas
bukanmin delta
, terinspirasi oleh user202729sumber
Brachylog v2, 9 byte
Cobalah online!
Ini adalah pengiriman fungsi. Interpreter Brachylog dapat dibuat untuk mengevaluasi suatu fungsi seolah-olah itu adalah program penuh dengan memberikannya
Z
sebagai argumen baris perintah; dalam hal ini, input ditentukan dalam format, misalnya,[1, 2, 4]
dan output dikembalikan dalam format yang sama, misalnyaZ = [1, 2, 3, 4]
. (Tentu saja, untuk pengiriman fungsi, input dan output tidak dalam format apa pun; mereka hanya daftar.)Ini sebenarnya memecahkan masalah yang lebih sulit daripada yang diminta OP: ia bekerja di luar urutan aritmatika bilangan bulat yang berisi nilai yang ditentukan dalam urutan yang ditentukan, terlepas dari apakah penghapusannya berturut-turut atau tidak. Karena menggunakan brute force, bisa sangat lambat jika banyak nilai dihapus.
Penjelasan
Program ini memiliki tiga bagian utama.
⊆
menemukan supersekuensinya input (yaitu urutan yang memiliki input sebagai urutan). Ketika ada lebih dari satu kemungkinan output dari program Brachylog, output yang dipilih adalah output pertama dalam urutan tiebreak, dan urutan tiebreak ditentukan oleh perintah pertama dalam program yang memiliki pendapat tentang itu; dalam hal ini,⊆
tentukan pesanan yang mendukung output pendek daripada yang panjang. Jadi output yang akan kita dapatkan akan menjadi supersequence input terpendek yang mematuhi batasan di seluruh program..
...∧
digunakan untuk menampilkan nilai yang dilihatnya sebagai input (yaitu supersequence dalam kasus ini), tetapi juga menyatakan bahwa ada kondisi tertentu yang melekat padanya. Dengan kata lain, kami mengeluarkan supersequence terpendek yang mematuhi kondisi tertentu (dan mengabaikan hasil antara yang digunakan untuk melihat apakah itu mematuhi kondisi).Akhirnya, kita memiliki
s₂ᵇ-ᵐ
=
, yaitu "semua delta dari urutan sama", kondisi yang kita terapkan pada output. (Nilai balik dari ini adalah daftar delta, daripada supersequence itu sendiri, itulah sebabnya kita membutuhkan.
...∧
untuk memastikan bahwa hal yang benar adalah output.)Brachylog ditahan di sini dengan tidak memiliki builtin yang dapat menangani perhitungan delta, menerapkan operasi untuk pasangan yang tumpang tindih dari daftar, atau sejenisnya. Sebaliknya, kita harus mengatakan apa yang kita maksudkan secara eksplisit:
s₂ᵇ
temukan semua (ᵇ
) substring (s
) dengan panjang 2 (₂
) (penggunaanᵇ
diperlukan untuk menjaga hubungan antara yang tidak diketahui dalam substring dan dalam supersequence; semakin umum digunakanᶠ
akan memecahkan ini link). Kemudian-ᵐ
lakukan pengurangan pada masing-masing pasangan ini untuk menghasilkan delta. Sangat menyebalkan harus menulis lima bytes₂ᵇ-ᵐ
untuk sesuatu yang sebagian besar bahasa golf modern miliki, tapi itulah cara yang kadang-kadang dilakukan oleh codegolf, saya kira.sumber
Python 2,
104978983716760 byteTerima kasih kepada Chas Brown untuk menghemat 4 byte.
Berkat ovs untuk menghemat 7 byte.
Masukkan daftar dengan argumen.
Cobalah online!
Penjelasan:
Karena yang dihapus berturut-turut, cukup untuk memeriksa perbedaan antara dua pasang elemen berturut-turut.
sumber
b if b%c else c
dengan[c,b][b%c>0]
.key=abs
! Tampaknya di sini, orang sering menghilangkanf=
bagian kecuali fungsi rekursif digunakan; sehingga Anda bisa menghemat 2 byte dengan cara itu.a[-1]-a[-2]
dengana[2]-a[1]
- logikanya sama, dan Anda mendapatkan 2 byte lagi.Pyth , 11 byte
Coba di sini!
Terima kasih kepada Steven H. karena telah menghemat satu byte!
Pyth , 12 byte
Coba di sini!
Bagaimana itu bekerja
sumber
Q
sehingga Anda dapat mengurutkan dan mengambil elemen pertama alih-alihabs(GCD(Q))
dalam%hS.+SQ}hQe
11 byte. Test suiteJelly , 8 byte
Cobalah online!
Catatan:
Hanya bekerja pada beberapa versi lama Jelly. ( komit ini misalnya) (di mana
g
digunakanfractions.gcd
, yang memiliki tanda hasil sama dengan tanda input, bukannyamath.gcd
, yang selalu mengembalikan nilai positif).TIO tautan di atas adalah tautan TIO Python 3, kode Python terdiri dari kode sumber Jelly dari komit yang saya sebutkan di atas, dengan pengecualian untuk semuanya (3 file) yang dimasukkan ke dalam file yang sama (untuk menjalankan TIO) dan
dictionary.py
telah direduksi menjadi hanya beberapa baris. Namun demikiandictionary.py
tidak terkait dengan jawaban ini, karena tidak menggunakan string terkompresi. (“...»
konstruk)Penjelasan:
Pertama, karena segmen yang berkelanjutan dihapus dan setidaknya 3 elemen tersisa, ada dua angka berurutan dalam daftar lama yang tersisa, dan delta semuanya akan menjadi kelipatan dari langkah tersebut. Oleh karena itu daftar
gcd
perbedaan (I
, kenaikan) akan menjadi nilai absolut dari langkah tersebut.Untungnya
gcd
sudah ditandatangani (lihat catatan di atas)Jadi programnya:
Kisaran integer yang meningkat dari
Ṃ
inimum keṀ
aximum.Modular, pilih setiap elemen ke-n.
$
Kombinasi rantai Monadic ( )I
(kenaikan, perbedaan) dang/
(mengurangigcd
lebih dari elemen daftar). Jika kenaikannya positif makagcd
akan positif dan daftar kembali akan kiri-ke-kanan (meningkat), dan sebaliknya.sumber
gcd
bukannyamin
membuat kami mengikat. Sayang sekali saya mendapatkan gcd dengan tanda, kalau tidak saya akan berada di 7;)MATL , 13 byte
Cobalah online!
Penjelasan:
sumber
JavaScript (ES6),
9290Edit 2 byte disimpan thx Arnauld
Mudah, karena cukup untuk memeriksa perbedaan antara dua yang pertama dan dua yang terakhir. Tapi masih panjang sekali.
Kurang golf
Uji
sumber
a-=d=e*e>d*d?d:e
harus bekerja dan menghemat 2 byte.Bahasa Wolfram (Mathematica) , 50 byte
Cobalah online!
sumber
{##}
danLast@{##}
tapi yang terbaik yang bisa saya dapatkan adalah 51 byte.Ruby ,
65 62 5554 byteCobalah online!
Terima kasih -1 byte untuk Justin Mariner
sumber
h
, meninggalkan Anda dengana,*,b,c
. Cobalah online!Haskell ,
7369 byteCobalah online!
sumber
J ,
49, 4746 byteTerinspirasi oleh solusi Emigna.
Bagaimana itu bekerja:
Cobalah online!
sumber
Sekam , 9 byte
Cobalah online!
Terima kasih banyak kepada H.PWiz karena mengurangi separuh jumlah byte, dengan menunjukkan bahwa mendaftar
…
pada daftar akan membuatnya! ...sumber
F⌋
diganti▼
?gcd
adalah untuk berurusan dengan delta negatifC # (.NET Core) ,
167 + 13 = 180145 + 13 = 158 byteCobalah online!
+13 untuk
using System;
Yang mengejutkan, tantangan ini lebih bernuansa yang awalnya saya perkirakan.
Ucapan Terima Kasih
-22 byte disimpan karena beberapa penyederhanaan dari @DLosc.
DeGolfed
sumber
Python 2 , 147 byte
Cobalah online!
sumber
Python 2 , 78 byte
Cobalah online!
sumber
Jelly , 8 byte
Cobalah online!
sumber
dc , 64 byte
Cobalah online!
sumber
Japt , 12 byte
Cobalah
Penjelasan
Hasilkan array bilangan bulat (
õ
) dari elemen terakhir dari array input (Ì
) ke yang pertama (Ug
). Hitung langkah antara elemen dengan mendapatkan semua pasangan elemen dari input & menguranginya dengan perbedaan absolut (Uäa
) lalu mengurutkan (ñ
) array itu dan mengambil elemen pertama (g
).sumber