Помогите! Кажется, в некоторых моих массивах есть раздражающее эхо, и я бы хотел избавиться от него. Когда это происходит, исходный массив повторяется где-то посередине, вызывая добавление значений друг к другу.
Например, массив [ 422, 375, 527, 375, 859, 451, 754, 451 ]
содержит эхо-запрос, например:
[ 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
Пример 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 ]
Также возможно, что в массиве нет эха, и в этом случае вернуть исходный массив:
Пример 3:
[ 623, 533, 494, 382 ] <-- input
[ 623, 533, 494, 382 ] <-- output
Вызов:
Учитывая массив, который может содержать эхо, удалите его и верните массив без эха.
Входные данные:
- Массив, список, строка с разделителями, перфокарты или эквивалентный вашей платформе эквивалент, содержащий три или более целых числа, в диапазоне с хотя бы одним элементом .
- Эхо не может начинаться с первого или после последнего элемента.
- Эхо будет происходить только один раз или вообще не будет на входе.
Выход:
- Массив, список и т. Д. Целых чисел , с удаленным эхом.
- Если эхо отсутствует, верните исходный массив.
Правила и оценки:
- Это код-гольф , поэтому выигрывает самый короткий ответ в байтах для каждого языка.
- Применяются стандартные правила и правила ввода / вывода по умолчанию .
- Лазейки запрещены (конечно).
- Пожалуйста, предоставьте ссылку с тестом для вашего кода ( TIO.run и т. Д.).
- Четкое объяснение вашего ответа настоятельно рекомендуется.
Тестовые случаи:
С эхом:
[ 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 ]
Без эха:
[ 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 ]
[1, 2, 2, 2, 1]
; Выходные данные:[1, 1, 1, 1]
против[1, 2, 1]
[1, 2, 3, 1, 2, 3]
,[1, 2, 3, 0, 1, 2, 3]
,[0, 1, 3, 2, 0]
? Текущие ответы не согласны по всем этим входам.[1, 1, 1, 1]
против[1, 2, 1]
) являются приемлемыми. Изначально у меня было правило о том, что выбрать, но я снял его в песочнице, потому что это, казалось, применимо только к небольшому числу крайних случаев.[0, 1, 3, 2, 0]
должно быть[0, 1, 2, 0]
- я добавил к тестам. Ожидаемый ответ на два других может быть,[1, 2, 3]
хотя я бы не рассматривал эти действительные тестовые случаи, поскольку в соответствии с правиламиthe original array repeats itself somewhere in the middle
.[0,0,0]
(или0
массив all - all любого размера ) эхо чего-либо или если[0,0,0]
(без эха) также будет правильным ответом для этого особого случая, так как просто не хватает информации, чтобы определить, какой это. Я обновлю правила, чтобы ограничить их использование в качестве допустимых входных данных, поскольку это не приведет к аннулированию или изменению любых существующих ответов.Ответы:
MATL , 16 байт
Попробуйте онлайн! Или проверьте все тестовые случаи .
объяснение
Полиномиальное деление на победу!
источник
Haskell , 167 байт
Во-первых, важно заметить, что если присутствует эхо-сигнал, то входной массив представляет собой свертку другого массива с некоторым массивом формы
[1,1],[1,0,1],[1,0,0,1],...
.Это означает, что мы просто должны проверить это для всех этих массивов. Но дискретная свертка / деконволюция - это то же самое, что и полиномиальное умножение / длинное деление, так что это просто реализация, использующая полиномы, каждый раз возвращающие частное, если это возможно.
Одна хитрость, которая немного сократила все это, была в дополнение к вышеупомянутым массивам, также проверяющим
[1]
в качестве базового случая, потому что, если никакой другой массив не работает, деконволюция с[1]
будет работать и вернет исходный полином.Попробуйте онлайн!
источник
JavaScript ,
211171145 байтПопробуйте онлайн
40 байтов от Кевина Круйссена
Еще 26 байтов от Арнаулда
Мой первый ответ на кодовый гольф аннулирует потенциальные смещения и возвращает либо исходный, либо новый массив в зависимости от того, что он найдет. Если кто-нибудь знает, как сделать его короче, пожалуйста, дайте мне знать, это похоже на забавную игру.
источник
++
, изменение&&
к&
в первой проверки, изменения и.toString()
к+''
и т.д.) я получил свой код до 181 байт . Если вы еще не видели их, Советы по игре в гольф на JavaScript может быть интересно прочитать « и « Советы по игре в гольф на всех языках» . :)function q(s)
может бытьs=>
): 171 байт . Приятного пребывания! :)Haskell,
112111110 байтовПопробуйте онлайн!
источник
Wolfram Language (Mathematica) ,
13112912011910298979695 байтПопробуйте онлайн!
-1 байт благодаря attinat : мы можем написать
L=Tr[1^#]
вместо того,L=Length@#
чтобы аргумент представлял собой список чисел.Объяснение кода: итерация по усадке
d
(разница между длиной ввода и вывода). Для каждой длины выходного списка создайте список неизвестныхv={x[1],x[2],...,x[L-d]}
и добавьте его себе слева и справа к lengthL
(PadLeft[v,L]+PadRight[v,L]
), затем установите эту сумму равной входному списку и вычислите для неизвестныхx[1]...x[L-d]
. Выберите самое короткое решение, которое было сгенерировано последним: просто продолжайте перезаписывать переменнуюw
каждый раз, когда найдено решение.Версия без гольфа:
источник
Tr[1^#]
вместоLength@#
Желе ,
2524 байтаПопробуйте онлайн!
Монадическая ссылка, которая принимает и возвращает список целых чисел. Технически, успешные результаты вложены в два дальнейших списка, но при запуске в качестве полной программы неявный вывод на стандартный вывод игнорирует избыточные списки.
источник
Python 2 ,
113123128127123122 байтаПопробуйте онлайн!
1 байт в TFeld ; и 1 байт спасибо Себастьяну Крефту .
При каждом вызове
f
мы создаем потенциальное эхо длиныlen(a)-i
. Первая часть - это только первыеi
байты a; остаток рассчитывается так, чтобы «сумма эха» была правильной для «перекрывающейся» части суммы эха (т. е. сумма эха была верной доa[:-i]
).Тогда очень короткое сравнение, без игры в гольф, дает:
источник
e+=[v-e[-i]]
может бытьe+=v-e[-i],
i<=len(a)/2
Wolfram Language (Mathematica) , 93 байта
Попробуйте онлайн!
Возвращает самое короткое эхо, присутствующее в списке.
источник
{1,1,1}
и снова{1,0,1}
.{1,1,1}
что нет эха, поэтому вам нужно вернуть исходный массив. Для{1,0,1}
Я бы сказал , эхо ,{1}
но признаю , что это немного неясно , какие правила.PHP , 124 байта
Попробуйте онлайн!
Объяснение:
Создайте копию входного массива и пройдитесь по каждому возможному смещению эха. Для каждого столбца вычтите значение в позиции смещения из соответствующего значения в исходной позиции, чтобы определить значение, необходимое для суммирования с входными данными. Если это действительно (> 0 ), замените содержимое этого столбца на это значение. Продолжайте до конца, и если никакие значения не являются недействительными, это правильный ответ.
источник
Python 3 , 111 байт
Попробуйте онлайн!
Решение берет некоторые идеи из решения @Chas Brown, такие как рекурсивная структура и построение выходного массива. Между тем, он также вносит некоторые изменения в критерии оценки, а также помещает цикл for в выражение генератора, чтобы разрешить однострочное решение. Развернутая версия показана ниже. Здесь массив
out
вычисляется до конца входного массива, а затем мы проверяем, все ли последние егоl
элементы равны нулю. Если так, то первыйlen(arr)-l
элементы возвращаются как ответ, если все они неотрицательны.Ungolfed, нерекурсивная версия
Попробуйте онлайн!
источник
Древесный уголь , 62 байта
Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:
Предположим, что нет эха.
Попробуйте все возможные начальные точки эха. Примечание. Возможно, я неправильно прочитал вопрос, и, возможно, я не пробовал достаточно эхо-сигналов, и в этом случае
⊘
этом нет необходимости.Начните с массива нулей того же размера, что и начальная точка эха.
Для каждого элемента в исходном массиве циклически вычитайте из него элемент в массиве echo. Таким образом, каждый элемент в массиве эхо-сигналов создает чередующуюся сумму элементов, которые находятся на расстоянии друг от друга.
Если все чередующиеся суммы равны нулю, сохраните это как возможную начальную точку. (Таким образом, если существует более одной возможности, используется максимально возможная начальная точка.)
Создайте отражающий массив, вычитая элементы после начальной точки из соответствующего ранее вычисленного элемента.
Приведение к строке для неявного вывода на отдельных строках.
источник