Hazme una suma mágica mínima

27

Manteniendo este desafío corto.

Te dan 4 números: p1, p2, p3 y p4.

La suma mágica de los números se define de la siguiente manera:

magic_sum = |p1 - p2| + |p2 - p3| + |p3 - p4| + |p4 - p1|

Solo puede cambiar uno de los valores enteros anteriores (p1, p2, p3 o p4). Debe cambiar el valor de modo que la suma mágica de los valores alcance su valor mínimo.

Por ejemplo:

p1, p2, p3, p4 = 17, -6, 15, 33. El valor de la suma mágica es 78 en este caso.

Puede cambiar el -6 aquí a 16, y el valor de la suma mágica se convertirá en 36, que es el valor mínimo alcanzable.

Tenga en cuenta que los números pueden ser enteros positivos o negativos.

Este es el código de golf, por lo que gana menos bytes en el código. Brownie apunta por usar un lenguaje práctico sobre un lenguaje recreativo. Que el 4 de mayo esté contigo.

Reiterar:

Muestra 1

Entrada 1

17 -6 15 33

Salida 1

36

Explicacion 1

El -6 puede ser reemplazado por 16 y eso nos da la mínima suma mágica posible.

Muestra 2

Entrada 2

10 10 10 10

Salida 2

0 or 2

cualquiera es aceptable

Explicacion 2

La suma mágica mínima alcanzable es 0 ya que la suma mínima de 4 enteros positivos es 0. Si se debe cambiar un número, entonces uno de los 10 se puede cambiar a un 9 y, por lo tanto, producir la salida 2.

Muestra 3

Entrada 3

1 2 3 4

Salida 3

4

Explicación 3

La entrada por sí sola produce 6 como su suma mágica. Cambiando el 4 a 1 y se obtiene la suma mágica mínima, que es 4.

Koishore Roy
fuente
10
+1, pero podría hacer con más ejemplos.
Jonathan Allan
2
Un ejemplo completamente trabajado y un par de casos de prueba más y es +1de mi parte.
Shaggy
@Shaggy hecho. ¿Dónde está mi +1? : P
Koishore Roy
1
@KoishoreRoy ¿No probaría el caso 3 ser 6 sin el cambio?
wizzwizz4
@ wizzwizz4 | 1 - 2 | + | 2 - 3 | + | 3 - 4 | + | 4 - 1 | = 1 + 1 + 1 + 3 = 6. Estás en lo correcto. Hizo la edición.
Koishore Roy

Respuestas:

14

Jalea , 6 bytes

ṢŒœIṂḤ

Pruébalo en línea!

Un puerto de mi respuesta Python .

     (input)        [17, -6, 15, 33]
Ṣ    sort           [-6, 15, 17, 33]
Œœ   odd-even elts  [[-6, 17], [15, 33]]
I    increments     [23, 18]
M    minimum        18
Ḥ    double         36 
xnor
fuente
20

Python 2 , 44 bytes

a,b,c,d=sorted(input())
print min(c-a,d-b)*2

Pruébalo en línea!

Ordena la entrada como a,b,c,d,en orden ascendente, toma la menor de c-ay d-b, y la duplica. ¿Por qué funciona esto?

Primero, tenga en cuenta que cuando cambiamos un elemento para maximizarlo a la suma cíclica total de distancias, es óptimo (o empatado para óptimo) cambiarlo para que sea igual a un vecino, como 17, -6, 15, 33 -> 17, 17, 15, 33. Esto se debe a que su nueva distancia total a sus vecinos cíclicos izquierdo y derecho es al menos la distancia entre esos vecinos, por lo que hacer que estos sean iguales es lo mejor que podemos hacer.

Ahora, eliminar una de las dos copias adyacentes de un número da la misma suma cíclica de distancias. En el ejemplo, esto es 17, 15, 33, dar distancias 2 + 18 + 16. Entonces, en lugar de reemplazar uno de los cuatro números, es equivalente a eliminarlo dejando tres números y usar la suma de sus distancias cíclicas.

Observe que con 3 números, la distancia más grande es la suma de los dos más pequeños. Esto se debe a que si clasificamos los números a tener a ≤ b ≤ c, entonces |a - c| = |a - b| + |b - c|. En otras palabras, viajamos entre el número más grande y el más pequeño dos veces, utilizando el número medio como parada en boxes una de las veces. Entonces, la suma de las tres distancias es solo el doble de la distancia entre el mínimo y el máximo, entonces (c-a)*2.

Entonces, la pregunta es qué número eliminamos para obtener la distancia más pequeña entre el mínimo y el máximo de los tres números restantes. Claramente eliminamos el más pequeño o el más grande de los números. Al llamarlos a, b, c, den orden ordenado, eliminar ahojas d - by eliminar dhojas c - a, y el resultado final es el doble, el que sea más pequeño.

xnor
fuente
ayúdame con un caso de prueba aquí. ¿Qué pasa si la suma mágica ya es 0, que es el número más bajo posible? en ese caso, ¿la respuesta debería ser 0? o el siguiente número más bajo posible. En caso de que la entrada sea [10,10,10,10], la suma mágica es 0. el segundo más bajo posible es 2. Déjame saber lo que piensas.
Koishore Roy
Lo que te escucho decir es que puedes ignorar el orden de los cuatro números dados (tu primer paso es ordenarlos). Pero lo que si nos había pedido cinco números p1a través p5, y aún así sólo se permite el cambio de un número? El caso de cuatro números parece demasiado fácil (solo después de ver su respuesta).
Jeppe Stig Nielsen
@KoishoreRoy Me gusta su solución de permitir cualquiera de los dos.
xnor
@JeppeStigNielsen Sí, el hecho de que el orden no importa es especial para 4 números, y sucede porque después de eliminar uno para hacer tres números, todos los pares de números son adyacentes cíclicamente. Con cinco números esto no funcionaría (seguramente puedes encontrar un ejemplo), y el desafío sería muy diferente.
xnor
Ojalá pudiera votar dos veces. Hermosa observación, bien explicada.
Jonás
9

R , 66 33 bytes

function(x)2*min(diff(sort(x),2))

Pruébalo en línea!

Mucho más corto con el algoritmo de xnor (¡lee su explicación y vota tu publicación!).

Versión antigua:

R , 66 bytes

function(x,m=matrix(x,3,4))min(colSums(abs(diff(rbind(m,m[1,])))))

Pruébalo en línea!

Toma la entrada como un vector de 4 enteros.

p2p2p1p2p3|p1p2|+|p2p3|p2=p1.

Hay 4 formas de elegir qué número cambiamos; para cada uno de estos, solo tenemos que calcular la suma de 3 diferencias absolutas.

3×4rbind

Robin Ryder
fuente
4

Jalea , 11 10 bytes

I;SASƲ$-ƤṂ

Pruébalo en línea!

Un enlace monádico que toma una lista si son enteros como entrada. Debería funcionar para un tamaño de lista arbitrario. Funciona sobre la base de que se puede obtener la suma mínima mediante la prueba de eliminar cada número de la lista, calcular la suma mágica y tomar el mínimo.

Nick Kennedy
fuente
3

Jalea , 8 bytes

ṁ-Ƥ⁸IA§Ṃ

Un enlace monádico que acepta una lista de enteros * que produce un entero

* puede ser cualquier número siempre que haya más de 1; usando la misma fórmula mágica de estilo que resume las diferencias entre vecinos.

Pruébalo en línea!

¿Cómo?

ṁ-Ƥ⁸IA§Ṃ - Link: list of integers, X       e.g. [17,-6,15,33]
 -Ƥ      - for overlapping "outfixes" of length length(X)-1:
         -                                      [[-6,15,33],[17,15,33],[17,-6,33],[17,-6,15]]
ṁ  ⁸     -   mould like X                       [[-6,15,33,-6],[17,15,33,17],[17,-6,33,17],[17,-6,15,17]]
    I    - incremental differences              [[21,18,-39],[-2,18,-16],[-23,39,-16],[-23,21,2]]
     A   - absolute (vectorises)                [[21,18,39],[2,18,16],[23,39,16],[23,21,2]]
      §  - sums                                 [78,36,78,46]
       Ṃ - minimum                              36
Jonathan Allan
fuente
3

Japt -Q , 11 bytes

ñÍó ®r- ÑÃn

Utiliza el algoritmo de @ xnor, que me ahorró 4 bytes.

Guardado 5 bytes gracias a @Shaggy

Intentalo

Encarnación de la ignorancia
fuente
parece estar funcionando bien, pero ¿podría explicar por qué funciona esto?
Koishore Roy
@KoishoreRoy Agregó una explicación
Encarnación de la ignorancia
29 bytes ( creo )
Shaggy
@Shaggy cuando actualicé mi respuesta, reemplacé accidentalmente la suma con el mapa, haciendo que algunos campos de golf no sean válidos, pero otros son buenos
Encarnación de la ignorancia
Muy bien (más) golfed :) Puedes ahorrar 1 byte más reemplazándolo ÃÃcon una nueva línea.
Shaggy
3

J , 24 20 18 17 bytes

versión alternativa usando el algoritmo xnor:

2*[:<./2 2-/@$\:~

cómo

Dos veces 2 *el mínimo de [:<./la segunda fila restado de la primera fila [:-/de la matriz 2x2 formada al dar forma a 2 2$la entrada ordenada\:~

Pruébalo en línea!

respuesta original: J , 24 bytes

[:<./1(1#.2|@-/\],{.)\.]

Pruébalo en línea!

Usando la idea de Nick Kennedy.

  • 1(...)\.] aplicar el verbo en parens a todos los outfixes de longitud 1 (un outfix de longitud n es una lista con n elementos contiguos eliminados, por lo que esto produce todas las listas posibles con 1 olmo eliminado)
  • (1 #. 2 |@-/\ ] , {.)esto calcula la suma mágica agregando el primer olmo a la entrada ] , {.y aplicando la diferencia de abs |@-/a los infijos de longitud 2 2 ...\, y sumando el resultado 1 #..
  • [:<./ devuelve el min
Jonás
fuente
2

05AB1E , 11 7 bytes

Respuesta de Port of @xnor 's Jelly .
-4 bytes gracias a @Emigna y @Grimy .

{2ô`αß·

Pruébalo en línea.

Alternativa de 7 bytes que solo funciona en la versión heredada de 05AB1E (requeriría un antes ¥de la versión nueva):

{2ôø¥W·

Pruébalo en línea.

Explicación:

{        # Sort the (implicit) input-list
         #  i.e. [17,-6,15,33] → [-6,15,17,33]
 2ô      # Split this list into parts of size 2
         #  → [[-6,15],[17,33]]
   `     # Push both separated to the stack
    α    # And take their absolute differences
         #  → [23,18]
     ß   # Pop and push the minimum
         #  → 18
      ·  # Double it (and output implicitly as result)
         #  → 36

{        # Sort the (implicit) input-list
         #  i.e. [17,-6,15,33] → [-6,15,17,33]
 2ô      # Split this list into parts of size 2
         #  → [[-6,15],[17,33]]
   ø     # Zip/transpose, swapping rows/columns
         #  → [[-6,17],[15,33]]
    ¥    # Get the deltas/forward differences of the inner lists
         #  → [[23],[18]]
     W   # Get the flattened minimum (without popping)
         #  → 18
      ·  # Double it (and output implicitly as result)
         #  → 36
Kevin Cruijssen
fuente
1
7 bytes en legado: {2ôø¥W·u 8 con en la reescritura.
Emigna
2
7 bytes en no legado:{2ô`αW·
Grimmy
@Emigna Smart, gracias!
Kevin Cruijssen
@ Grimy ¡Gracias también!
Kevin Cruijssen
1

C ++ (gcc)

programa completo: 138 bytes

#include<iostream>
#include<regex>
using namespace std;int main(){int a[4];for(int&b:a)cin>>b;sort(a,a+4);cout<<min(a[2]-*a,a[3]-a[1])*2;}

Pruébalo en línea!

función principal: 84 bytes

#include<regex>
int m(int*a){std::sort(a,a+4);return std::min(a[2]-*a,a[3]-a[1])*2;}

Pruébalo en línea!

También usando el algoritmo xnor explicado en su publicación de Python 2.

movatica
fuente
0

Carbón de leña , 20 bytes

I⌊EEθΦθ⁻κμΣEι↔⁻λ§ι⊕μ

Pruébalo en línea! El enlace es a la versión detallada del código. Resulta que estoy usando la idea de @ NickKennedy. Explicación:

   Eθ                   Map over input array
     Φθ                 Filter over input array where
       ⁻κμ              Outer and inner indices differ
  E                     Map over resulting list of lists
           Eι           Map over remaining values in list
                §ι⊕μ    Get the next value in the list
             ↔⁻λ        Compute the absolute difference with the current value
          Σ             Take the sum of absolute differences
 ⌊                      Take the minimum sum
I                       Cast to string and implicitly print
Neil
fuente
0

Java 8 , 235 bytes

Un puerto de respuesta y algoritmo Python de @ xnor

import java.util.*;interface M{static void main(String[]A){Scanner I=new Scanner(System.in);int a[]={0,0,0,0};for(int i=0;i<4;a[i++]=I.nextInt());java.util.Arrays.sort(a);System.out.print(2*(a[2]-a[0]>a[3]-a[1]?a[3]-a[1]:a[2]-a[0]));}}

Pruébalo en línea!

Java 10 , no probado, 222 bytes

Con Java 10, debería poder reemplazar el lado izquierdo de la declaración del escáner var, aunque no pude compilarlo en línea y, por lo tanto, solo puedo agregarlo como una trivia. Lo siento.

interface M{static void main(String[]A){var I=new java.util.Scanner(System.in);int a[]={0,0,0,0};for(int i=3;i<4;a[i++]=I.nextInt());java.util.Arrays.sort(a);System.out.print(2*(a[2]-a[0]>a[3]-a[1]?a[3]-a[1]:a[2]-a[0]));}}
Polvo de diamante
fuente
1
AFAIK puede simplemente tener una función como su envío, como lo han hecho las otras respuestas. No es necesario incluir la clase circundante, la interfaz, etc.
Tau