34
2
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:
- This is code-golf, so shortest answer in bytes for each language wins.
- Standard rules and default I/O rules apply.
- Loopholes forbidden (of course).
- Please provide link with a test for your code (TIO.run, etc).
- A clear explanation for your answer is highly recommended.
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 ]
3What if there are multiple possible outputs? Input:
[1, 2, 2, 2, 1]
; Output:[1, 1, 1, 1]
vs.[1, 2, 1]
– tsh – 2019-07-11T02:39:47.6003What 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. – tsh – 2019-07-11T03:47:30.203@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. – 640KB – 2019-07-11T10:28:53.087@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 rulesthe original array repeats itself somewhere in the middle
. – 640KB – 2019-07-11T13:56:42.400Yet another interesting test case:
[0,0,0]
which should result in[0,0]
. – nimi – 2019-07-11T16:50:35.9571@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. – 640KB – 2019-07-11T17:18:30.380I think your
[235, 121, 52, ...]
example is wrong. – Roman – 2019-07-14T19:07:05.147@Roman Fixed, thx. – 640KB – 2019-07-15T16:40:45.720
What about outputting all possible outputs? (i.e. both
[1, 1, 1, 1]
and[1, 2, 1]
for input[1, 2, 2, 2, 1]
) – attinat – 2019-07-17T23:01:36.057Do we need to check if the echo is not in the specified range? (
[2, -1, 2]
for[2, 1, 1, 2]
) – attinat – 2019-07-17T23:40:13.403@attinat no, you do not need to validate input. You can assume valid input and output per spec - 0 <= n < 10000. – 640KB – 2019-07-18T00:38:25.217
@attinat you may return multiple results if you find them, but it's not required - any demonstrably correct answer is acceptable. I believe there are relatively few possible inputs with more than one valid output, though if you generate sequences that have two or more possible answers I'd be curious to see them! – 640KB – 2019-07-18T00:45:14.173