Rekonstruksi urutan aritmatika

23

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 ; jawaban terpendek di setiap bahasa menang.

DLosc
sumber
Terkait
DLosc
Akan menarik untuk memiliki input dalam bentuk2 5 ... 17
schnaader

Jawaban:

9

Haskell , 63 byte

f(a:b:c)|s<-[a,b..last c],all(`elem`s)c=s
f a=r$f$r a
r=reverse

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!

pengguna1472751
sumber
5
Meskipun ini cantik, sepertinya tidak selalu berhasil: [1,3,4,5]memberi [1,3,5].
xnor
1
Dan saya pikir all(`elem`s)charus memperbaikinya dengan jumlah byte yang sama.
xnor
6

05AB1E , 9 8 byte

Ÿs¥¿Äô€н

Cobalah online!

Penjelasan

  • Bangun kisaran [pertama, ..., terakhir] dengan selisih +/- 1
  • Hitung delta input
  • Dapatkan nilai absolut dari gcd dari delta
  • Bagi rentang penuh dalam potongan ukuran itu
  • Dapatkan elemen pertama dari setiap chunk

Disimpan 1 byte menggunakan gcd of deltasbukan min delta, terinspirasi oleh user202729

Emigna
sumber
5

Brachylog v2, 9 byte

⊆.s₂ᵇ-ᵐ=∧

Cobalah online!

Ini adalah pengiriman fungsi. Interpreter Brachylog dapat dibuat untuk mengevaluasi suatu fungsi seolah-olah itu adalah program penuh dengan memberikannya Zsebagai argumen baris perintah; dalam hal ini, input ditentukan dalam format, misalnya, [1, 2, 4]dan output dikembalikan dalam format yang sama, misalnya Z = [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 byte s₂ᵇ-ᵐuntuk sesuatu yang sebagian besar bahasa golf modern miliki, tapi itulah cara yang kadang-kadang dilakukan oleh codegolf, saya kira.


sumber
4

Python 2, 104 97 89 83 71 67 60 byte

Terima kasih kepada Chas Brown untuk menghemat 4 byte.
Berkat ovs untuk menghemat 7 byte.

Masukkan daftar dengan argumen.

lambda a,b,*c:range(a,c[-1],min(b-a,c[0]-b,key=abs))+[c[-1]]

Cobalah online!

Penjelasan:

Karena yang dihapus berturut-turut, cukup untuk memeriksa perbedaan antara dua pasang elemen berturut-turut.

Colera Su
sumber
Anda dapat menyimpan 3 byte dengan menggantinya b if b%c else cdengan [c,b][b%c>0].
Chas Brown
@ ChasBrown Terima kasih, meskipun saya segera datang dengan pendekatan yang lebih baik.
Colera Su
1
Baik dengan key=abs! Tampaknya di sini, orang sering menghilangkan f=bagian kecuali fungsi rekursif digunakan; sehingga Anda bisa menghemat 2 byte dengan cara itu.
Chas Brown
1
Juga, ganti a[-1]-a[-2]dengan a[2]-a[1]- logikanya sama, dan Anda mendapatkan 2 byte lagi.
Chas Brown
1
60 bytes
ovs
4

Pyth , 11 byte

%hS.+SQ}hQe

Coba di sini!

Terima kasih kepada Steven H. karena telah menghemat satu byte!

Pyth , 12 byte

%.aiF.+Q}hQe

Coba di sini!

Bagaimana itu bekerja

% .aiF. + Q} hQe ~ Program lengkap.

     . + Q ~ Dapatkan delta.
   iF ~ Reduce by GCD.
 .a ~ Nilai absolut.
% ~ Modular. Dapatkan setiap elemen ke ...
        } ~ Kisaran numerik inklusif antara ...
         hQ ~ Elemen pertama, dan ...
           e ~ Elemen terakhir.
Tuan Xcoder
sumber
Presort Qsehingga Anda dapat mengurutkan dan mengambil elemen pertama alih-alih abs(GCD(Q))dalam %hS.+SQ}hQe11 byte. Test suite
Steven H.
3

Jelly , 8 byte

ṂrṀmIg/$

Cobalah online!

Catatan:

  • Hanya bekerja pada beberapa versi lama Jelly. ( komit ini misalnya) (di mana gdigunakan fractions.gcd, yang memiliki tanda hasil sama dengan tanda input, bukannya math.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.pytelah direduksi menjadi hanya beberapa baris. Namun demikian dictionary.pytidak 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 gcdperbedaan ( I, kenaikan) akan menjadi nilai absolut dari langkah tersebut.

Untungnya gcdsudah ditandatangani (lihat catatan di atas)

Jadi programnya:

ṂrṀ

Kisaran integer yang meningkat dari inimum ke aximum.

m

Modular, pilih setiap elemen ke-n.

Ig/$

$Kombinasi rantai Monadic ( ) I(kenaikan, perbedaan) dan g/(mengurangi gcdlebih dari elemen daftar). Jika kenaikannya positif maka gcdakan positif dan daftar kembali akan kiri-ke-kanan (meningkat), dan sebaliknya.

pengguna202729
sumber
Yay! Ketukan jawaban 05AB1E dengan 1 byte!
user202729
Menggunakan gcdbukannya minmembuat kami mengikat. Sayang sekali saya mendapatkan gcd dengan tanda, kalau tidak saya akan berada di 7;)
Emigna
3

MATL , 13 byte

1)0GdYkG0)3$:

Cobalah online!

Penjelasan:

Consider the example input [2 14 17]:
           # implicit input, STACK: [[2 14 17]]
1)         # push 1, index, STACK: [2]
0G         # push 0, duplicate input, STACK: [2, 0, [2 14 17]]
d          # take differences, STACK: [2, 0, [12, 3]]
Yk         # get value in [12, 3] nearest to 0, STACK: [2, 3]
G0)        # get last element in input, STACK: [2, 3, 17]
3$:        # 3-input :, computes 2:3:17, the range from 2 to 17 by 3
           # STACK: [[2 5 8 11 14 17]], implicit output.

Giuseppe
sumber
3

JavaScript (ES6), 92 90

Edit 2 byte disimpan thx Arnauld

Mudah, karena cukup untuk memeriksa perbedaan antara dua yang pertama dan dua yang terakhir. Tapi masih panjang sekali.

s=>(e=(z=s.pop(a=s[0]))-s.pop(d=s[1]-a),[...Array((z-(a-=d=e*e>d*d?d:e))/d)].map(_=>a+=d))

Kurang golf

s=>{
  a =s[0]
  b =s[1]
  z = s.pop()
  y = s.pop()
  d = b-a
  e = z-y
  d = e*e>d*d?d:e  
  n = (z-a)/d+1
  return [...Array(n)].map((_,i) => a + i*d)
}

Uji

var F=
s=>(e=(z=s.pop(a=s[0]))-s.pop(d=s[1]-a),[...Array((z-(a-=d=e*e>d*d?d:e))/d)].map(_=>a+=d))

var test=`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`.split`\n`
.map(r=>r.split`Out`.map(x=>x.match(/\d+/g)))

test.forEach(([i,k])=>{
  var o=F(i.slice(0))
  var ok = o+''==k
  console.log(ok?'OK':'KO',i+' => '+o)
})

edc65
sumber
a-=d=e*e>d*d?d:eharus bekerja dan menghemat 2 byte.
Arnauld
@Arnauld bekerja dengan benar, terima kasih
edc65
2

Bahasa Wolfram (Mathematica) , 50 byte

Range[#&@@#,#[[-1]],#&@@Differences@#~SortBy~Abs]&

Cobalah online!

JungHwan Min
sumber
Apakah "daftar angka" termasuk memiliki angka sebagai argumen individual? Jika demikian, sepertinya Anda bisa menyimpan banyak byte.
numbermaniac
@numbermaniac Saya rasa tidak, karena tidak ada builtin yang mengambil input terakhir ...
JungHwan Min
Ahh ... benar. Lupa tentang itu.
numbermaniac
Anda dapat menggunakan {##}dan Last@{##}tapi yang terbaik yang bisa saya dapatkan adalah 51 byte.
numbermaniac
2

Ruby , 65 62 55 54 byte

->l{a,*,b,c=l;[*a.step(c,[l[1]-a,c-b].min_by(&:abs))]}

Cobalah online!

Terima kasih -1 byte untuk Justin Mariner

GB
sumber
Anda dapat menyimpan byte dengan menghapus h, meninggalkan Anda dengan a,*,b,c. Cobalah online!
Justin Mariner
1

Haskell , 73 69 byte

f(h:t)=do(#)<-[(-),(+)];[h,h#minimum(abs<$>zipWith(-)t(h:t))..last t]

Cobalah online!

Laikoni
sumber
1
Saya menemukan solusi 63 byte tetapi sangat berbeda dari milik Anda. Haruskah saya membuat posting terpisah?
user1472751
@ user1472751 Saya bukan Laikoni, tetapi situs ini ditujukan untuk kompetisi, serta kolaborasi. Jadi saya akan mempostingnya.
H.PWiz
@ user1472751 Pendekatan yang bagus! Silakan lanjutkan dan kirimkan sebagai jawaban Anda sendiri.
Laikoni
1

J , 49, 47 46 byte

(0-[:<./2|@-/\]){.@[&]\({.<.{:)+[:i.{:(+*)@-{.

Terinspirasi oleh solusi Emigna.

Bagaimana itu bekerja:

 (0-[:<./2|@-/\]){.@[&]\({.<.{:)+[:i.{:(+*)@-{. - fork of 3 verbs

                        ({.<.{:)+[:i.{:(+*)@-{. - generates a list in the entire range of values
                                     {:     -{. - last minus first element  
                                       (+*)@    - adds the signum of the difference
                                 [:i.           - makes a list 
                       ({.<.{:)                 - the smallest of first and last elements                                     
                               +                - adds the offset to the list (translates all elements according to the first one)

 (0-[:<./2|@-/\])                               - finds the step
         2|@-/\]                                - the absolute differences between all consecutive elements
    [:<./                                       - the smallest one
  0-                                            - negate (for splitting)

                 {.@[&]\                        - splits the list from the right verb into left verb's result sublists and takes their first elements

Cobalah online!

Galen Ivanov
sumber
1

Sekam , 9 byte

m←C▼Ẋ≠⁰…⁰

Cobalah online!

Terima kasih banyak kepada H.PWiz karena mengurangi separuh jumlah byte, dengan menunjukkan bahwa mendaftar pada daftar akan membuatnya! ...

Tuan Xcoder
sumber
@ HP.Wiz X_X Saya tidak tahu Husk menampilkan daftar seperti itu ... Apakah Anda yakin tidak ingin mempostingnya sebagai jawaban Anda sendiri?
Tn. Xcoder
@ HP.Wiz Terima kasih, loooot !
Tn. Xcoder
Juga, dapatkah F⌋diganti ?
H.PWiz
@ H.PWiz @ _ @ Mengapa itu bekerja?
Tn. Xcoder
Perbedaan terkecil (absolut) akan menjadi perbedaan asli. Satu-satunya alasan gcdadalah untuk berurusan dengan delta negatif
H.PWiz
1

C # (.NET Core) , 167 + 13 = 180 145 + 13 = 158 byte

a=>{int x=a[1]-a[0],y=a[2]-a[1],d=x*x<y*y?x:y,s=Math.Abs((a[a.Length-1]-a[0])/d),i=0,j=a[0];var r=new int[s+1];for(;i<=s;j+=d)r[i++]=j;return r;}

Cobalah 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

a=>{
    int x = a[1]-a[0],        // difference between first and second numbers
        y = a[2]-a[1],        // difference between second to last and last numbers
        d = x*x < y*y? x : y, // smallest absolute value difference
        s = Math.Abs((a[a.Length-1] - a[0]) / d), // number of steps in the reconstructed sequence (not the number of elements)
        i = 0,                // step position
        j = a[0];             // next number in reconstructed sequence

    var r = new int[s+1];

    // reconstruct the sequence
    for(; i <= s; j+=d)
        r[i++]=j;

    return r;
}
Ayb4btu
sumber
0

Python 2 , 147 byte

from fractions import*
a=input()
b=[j-i for i,j in zip(a[:-1],a[1:])]
l=min(gcd(i,j)for i in b for j in b)
print list(range(a[0],a[-1]+l/abs(l),l))

Cobalah online!

Neil
sumber
0

Python 2 , 78 byte

lambda a:range(a[0],a[-1],[min,max][a[0]>a[1]](a[1]-a[0],a[-1]-a[-2]))+[a[-1]]

Cobalah online!

Chas Brown
sumber
77 bytes
ovs
0

dc , 64 byte

?dsx[ksE0_1]sg[scdlcr-d2^vdK>gK0=g+sqz1<l]dslx[pdlE+dlx!=Z]dsZxp

Cobalah online!

R. Kap
sumber
0

Japt , 12 byte

ÌõUg Uäa ñ g

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).

Shaggy
sumber