Obtenha as etapas da sequência

17

Desafio

Dada uma sequência de números, crie uma função que retorne as etapas da sequência.

  • Suponha que uma sequência será N >= 3
  • A sequência repetirá as etapas pelo menos uma vez
  • Sequência conterá apenas números naturais
  • Sua função ou programa deve retornar a menor seqüência possível de etapas

Exemplo:

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

Resultado: [1, 1, 2]

Explicação: A sequência inicial vai de1 => 2 (1 step), 2 => 3 (1 step), 3 => 5 (2 steps) . Então repete. A saída é então[1 step, 1 step, 2 steps] => [1, 1, 2]

Outro exemplo:

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

Resultado: [3, 1, 1, 1]

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

Casos de teste

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]


Esclarecimentos

  • O comprimento de entrada - 1 é divisível pelo comprimento de saída
  • Suponha que a sequência sempre aumentará

Isso é , então a resposta mais curta em bytes vence.

Luis felipe De jesus Munoz
fonte
Desafio relacionado .
AdmBorkBork
6
Vi alguns desafios que você postou recentemente com muitos comentários esclarecedores, e alguns foram encerrados como "pouco claros" e, em seguida, reabridos depois de fazer as edições apropriadas. Você já pensou em publicá-las na sandbox por alguns dias / semana? Eu apreciei seus desafios, pois eles são bastante acessíveis, mas todos os desafios, por mais simples ou por quem sejam publicados, podem usar refinamento.
Giuseppe
2
@ Giuseppe Obrigado por suas sugestões. Eu publiquei alguns outros desafios na caixa de areia (geralmente, se eu não conseguir o caminho certo para criar um desafio, eu o excluo). Para esses desafios, achei que eles eram claros o suficiente e foi por isso que postei imediatamente, mas vou começar a publicá-los na sandbox primeiro. Obrigado
Luis felipe De jesus Munoz
2
@LuisMendo Heretic! 0 é um número natural! Billy Joel ainda teve um álbum inteiro dedicado ao Peano Man!
ngm
1
@AdmBorkBork, isso está mais relacionado em virtude de lidar com listas de operações de tamanho arbitrário.
Peter Taylor

Respostas:

10

Geléia , 9 7 bytes

IsJEƇḢḢ

Experimente online!

Como funciona

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
fonte
9

JavaScript (ES6), 58 bytes

Gera uma sequência separada por vírgula (com uma vírgula inicial).

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

Experimente online!

Ou 56 bytes, se usarmos ,-como separador e assumirmos que a sequência é sempre estritamente aumentando .

Quão?

Primeiro convertemos a matriz de entrada a [] em uma lista de diferenças consecutivas com:

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

Como p é inicialmente definido como um valor não numérico (a função de retorno de chamada de map () ), a primeira iteração gera NaN .

Exemplo:

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

Coagimos então o resultado a uma string:

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

Finalmente, procuramos o menor padrão 1 de números inteiros separados por vírgula ( ,\d+) começando logo após "NaN" e repetindo até o final da string:

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

1: usando o não ganancioso *?

Arnauld
fonte
Estou postando uma solução baseada na mesma ideia de regex, mas muito diferente na implementação. É claro que eu não olhei para outras soluções antes de desenvolver as minhas, e parece bastante diferente. E talvez seja a primeira vez que eu consiga pontuar melhor do que você aqui.
Edc65 6/06/19
1
53 bytes: /(,.+?)\1*$/.
911 Neil
6

Braquilog , 11 bytes

s₂ᶠ-ᵐṅᵐ~j₍t

Experimente online!

Seriam 5 bytes se houvesse um interno para diferenças consecutivas.

Explicação

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]
Fatalizar
fonte
Você pode negar após a cauda, ​​para salvar um byte?
Rod
@ Rod Eu ainda precisaria mapeá-lo, por isso teria o mesmo comprimento. Negar é um predicado entre dois números, isso não acontece vectorize automaticamente para listas como outras línguas (caso contrário ele não iria trabalhar bem com desconhecidos entradas / saídas que são comuns em programas declarativas)
Fatalize
5

Pitão, 11 bytes

<J.+Qf.<IJT

Experimente aqui

Explicação

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

fonte
5

Japonês , 14 12 bytes

äa
¯@eUéX}aÄ

Tente


Explicação

              :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

Original

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

Tente

Shaggy
fonte
5

R , 49 46 bytes

Programa completo:

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

Experimente online!

R , 72 58 54 bytes

Envio da função original com todos os casos de teste em um só lugar:

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

Experimente online!

Agradecemos a JayCe por sugerir a rota completa do programa e -4 bytes na função, e a Giuseppe por mais -3.

Kirill L.
fonte
-9 bytes abusando de um built-in e tornando-o um programa completo O desafio permite um programa completo.
Jayce
@JayCe não precisa a<-aqui também
Giuseppe
4

J , 22 19 bytes

3 bytes salvos graças ao FrownyFrog!

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

Experimente online!

[Experimente online!] [TIO-ji2uiwla]

Quão?

                 -      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
fonte
Se você, em /:vez de #\, poderá 0{"1[:~.salvar 1 byte.
FrownyFrog
E "0 1é #"{
FrownyFrog
@FrownyFrog Obrigado, mais uma vez!
Galen Ivanov
1
Isso é lindo.
Jonah
@ Jonah Sim, obrigado a FrownyFrog!
Galen Ivanov
4

05AB1E , 8 bytes

Economizou 3 bytes graças a Kevin Cruijssen .

¥.œʒË}нн

Experimente online!


05AB1E , 11 bytes

āεI¥ô}ʒË}нн

Experimente online!

āεI ¥ ô} ʒË} нн Programa completo.
range Faixa de comprimento. Pressione [1 ... len (inp)].
 ε} Para cada ...
  I ¥ ô ... Pique os deltas em pedaços do tamanho correspondente
      Mantenha apenas aqueles que têm todos os seus elementos iguais.
         нн E primeiro recupere o primeiro elemento do primeiro.

13 bytes

Uma alternativa atraente, IMO:

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

Experimente 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.
Mr. Xcoder
fonte
1
8 bytes usando.
Kevin Cruijssen
3

Javascript, 49 56 bytes

Editar 7 bytes salvos, obrigado (adivinhe quem?)

Mesma ideia de regex que Arnauld, mas curiosamente tão diferente na implementação ...

Retornando uma sequência com etapas separadas por vírgula (e uma vírgula inicial)

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

Teste

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
fonte
Usar matchfoi uma péssima decisão minha. Você pode me superar um pouco mais . :-) #
584 Arnauld
3

MATL , 14 13 12 bytes

dt5YLFTF#Xu)

Experimente online!

Acabei de descobrir que o MATL tem uma função circulante!

Explicação

d - Obtenha as diferenças entre termos sucessivos, como uma matriz

t5YL- duplique isso e chame a função YL('galeria') com5 ('circulante'). Cria uma matriz com o vetor fornecido como primeira linha e, em seguida, as linhas sucessivas são movidas circularmente até o mesmo vetor, até que se envolva.

FTF#Xu- Verifique se há linhas exclusivas e obtenha seus números de linha (não tenho certeza se há uma maneira mais curta de fazer isso). Quando as etapas da sequência se repetem, a linha deslocada circularmente é a mesma que a primeira linha e as linhas subseqüentes serão repetidas. Portanto, isso obtém os índices da primeira execução das etapas da sequência antes que eles comecem a repetir.

) - indexe usando isso na matriz de diferenças original, para obter a resposta.


Mais velho:

d`tt@YS-a}@:)

Experimente online!

(-1 byte graças a Giuseppe)

Explicação:

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 - Restabelecer Monica
fonte
2

Python 2 , 101 bytes

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]

Experimente online!

Primeiro gera os deltas d , depois encontra o primeiro prefixo p de d que, quando repetido ⌊len (L) / len (p) ⌋ vezes, produz L , onde L é a lista de entrada.

Mr. Xcoder
fonte
2

Ruby , 62 bytes

Baseia-se na lógica Regex adaptada da resposta de Arnauld .

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

Experimente online!

Determinação alternativa de diferenças de etapas, também 62 bytes:

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

Experimente online!

Kirill L.
fonte
2

Java 10, 104 100 bytes

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

Regex ( ?.+?)\1*$para menor repetindo substring de @Neil 'comentário s sobre @Arnauld ' JavaScript resposta s (ES6) .

Experimente online.

Explicação:

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
fonte
1

APL + WIN, 39 bytes

Solicitar entrada.

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

Experimente online! Cortesia de Dyalog Classic

Explicação:

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
fonte
1

Python 2 , 86 85 bytes

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)

Experimente online!

Construa as diferenças como d; se drepete com o tamanho da unidade nentão d[n:]==d[:-n]; mais recurse.

Chas Brown
fonte
1

Retina 0.8.2 , 42 bytes

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

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

Experimente online! O link inclui casos de teste. A saída inclui vírgula inicial. Explicação:

\d+
$*

Converta para unário.

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

Calcule as diferenças para a frente, exceto o primeiro número, que é deixado para trás.

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

Corresponder às diferenças repetidas.

1+
$.&

Converta para decimal.

Neil
fonte
1

05AB1E , 14 13 bytes

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

Experimente online ou verifique todos os casos de teste .

Eu sei que já existem duas respostas 05AB1E mais curtas postadas por @ Mr.Xcoder , mas eu queria tentar essa abordagem alternativa usando rotação e verificação de igualdade.
Pode ser capaz de jogar alguns bytes sem cair Á.

-1 byte após uma dica de @Emigna para remover os registros global_variable ( ©e 2x ®) e usar um Duplicate ( D) e um Triplicate (Ð ).

Explicação:

¥             # 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
fonte
1
Aqui está um 9 (resposta separada, pois é um algo muito diferente, embora ele compartilhe o ¥ η).
Grimmy
@Grimy Você está passando por todas as minhas respostas 05AB1E e jogando golfe em cada uma delas, haha? ; p Boa resposta (mais uma vez), +1 de mim.
Kevin Cruijssen
1
Nem todos eles, estou apenas passando por aqueles que estão vinculados neste post .
Grimmy
@ Grimy Ah ok, isso faz sentido. :)
Kevin Cruijssen
1

Haskell, 107 bytes

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

x é a matriz de entrada.

misja111
fonte
Bem-vindo ao PPCG e Haskell, em particular! Você não pode presumir que a entrada esteja presente em uma determinada variável, embora isso seja facilmente corrigido pela adição antecipada f x=. Além disso, o uso de initsexige import Data.List, pois não faz parte do Prelude: Experimente online!
Laikoni 6/06/19
No entanto, você pode salvar alguns bytes: (init x)pode ser xporque ziptrunca automaticamente se uma das listas for maior que a outra. E para map(uncurry(-))$zipexiste uma build-in: zipWith(-). Em vez de f x=let i=...invocê pode usar um guarda padrão: f x|i<-...=.
Laikoni 6/06/19
Além disso, você pode usar uma compreensão da lista em vez de filter, em !!0vez de heade em cyclevez de concat$repeat: Experimente online!
Laikoni 6/06/19
@Laikoni Muito obrigado por suas melhorias! Você está certo, meu código precisa de uma declaração de função e de uma importação para Data.List.inits. Mas eu queria saber, isso deveria ser adicionado ao comprimento do código? Estou perguntando porque alguns dos outros exemplos de código também contam com algum código extra.
misja111
Sim, é consenso geral que esses bytes sejam incluídos na pontuação. Temos um guia sobre regras de golfe em Haskell, que abrange a maioria desses casos.
precisa saber é o seguinte
1

Stax , 8 6 bytes

░»F\☺»

Execute e depure

Aqui está uma versão anotada descompactada para mostrar como funciona.

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

Execute este

recursivo
fonte
1

Perl 6 , 57 bytes

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

Teste-o

A saída é separada por espaço ( "1 1 2")

Expandido:

{      # 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
fonte
Toda a primeira parte pode ser~(.skip Z-$_)
Jo King
1

05AB1E , 9 bytes

¥©η.ΔÞ®Å?

Explicação:

          # 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

Alternativa de 9 bytes:

¥η.ΔÞ.¥-Ë

O mesmo, mas em vez de comparar com a lista de deltas (que precisa ser salva / restaurada), isso usa (undelta) e compara com a entrada (implícita).

Experimente online!

Grimmy
fonte
0

K4 , 30 bytes

Solução:

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

Exemplos:

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

Explicação:

Parece pesado para o que estamos tentando resolver. Obtenha os deltas da entrada e, em seguida, construa sequências e determine a menor que corresponda a ela.

(*&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
rua
fonte
0

Perl 5 -p , 55 bytes

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

Experimente online!

Os números são inseridos como uma lista separada por espaços. Saída é o mesmo formato.

Xcali
fonte