34
\$\begingroup\$

Help! I seem to have an annoying echo in some of my arrays, and I'd like to get rid of it. When this occurs, the original array repeats itself somewhere in the middle causing the values to be added to each other.

For example, the array [ 422, 375, 527, 375, 859, 451, 754, 451 ] contains an echo of itself like so:

[ 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

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

It's also possible that there is no echo in the array, in which case return the original array:

Example 3:

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

Challenge:

Given an array that may contain an echo, remove it and return the array without an echo.

Input:

  • An array, list, delimited string, punched cards or your platform-suitable equivalent, containing three or more integers, in the range of \$0\leq n\lt10000\$ with at least one element \$\gt 0\$.
  • The echo cannot begin at the first or after the last element.
  • The echo will only occur once or not at all within the input.

Output:

  • An array, list, etc of integers \$0\leq n\lt10000\$, with the echo removed.
  • If there is no echo, return the original array.

Rules and scoring:

Test cases:

With echo:

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

Without echo:

[ 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 ]
\$\endgroup\$
  • 3
    \$\begingroup\$ What if there are multiple possible outputs? Input: [1, 2, 2, 2, 1]; Output: [1, 1, 1, 1] vs. [1, 2, 1] \$\endgroup\$ – tsh Jul 11 at 2:39
  • 3
    \$\begingroup\$ What is the expected output for [1, 2, 3, 1, 2, 3], [1, 2, 3, 0, 1, 2, 3], [0, 1, 3, 2, 0]? Current answers do not agree on all of these inputs. \$\endgroup\$ – tsh Jul 11 at 3:47
  • \$\begingroup\$ @tsh Either of those ([1, 1, 1, 1] vs. [1, 2, 1]) are acceptable. I originally had a rule about which to choose, but took it off in sandbox because it seemed to only apply to a small number of edge cases. \$\endgroup\$ – 640KB Jul 11 at 10:28
  • \$\begingroup\$ @tsh, [0, 1, 3, 2, 0] should be [0, 1, 2, 0] - I've added to the test cases. An expected answer on the other two could be [1, 2, 3] though I wouldn't consider those valid test cases since according to the rules the original array repeats itself somewhere in the middle. \$\endgroup\$ – 640KB Jul 11 at 13:56
  • 1
    \$\begingroup\$ @nimi Good one. I would say it's ambiguous whether [0,0,0] (or any sized all-0's array) represents an echo of anything or if [0,0,0] (no echo) would also be a valid answer for this special case as well, as there is simply not enough information to determine which it is. I will update the rules to restrict this from being a valid input, as that will not invalidate or alter any existing answers. \$\endgroup\$ – 640KB Jul 11 at 17:18

11 Answers 11

8
+200
\$\begingroup\$

MATL, 16 bytes

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

Try it online! Or verify all test cases.

Explanation

Polynomial division for the win!

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
\$\endgroup\$
  • \$\begingroup\$ No takers on the "eso" or "historic" language bounty on this... so bounty goes to popularity! \$\endgroup\$ – 640KB Sep 4 at 14:58
  • 1
    \$\begingroup\$ @640KB I didn't know there was a bounty on this challenge! Thank you! \$\endgroup\$ – Luis Mendo Sep 4 at 16:37
7
\$\begingroup\$

Haskell, 167 bytes

First it is important to notice that if there is an echo present, then the input array is a convolution of another array with some array of the form [1,1],[1,0,1],[1,0,0,1],....

This means we just have to check this for all these arrays. But discrete convolution/deconvolution is the same as polynomial multiplication/long division, so this is just an implementation using polynomials, each time returning the quotient if possible.

One trick that shortened the whole thing a little bit was in addition to the arrays above also checking for [1] as a base case, because if no other array works, the deconvolution with [1] will work and will return the original polynomial.

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] 

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Good trick with the base case! I tried to incorporate that into my answer but I could shorten the code \$\endgroup\$ – Luis Mendo Jul 11 at 11:02
4
\$\begingroup\$

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}

Try it online

40 bytes from Kevin Cruijssen

Another 26 bytes from Arnauld

My first code golf answer, invalidates potential offsets, and returns either the original or the new array dependent on what it finds. If anyone knows how to make it shorter pls let me know, seems like a fun game.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'm not too skilled with JavaScript, but with some basic golfs (i.e. removing unnecessary brackets, changing the placements of the ++, changing && to & in the first check, changing both .toString() to +'', etc.) I got your code down to 181 bytes. If you haven't seen them yet, Tips for golfing in JavaScript and Tips for golfing in all languages might be interesting to read through. :) \$\endgroup\$ – Kevin Cruijssen Jul 26 at 8:03
  • 1
    \$\begingroup\$ Oh, forgot one (function q(s) can be s=>): 171 bytes. Enjoy your stay! :) \$\endgroup\$ – Kevin Cruijssen Jul 26 at 8:06
  • \$\begingroup\$ Thanks for that, I'll have a read. I'm not very handy with javascript but I've had to do a little lately and thought this might be a good way to brush up a little in my downtime \$\endgroup\$ – Levi Faid Jul 28 at 21:56
  • 1
    \$\begingroup\$ Golfed some more (without all tests so that it fits as a direct URL in this comment) \$\endgroup\$ – Arnauld Jul 29 at 11:05
  • 1
    \$\begingroup\$ Welcome to Code Golf SE! We hope you enjoy your time golfing here! \$\endgroup\$ – Giuseppe Jul 29 at 22:47
3
\$\begingroup\$

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]

Try it online!

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 
\$\endgroup\$
3
\$\begingroup\$

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

Try it online!

−1 byte thanks to attinat: we can write L=Tr[1^#] instead of L=Length@# when the argument is a list of numbers.

Code explanation: Iterate through the shrinkage d (difference between input and output lengths). For each output list length, construct a list of unknowns v={x[1],x[2],...,x[L-d]} and add it to itself left-padded and right-padded to length L (PadLeft[v,L]+PadRight[v,L]), then set this sum equal to the input list and solve for the unknowns x[1]...x[L-d]. Pick the shortest solution, which is the last one generated: just keep overwriting the variable w every time a solution is found.

Un-golfed version:

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 *)
\$\endgroup\$
  • \$\begingroup\$ -1 with Tr[1^#] instead of Length@# \$\endgroup\$ – attinat Jul 17 at 23:05
2
\$\begingroup\$

Jelly, 25 24 bytes

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

Try it online!

A monadic link that takes and returns a list of integers. Technically, the successful results are nested in two further lists, but when run as a full program the implicit output to stdout ignores the redundant lists.

\$\endgroup\$
2
\$\begingroup\$

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

Try it online!

1 byte thx to TFeld; and 1 byte thx to Sebastian Kreft.

On each call to f, we construct a potential echo of length len(a)-i. The first part is just the first i bytes of a; the remainder is calculated so that the 'echoed sum' will be correct for the 'overlapped' section of the echo sum (i.e., the echo-sum is correct up to a[:-i]).

Then the very short-cutted comparison, un-golfed, gives:

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
\$\endgroup\$
  • \$\begingroup\$ e+=[v-e[-i]] can be e+=v-e[-i], \$\endgroup\$ – TFeld Jul 11 at 8:41
  • \$\begingroup\$ you can shave one more character by doing i<=len(a)/2 \$\endgroup\$ – Sebastian Kreft Jul 18 at 3:41
2
\$\begingroup\$

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

Try it online!

Returns the shortest echo present in the list.

\$\endgroup\$
  • \$\begingroup\$ It looks like this fails on {1,1,1} and on {1,0,1}. \$\endgroup\$ – Roman Jul 18 at 21:47
  • \$\begingroup\$ @Roman isn't there no echo for either of those cases? \$\endgroup\$ – attinat Jul 18 at 23:07
  • \$\begingroup\$ For {1,1,1} there is no echo, so you need to return the original array. For {1,0,1} I'd say the echo is {1} but admit it's a bit unclear what the rules are. \$\endgroup\$ – Roman Jul 19 at 6:29
  • \$\begingroup\$ Ah, right. Thanks for the catch! \$\endgroup\$ – attinat Jul 19 at 7:24
2
\$\begingroup\$

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

Try it online!

Explanation:

Create a copy of the input array and loop through each possible offset of the echo. For each column, subtract the value in the offset position from the corresponding value in the original position to determine the value necessary to add up to the input. If it is valid (\$\gt 0\$), replace the contents of that column with that value. Continue to the end and if no values are invalid, it is a correct answer.

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;
}
\$\endgroup\$
2
\$\begingroup\$

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

Try it online!

The solution takes some ideas from @Chas Brown's solution such as the recursive structure and the construction of the output array. Meanwhile, it also makes some changes in the judging criteria as well as putting the for loop into a generator expression to allow a single-line solution. The ungolfed version is shown in the following. Here, the array out is computed all the way to the end of the input array and then we check whether the last l elements of it are all zero. If so, the first len(arr)-l elements are returned as the answer if all of them are non-negative.

Ungolfed, non-recursive version

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ @640KB I checked whether the returned answer matches the expected result in my code and prints message only if there is an unmatch. So no output means everything is correct. I admit that this can be confusing at the first glance and I'll update it later to print "Correct" on a match. \$\endgroup\$ – Joel Aug 29 at 15:56
  • 1
    \$\begingroup\$ @640KB Updated. \$\endgroup\$ – Joel Aug 29 at 16:10
1
\$\begingroup\$

Charcoal, 62 bytes

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

Try it online! Link is to verbose version of code. Explanation:

≔⁰ζ

Assume there's no echo.

F⊘Lθ«

Try all possible start points of echo. Note: I may have misread the question and might not be trying enough sizes of echo, in which case the would not be necessary.

≔E⊕ι⁰η

Start with an array of zeros the same size as the start point of the echo.

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

For each element in the original array, subtract the element in the echo array cyclically from it. Each element in the echo array thus builds up the alternating sum of the elements that distance apart.

¿⬤η¬κ≔⊕ιζ»

If all of the alternating sums are zero then save this as a possible start point. (So if there is more than one possibility then the largest possible start point is used.)

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

Build up the echoing array by subtracting elements after the start point from the appropriate previously calculated element.

Iυ

Cast to string for implicit output on separate lines.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.