Dada una secuencia aritmética finita de enteros positivos con algunos términos eliminados del medio, reconstruya toda la secuencia.

La tarea

Considere una secuencia aritmética: una lista de enteros positivos en los que la diferencia entre dos elementos sucesivos es la misma.

2 5 8 11 14 17

Ahora suponga que uno o más enteros se eliminan de la secuencia, sujeto a las siguientes restricciones:

• Los enteros eliminados serán términos consecutivos de la secuencia.
• El primer y el último número entero de la secuencia no se eliminarán.
• Al menos tres enteros permanecerán en la secuencia.

Para la secuencia anterior, las posibles eliminaciones incluyen:

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

Su tarea: Dada una de estas secuencias parciales, reconstruya la secuencia completa original.

Detalles

Puede suponer que la entrada es válida (tiene una solución) y le falta al menos un término. Todos los números en la secuencia serán enteros positivos (> 0). La secuencia puede tener una diferencia positiva o negativa entre los términos (es decir, puede estar aumentando o disminuyendo). No será una secuencia constante (p 5 5 5. Ej .).

Su solución puede ser un programa completo o una función . Cualquiera de los métodos de entrada y salida predeterminados son aceptables.

Su entrada y salida puede ser una cadena (con cualquier delimitador razonable), una lista de cadenas o una lista de números. Puede representar los números en cualquier base que sea conveniente para su idioma.

Mencione cualquier método / formato de E / S inusual en su envío, para que otros puedan probar su código más fácilmente.

Casos de prueba

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

Este es el código de golf ; gana la respuesta más corta en cada idioma.

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

Pruébalo en línea!

Básicamente funciona tratando de construir el resultado desde el frente y, si eso falla, desde la parte posterior. Esto utiliza el hecho de que el primer y el último miembro de la entrada siempre serán correctos, el hecho de que los miembros eliminados deben ser consecutivos y el hecho de que siempre habrá al menos tres elementos en la entrada. Todo lo que tengo que hacer es asumir que el segundo o el penúltimo miembro son precisos y verificar si funciona. Afortunadamente, Haskell tiene una sintaxis realmente hermosa para crear series aritméticas.

EDITAR: ¡gracias a @xnor por señalar un error y proporcionar una solución!

05AB1E , 9 8 bytes

Ÿs¥¿Äô€н

Pruébalo en línea!

Explicación

• Construya el rango [primero, ..., último] con una diferencia de +/- 1
• Calcular deltas de la entrada
• Obtenga el valor absoluto de la mcd de los deltas
• Divida el rango completo en trozos de ese tamaño
• Obtén el primer elemento de cada fragmento

Se guardó 1 byte usando en gcd of deltaslugar de min delta, inspirado por el usuario202729

Brachylog v2, 9 bytes

⊆.s₂ᵇ-ᵐ=∧

Pruébalo en línea!

Esta es una presentación de función. Se puede hacer que el intérprete Brachylog evalúe una función como si fuera un programa completo proporcionándola Zcomo un argumento de línea de comando; en este caso, la entrada se especifica en el formato, por ejemplo, [1, 2, 4]y la salida se devuelve en un formato similar, por ejemplo Z = [1, 2, 3, 4]. (Por supuesto, para el envío de una función, la entrada y la salida no están en ningún formato; son solo listas).

En realidad, esto resuelve un problema más difícil que el que solicitó el OP: resuelve la secuencia aritmética más corta de enteros que contienen los valores especificados en el orden especificado, independientemente de si las eliminaciones son consecutivas o no. Debido a que usa la fuerza bruta, puede ser muy lento si se eliminan muchos valores.

Explicación

El programa tiene tres partes principales.

⊆encuentra una supersecuencia de la entrada (es decir, una secuencia que tiene la entrada como subsecuencia). Cuando hay más de una salida posible de un programa Brachylog, la salida elegida es la primera salida en orden de desempate, y el orden de desempate se determina por el primer comando en el programa que tiene una opinión al respecto; en este caso, ⊆especifica un orden que favorece las salidas cortas sobre las largas. Entonces, la salida que obtendremos será la supersecuencia más corta de la entrada que obedece a las restricciones en el resto del programa.

.... ∧se utiliza para generar el valor que ve como entrada (es decir, la supersecuencia en este caso), pero también afirma que una condición específica se mantiene en él. En otras palabras, estamos generando la supersecuencia más corta que obedece a una condición específica (e ignoramos los resultados intermedios utilizados para ver si obedece a la condición).

Finalmente, tenemos s₂ᵇ-ᵐ =, es decir, "todos los deltas de la secuencia son iguales", la condición que estamos aplicando a la salida. (El valor de retorno de esto es una lista de deltas, en lugar de la supersecuencia en sí misma, por eso necesitamos .... ∧para asegurarnos de que salga lo correcto).

Brachylog se retiene aquí al no tener ningún componente interno que pueda manejar el cálculo de deltas, aplicando una operación a pares superpuestos de una lista o similares. En cambio, tenemos que decir lo que queremos decir explícitamente: s₂ᵇencuentra todas ( ᵇ) las subcadenas ( s) de longitud 2 ( ₂) ( ᵇse requiere el uso de para mantener un vínculo entre las incógnitas en las subcadenas y en la supersecuencia; el uso más común ᶠrompería esto enlazar). Luego -ᵐhace una resta en cada uno de estos pares para producir un delta. Es molesto tener que escribir cinco bytes s₂ᵇ-ᵐpara algo para lo que la mayoría de los lenguajes de golf modernos tienen incorporado, pero esa es la forma en que va el codegolf a veces, supongo.

Python 2, 104 97 89 83 71 67 60 bytes

Gracias a Chas Brown por guardar 4 bytes.
Gracias a ovs por guardar 7 bytes.

Ingrese la lista por argumentos.

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

Pruébalo en línea!

Explicación:

Como los eliminados son consecutivos, es suficiente verificar las diferencias entre dos pares de elementos consecutivos.

Pyth , 11 bytes

%hS.+SQ}hQe

Pruébalo aquí!

¡Gracias a Steven H. por guardar un byte!

Pyth , 12 bytes

%.aiF.+Q}hQe

Pruébalo aquí!

Cómo funciona

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

     . + Q ~ Obtener los deltas.
   iF ~ Reducir por GCD.
 .a ~ Valor absoluto.
% ~ Modular. Obtenga cada enésimo elemento de ...
        } ~ El rango numérico inclusivo entre ...
         hQ ~ El primer elemento, y ...
           e ~ El último elemento.

Jalea , 8 bytes

ṂrṀmIg/$

Pruébalo en línea!

Notas:

• Solo funciona en alguna versión antigua de Jelly. ( esta confirmación, por ejemplo) (donde guse fractions.gcd, que tiene el signo de resultado igual que el signo de entrada, en lugar de math.gcd, que siempre devuelve un valor positivo).

• El enlace TIO anterior es el enlace Python 3 TIO, el código Python consiste en el código fuente Jelly de la confirmación que mencioné anteriormente, con la excepción de todo (3 archivos) empaquetados en el mismo archivo (para que se ejecute TIO) y dictionary.pyse ha reducido a Solo algunas líneas. Sin embargo, dictionary.pyno está relacionado con esta respuesta, ya que no utiliza una cadena comprimida. (la “...»construcción)

Explicación:

Primero, debido a que se elimina un segmento continuo y quedan al menos 3 elementos, quedan dos números consecutivos en la lista anterior, y todos los deltas serán múltiplos del paso. Por lo tanto, la lista gcdde diferencias ( I, incrementos) será el valor absoluto del paso.

Afortunadamente el gcdestá firmado (ver nota arriba)

Entonces el programa hace:

ṂrṀ

Un rango entero creciente desde el Ṃmínimo hasta el Ṁmáximo.

m

Modular, elige cada enésimo elemento.

Ig/$

Combinación de $cadena monádica ( ) I(incrementos, diferencias) y g/(reducción gcdsobre elementos de la lista). Si los incrementos son positivos, entonces gcdserá positivo y la lista de retorno será de izquierda a derecha (en aumento), y viceversa.

MATL , 13 bytes

1)0GdYkG0)3$:

Pruébalo en línea!

Explicación:

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.

JavaScript (ES6), 92 90

Editar 2 bytes guardados gracias a Arnauld

Fácil, ya que es suficiente para comprobar las diferencias entre los dos primeros y los dos últimos. Pero aún así increíblemente largo.

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

Prueba

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

Wolfram Language (Mathematica) , 50 bytes

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

Pruébalo en línea!

Ruby , 65 62 55 54 bytes

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

Pruébalo en línea!

-1 byte gracias a Justin Mariner

Haskell , 73 69 bytes

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

Pruébalo en línea!

J , 49, 47 46 bytes

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

Inspirado en la solución de Emigna.

Cómo 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

Pruébalo en línea!

Casco , 9 bytes

m←C▼Ẋ≠⁰…⁰

Pruébalo en línea!

¡Muchas gracias a H.PWiz por reducir a la mitad el recuento de bytes, señalando que aplicar …en una lista lo rangifica! ...

C # (.NET Core) , 167 + 13 = 180145 + 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;}

Pruébalo en línea!

+13 para using System;

Sorprendentemente, este desafío tenía más matices de lo que inicialmente anticipé.

Expresiones de gratitud

-22 bytes guardados debido a algunas simplificaciones claras de @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;
}

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

Pruébalo en línea!

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

Pruébalo en línea!

Jalea , 8 bytes

ṂrṀmILÞṪ

Pruébalo en línea!

dc , 64 bytes

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

Pruébalo en línea!

Japt , 12 bytes

ÌõUg Uäa ñ g

Intentalo

Explicación

Genere una matriz de enteros ( õ) desde el último elemento de la matriz de entrada ( Ì) hasta el primero ( Ug). Calcule el paso entre elementos obteniendo los dos pares de elementos de la entrada y reduciéndolos por diferencia absoluta ( Uäa) luego ordenando ( ñ) esa matriz y tomando el primer elemento ( g).