Aidez-moi! Il me semble que certains de mes tableaux contiennent un écho gênant et j'aimerais bien m'en débarrasser. Lorsque cela se produit, le tableau d'origine se répète quelque part au milieu, ce qui entraîne l'ajout des valeurs.

Par exemple, le tableau [ 422, 375, 527, 375, 859, 451, 754, 451 ]contient un écho de lui-même, comme ceci:

[ 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

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

Il est également possible qu'il n'y ait pas d'écho dans le tableau. Dans ce cas, renvoyez le tableau d'origine:

Exemple 3:

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

Défi:

Étant donné qu'un tableau peut contenir un écho, supprimez-le et renvoyez le tableau sans écho.

Contribution:

• Un tableau, une liste, une chaîne délimitée, des cartes perforées ou votre équivalent adapté à la plate-forme, contenant au moins trois entiers, dans la plage de $0\leq n\lt10000$ avec au moins un élément $\gt 0$ .
• L'écho ne peut pas commencer au premier ou après le dernier élément.
• L'écho ne se produira qu'une fois ou pas du tout dans l'entrée.

Sortie:

• Un tableau, une liste, etc., d'entiers $0\leq n\lt10000$ , l'écho étant supprimé.
• S'il n'y a pas d'écho, retournez le tableau d'origine.

Règles et notation:

• C'est du code-golf , donc la réponse la plus courte en octets pour chaque langue gagne.
• Les règles standard et les règles d' entrée / sortie par défaut s'appliquent.
• Les échappatoires sont interdites (bien sûr).
• Veuillez fournir un lien avec un test pour votre code ( TIO.run , etc.).
• Une explication claire de votre réponse est fortement recommandée.

Cas de test:

Avec écho:

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

Sans écho:

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

MATL , 16 octets

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

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Division polynomiale pour la victoire!

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

Haskell , 167 octets

Tout d'abord, il est important de noter que s'il y a un écho présent, le tableau en entrée est une convolution d'un autre tableau avec un tableau de la forme [1,1],[1,0,1],[1,0,0,1],....

Cela signifie que nous devons juste vérifier ceci pour tous ces tableaux. Mais la déconvolution / déconvolution discrète est identique à la multiplication / division longue polynomiale. Il ne s'agit donc que d'une implémentation utilisant des polynômes, renvoyant à chaque fois le quotient si possible.

Une astuce qui a un peu raccourci le tout est venue s'ajouter aux tableaux ci-dessus, qui servaient également de [1]base, car si aucun autre tableau ne fonctionne, la déconvolution avec [1]fonctionnera et retournera le polynôme d'origine.

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] 

Essayez-le en ligne!

JavaScript , 211 171 145 octets

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}

Essayez-le en ligne

40 octets de Kevin Cruijssen

Un autre 26 octets d' Arnauld

Ma première réponse au code de golf invalide les compensations potentielles et renvoie le tableau d'origine ou le nouveau en fonction de ce qu'il trouve. Si quelqu'un sait comment le rendre plus court, faites-le-moi savoir, semble être un jeu amusant.

Haskell, 112 111 110 octets

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]

Essayez-le en ligne!

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 

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

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

Essayez-le en ligne!

−1 octet grâce à attinat : on peut écrire L=Tr[1^#]au lieu de L=Length@#quand l’argument est une liste de nombres.

Explication de code: Parcourez le retrait d(différence entre les longueurs d'entrée et de sortie). Pour chaque longueur de liste en sortie, construisez une liste d'inconnues v={x[1],x[2],...,x[L-d]}et ajoutez-la à elle-même, complétée à gauche et à droite, à length L( PadLeft[v,L]+PadRight[v,L]), puis définissez cette somme sur la liste d'entrée et résolvez les inconnues x[1]...x[L-d]. Choisissez la solution la plus courte, qui est la dernière générée: continuez à écraser la variable wchaque fois qu'une solution est trouvée.

Version non-golfée:

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

Gelée , 25 à 24 octets

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

Essayez-le en ligne!

Un lien monadique qui prend et retourne une liste d'entiers. Techniquement, les résultats obtenus sont imbriqués dans deux listes supplémentaires, mais lorsqu'ils sont exécutés en tant que programme complet, la sortie implicite sur stdout ignore les listes redondantes.

Python 2 , 113 123 128 127 127 123 122 octets

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

Essayez-le en ligne!

1 octet à TFeld ; et 1 octet à Sebastian Kreft .

À chaque appel à f, nous construisons un écho potentiel de longueur len(a)-i. La première partie n'est que les premiers ioctets de a; le reste est calculé de manière à ce que la "somme d'écho" soit correcte pour la section "superposée" de la somme d'écho (c'est-à-dire que la somme d'écho est correcte jusqu'à a[:-i]).

Ensuite, la comparaison très courte, sans jeu, donne:

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

Wolfram Language (Mathematica) , 93 octets

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

Essayez-le en ligne!

Retourne l'écho le plus court présent dans la liste.

PHP , 124 octets

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

Essayez-le en ligne!

Explication:

$\gt 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;
}

Python 3 , 111 octets

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

Essayez-le en ligne!

La solution prend quelques idées de la solution de @Chas Brown telles que la structure récursive et la construction du tableau de sortie. Dans le même temps, il modifie également les critères de jugement et place la boucle for dans une expression génératrice afin de permettre une solution à une ligne. La version non-lisée est illustrée ci-dessous. Ici, le tableau outest calculé jusqu’à la fin du tableau d’entrée, puis nous vérifions si les derniers léléments sont nuls. Si tel est le cas, les premiers len(arr)-léléments sont renvoyés en tant que réponse si tous ne sont pas négatifs.

Version non golfée, non récursive

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

Essayez-le en ligne!

Charbon de bois , 62 octets

≔⁰ζＦ⊘Ｌθ«≔Ｅ⊕ι⁰ηＦＬθ§≔ηκ⁻§θκ§ηκ¿⬤η¬κ≔⊕ιζ»Ｆ⁻Ｌθζ⊞υ⁻§θι∧ζ∧¬‹ιζ§υ±ζＩυ

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Explication:

≔⁰ζ

Supposons qu'il n'y ait pas d'écho.

Ｆ⊘Ｌθ«

Essayez tous les points de départ possibles de l'écho. Remarque: j'ai peut-être mal interprété la question et je n'ai peut-être pas essayé suffisamment d'écho, auquel cas ⊘cela ne serait pas nécessaire.

≔Ｅ⊕ι⁰η

Commencez avec un tableau de zéros de la même taille que le point de départ de l'écho.

ＦＬθ§≔ηκ⁻§θκ§ηκ

Pour chaque élément du tableau d'origine, soustrayez-le cycliquement de l'élément. Chaque élément de la matrice d'écho constitue ainsi la somme alternée des éléments distants.

¿⬤η¬κ≔⊕ιζ»

Si toutes les sommes alternées sont égales à zéro, sauvegardez-les comme point de départ possible. (Donc, s'il y a plus d'une possibilité, le point de départ le plus grand possible est utilisé.)

Ｆ⁻Ｌθζ⊞υ⁻§θι∧ζ∧¬‹ιζ§υ±ζ

Construisez le tableau en écho en soustrayant les éléments après le point de départ de l'élément calculé précédemment.

Ｉυ

Transformation en chaîne pour une sortie implicite sur des lignes séparées.