Hay un eco en mi matriz ... eco en mi matriz ... mi matriz

34

¡Ayuda! Parece que tengo un eco molesto en algunos de mis arreglos, y me gustaría deshacerme de él. Cuando esto ocurre, la matriz original se repite en algún lugar en el medio, lo que hace que los valores se agreguen entre sí.

Por ejemplo, la matriz [ 422, 375, 527, 375, 859, 451, 754, 451 ]contiene un eco de sí mismo así:

[ 422, 375, 527, 375, 859, 451, 754, 451 ] <-- array with echo (input)

[ 422, 375, 105,   0, 754, 451           ] <-- original array (output)
[           422, 375, 105,   0, 754, 451 ] <-- echo of original array

Ejemplo 2

[ 321, 526, 1072, 899, 6563, 798, 7038, 3302, 3032, 3478, 1806, 601 ] <-- input

[ 321, 526,  751, 373, 5812, 425, 1226, 2877, 1806,  601            ] <-- output
[            321, 526,  751, 373, 5812,  425, 1226, 2877, 1806, 601 ]

También es posible que no haya eco en la matriz, en cuyo caso devolverá la matriz original:

Ejemplo 3:

[ 623, 533, 494, 382 ] <-- input
[ 623, 533, 494, 382 ] <-- output

Reto:

Dado un conjunto que puede contener un eco, elimínelo y devuelva el conjunto sin un eco.

Entrada:

  • Una matriz, lista, cadena delimitada, tarjetas perforadas o su equivalente adecuado para la plataforma, que contiene tres o más enteros, en el rango de con al menos un elemento .0n<10000>0
  • El eco no puede comenzar en el primero o después del último elemento.
  • El eco solo se producirá una vez o nada en la entrada.

Salida:

  • Una matriz, lista, etc. de enteros , con el eco eliminado.0n<10000
  • Si no hay eco, devuelva la matriz original.

Reglas y puntuación:

Casos de prueba:

Con eco:

[ 422, 375, 527, 375, 859, 451, 754, 451 ]
[ 422, 375, 105, 0, 754, 451 ]

[ 321, 526, 1072, 899, 6563, 798, 7038, 3302, 3032, 3478, 1806, 601 ]
[ 321, 526, 751, 373, 5812, 425, 1226, 2877, 1806, 601 ]

[ 4330, 3748, 363, 135, 2758, 3299, 1674, 1336, 4834, 2486, 4087, 1099, 4098, 4942, 2159, 460, 4400, 4106, 1216, 3257, 1638, 2848, 3616, 3554, 1605, 490, 1308, 2773, 3322, 3284, 4037, 7109, 4171, 5349, 2675, 3056, 4702, 4229, 1726, 5423, 6039, 8076, 6047, 7088, 9437, 4894, 1946, 7501, 5331, 3625, 5810, 6289, 2858, 6610, 4063, 5565, 2200, 3493, 4573, 4906, 3585, 4147, 3748, 3488, 5625, 6173, 3842, 5671, 2555, 390, 589, 3553, 3989, 4948, 2990, 4495, 2735, 1486, 3101, 1225, 2409, 2553, 4651, 10, 2994, 509, 3960, 1710, 2185, 1800, 1584, 301, 110, 969, 3065, 639, 3633, 3544, 4268 ]
[ 4330, 3748, 363, 135, 2758, 3299, 1674, 1336, 4834, 2486, 4087, 1099, 4098, 4942, 2159, 460, 4400, 4106, 1216, 3257, 1638, 2848, 3616, 3554, 1605, 490, 1308, 2773, 3322, 3284, 4037, 2779, 423, 4986, 2540, 298, 1403, 2555, 390, 589, 3553, 3989, 4948, 2990, 4495, 2735, 1486, 3101, 1225, 2409, 2553, 4651, 10, 2994, 509, 3960, 1710, 2185, 1800, 1584, 301, 110, 969, 3065, 639, 3633, 3544, 4268 ]

[ 24, 12, 52, 125, 154, 3, 567, 198, 49, 382, 53, 911, 166, 18, 635, 213, 113, 718, 56, 811, 67, 94, 80, 241, 343, 548, 68, 481, 96, 79, 12, 226, 255, 200, 13, 456, 41 ]
[ 24, 12, 52, 125, 154, 3, 567, 198, 25, 370, 1, 786, 12, 15, 68, 15, 88, 348, 55, 25, 55, 79, 12, 226, 255, 200, 13, 456, 41 ]

[ 1, 3, 2 ]
[ 1, 2 ]

[ 0, 1, 3, 2, 0 ]
[ 0, 1, 2, 0 ]

Sin eco:

[ 623, 533, 494, 382 ]
[ 623, 533, 494, 382 ]

[ 1141, 1198, 3106, 538, 3442, 4597, 4380, 3653, 1370, 3987, 1964, 4615, 1844, 5035, 2463, 6345, 4964, 4111, 5192, 8555, 5331, 3331, 4875, 6586, 5728, 4532, 5972, 2305, 3491, 6317, 2256, 2415, 5788, 4873, 6480, 2080, 5319, 4551, 6527, 5267, 4315, 2178, 2615, 5735, 5950, 6220, 7114, 6259, 5000, 4183, 6822, 6927, 7150, 8003, 5603, 3154, 8231, 5005, 5743, 6779, 4530, 4029, 5336, 6105, 4777, 6183, 6838, 5725, 6819, 8584, 3142, 3840, 3291, 4284, 2933, 4859, 2906, 5176, 2853, 2110, 2048, 4389, 4501, 2267, 2704, 431, 1495, 2712, 3008, 187, 3487, 630 ]
[ 1141, 1198, 3106, 538, 3442, 4597, 4380, 3653, 1370, 3987, 1964, 4615, 1844, 5035, 2463, 6345, 4964, 4111, 5192, 8555, 5331, 3331, 4875, 6586, 5728, 4532, 5972, 2305, 3491, 6317, 2256, 2415, 5788, 4873, 6480, 2080, 5319, 4551, 6527, 5267, 4315, 2178, 2615, 5735, 5950, 6220, 7114, 6259, 5000, 4183, 6822, 6927, 7150, 8003, 5603, 3154, 8231, 5005, 5743, 6779, 4530, 4029, 5336, 6105, 4777, 6183, 6838, 5725, 6819, 8584, 3142, 3840, 3291, 4284, 2933, 4859, 2906, 5176, 2853, 2110, 2048, 4389, 4501, 2267, 2704, 431, 1495, 2712, 3008, 187, 3487, 630 ]

[ 4791, 1647, 480, 3994, 1507, 99, 61, 3245, 2932, 8358, 6618, 1083, 5391, 3498, 4865, 1441, 3729, 5322, 5371, 6271, 2392, 1649, 5553, 9126, 3945, 2179, 3672, 2201, 4433, 5473, 4924, 6585, 6407, 3862, 6505, 1530, 5293, 4792, 6419, 6739, 3258, 3839, 3891, 7599, 2576, 5969, 5659, 6077, 5189, 1325, 4490, 5694, 6567, 6367, 5724, 5756, 6450, 5863, 4360, 2697, 3100, 3779, 4040, 4653, 1755, 3109, 2741, 3269 ]
[ 4791, 1647, 480, 3994, 1507, 99, 61, 3245, 2932, 8358, 6618, 1083, 5391, 3498, 4865, 1441, 3729, 5322, 5371, 6271, 2392, 1649, 5553, 9126, 3945, 2179, 3672, 2201, 4433, 5473, 4924, 6585, 6407, 3862, 6505, 1530, 5293, 4792, 6419, 6739, 3258, 3839, 3891, 7599, 2576, 5969, 5659, 6077, 5189, 1325, 4490, 5694, 6567, 6367, 5724, 5756, 6450, 5863, 4360, 2697, 3100, 3779, 4040, 4653, 1755, 3109, 2741, 3269 ]

[ 235, 121, 52, 1249, 154, 26, 5672, 1975, 482, 3817, 532, 9104, 1661, 171, 6347, 2124, 1122, 7175, 558, 8101, 667, 934, 798, 2404, 3424, 5479, 672, 4808, 956, 789, 123, 2255, 2549, 200, 126, 4562, 41 ]
[ 235, 121, 52, 1249, 154, 26, 5672, 1975, 482, 3817, 532, 9104, 1661, 171, 6347, 2124, 1122, 7175, 558, 8101, 667, 934, 798, 2404, 3424, 5479, 672, 4808, 956, 789, 123, 2255, 2549, 200, 126, 4562, 41 ]

[ 1, 1, 1, 1, 1 ]
[ 1, 1, 1, 1, 1 ]
640 KB
fuente
3
¿Qué pasa si hay múltiples salidas posibles? Entrada [1, 2, 2, 2, 1]:; Salida: [1, 1, 1, 1]vs.[1, 2, 1]
tsh
3
¿Cuál es el resultado que se espera para [1, 2, 3, 1, 2, 3], [1, 2, 3, 0, 1, 2, 3], [0, 1, 3, 2, 0]? Las respuestas actuales no están de acuerdo con todas estas entradas.
tsh
@tsh Cualquiera de esos ( [1, 1, 1, 1]vs. [1, 2, 1]) son aceptables. Originalmente tenía una regla sobre cuál elegir, pero la quité en el cajón de arena porque parecía aplicarse solo a un pequeño número de casos extremos.
640 KB
@tsh, [0, 1, 3, 2, 0]debería ser [0, 1, 2, 0]- He agregado a los casos de prueba. Una respuesta esperada en los otros dos podría ser [1, 2, 3]que no consideraría esos casos de prueba válidos ya que de acuerdo con las reglas the original array repeats itself somewhere in the middle.
640 KB
1
@nimi Buena. Diría que es ambiguo si [0,0,0](o cualquier 0matriz de todos los tamaños ) representa un eco de algo o si [0,0,0](sin eco) también sería una respuesta válida para este caso especial, ya que simplemente no hay suficiente información para determinar qué está. Actualizaré las reglas para restringir que esto sea una entrada válida, ya que eso no invalidará ni alterará ninguna respuesta existente.
640 KB

Respuestas:

8

MATL , 16 bytes

t"GX@WQB&Y-~?w]x

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

División polinómica para la victoria!

t      % Implicit input. Duplicate
"      % For each (do the following as many times as input length)
  G    %   Push input again. This will be the output if no solution exists
  X@   %   Push current iteration index, k
  WQB  %   2 raised to that, add 1, convert to binary. Gives [1 0 ... 0 1] (k-1 zeros)
  &Y-  %   Two-output polynomial division (deconvolution). Gives quotient and remainder
  ~    %   Logical negate: transforms zeros into 1, nonzeros into 0
  ?    %   If all values are nonzero (i.e. if remainder was all zeros): solution found
    w  %      Swap. This moves the copy of the input to top (to be deleted)
  ]    %   End
  x    %   Delete. This deletes the quotient if it was not a solution, or else deletes
       %   the copy of the input
       % End (implicit). Since it is guaranteed that at most one solution exists, at this
       % point the stack contains either the solution or the input
       % Implicit display
Luis Mendo
fuente
No se toman en cuenta la recompensa del lenguaje "eso" o "histórico" en esto ... ¡así que la recompensa se vuelve popular!
640 KB el
1
@ 640 KB ¡No sabía que había una recompensa por este desafío! ¡Gracias!
Luis Mendo
7

Haskell , 167 bytes

Primero es importante notar que si hay un eco presente, entonces la matriz de entrada es una convolución de otra matriz con alguna matriz de la forma [1,1],[1,0,1],[1,0,0,1],....

Esto significa que solo tenemos que verificar esto para todas estas matrices. Pero la convolución / deconvolución discreta es lo mismo que la multiplicación polinómica / división larga, por lo que esta es solo una implementación que usa polinomios, cada vez que devuelve el cociente si es posible.

Un truco que acortó todo un poco fue, además de las matrices anteriores, también verificar [1]como un caso base, porque si ninguna otra matriz funciona, la deconvolución [1]funcionará y devolverá el polinomio original.

import Math.Polynomial
import Data.Ratio
p=poly LE
c z=last[polyCoeffs LE q|k<-zipWith const[p(take k(1:repeat 0)++[1])|k<-[0..]]z,(q,r)<-[quotRemPoly(p z)k],r==zero] 

Pruébalo en línea!

falla
fuente
Buen truco con el caso base! Traté de incorporar eso en mi respuesta pero pude acortar el código
Luis Mendo
4

JavaScript , 211 171 145 bytes

s=>{for(n=x=0,y=s.length;++x<y/2&!n;)for(n=s.slice(i=0,x);i+x<y-x&&n;)n=(n[i+x]=s[i+x]-n[i++])<0?0:n;return n&&n.slice(1-x)+''==s.slice(1-x)?n:s}

Pruébalo en línea

40 bytes de Kevin Cruijssen

Otros 26 bytes de Arnauld

Mi primera respuesta de golf de código, invalida las posibles compensaciones y devuelve la matriz original o la nueva dependiendo de lo que encuentre. Si alguien sabe cómo hacerlo más corto, por favor hágamelo saber, parece un juego divertido.

Levi Faid
fuente
1
No estoy muy hábil con JavaScript, pero con algunos campos de golf básicos (es decir, la eliminación de corchetes innecesarios, cambiando las colocaciones del ++, cambiando &&a &en el primer control, cambiando tanto .toString()a +'', etc.) Tengo el código de abajo a 181 bytes . Si aún no los ha visto, puede ser interesante leer los Consejos para jugar golf en JavaScript y los Consejos para jugar golf en todos los idiomas . :)
Kevin Cruijssen
1
Oh, olvidé uno ( function q(s)puede ser s=>): 171 bytes . ¡Disfruta tu estancia! :)
Kevin Cruijssen
Gracias por eso, tendré una lectura. No soy muy útil con javascript, pero he tenido que hacer un poco últimamente y pensé que esta podría ser una buena manera de repasar un poco en mi tiempo de inactividad
Levi Faid
1
Golfé un poco más (sin todas las pruebas para que se ajuste como una URL directa en este comentario)
Arnauld
1
¡Bienvenido a Code Golf SE! ¡Esperamos que disfrute de su tiempo jugando al golf aquí!
Giuseppe
3

Haskell, 112 111 110 bytes

l=length
(!)=splitAt
f a=last$a:[x|i<-[1..l a],let (h,t)=i!a;o=h++zipWith(-)t o;(x,y)=l t!o,all(>=0)o,sum y<1]

Pruébalo en línea!

f a=                
      i<-[1..l a]                -- for all indices 'i' of the input array 'a'
      (h,t)=i!a                  -- split 'a' at 'i' into 'h' and 't'
                                 -- e.g. a: [1,2,3,4], i: 1 -> h: [1], t:[2,3,4] 
      o=                         -- calculate the original array by
        h++                      --   prepended 'h' to
        zipWith(-)t o            --   the (element-wise) difference of
                                 --   't' and itself
      (x,y)=l t!o                -- split 'o' at position <length of t>
                                 --
                                 -- example:
                                 --      a: [0,1,3,2,0]
                                 --      h: [0]
                                 --      t: [1,3,2,0]
                                 --   now
                                 --      o: [0,1,2,0,0]
                                 --      x: [0,1,2,0]
                                 --      y: [0]
                                 --
    ,                            -- 'o' is valid, if
     all(>=0)o                   --   all elements of 'o' are not negative
    ,sum y<1                     --   and 'y' is all zeros
  [x|         ]                  -- keep 'x' (a valid echo array) if 'o' is valid

 last $ a :[  ]                  -- if there's no echo, the list of 'x's is empty
                                 -- and 'a' is picked, else the last of the 'x's 
nimi
fuente
3

Wolfram Language (Mathematica) , 131 129 120 119 102 98 97 96 95 bytes

(w=#;Do[(w=v/.#)&/@Thread[#==PadLeft[v=Array[x,L-d],L]+v~PadRight~L]~Solve~v,{d,L=Tr[1^#]}];w)&

Pruébalo en línea!

-1 byte gracias a attinat : podemos escribir en L=Tr[1^#]lugar de L=Length@#cuando el argumento es una lista de números.

Explicación del código: iterar a través de la contracción d(diferencia entre las longitudes de entrada y salida). Para cada longitud de la lista de salida, construya una lista de incógnitas v={x[1],x[2],...,x[L-d]}y agréguela a sí misma con relleno izquierdo y relleno derecho con longitud L( PadLeft[v,L]+PadRight[v,L]), luego establezca esta suma igual a la lista de entrada y resuelva las incógnitas x[1]...x[L-d]. Elija la solución más corta, que es la última generada: solo siga sobrescribiendo la variable wcada vez que encuentre una solución.

Versión sin golf:

F = Function[A,                                  (* A is the input list *)
  Module[{L = Length[A],                         (* length of A *)
          v,                                     (* list of unknowns *)
          x,                                     (* unknowns in v *)
          w = A},                                (* variable for solution, defaults to A *)
    Do[                                          (* loop over shrinkage: d = Length[A]-Length[output] *)
      v = Array[x, L - d];                       (* list of unknowns to be determined *)
      (w = v /. #) & /@                          (* overwrite w with every... *) 
        Solve[                                   (* ...solution of... *)
          Thread[PadLeft[v,L]+PadRight[v,L]==A], (* ...v added to itself, left-padded and right-padded, equals A *)
          v],                                    (* solve for elements of v *)
    {d, L}];                                     (* loop for shrinkage from 1 to L (the last case d=L is trivial) *)
    w]];                                         (* return the last solution found *)
romano
fuente
-1 con en Tr[1^#]lugar deLength@#
attinat
2

Jalea , 25 24 bytes

ðsạ\FḣL_¥,+¥Ż⁹¡$µⱮLṪ⁼¥Ƈȯ

Pruébalo en línea!

Un enlace monádico que toma y devuelve una lista de enteros. Técnicamente, los resultados exitosos se anidan en otras dos listas, pero cuando se ejecuta como un programa completo, la salida implícita a stdout ignora las listas redundantes.

Nick Kennedy
fuente
2

Python 2 , 113 123 128 127 123 122 bytes

def f(a,i=1):
 e=a[:i]
 for v in a[i:-i]:e+=v-e[-i],
 return i<=len(a)/2and(min(e)>=0<e[-i:]==a[-i:]and e or f(a,i+1))or a

Pruébalo en línea!

1 byte thx a TFeld ; y 1 byte gracias a Sebastian Kreft .

En cada llamada a f, construimos un eco potencial de longitud len(a)-i. La primera parte son solo los primeros ibytes de a; el resto se calcula de modo que la 'suma de eco' sea correcta para la sección 'superpuesta' de la suma de eco (es decir, la suma de eco es correcta hasta a[:-i]).

Luego, la comparación muy corta, sin golf, da:

if i>=len(a)/2+1:
    return a # because it can't be that short, so there is no echo
else:
    if min(e)>=0                       # all elements are non-negative
                 and e[-i:]==a[-i:]:   # and the tails are the same
        return e                       # it's a match!
    else:
        return f(a,i+1)                # recurse
Chas Brown
fuente
e+=[v-e[-i]]puede sere+=v-e[-i],
TFeld
puedes afeitarte un personaje más haciendoi<=len(a)/2
Sebastian Kreft
2

Wolfram Language (Mathematica) , 93 bytes

(b=#;Do[a=#;Do[a[[i+j]]-=a[[j]],{j,2k}];a/.{__?(#>=0&),0}:>(b=a~Drop~-i),{i,k=Tr[1^#]/2}];b)&

Pruébalo en línea!

Devuelve el eco más corto presente en la lista.

attinat
fuente
Parece que esto falla una {1,1,1}y otra vez {1,0,1}.
Roman
@Roman ¿no hay eco para ninguno de esos casos?
attinat
Como {1,1,1}no hay eco, debe devolver la matriz original. Porque {1,0,1}diría que el eco es {1}pero admito que no está claro cuáles son las reglas.
Roman
Ah bien. Gracias por la captura!
attinat
2

PHP , 124 bytes

function($a){while(!$z&&++$y<$c=count($b=$a))for($x=0;$x<$c&$z=0<=$b[$x+$y]-=$b[$x++];);return array_slice($b,0,$c-$y)?:$a;}

Pruébalo en línea!

Explicación:

>0

function( $a ) {
  // iterate through all possible offsets of echo
  while( ! $b && ++$y < $c = count( $b = $a ) ) {
    // create a copy of input array, iterate through all elements
    for( $x = 0; $b && $x < $c; ) {
      // if difference between the elements in the offset copy of 
      // the array is positive, subtract the value in the input array
      // from the offset array in the same column
      if ( ( $b[ $x+$y ] -= $b[ $x++ ] ) < 0 ) {
        // result is not valid, erase array and break out of loop
        $b = 0;
      }
    }
  }
  // truncate output array to correct size. if still contains values, 
  // it is a valid result. otherwise return the original array
  return array_slice( $b, 0, $c-$y ) ?: $a;
}
640 KB
fuente
2

Python 3 , 111 bytes

def f(r,l=1):o=r[:l];o+=(v-o[-l]for v in r[l:]);return l<len(r)and(min(o)<any(o[-l:])and f(r,l+1)or o[:-l])or r

Pruébalo en línea!

La solución toma algunas ideas de la solución de @Chas Brown , como la estructura recursiva y la construcción de la matriz de salida. Mientras tanto, también realiza algunos cambios en los criterios de evaluación, así como poner el bucle for en una expresión generadora para permitir una solución de una sola línea. La versión sin golf se muestra a continuación. Aquí, la matriz outse calcula hasta el final de la matriz de entrada y luego verificamos si sus últimos lelementos son todos cero. Si es así, los primeros len(arr)-lelementos se devuelven como respuesta si todos ellos no son negativos.

Versión no recursiva, sin golf

def remove_echo(arr):
    l = 1
    while l < len(arr):
        out = arr[:l]
        out += (v - out[-l] for v in arr[l:])
        if min(out) >= 0 and out[-l:] == [0] * l:
            return out[:-l]
        l += 1
    return arr

Pruébalo en línea!

Joel
fuente
1
@ 640KB Verifiqué si la respuesta devuelta coincide con el resultado esperado en mi código e imprime el mensaje solo si no coincide. Entonces, sin salida significa que todo es correcto. Admito que esto puede ser confuso a primera vista y lo actualizaré más tarde para imprimir "Correcto" en una coincidencia.
Joel
1
@ 640 KB actualizado.
Joel
1

Carbón , 62 bytes

≔⁰ζF⊘Lθ«≔E⊕ι⁰ηFLθ§≔ηκ⁻§θκ§ηκ¿⬤η¬κ≔⊕ιζ»F⁻Lθζ⊞υ⁻§θι∧ζ∧¬‹ιζ§υ±ζIυ

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

≔⁰ζ

Supongamos que no hay eco.

F⊘Lθ«

Pruebe todos los puntos de inicio posibles de eco. Nota: es posible que haya leído mal la pregunta y no esté probando suficientes tamaños de eco, en cuyo caso no sería necesario.

≔E⊕ι⁰η

Comience con una matriz de ceros del mismo tamaño que el punto de inicio del eco.

FLθ§≔ηκ⁻§θκ§ηκ

Para cada elemento en la matriz original, reste el elemento en la matriz de eco cíclicamente. Cada elemento en la matriz de eco genera así la suma alterna de los elementos que se distancian.

¿⬤η¬κ≔⊕ιζ»

Si todas las sumas alternas son cero, guárdelo como un posible punto de inicio. (Entonces, si hay más de una posibilidad, se usa el punto de inicio más grande posible).

F⁻Lθζ⊞υ⁻§θι∧ζ∧¬‹ιζ§υ±ζ

Construya la matriz de eco restando elementos después del punto de inicio del elemento apropiado previamente calculado.

Iυ

Transmitir a cadena para salida implícita en líneas separadas.

Neil
fuente