Матрица переменного знака представляет собой с n
помощью n
матрицы , состоящей из чисел -1, 0, 1, таким образом, что:
- Сумма каждой строки и столбца равна 1
- Ненулевые записи в каждой строке и столбце чередуются в знаке
Эти матрицы обобщают матрицы перестановок, и число таких матриц для заданного n
представляло интерес в течение некоторого времени. Они происходят естественным образом во время метода конденсации Доджсона вычисления матричных определителей (названных в честь Чарльза Доджсона, более известного как Льюис Кэрролл).
Вот несколько примеров матриц с чередующимися знаками 4 на 4:
0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0 0 1 -1 1 1 0 -1 1
1 0 0 0 0 1 -1 1 1 -1 1 0 0 1 0 0
0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0
А вот несколько примеров матриц 4 на 4, которые не являются знакопеременными матрицами:
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 -1 (last row and last column don't add to 1)
0 0 0 1
1 0 0 0
-1 1 1 0
1 0 0 0 (third row does not alternate correctly)
Ваша программа или функция будет дано n
по n
матрице ( n >= 1
) из -1S, 0 и 1 - выводить значение truthy , если данная матрица представляет собой матрицу Знакопеременности, иначе выведите на falsy значения.
Это код-гольф , поэтому цель состоит в том, чтобы минимизировать количество используемых байтов.
Контрольные примеры
Следующие тестовые примеры приведены в формате списка в стиле Python.
Truthy:
[[1]]
[[1,0],[0,1]]
[[0,1],[1,0]]
[[0,1,0],[0,0,1],[1,0,0]]
[[0,1,0],[1,-1,1],[0,1,0]]
[[0,1,0,0],[0,0,1,0],[1,0,0,0],[0,0,0,1]]
[[1,0,0,0],[0,0,1,0],[0,1,-1,1],[0,0,1,0]]
[[0,0,1,0],[0,1,-1,1],[1,-1,1,0],[0,1,0,0]]
[[0,0,1,0],[1,0,-1,1],[0,1,0,0],[0,0,1,0]]
[[0,0,1,0,0],[0,1,-1,1,0],[1,-1,1,0,0],[0,1,0,-1,1],[0,0,0,1,0]]
[[0,0,1,0,0,0,0,0],[1,0,-1,0,1,0,0,0],[0,0,0,1,-1,0,0,1],[0,0,1,-1,1,0,0,0],[0,0,0,0,0,0,1,0],[0,0,0,0,0,1,0,0],[0,1,-1,1,0,0,0,0],[0,0,1,0,0,0,0,0]]
[[0,0,0,0,1,0,0,0],[0,0,1,0,-1,1,0,0],[0,0,0,1,0,0,0,0],[1,0,0,-1,1,-1,1,0],[0,1,-1,1,-1,1,0,0],[0,0,0,0,1,0,0,0],[0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1]]
Falsy:
[[0]]
[[-1]]
[[1,0],[0,0]]
[[0,0],[0,1]]
[[-1,1],[1,0]]
[[0,1],[1,-1]]
[[0,0,0],[0,0,0],[0,0,0]]
[[0,1,0],[1,0,1],[0,1,0]]
[[-1,1,1],[1,-1,1],[1,1,-1]]
[[0,0,1],[1,0,0],[0,1,-1]]
[[0,1,0,0],[0,0,0,1],[1,0,0,0],[0,0,1,-1]]
[[0,0,1,0],[0,0,1,0],[1,0,-1,1],[0,1,0,0]]
[[0,0,0,1],[1,0,0,0],[-1,1,1,0],[1,0,0,0]]
[[1,0,1,0,-1],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,1,0],[0,0,0,0,1]]
[[0,0,1,0,0],[0,1,-1,1,0],[1,-1,1,0,0],[0,1,1,-1,0],[0,0,-1,1,1]]
[[0,-1,0,1,1],[1,-1,1,-1,1],[0,1,1,0,-1],[1,1,-1,1,-1],[-1,1,0,0,1]]
[[0,0,1,0,0,0,0,0],[1,0,1,0,1,0,0,0],[0,0,0,1,-1,0,0,1],[0,0,1,-1,1,0,0,0],[0,0,0,0,0,0,1,0],[0,0,0,0,0,1,0,0],[0,1,-1,1,0,0,0,0],[0,0,1,0,0,0,0,0]]
Ответы:
Retina ,
62585653 байтаЧисло байтов предполагает кодировку ISO 8859-1, и их
\t
следует заменить фактическими символами табуляции (0x09, которые в противном случае будут преобразованы в пробелы SE).Формат ввода - это матрица, в которой каждый столбец использует три выровненных по правому краю символа, например:
Вывод либо
0
(ложный), либо1
(правдивый).Тестирование. (Первые несколько строк преобразуют формат ввода и позволяют Retina запускать несколько тестов одновременно.)
объяснение
К счастью, ввод представляет собой квадратную матрицу: транспонирование квадратов практически выполнимо в Retina, тогда как транспонирование прямоугольников - огромная боль.
Мы начинаем с добавления вкладки, снова всего ввода (используя префикс
$`
) и затем перевода строки в конце (используя псевдоним Retina¶
). Мы используем вкладку для разделения двух копий, чтобы мы могли различать их при переносе одной из них, а с помощью символа пробела мы можем сохранить пару байтов позже.Это самый хитрый бит: транспонирование первой копии матрицы. Идея состоит в том, чтобы сопоставить ячейки в первой копии, а затем отсортировать их (стабильно) по горизонтальному положению. Мы сопоставляем ячейки с
...
(так как они всегда три символа в ширину), а затем измеряем горизонтальное положение(.+)
внутри вид сзади. Затем, чтобы убедиться, что мы транспонируем только первую копию, мы проверяем, что можем достичь начала строки, не проходя мимо табуляции.Вы можете заметить, что это также будет соответствовать некоторым трехбайтовым строкам (которые даже не совпадают с ячейками) в первом ряду второй копии, потому что они
.+
могут проходить через вкладку. Однако это не проблема, потому что горизонтальное положение этих совпадений строго больше, чем в первой копии, поэтому эти совпадения остаются на своих местах.Остальное довольно просто:
Мы удаляем пробелы и нули из входных данных.
И , наконец , мы проверяем , что весь вход состоит из пробельных завершающих строк формы
1(-11)*
, т.е. контрастной последовательности1
и-1
которая начинается и заканчивается1
(так как в противном случае он не суммируется с1
).источник
Желе, 15 байт
Попробуйте онлайн!
источник
Pyth, 16 байт
Попробуйте онлайн: демонстрация или тестовый набор
Объяснение:
источник
Желе , 11 байт
Возвращает 1 для знакопеременных матриц, 0 в противном случае. Попробуйте онлайн! или проверьте все контрольные примеры .
Фон
Независимо от нулей, каждая строка и столбец должны состоять из шаблона (1, -1) * 1 , то есть чередующихся вхождений 1 и -1 , начинающихся и заканчивающихся 1 (таким образом, сумма равна 1 ).
Чтобы убедиться в этом, мы берем массив всех строк и столбцов и соединяем их, используя -1 в качестве разделителя. Поскольку все конечные точки равны 1 , результирующий плоский массив удовлетворяет шаблону (1, -1) * 1 тогда и только тогда, когда это делают строки и столбцы.
Для фактического теста мы вычисляем накопленную сумму массива. Для матрицы чередующихся знаков результатом будет массив из 0 и 1 , который заканчивается на 1 .
Мы обращаем кумулятивную сумму и дедуплицируем ее, сохраняя порядок начальных вхождений всех уникальных элементов. Для достоверного ввода результатом будет список [1, 0] .
Чтобы вывести соответствующее логическое значение, мы конвертируем дублированные кумулятивные суммы из двоичного в целое и проверяем, равен ли результат 2 .
Как это устроено
источник
MATL,
18161513 байт3 байта сохранены благодаря @Luis
Это решение принимает двумерный массив в качестве входных данных и выводит массив истинности или ложности . Важно отметить, что в MATL истинный массив состоит из всех ненулевых элементов, в то время как результат Фальси имеет по крайней мере один нулевой элемент. Вот еще одна демонстрация массивов правды / фальши .
Попробуйте онлайн
Модифицированная версия, чтобы показать все тестовые случаи
объяснение
источник
Юлия, 36 байт
Попробуйте онлайн!
источник
JavaScript (ES6),
112100 байтВыравнивает массив и его транспонирование в строки, затем (игнорируя
0
s) проверяет шаблон1-11...1-11
в каждой строке.Изменить: Сохранено 12 байтов благодаря @PeterTaylor.
источник
-11-1...-11-1
потому что , так как записи чередуются и имеют положительную сумму, должен быть один больше ,1
чем-1
, так что шаблон должен быть1-11...1-11
.Python 2,
6360 байтВход представляет собой список кортежей.
Это заканчивается кодом выхода 0 для переменных знаковых матриц и кодом выхода 1 в противном случае. Это то, что делают true и false , и - как показано в разделе проверки - это действительно может использоваться как условие, например, в скрипте Bash.
верификация
Тест-cases.txt
test-suite.sh
Выход
Как это устроено
Независимо от нулей, каждая строка и столбец должны состоять из шаблона (1, -1) * 1 , то есть чередующихся вхождений 1 и -1 , начинающихся и заканчивающихся 1 (таким образом, сумма равна 1 ).
Чтобы убедиться в этом, мы заархивируем / транспонируем входную матрицу M , добавим результат в M (теперь состоящий из списка строк и столбцов) и добавляем -1 к каждой строке / столбцу.
Например, если M - одна из следующих матриц (действительная, недействительная)
результаты
Чтение сгенерированной матрицы по строкам должно привести к плоской последовательности с шаблоном (-1, 1) * . Чтобы убедиться, что это так, мы берем совокупную сумму всех записей, начиная с верхнего ряда.
Для примеров матриц это приводит к
Для действительной матрицы знакопеременных выходной результат будет состоять из -1 и 0 и - так как каждый -1 отменяет предыдущее 1 и наоборот - никаких других чисел.
На первый взгляд может показаться, что проверка последнего столбца с 1 не выполнена . Однако для матрицы n × n, содержащей k нулей, допустимые строки будут содержать n + k единиц. Если бы действовали также все столбцы, кроме последнего , в столбцах было бы n + k - 1 , что невозможно.
Чтобы проверить, что других чисел нет, мы сохраняем частичные суммы в переменной s и обновляем их для каждой записи сгенерированной матрицы с помощью
s+=[n][s]
.Если s = 0 или s = -1 , это эквивалентно
s+=n
. Однако для всех других значений s это вызывает IndexError , поэтому Python немедленно завершается с кодом выхода 1 . Если этого не произойдет ни в какой момент, программа завершает работу с кодом завершения 0 .источник
R, 54 байта
Анонимная функция, использует ту же логику, что и ответы Денниса на Python 2, Jelly и Julia.
источник