Reconstruir uma sequência aritmética

23

Dada uma sequência aritmética finita de números inteiros positivos, com alguns termos removidos do meio, reconstrua a sequência inteira.

A tarefa

Considere uma sequência aritmética: uma lista de números inteiros positivos na qual a diferença entre dois elementos sucessivos é a mesma.

2 5 8 11 14 17

Agora, suponha que um ou mais números inteiros sejam removidos da sequência, sujeitos às seguintes restrições:

  • Os números inteiros removidos serão termos consecutivos da sequência.
  • O primeiro e o último número inteiro na sequência não serão removidos.
  • Pelo menos três números inteiros permanecerão na sequência.

Para a sequência acima, as possíveis remoções incluem:

2 5 8 14 17  (removed 11)
2 5 17       (removed 8 11 14)
2 14 17      (removed 5 8 11)

Sua tarefa: Dada uma dessas seqüências parciais, reconstrua a sequência completa original.

Detalhes

Você pode assumir que a entrada é válida (tem uma solução) e está faltando pelo menos um termo. Todos os números na sequência serão números inteiros positivos (> 0). A sequência pode ter uma diferença positiva ou negativa entre os termos (ou seja, pode estar aumentando ou diminuindo). Não será uma sequência constante (por exemplo 5 5 5).

Sua solução pode ser um programa completo ou uma função . Qualquer um dos métodos padrão de entrada e saída é aceitável.

Sua entrada e saída podem ser uma string (com qualquer delimitador razoável), uma lista de strings ou uma lista de números. Você pode representar os números em qualquer base que seja conveniente para o seu idioma.

Mencione quaisquer métodos / formatos incomuns de E / S em seu envio, para que outros possam testar seu código mais facilmente.

Casos de teste

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

Isso é ; a resposta mais curta em cada idioma vence.

DLosc
fonte
Relacionado
DLosc 22/11
Teria sido interessante ter a entrada na forma2 5 ... 17
schnaader

Respostas:

9

Haskell , 63 bytes

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

Experimente online!

Basicamente, funciona tentando criar o resultado pela frente e, se isso falhar, por trás. Isso usa o fato de que o primeiro e o último membro da entrada sempre estarão corretos, o fato de que os membros excluídos precisam ser consecutivos e o fato de que sempre haverá pelo menos três itens na entrada. Tudo o que tenho a fazer é supor que o segundo ou penúltimo membro seja preciso e verifique se funciona. Felizmente, Haskell tem uma sintaxe realmente bonita para criar séries aritméticas.

EDIT: obrigado a @xnor por apontar um erro e fornecer uma solução!

user1472751
fonte
5
Embora isso seja bonito, parece que nem sempre funciona: [1,3,4,5][1,3,5].
Xnor
1
E acho que all(`elem`s)cdeveria corrigi-lo com a mesma contagem de bytes.
Xnor
6

05AB1E , 9 8 bytes

Ÿs¥¿Äô€н

Experimente online!

Explicação

  • Construa o intervalo [primeiro, ..., último] com uma diferença de +/- 1
  • Calcular deltas da entrada
  • Obtenha o valor absoluto do MDC dos deltas
  • Divida a faixa completa em pedaços desse tamanho
  • Obter o primeiro elemento de cada pedaço

Salvo 1 byte usando, em gcd of deltasvez de min delta, inspirado pelo usuário202729

Emigna
fonte
5

Brachylog v2, 9 bytes

⊆.s₂ᵇ-ᵐ=∧

Experimente online!

Este é um envio de função. O intérprete Brachylog pode ser feito para avaliar uma função como se fosse um programa completo, fornecendo-a Zcomo um argumento de linha de comando; neste caso, a entrada é especificada no formato, por exemplo, [1, 2, 4]e a saída é retornada em um formato semelhante, por exemplo Z = [1, 2, 3, 4]. (Obviamente, para o envio de uma função, a entrada e a saída não estão em nenhum formato; são apenas listas.)

Na verdade, isso resolve um problema mais difícil do que o solicitado pelo OP: elabora a menor sequência aritmética de números inteiros que contém os valores especificados na ordem especificada, independentemente de as exclusões serem consecutivas ou não. Por usar força bruta, pode ser muito lento se muitos valores forem excluídos.

Explicação

O programa tem três partes principais.

encontra uma superssequência da entrada (isto é, uma sequência que possui a entrada como uma subsequência). Quando há mais de uma saída possível de um programa Brachylog, a saída escolhida é a primeira saída em ordem de desempate, e a ordem de desempate é determinada pelo primeiro comando do programa que possui uma opinião; neste caso, especifica uma ordem que favorece saídas curtas em vez de longas. Portanto, a saída que obteremos será a menor superseqüência da entrada que obedecer às restrições no restante do programa.

.É usado para gerar o valor que vê como entrada (isto é, a superssequência neste caso), mas também afirmar que uma condição específica se mantém nele. Em outras palavras, estamos produzindo a menor superseqüência que obedece a uma condição específica (e ignorando os resultados intermediários usados ​​para ver se ela obedece à condição).

Finalmente, temos s₂ᵇ-ᵐ =, ou seja, "todos os deltas da sequência são iguais", a condição que estamos aplicando à saída. (O valor de retorno disso é uma lista de deltas, em vez da própria superseqüência, e é por isso que precisamos de .para garantir que a coisa certa seja exibida.)

O Brachylog é retido aqui por não ter nenhum built-in que possa lidar com o cálculo de deltas, aplicando uma operação a pares sobrepostos de uma lista ou algo semelhante. Em vez disso, precisamos dizer o que queremos dizer explicitamente: s₂ᵇencontra todos os ( ) substrings ( s) de comprimento 2 ( ) ( é necessário o uso de para manter um vínculo entre incógnitas nos substrings e na superseqüência; o mais comumente usado quebraria isso ligação). Em seguida, -ᵐfaz uma subtração em cada um desses pares para produzir um delta. É irritante ter que escrever cinco bytes s₂ᵇ-ᵐpara algo que a maioria das linguagens de golfe modernas tem, mas é dessa maneira que o codegolf às vezes é, eu acho.


fonte
4

Python 2, 104 97 89 83 71 67 60 bytes

Agradecimentos a Chas Brown por economizar 4 bytes.
Agradecimentos a ovs por economizar 7 bytes.

Insira a lista por argumentos.

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

Experimente online!

Explicação:

Como os removidos são consecutivos, basta verificar as diferenças entre dois pares de elementos consecutivos.

Colera Su
fonte
Você pode salvar 3 bytes substituindo b if b%c else cpor [c,b][b%c>0].
quer
@ChasBrown Obrigado, apesar de logo ter uma abordagem melhor.
Colera Su
1
Bom com o key=abs! Parece que, aqui em diante, as pessoas frequentemente omitem a f=peça, a menos que uma função recursiva seja usada; para que você possa economizar 2 bytes dessa maneira.
quer
1
Além disso, substitua a[-1]-a[-2]por a[2]-a[1]- a lógica é a mesma e você recebe outros 2 bytes.
quer
1
60 bytes
ovs 22/11/19
4

Pitão , 11 bytes

%hS.+SQ}hQe

Experimente aqui!

Agradecimentos a Steven H. por salvar um byte!

Pitão , 12 bytes

%.aiF.+Q}hQe

Experimente aqui!

Como funciona

% .aiF. + Q} hQe ~ Programa completo.

     . + Q ~ Obtenha os deltas.
   iF ~ Reduzido por GCD.
 .a ~ Valor absoluto.
% ~ Modular. Obtenha todo enésimo elemento de ...
        } ~ O intervalo numérico inclusivo entre ...
         hQ ~ O primeiro elemento e ...
           e ~ O último elemento.
Mr. Xcoder
fonte
Presort Qpara que você possa classificar e dar o primeiro elemento em vez de abs(GCD(Q)), como no %hS.+SQ}hQede 11 bytes. Suíte de teste
Steven H.
3

Geléia , 8 bytes

ṂrṀmIg/$

Experimente online!

Notas:

  • Trabalhe apenas em uma versão antiga do Jelly. ( este commit, por exemplo) (onde guse fractions.gcd, que tem o resultado, assina o mesmo que o sinal de entrada, em vez de math.gcd, que sempre retorna valor positivo).

  • O link TIO acima é o link Python 3 TIO, o código Python consiste no código-fonte Jelly da confirmação mencionada acima, com exceção de tudo (3 arquivos) compactados no mesmo arquivo (para execução do TIO) e dictionary.pyfoi reduzido para apenas algumas linhas. No entanto, dictionary.pynão está relacionado a esta resposta, pois não usa string compactada. (a “...»construção)

Explicação:

Primeiro, como um segmento contínuo é excluído e pelo menos três elementos permanecem, há dois números consecutivos na lista antiga e os deltas serão todos múltiplos da etapa. Portanto, a lista gcddas diferenças ( I, incrementos) será o valor absoluto da etapa.

Felizmente o documento gcdestá assinado (veja a nota acima)

Então o programa faz:

ṂrṀ

Um número inteiro crescente do mínimo ao aximal.

m

Modular, escolha todos os enésimos elementos.

Ig/$

Combinação de $cadeia monádica ( ) combinada I(incrementos, diferenças) e g/(redução de gcdelementos da lista). Se os incrementos forem positivos, gcdserá positivo e a lista de retorno será da esquerda para a direita (crescente) e vice-versa.

user202729
fonte
Yay! Bate a resposta 05AB1E em 1 byte!
user202729
Usando em gcdvez de minnos fez amarrar. Pena que eu obter um gcd com sinal, caso contrário eu estaria no 7;)
Emigna
3

MATL , 13 bytes

1)0GdYkG0)3$:

Experimente online!

Explicação:

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

JavaScript (ES6), 92 90

Editar 2 bytes salvos thx Arnauld

Fácil, pois basta verificar as diferenças entre os dois primeiros e os dois últimos. Mas ainda incrivelmente longo.

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

Menos golfe

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

Teste

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
fonte
a-=d=e*e>d*d?d:edeve funcionar e salvar 2 bytes.
Arnauld
@Arnauld funciona de fato graças
edc65
2

Wolfram Language (Mathematica) , 50 bytes

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

Experimente online!

JungHwan Min
fonte
Uma "lista de números" inclui ter os números como argumentos individuais? Nesse caso, parece que você poderia salvar um bom número de bytes.
numbermaniac
@numbermaniac Eu não penso assim, uma vez que não é um builtin que busca a última entrada ...
JungHwan Min
Ahh ... verdade. Esqueceu sobre isso.
numbermaniac
Você pode usar {##}e Last@{##}, mas o melhor que eu poderia conseguir com que foi de 51 bytes.
Numbermaniac
2

Ruby , 65 62 55 54 bytes

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

Experimente online!

-1 byte graças a Justin Mariner

GB
fonte
Você pode salvar um byte removendo-o he deixando-o com a,*,b,c. Experimente online!
Justin Mariner
1

Haskell , 73 69 bytes

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

Experimente online!

Laikoni
fonte
1
Encontrei uma solução de 63 bytes, mas é bem diferente da sua. Devo fazer um post separado?
user1472751
@ user1472751 Não sou Laikoni, mas este site foi destinado à competição e também à colaboração. Então eu postaria.
H.PWiz
@ user1472751 Boa abordagem! Por favor, vá em frente e publique como sua própria resposta.
Laikoni
1

J , 49, 47 46 bytes

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

Inspirado pela solução da Emigna.

Como funciona:

 (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

Experimente online!

Galen Ivanov
fonte
1

Casca , 9 bytes

m←C▼Ẋ≠⁰…⁰

Experimente online!

Muito obrigado a H.PWiz por reduzir pela metade a contagem de bytes, apontando que a aplicação em uma lista a varia!

Mr. Xcoder
fonte
@ HP.Wiz X_X Eu não sabia que Husk lista intervalos como esse ... Tem certeza de que não deseja publicá-lo como sua própria resposta separada?
Mr. Xcoder
@ HP.Wiz Muito obrigado !
Xcoder
Além disso, pode F⌋ser substituído por ?
H.PWiz
@ H.PWiz @ _ @ Por que isso funciona?
Mr. Xcoder
A menor diferença (absoluta) será a diferença original. A única razão para isso gcdfoi lidar com deltas negativos #
2117 H.PWiz
1

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

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;}

Experimente online!

+13 para using System;

Surpreendentemente, esse desafio teve mais nuances do que eu previ inicialmente.

Agradecimentos

-22 bytes salvos devido a algumas simplificações puras do @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
fonte
0

Python 2 , 147 bytes

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

Experimente online!

Neil
fonte
0

Python 2 , 78 bytes

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

Experimente online!

Chas Brown
fonte
77 bytes
ovs 22/11/2017
0

dc , 64 bytes

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

Experimente online!

R. Kap
fonte
0

Japonês , 12 bytes

ÌõUg Uäa ñ g

Tente


Explicação

Gere uma matriz de números inteiros ( õ) do último elemento da matriz de entrada ( Ì) para o primeiro ( Ug). Calcule a etapa entre os elementos, obtendo todos os dois pares de elementos da entrada e reduzindo-os pela diferença absoluta ( Uäa), classificando ( ñ) essa matriz e obtendo o primeiro elemento ( g).

Shaggy
fonte