Dapatkan langkah-langkah urutan

17

Tantangan

Diberikan urutan angka, buat fungsi yang mengembalikan langkah urutan.

  • Asumsikan urutannya akan N >= 3
  • Urutan akan mengulanginya langkah setidaknya sekali
  • Urutan hanya akan berisi bilangan asli
  • Fungsi atau program Anda harus mengembalikan urutan langkah sesingkat mungkin

Contoh:

Memasukkan: [1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17]

Keluaran: [1, 1, 2]

Penjelasan: Urutan awal dari 1 => 2 (1 step), 2 => 3 (1 step), 3 => 5 (2 steps). Lalu berulang. Outputnya adalah[1 step, 1 step, 2 steps] => [1, 1, 2]

Contoh lain:

Memasukkan: [2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20]

Keluaran: [3, 1, 1, 1]

[2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20]
 \  /\ /\ /\ / 
  3   1  1  1  Then it repeats...

Uji Kasus

Input: [1, 4, 8, 9, 10, 13, 17, 18, 19, 22, 26, 27, 28] => Output: [3,4,1,1]

Input: [6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41] => Output: [5,2]

Input: [2, 6, 10, 13, 17, 21, 25, 28, 32, 36, 40, 43, 47] => Output: [4,4,3,4]

Input: [5, 6, 7] => Output: [1]


Klarifikasi

  • Panjang input - 1 dapat dibagi dengan panjang output
  • Asumsikan urutan akan selalu meningkat

Ini adalah , jadi jawaban tersingkat dalam byte menang.

Luis felipe De jesus Munoz
sumber
Tantangan terkait .
AdmBorkBork
6
Saya telah melihat beberapa tantangan yang baru-baru ini Anda posting dengan banyak komentar klarifikasi, dan beberapa ditutup sebagai "tidak jelas", dan kemudian dibuka kembali setelah Anda melakukan pengeditan yang sesuai. Sudahkah Anda mempertimbangkan untuk memposting ini di kotak pasir selama beberapa hari / minggu? Saya telah menikmati tantangan Anda karena mereka cukup mudah didekati, tetapi semua tantangan, tidak peduli seberapa sederhana atau oleh siapa mereka diposting, dapat menggunakan penyempurnaan.
Giuseppe
2
@Giuseppe Terima kasih atas saran Anda. Saya telah memposting beberapa tantangan lain di kotak pasir (biasanya jika saya tidak mendapatkan cara yang tepat untuk membuat tantangan dengannya saya menghapusnya). Untuk tantangan ini saya pikir mereka sudah cukup jelas dan itulah sebabnya saya segera memposting tetapi saya akan mulai mempostingnya di kotak pasir terlebih dahulu. Terima kasih
Luis felipe De jesus Munoz
2
@LuisMendo Bidat! 0 adalah bilangan alami! Billy Joel bahkan memiliki seluruh album yang didedikasikan untuk Peano Man!
ngm
1
@ AdmBorkBork, ini lebih terkait berdasarkan berurusan dengan daftar operasi sewenang-wenang.
Peter Taylor

Jawaban:

10

Jelly , 9 7 byte

IsJEƇḢḢ

Cobalah online!

Bagaimana itu bekerja

IsJEƇḢḢ  Main link. Argument: A (array)

I        Increment; compute D, the array of A's forward differences.
  J      Indices; yield [1, ..., len(A)].
 s       Split D into chunks of length k, for each k in [1, ..., len(A)].
   EƇ    Comb equal; keep only partitions of identical chunks.
     Ḣ   Head; extract the first matching parititon.
      Ḣ  Head; extract the first chunk.
Dennis
sumber
9

JavaScript (ES6), 58 byte

Menghasilkan string yang dipisahkan koma (dengan koma terkemuka).

a=>(a.map(p=x=>-(p-(p=x)))+'').match(/N((,\d+)*?)\1*$/)[1]

Cobalah online!

Atau 56 byte jika kita gunakan ,-sebagai pemisah dan kita mengasumsikan bahwa urutannya selalu meningkat secara ketat .

Bagaimana?

Kami pertama-tama mengonversi array input a [] ke daftar perbedaan berurutan dengan:

a.map(p = x => -(p - (p = x)))

Karena p awalnya diatur ke nilai non-numerik (fungsi panggilan balik peta () ), iterasi pertama menghasilkan NaN .

Contoh:

[6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41]
[ NaN, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2 ]

Kami kemudian memaksa hasil ke string:

"NaN,5,2,5,2,5,2,5,2,5,2"

Akhirnya, kita mencari pola terpendek 1 dari integer yang dipisahkan koma ( ,\d+) dimulai tepat setelah "NaN" dan diulang sampai akhir string:

match(/N((,\d+)*?)\1*$/)

1: menggunakan yang tidak rakus *?

Arnauld
sumber
Saya memposting solusi berdasarkan ide regex yang sama, tetapi sangat berbeda dalam implementasinya. Tentu saja saya tidak melihat solusi lain sebelum mengembangkan tambang, dan sepertinya cukup berbeda, dan mungkin ini pertama kalinya saya berhasil mencetak skor lebih baik daripada Anda di sini.
edc65
1
53 byte: /(,.+?)\1*$/.
Neil
6

Brachylog , 11 byte

s₂ᶠ-ᵐṅᵐ~j₍t

Cobalah online!

Akan menjadi 5 byte jika ada built-in untuk perbedaan berurutan.

Penjelasan

Example input: [6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41] 

s₂ᶠ             Find all substrings of length 2: [[6,11],[11,13],…,[34,39],[39,41]]
   -ᵐ           Map subtraction: [-5,-2,-5,-2,-5,-2,-5,-2,-5,-2]
     ṅᵐ         Map negate: [5,2,5,2,5,2,5,2,5,2]
       ~j₍      Anti-juxtapose the list of differences; the shortest repeated list is found
                  first, with the biggest number of repetitions: [5,[5,2]]
            t   Tail: [5,2]
Fatalisasi
sumber
Bisakah Anda meniadakan setelah ekor, untuk menyimpan byte?
Rod
@Rod Aku masih harus memetakannya, jadi itu akan menjadi panjang yang sama. Meniadakan adalah predikat antara dua angka, itu tidak membuat vektor secara otomatis ke daftar seperti bahasa lain (kalau tidak itu tidak akan bekerja dengan baik dengan input / output yang tidak diketahui yang umum dalam program deklaratif)
Fatalize
5

Pyth, 11 byte

<J.+Qf.<IJT

Coba di sini

Penjelasan

<J.+Qf.<IJT
 J.+Q          Call the sequence of differences in the input J.
     f         Find the first positive integer T...
      .<IJT    ... where rotating J by T doesn't change it.
<J             Take that many elements of J.

sumber
5

Japt , 14 12 byte

äa
¯@eUéX}aÄ

Cobalah


Penjelasan

              :Implicit input of array U
äa            :Consecutive absolute differences
\n            :Reassign to U
 @    }aÄ     :Return the first positive integer X that returns true
   UéX        :  Rotate U right X times
  e           :  Check equality with U
¯             :Slice U to that element

Asli

äa
@eUîX}a@¯XÄ

Cobalah

Shaggy
sumber
5

R , 49 46 byte

Program lengkap:

d=diff(scan());while(any((s=d[1:T])-d))T=T+1;s

Cobalah online!

R , 72 58 54 byte

Pengajuan fungsi asli dengan semua kasus uji di satu tempat:

function(a,d=diff(a)){while(any((s=d[1:T])-d))T=T+1;s}

Cobalah online!

Terima kasih kepada JayCe karena menyarankan rute program lengkap dan -4 byte pada fungsi, dan untuk Giuseppe untuk lebih lanjut -3.

Kirill L.
sumber
-9 byte dengan menyalahgunakan built-in dan menjadikannya program yang penuh Tantangan memungkinkan program yang lengkap.
JayCe
@JayCe tidak perlu di a<-sini juga
Giuseppe
4

J , 22 19 byte

3 byte disimpan berkat FrownyFrog!

0{"1[:~./:|."{}.-}:

Cobalah online!

[Cobalah online!] [TIO-ji2uiwla]

Bagaimana?

                 -      find the successive differences by subtracting 
                  }:    the list with last element dropped
               }.       from the list with the first element dropped 
           |."{         rotate the list of differences
         /:             0..length-1 times (the input graded up)
     [:~.               remove duplicating rows
 0{"1                   take the first element of each row
Galen Ivanov
sumber
Jika /:bukan #\, Anda bisa 0{"1[:~.menghemat 1 byte.
FrownyFrog
Dan "0 1adalah"{
FrownyFrog
@FrownyFrog Terima kasih, sekali lagi!
Galen Ivanov
1
ini cantik.
Jonah
@Jonah Ya, terima kasih kepada FrownyFrog!
Galen Ivanov
4

05AB1E , 8 byte

Disimpan 3 byte berkat Kevin Cruijssen .

¥.œʒË}нн

Cobalah online!


05AB1E , 11 byte

āεI¥ô}ʒË}нн

Cobalah online!

āεI ¥ ô} ʒË} нн Program lengkap.
ā Rentang panjang. Tekan [1 ... len (inp)].
 ε} Untuk setiap ...
  Saya ¥ ô ... Memotong delta menjadi potongan-potongan dengan ukuran yang sesuai
      ʒË} Jaga agar hanya mereka yang memiliki semua elemen yang sama.
         нн Dan pertama ambil elemen pertama dari yang pertama.

13 byte

Alternatif yang lucu, IMO:

¥©ηʒDg®ôÙ˜Q}н

Cobalah online!

¥©ηʒDg®ôÙ˜Q}н   Full program.
¥               Push the deltas.
 ©              Copy them to the register.
  ηʒ       }    And filter the prefixes by...
    D     Q     ... Is the prefix itself equal to...
     g®ô        ... The deltas, split into chunks of its length...
        Ù˜      ... Deduplicated and flattened?
            н   Head.
Tuan Xcoder
sumber
1
8 byte dengan menggunakan.
Kevin Cruijssen
3

Javascript, 49 56 byte

Sunting 7 byte yang disimpan, terima kasih (tebak siapa?) Arnauld

Ide regex yang sama seperti Arnauld, tetapi anehnya begitu berbeda dalam implementasinya ...

Mengembalikan string dengan langkah yang dipisahkan koma (dan koma yang memimpin)

p=>/N(.+?)\1+$/.exec(p.map(p=v=>[v-p,p=v][0]))[1]

Uji

var F=
p=>/N(.+?)\1+$/.exec(p.map(p=v=>[v-p,p=v][0]))[1]

;[[1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17]
,[1, 4, 8, 9, 10, 13, 17, 18, 19, 22, 26, 27, 28]
,[6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41] 
,[2, 6, 10, 13, 17, 21, 25, 28, 32, 36, 40, 43, 47]
,[5, 6, 7]]
.forEach(x=>console.log(x + ' -> ' + F(x)))

edc65
sumber
Menggunakan matchadalah keputusan saya yang buruk. Anda bisa mengalahkan saya lagi . :-)
Arnauld
3

MATL , 14 13 12 byte

dt5YLFTF#Xu)

Cobalah online!

Baru saja menemukan bahwa MATL memang memiliki fungsi peredaran darah!

Penjelasan

d - Dapatkan perbedaan antara istilah berturut-turut, sebagai sebuah array

t5YL- duplikat itu, lalu panggil fungsi YL('galeri') dengan 5opsi ('edaran'). Membuat matriks dengan vektor yang diberikan sebagai baris pertama, kemudian baris berturut-turut adalah vektor yang sama bergeser secara melingkar, sampai membungkus.

FTF#Xu- Periksa baris unik dan dapatkan nomor baris mereka (tidak yakin apakah ada cara yang lebih pendek untuk melakukan ini). Ketika langkah-langkah urutan ulangi, baris yang digeser secara melingkar akan sama dengan baris pertama, dan baris berikutnya akan berulang. Jadi ini mendapatkan indeks menjalankan urutan langkah pertama sebelum mereka mulai mengulangi.

) - indeks menggunakannya ke dalam array perbedaan asli, untuk mendapatkan jawabannya.


Lebih tua:

d`tt@YS-a}@:)

Cobalah online!

(-1 byte terima kasih kepada Giuseppe)

Penjelasan:

d   % Get the differences between successive terms, as an array
`   % Start do-while loop
  tt  % duplicate the difference array twice
  @   % push the current loop index value
  YS  % circularly shift the difference array by that amount
  -   % subtract the shifted diffs from the original diffs
  a   % see if the subtraction resulted in any non-zeros
    % if it did, shifted differences were not equal to original differences, so continue loop 
}@ % if it didn't, then get loop index
:) % get the differences upto the loop index, before they started repeating
   % implicit loop end
sundar - Pasang kembali Monica
sumber
2

Python 2 , 101 byte

def f(l):d=[y-x for x,y in zip(l,l[1:])];g=len(l);print[d[:k]for k in range(1,g+1)if g/k*d[:k]==d][0]

Cobalah online!

Pertama menghasilkan delta d , kemudian menemukan awalan p pertama dari d bahwa ketika berulang ⌊len (L) / len (p) ⌋ kali menghasilkan L , di mana L adalah daftar input.

Tuan Xcoder
sumber
2

Ruby , 62 byte

Bergantung pada logika Regex yang diadaptasi dari jawaban Arnauld .

->a{i=-2;a.map{|x|(i+=1)>=0?x-a[i]:0}*?,=~/((,\d+)*?)\1*$/;$1}

Cobalah online!

Alternatif penentuan perbedaan langkah, juga 62 byte:

->a{[0,*a.each_cons(2).map{|x,y|y-x}]*?,=~/((,\d+)*?)\1*$/;$1}

Cobalah online!

Kirill L.
sumber
2

Java 10, 104 100 byte

a->{var t="";for(int i=a.length;i-->1;t+=a[i]-a[i-1]+" ");return t.replaceAll("( ?.+?)\\1*$","$1");}

Regex ( ?.+?)\1*$untuk substring berulang terpendek dari komentar @Neil pada jawaban @ Arnauld 's JavaScript (ES6) .

Cobalah online.

Penjelasan:

a->{                        // Method with integer-array parameter and String return-type
  var t="";                 //  Temp-String, starting empty
  for(int i=a.length;i-->1; //  Loop backward over the input-array, skipping the first item
    t+=a[i]-a[i-1]          //   Calculate the difference between two adjacent items
       +" ");               //   And append this with a space to the temp-String
  return t.replaceAll("( ?.+?)\\1*$", 
                            //  Find the shortest repeating substring
                     "$1");}//  And only keep one such substring
Kevin Cruijssen
sumber
1

APL + WIN, 39 byte

Meminta input.

(↑((⍴v)=+/¨(⊂v)=(⍳⍴v)⌽¨⊂v)/⍳⍴v)↑v←-2-/⎕

Cobalah online! Atas perkenan Dyalog Classic

Penjelasan:

v←-2-/⎕ Prompt for input and take successive differences

(⍳⍴v)⌽¨⊂v create a nested vector ans sequentially rotate by one to length of v

+/¨(⊂v)= compare to original v and sum positions where there is match

(⍴v)= identify where all elements match

(↑(....) identify number of rotations giving a first complete match

(↑(...)↑v take first number of elements from above from v as repeated sequence
Graham
sumber
1

Python 2 , 86 85 byte

def f(a,n=1):d=[y-x for x,y in zip(a,a[1:])];return d[:-n]==d[n:]and d[:n]or f(a,n+1)

Cobalah online!

Bangun perbedaan sebagai d; jika ddiulangi dengan ukuran unit nmaka d[n:]==d[:-n]; lain kambuh.

Chas Brown
sumber
1

Retina 0.8.2 , 42 byte

\d+
$*
(?<=(1+),)\1

1+(.+?)\1*$
$1
1+
$.&

Cobalah online! Tautan termasuk kasus uji. Output termasuk koma terkemuka. Penjelasan:

\d+
$*

Konversikan ke unary.

(?<=(1+),)\1

Hitung perbedaan forward, kecuali untuk angka pertama, yang tertinggal.

1+(.+?)\1*$
$1

Cocokkan perbedaan yang berulang.

1+
$.&

Konversikan ke desimal.

Neil
sumber
1

05AB1E , 14 13 byte

¥DηvÐNƒÁ}QD—#

Cobalah secara online atau verifikasi semua kasus uji .

Saya tahu sudah ada dua jawaban 05AB1E yang lebih pendek diposting oleh @ Mr.Xcoder , tapi saya ingin mencoba pendekatan alternatif ini menggunakan rotasi dan pemeriksaan kesetaraan.
Mungkin dapat golf turun beberapa byte tanpa menjatuhkanÁ .

-1 byte setelah tip @Emigna untuk menghapus register global_variable ( ©dan 2x ®) dan menggunakan Duplicate ( D) dan Triplicate (Ð ) sebagai gantinya.

Penjelasan:

¥             # Calculate the deltas of the input-array
              #  i.e. [1,2,3,5,6,7,9] → [1,1,2,1,1,2]
 D            # Duplicate it
  η           # Push all its prefixes
              #  [1,1,2,1,1,2] → [[1],[1,1],[1,1,2],[1,1,2,1],[1,1,2,1,1],[1,1,2,1,1,2]]
v             # For-each over these prefixes
 Ð            #  Triplicate the (duplicated) deltas-list
  NƒÁ}        #  Rotate the deltas-list N+1 amount of times,
              #  where N is the prefix index (== prefix_length-1)
              #   i.e. [1,1,2] and [1,1,2,1,1,2] (rotate 3 times) → [1,1,2,1,1,2]
      Q       #  If the rotated deltas and initial deltas are equal
              #   [1,1,2,1,1,2] and [1,1,2,1,1,2] → 1
       D—#    #  Print the current prefix-list, and stop the for-each loop
Kevin Cruijssen
sumber
1
Berikut ini adalah 9 (jawaban terpisah karena itu adalah algo yang sangat berbeda, meskipun ia membagikan ¥ η).
Grimmy
@Grimy Apakah Anda akan melalui semua jawaban 05AB1E saya dan golf masing-masing, haha? ; p Jawaban yang bagus (sekali lagi), +1 dari saya.
Kevin Cruijssen
1
Tidak semua dari mereka, saya hanya akan melalui yang tertaut dalam posting ini .
Grimmy
@ Grim Ah, ok, itu masuk akal. :)
Kevin Cruijssen
1

Haskell, 107 byte

let i=map(uncurry(-))$zip(tail x)(init x)in head$filter(\s->take(length i)(concat$repeat s)==i)(tail$inits i)

x adalah array input.

misja111
sumber
Selamat datang di PPCG dan golf Haskell khususnya! Anda tidak dapat mengasumsikan input hadir dalam variabel tertentu, meskipun ini mudah diperbaiki dengan menambahkan sebelumnya f x=. Juga penggunaan initsmemerlukan import Data.List, karena itu bukan bagian dari Prelude: Coba online!
Laikoni
Namun Anda dapat menyimpan beberapa byte: (init x)bisa saja xkarena zipmemotong secara otomatis jika salah satu daftar lebih panjang dari yang lain. Dan untuk map(uncurry(-))$zipada sebuah build-in: zipWith(-). Alih-alih f x=let i=...inAnda dapat menggunakan penjaga pola: f x|i<-...=.
Laikoni
Selain itu, Anda dapat menggunakan pemahaman daftar alih- alih filter, !!0alih- alih headdan cyclealih-alih concat$repeat: Coba online!
Laikoni
@Laikoni Terima kasih banyak atas peningkatan Anda! Anda benar, kode saya memerlukan deklarasi fungsi dan impor untuk Data.List.inits. Tapi saya bertanya-tanya, haruskah itu ditambahkan ke panjang kode? Saya bertanya karena beberapa contoh kode lainnya bergantung pada beberapa kode tambahan juga.
misja111
Ya, itu adalah konsensus umum bahwa byte tersebut termasuk dalam skor. Kami memiliki panduan untuk aturan golf di Haskell yang mencakup sebagian besar kasus ini.
Laikoni
1

Stax , 8 6 byte

░»F\☺»

Jalankan dan debug itu

Berikut adalah versi beranotasi yang belum dibongkar untuk menunjukkan cara kerjanya.

:-  pairwise differences
:(  all leftward rotations of array
u   keep only unique rotations
mh  output the first element from each unique rotation

Jalankan yang ini

rekursif
sumber
1

Perl 6 , 57 byte

{~(.rotor(2=>-1).map:{.[1]-.[0]})~~/^(.+?){}" $0"+$/;~$0}

Menguji

Output dipisahkan oleh ruang ("1 1 2" )

Diperluas:

{      # bare block lambda with implicit parameter $_

  ~(   # stringify (space separated)

    .rotor( 2 => -1 )     # from the input take 2 backup 1, repeat
    .map: { .[1] - .[0] } # subtract each pair to find the differences
  )

  ~~   # smartmatch

  /    # regex

    ^  # beginning of string

    ( .+? ) # match at least one character, but as few as possible
    {}      # make sure $0 is set (probably a compiler bug)
    " $0"+  # match $0 one or more times (with a leading space)

    $  # end of string
  /;

  ~$0  # return the stringified $0
}
Brad Gilbert b2gills
sumber
Seluruh bagian pertama bisa~(.skip Z-$_)
Jo King
1

05AB1E , 9 byte

¥©η.ΔÞ®Å?

Penjelasan:

          # take input implicitly
¥         # deltas, eg [4, 5, 7, 8, 10] -> [1, 2, 1, 2]
 ©        # save this to the global register
  η       # prefixes, eg [1, 2, 1, 2] -> [[1], [1, 2], ...]
   .Δ     # find the first one such that
     Þ    # cycled infinitely, eg [1, 2] -> [1, 2, 1, 2, ...]
       Å? # starts with
      ®   # the global register
          # and implicitly print the found element

Alternatif 9-byte:

¥η.ΔÞ.¥-Ë

Algo yang sama, tetapi alih-alih membandingkan ke daftar delta (yang perlu disimpan / dipulihkan), ini menggunakan (undelta) kemudian membandingkan dengan input (implisit).

Cobalah online!

Grimmy
sumber
0

K4 , 30 byte

Larutan:

(*&d~/:c#'(!c:#d)#\:d)#d:1_-':

Contoh:

q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20
3 1 1 1
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17
1 1 2
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':1, 4, 8, 9, 10, 13, 17, 18, 19, 22, 26, 27, 28
3 4 1 1
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41
5 2
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':2, 6, 10, 13, 17, 21, 25, 28, 32, 36, 40, 43, 47
4 4 3 4
q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':5 6 7
,1

Penjelasan:

Tampaknya lumayan untuk apa yang kita coba pecahkan. Dapatkan delta input dan kemudian buat urutan dan tentukan yang terpendek yang cocok dengannya.

(*&d~/:c#'(!c:#d)#\:d)#d:1_-': / the solution
                           -': / deltas 
                         1_    / drop first
                       d:      / save as d
                      #        / take (#) from
(                    )         / do this together
                 #\:d          / take (#) each-left (\:) from d
          (     )              / do this together
              #d               / count length of d
            c:                 / save as c
           !                   / range 0..c-1
       c#'                     / take c copies of each
   d~/:                        / d equal (~) to each right (/:)
  &                            / where true
 *                             / first one
streetster
sumber
0

Perl 5 -p , 55 byte

s/\d+ (?=(\d+))/($1-$&).$"/ge;s/\d+$//;s/^(.+?)\1*$/$1/

Cobalah online!

Angka dimasukkan sebagai daftar yang dipisahkan oleh spasi. Output adalah format yang sama.

Xcali
sumber