Найдите бинарный массив!

24

Мы определяем бинарный массив как массив, удовлетворяющий следующим свойствам:

  • это не пусто
  • первое значение 1
  • последнее значение 1
  • все остальные значения либо 0или1

Например, массив [ 1, 1, 0, 1 ]является допустимым binarray .

Задание

Учитывая непустой массив A неотрицательных целых чисел и положительное целое число N , ваша задача состоит в том, чтобы найти двоичный массив B длины N, который позволяет генерировать A путем суммирования неограниченного числа копий B , сдвинутых на неограниченное число позиции.

пример

A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
N = 4

Для этого ввода binarray B = [ 1, 1, 0, 1 ] будет правильным ответом, потому что мы можем сделать:

  [ 1, 1, 0, 1 ]
+       [ 1, 1, 0, 1 ]
+       [ 1, 1, 0, 1 ]
+          [ 1, 1, 0, 1 ]
+                   [ 1, 1, 0, 1 ]
+                                  [ 1, 1, 0, 1 ]
  -----------------------------------------------
= [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]

правила

  • Входные данные могут быть приняты в любом разумном формате.
  • Вывод может быть либо собственным массивом (например [1, 1, 0, 1]), либо двоичной строкой с разделителем или без него (например, "1,1,0,1"или "1101")
  • Вам нужно только распечатать или вернуть один действительный бинарный массив . Кроме того, вы можете распечатать или вернуть их все, когда существует несколько решений.
  • Вы не обязаны поддерживать материалы, которые не приводят к какому-либо решению.
  • Сумма может включать в себя неявные нули , которые не пересекаются с любой копией B . Второй ноль в приведенной выше сумме является таким неявным нулем.
  • Можно предположить, что максимальный размер A равен 100, а максимальный размер B равен 30.
  • Это код-гольф, поэтому выигрывает самый короткий ответ в байтах. Стандартные лазейки запрещены.

Контрольные примеры

Input : N = 1 / A = [ 1, 2, 3, 4, 5 ]
Output: [ 1 ]

Input : N = 2 / A = [ 1, 2, 100, 99 ]
Output: [ 1, 1 ]

Input : N = 3 / A = [ 1, 1, 1 ]
Output: [ 1, 1, 1 ]

Input : N = 3 / A = [ 1, 1, 3, 2, 2 ]
Output: [ 1, 1, 1 ]

Input : N = 3 / A = [ 1, 0, 2, 1, 1, 1, 0, 0, 1, 0, 1 ]
Output: [ 1, 0, 1 ]

Input : N = 4 / A = [ 1, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1 ]

Input : N = 4 / A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1 ]

Input : N = 4 / A = [ 1, 1, 0, 2, 1, 0, 1 ]
Output: [ 1, 0, 0, 1 ] or [ 1, 1, 0, 1 ]

Input : N = 5 / A = [ 1, 3, 6, 9, 8, 6, 3, 4 ]
Output: [ 1, 1, 1, 0, 1 ]

Input : N = 8 / A = [ 2, 1, 0, 2, 3, 3, 1, 2, 1 ]
Output: [ 1, 0, 0, 1, 1, 1, 0, 1 ]

Input : N = 10 / A = [ 1, 2, 1, 2, 2, 1, 3, 3, 3, 2, 3, 0, 2, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1, 0, 1, 1, 1, 0, 1 ]

Input : N = 13 / A = [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 ]
Output: [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]

Input : N = 5 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1, 1 ]

Input : N = 6 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 0, 0, 0, 1 ]

Input : N = 7 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 0, 0, 0, 1, 1 ]

Input : N = 9 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 1, 0, 1, 0, 1, 0, 1 ]
code-golf array-manipulation polynomials Arnauld
источник
Какая самая большая ценность Nэтого должна обоснованно поддерживаться?
Нил
@Neil Я добавил ограничения по размеру как на А, так и на Б.
Арно
1
@ fəˈnɛtɪk Возможно, но N=4, A = [ 1, 1, 2, 4, 1, 2, 2, 2, 1, 2, 2, 1, 2, 0, 1 ]вы получите 30459, который делится на 11 и 13, но только один из них [ 1, 1, 0, 1 ]и [ 1, 0, 1, 1 ]является правильным ответом.
Нил
1
@ fəˈnɛtɪk Эти числа не записаны в базе 2, поэтому правила арифметики не применяются. Например, вы явно не можете нести при добавлении.
BallpointBen
2
Пожалуйста, добавьте эти контрольные примеры, которые, кажется, ломают почти все опубликованные ответы: N = 3, A = [1, 0, 2, 0, 2, 0, 1], output = [1, 0, 1]; N = 3, A = [1, 1, 1, 0, 0, 0, 1, 1, 1], выход = [1, 1, 1].
Андерс Касеорг

Ответы:

8

PHP 105 92 90 86 байт

Решение Jörg исправлено и отлажено:

for($b=1+2**$argv[1];;)--$argc>1?$s+=$argv[$argc]*2**$i++:$s%($b-=2)||die(decbin($b));

берет Nиз первого аргумента командной строки, значения после этого; запустить -rили проверить это онлайн .
печатает двоичное число (формат 10001); печатает недействительное решение или работает мертвым, если нет действительного решения.

первая версия (теперь 97 байт), которая ничего не печатает для неверного ввода: протестируйте его онлайн

for($b=1+$m=2**$argv[1];$m/2<=$b;)--$argc>1?$s+=$argv[$argc]*2**$i++:$s%($b-=2)||die(decbin($b));

сломать

for($b=1+$m=2**$argv[1];$m/2<=$b;)  # second loop: loop $b from 2^N-1 by -2 to 2^(N-1)
--$argc>1                           # first loop: decrease $argc ...
    ?$s+=$argv[$argc]*2**$i++           # while $argc>1: binary sum from last to 2nd argument
    :$s%($b-=2)||die(decbin($b));       # later: if $b divides $s, print in binary and exit
Titus
источник
Хорошо, не могли бы вы достичь числа байтов меньше 100?
Йорг Хюльсерманн
1
@ JörgHülsermann Я мог бы.
Титус
Тяжелое мышление. До этого я знаю, что ты лучше. Я надеюсь, что вы можете держать самый низкий счетчик байтов
Йорг Хюльсерманн
1
При N = 3, A = [1, 0, 2, 0, 2, 0, 1] это неверно возвращает значение,111 где единственным правильным результатом является [1, 0, 1].
Андерс Касорг
8

PHP , 219 байт

<?for(list($g,$z)=$_GET,$d=~-$l=2**$z;$d>=$l/2;max(array_diff_assoc($r,$g)?:[0])?:$o[]=$b,$d-=2)for($r=[],$b=decbin($d),$k=0;$k<count($g);$k++)for($u=$g[$k]-$r[$k],$i=0;$i<$z;$i++)$u<1?:$r[$k+$i]+=$u*$b[$i];print_r($o);

Попробуйте онлайн!

-4 байта, используя [$g,$z]=$_GETPHP 7.1 вместоlist($g,$z)=$_GET

Йорг Хюльсерманн
источник
Кажется, что он выводит как valid ( [1,0,1,0,1,0,1,0,1]), так и неверный answer ( [1,0,0,0,1,0,1,1,1]) для последнего контрольного примера.
Арно
-8 байт: while($_GET[0])$s+=2**$i++*array_pop($_GET[0]);. -5 байт: range(1|.5*$m=2**$_GET[1],$m,2).
Титус
@Arnauld Да, я должен дать в качестве выходных данных только самый высокий бинарный массив, чтобы сделать это решение правильным
Йорг Хюльсерманн
2
@ fəˈnɛtɪk Я согласен с вашей математикой, но проблема в том, чтобы найти шаблон, который можно суммировать точно в A, а не в эквивалентном расположении. Здесь мы бы получили [ 1,0,1,1,1,0,2,2,2,2,2,1 ].
Арно
1
-1 байт с for($g=$_GET[0];$g;).
Титус
3

Python, 166 байт

def f(a,n):
 for i in range(1<<n-1,1<<n):
  b=bin(i)[2:];u,v=(int(('0{:0>%d}'%sum(a)*len(s)).format(*s))for s in[a,b])
  if u%v<1>int(str(u//v*10)[::~sum(a)]):yield b

Попробуйте онлайн!

Как это работает

Рассмотрим A и B как цифры базовых k чисел u и v . Например (мы будем использовать k = 1000 для иллюстрации):

A = [1, 2, 1, 3, 2, 1, 2]
B = [1, 0, 0, 1]
u = 1 002 001 003 002 001 002
v = 1 000 000 001

Как заметили многие из других ответчиков, если B - правильный ответ, то u делится на v . В этом случае,

и = 1 002 001 002 ⋅ в

Этот коэффициент, переведенный обратно в массив [1, 2, 1, 2], говорит нам точно, сколько копий B нам нужно переместить в каждую позицию.

  [1, 0, 0, 1]
+    [1, 0, 0, 1]
+    [1, 0, 0, 1]
+       [1, 0, 0, 1]
+          [1, 0, 0, 1]
+          [1, 0, 0, 1]
-----------------------
  [1, 2, 1, 3, 2, 1, 2]

(Почему? Потому что именно так долго работает умножение в базе k .)

Другие авторы не заметили, что вышеприведенного условия недостаточно . Например:

A = [1, 2, 1, 3, 2, 1, 2]
B = [1, 1, 1, 1]
u = 1 002 001 003 002 001 002
v = 1 001 001 001
u = 1 000 999 002 ⋅ v

Говоря математически, мы все еще можем перевести этот коэффициент обратно в массив [1, 1, -1, 2], что прекрасно работает, если нам разрешено использовать отрицательные копии B:

  [1, 1, 1, 1]
+    [1, 1, 1, 1]
−       [1, 1, 1, 1]
+          [1, 1, 1, 1]
+          [1, 1, 1, 1]
-----------------------
  [1, 2, 1, 3, 2, 1, 2]

но, конечно, вызов не допускает негативных копий. Поэтому нам нужна дополнительная проверка.

С этой целью мы выбираем основание k = 10 e, где k > 10 ⋅ sum (A), и проверяем, чтобы ни одна из цифр base k не перетекла в следующую цифру k базы, когда мы умножаем частное на десять. То есть, каждый е й база десять цифры, начиная с концом, в десятичном представлении раз фактормодулей десять, должно быть 0. Это гарантирует , что фактор переводит обратно в массив с неотрицательными элементами.

Андерс Касеорг
источник
1
Мне нравится ваш трюк с использованием большой степени 10 в качестве базы, чтобы облегчить конвертацию базы.
Нил
2

PHP, 213 байт

Точно так же немного в гольф

<?for($b=2**~-$l=$_GET[1];$b<2**$l;array_filter($t[$b++])?:$d[]=$o)for($g=count($t[$b]=$_GET[$i=0]);min($t[$b])>-1&$i<=$g-$l;$i++)for($e=$t[$b][$i],$k=0,$o=decbin($b);$k<$l;)$t[$b][$k+$i]-=$o[$k++]*$e;print_r($d);

Попробуйте онлайн!

PHP, 344 байт первый рабочий

После моего первого ответа я решил сделать более длинную попытку, чтобы вернуть все правильные решения.

<?foreach(range(2**($l=$_GET[1])-1,2**($l-1))as$b){$t[$b]=($g=$_GET[0]);for($i=0;$t[$b]&&$i<=count($g)-$l;$i++){$e=reset($y=array_slice($t[$b],$i,$l));foreach(str_split(decbin($b))as$k=>$v)$t[$b][$k+$i]=$y[$k]-$e*$v;if(min($t[$b])<0)unset($t[$b]);}}foreach($t as$k=>$v)if(max($v)>0)unset($t[$k]);echo join(",",array_map(decbin,array_keys($t)));

Онлайн версия

Сломать

foreach(
    range(2**($l=$_GET[1])-1
    ,2**($l-1)
    ) # make decimal range of a binarray with given length
    as$b){
$t[$b]=($g=$_GET[0]); # make a copy for each possible solution pattern
    for($i=0;$t[$b]&&$i<=count($g)-$l;$i++){ # Loop till solution is valid or reach last digit
        $e=reset($y=array_slice($t[$b],$i,$l)); # take first value of a sequence with the length
        foreach(str_split(decbin($b))as$k=>$v)
            $t[$b][$k+$i]=$y[$k]-$e*$v; # replace values in copy
        if(min($t[$b])<0)unset($t[$b]); # kill solution if a minimum <0 exists
    }
}
foreach($t as$k=>$v)if(max($v)>0)unset($t[$k]); # drop all solutions where the sum is not zero 


echo join(",",array_map(decbin,array_keys($t))); #Output all solutions
Йорг Хюльсерманн
источник
Похоже, что это работает для N ≥ 2, но терпит неудачу в N = 1 случаях, таких как первый тестовый случай в задаче.
Андерс Касеорг
@AndersKaseorg Теперь он поддерживает случаи N = 1, которые ему нужны только для установки a =в первом цикле для более короткой версии. В большей версии необходимо удалить четыре байта
Jörg Hülsermann
1

Python, 205 байт

def f(a,l):
 b=lambda s:b(s[:-1])*sum(a)*8+int(s[-1])if s else 0
 c=lambda n:n and(n/sum(a)/4%2 or c(n/sum(a)/8))
 for i in range(2**~-l,2**l):
  j=bin(i)[2:]
  if b(a)%b(j)<1 and not c(b(a)/b(j)):return j

Возвращает двоичную строку без разделителя. Как указывает @AndersKaseorg, существуют входные данные, для которых решение @ fəˈnɛtɪk не работает, поскольку деление представляет отрицательный коэффициент, который запрещен. Чтобы обойти это, я использую очень большую базу и проверяю, что в подразделении нет заимствований.

Нил
источник
Хорошо, я думаю, что это фактический контрпример: f([1, 1, 1, 0, 0, 0, 1, 1, 1], 3)неправильно возвращается 101.
Андерс Касеорг
@AndersKaseorg Хм, помогает ли обратный порядок цикла, или алгоритм все еще принципиально нарушен?
Нил
Я думаю, что это принципиально сломано без дополнительных проверок. Обратный вариант не включается f([1, 0, 2, 0, 2, 0, 1], 3), и прямой и обратный варианты не включаются f([1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0], 5).
Андерс Касеорг
И даже если вы проверите, что iэто нечетно, оба варианта: прямой и обратный f([1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]*10, 5).
Андерс Касеорг
1
@AndersKaseorg Ах да, когда gcd (k, n) = 1, (x^kn-1)/(x^k-1)всегда имеет (x^n-1)/(x-1)фактор, который обманывает решение @ fəˈnɛtɪk в любой базе.
Нил
1

Pyth, 32 байта

f!|%FKiRJysQ,QT>#sQj/FKJ+L1^U2tE

Попробуйте онлайн

Как это работает

                           ^U2tE   Cartesian power [0, 1]^(N - 1)
                        +L1        prepend 1 to every list
f                                  filter for lists T such that:
          sQ                         sum(A)
         y                           double
        J                            assign to J
      iR    ,QT                      convert [A, T] from base J
     K                               assign to K
   %F                                fold modulo
  |                                  logical OR with
                    /FK                fold integer division over K
                   j   J               convert to base J
               >#sQ                    filter for digits greater than sum(A)
 !                                   logical NOT

Стратегия аналогична моему ответу на Python , за исключением того, что, поскольку Pyth имеет встроенные функции для преобразования базы, мы можем использовать более эффективную базу k = 2 ⋅ sum (A) и проверять непосредственно, что каждая цифра частного не больше суммы (A ).

Андерс Касеорг
источник
1

Пари / ГП , 77 74 96 80 байт

n->a->[v|d<-divisors(b=Pol(a)),(v=Vec(d))%2==v&&vecmin(Vec(b/d))>=0&&d%x&&#d==n]

Возвращает все решения.

Сначала преобразует массив aв полином b. Затем выбирает из делителей такие bмногочлены d, что все коэффициенты dравны всем 1и 0, а все коэффициенты b / dнеотрицательны, и d(0) = 1, и deg(d) = n + 1. Наконец, преобразует их обратно в массивы.

Попробуйте онлайн!

alephalpha
источник