Reconstruir una secuencia aritmética.

23

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 ; gana la respuesta más corta en cada idioma.

DLosc
fuente
Relacionado
DLosc
2 5 ... 17
Hubiera

Respuestas:

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

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!

usuario1472751
fuente
55
Aunque esto es bonito, parece que no siempre funciona: [1,3,4,5]da [1,3,5].
xnor
1
Y creo que all(`elem`s)cdebería solucionarlo con el mismo número de bytes.
xnor
6

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

Emigna
fuente
5

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.


fuente
4

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.

Colera Su
fuente
Puede guardar 3 bytes reemplazando b if b%c else ccon [c,b][b%c>0].
Chas Brown
@ChasBrown Gracias, aunque pronto se me ocurrió un mejor enfoque.
Colera Su
1
Agradable con el key=abs! Parece que por aquí, las personas a menudo omiten la f=parte a menos que se use una función recursiva; para que pueda guardar 2 bytes de esa manera.
Chas Brown
1
Además, reemplace a[-1]-a[-2]con a[2]-a[1]: la lógica es la misma y obtiene otros 2 bytes.
Chas Brown el
1
60 bytes
ovs
4

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.
Sr. Xcoder
fuente
Ordenar previamente Qpara que pueda ordenar y tomar el primer elemento en lugar de abs(GCD(Q))como en %hS.+SQ}hQe11 bytes. Test suite
Steven H.
3

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.

usuario202729
fuente
¡Hurra! ¡Supera la respuesta 05AB1E por 1 byte!
user202729
Usar en gcdlugar de minhacernos atar. Lástima que obtengo un mcd con signo, de lo contrario estaría a las 7;)
Emigna
3

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.

Giuseppe
fuente
3

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

edc65
fuente
a-=d=e*e>d*d?d:edebería funcionar y guardar 2 bytes.
Arnauld el
@Arnauld funciona realmente gracias
edc65
2

Wolfram Language (Mathematica) , 50 bytes

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

Pruébalo en línea!

JungHwan Min
fuente
¿Una "lista de números" incluye tener los números como argumentos individuales? Si es así, parece que podría guardar una buena cantidad de bytes.
númeromaniac
@numbermaniac No lo creo, ya que no hay un generador incorporado que obtenga la última entrada ...
JungHwan Min
Ahh ... cierto. Olvidé eso.
númeromaniac
Puedes usar {##}y, Last@{##}pero lo mejor que pude obtener con eso fue 51 bytes.
númeromaniac
1

Haskell , 73 69 bytes

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

Pruébalo en línea!

Laikoni
fuente
1
Encontré una solución de 63 bytes pero es bastante diferente de la tuya. ¿Debo hacer una publicación separada?
user1472751
@ user1472751 No soy Laikoni, pero este sitio estaba destinado a la competencia, así como a la colaboración. Entonces lo publicaría.
H.PWiz
@ user1472751 ¡Buen enfoque! Por favor, adelante y publíquelo como su propia respuesta.
Laikoni
1

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!

Galen Ivanov
fuente
1

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

Sr. Xcoder
fuente
@ HP.Wiz X_X No sabía que Husk enumera rangos como ese ... ¿Estás seguro de que no quieres publicarlo como tu propia respuesta por separado?
Sr. Xcoder
@ HP.Wiz ¡Muchas gracias !
Sr. Xcoder
Además, puede F⌋ser reemplazado por ?
H.PWiz
@ H.PWiz @ _ @ ¿Por qué eso funciona?
Sr. Xcoder
La diferencia más pequeña (absoluta) será la diferencia original. La única razón para que gcdera para hacer frente a los deltas negativos
H.PWiz
1

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;
}
Ayb4btu
fuente
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))

Pruébalo en línea!

Neil
fuente
0

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

Lanudo
fuente