Рассмотрим массив целых чисел:
[1, 0, 9, 1, 3, 8]
Есть много способов разделить этот список на последовательные списки. Вот три:
A: [[1, 0, 9], [1, 3, 8]]
B: [[1], [0, 9], [1, 3], [8]]
C: [[1, 0], [9, 1], [3, 8]]
Мы будем называть разбиение Y и утонченность другого раздела X , если X может быть получено из Y , соединив несколько его подсписков вместе.
Так B
есть уточнение A
: если мы объединим две первые и две последние подсписки вместе, мы получаем A
. Но C
это не уточнение A
: мы должны были бы разделить 9
и 1
, чтобы оправиться A
от этого. Кроме того, любой раздел является тривиальным уточнением самого себя.
Обратите внимание, что мы не можем переставлять любые списки или элементы в любой точке.
Соревнование
Учитывая два раздела (списки списков целых чисел) X
и Y
, определить, Y
является ли уточнениеX
.
Вы можете предположить, что разделы будут содержать только целые числа от 0
до 9
, включительно. Вы не должны предполагать, что X
и Y
являются разделами одного и того же списка (если они не являются, они также не являются уточнениями друг друга). X
и / или Y
может быть пустым, но никогда не будет содержать пустых списков.
Вы можете написать программу или функцию, принимая ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и выводя результат через STDOUT (или ближайшую альтернативу), возвращаемое значение функции или параметр функции (out).
Ввод может быть сделан в любой удобной строке или формате списка. Поскольку элементы будут состоять только из однозначных целых чисел, вы можете опустить разделитель в подсписках, но убедитесь, что 0
возможны начальные s. Вы можете взять X
и Y
в обратном порядке.
Вывод должен быть правдивым, если Y
уточнение, X
и ложным в противном случае.
Ваш код должен быть в состоянии решить каждый из приведенных ниже тестовых примеров за 1 секунду на подходящем настольном компьютере. (Это всего лишь проверка работоспособности, чтобы избежать простых переборов.)
Это код для гольфа, так что самый короткий ответ (в байтах) выигрывает.
Тестовые случаи
Каждый тестовый пример находится в отдельной строке, записанной как X Y
. Я использую обозначение массива в стиле GolfScript / CJam, чтобы сэкономить пространство по горизонтали:
Truthy:
[] []
[[0]] [[0]]
[[1 0 9 1 3 8]] [[1 0 9] [1 3 8]]
[[1 0 9 1 3 8]] [[1 0 9 1 3] [8]]
[[1 0 9 1 3 8]] [[1] [0] [9] [1] [3] [8]]
[[1 0 9] [1 3 8]] [[1 0 9] [1 3 8]]
[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]
[[9 8 8 5 8 2 7] [5] [1 4] [2 0 0 6 0 8 4 2 6 4 2 3 7 8 7 3 9 5 7 9 8 2 9 5] [3 9 8] [7 1 4 9 7 4 5 9] [3 3 3] [9 0 7 8] [3 9 4 7 2 7 8 0 3 0] [8 2 2 7 3 9 3 2] [2 9 0 8 5 4 1 8 5 5 6 2 0 9 2 7 7 9 2 7] [3 6] [1 2 7 7 4 4 2 9]] [[9 8] [8] [5 8 2] [7] [5] [1 4] [2] [0 0 6] [0] [8 4 2] [6 4] [2] [3] [7 8] [7 3] [9] [5 7 9] [8 2] [9 5] [3] [9 8] [7 1 4] [9 7] [4 5 9] [3 3] [3] [9 0] [7 8] [3] [9] [4] [7 2] [7 8] [0] [3 0] [8 2] [2] [7 3] [9 3] [2] [2] [9] [0] [8 5 4] [1 8] [5 5] [6] [2 0] [9] [2] [7 7 9] [2 7] [3 6] [1 2] [7 7] [4 4 2] [9]]
Falsy:
[[0]] []
[[0]] [[1]]
[[1 0 9]] [[1 0 9] [1 3 8]]
[[1 0 9] [1 3 8]] [[1 0 9 1 3 8]]
[[1 0 9] [1 3 8]] [[1 0 9]]
[[1 0 9] [1 3 8]] [[1 0] [9]]
[[1 0 9] [1 3 8]] [[1 0] [9 1] [3 8]]
[[1] [0 9] [1 3] [8]] [[1 0 9] [1 3 8]]
[[9 8 8 5 8 2 7] [5] [1 4] [2 0 0 6 0 8 4 2 6 4 2 3 7 8 7 3 9 5 7 9 8 2 9 5] [3 9 8] [7 1 4 9 7 4 5 9] [3 3 3] [9 0 7 8] [3 9 4 7 2 7 8 0 3 0] [8 2 2 7 3 9 3 2] [2 9 0 8 5 4 1 8 5 5 6 2 0 9 2 7 7 9 2 7] [3 6] [1 2 7 7 4 4 2 9]] [[9 8] [8] [5 8 2] [7] [5 1] [4] [2] [0 0 6] [0] [8 4 2] [6 4] [2] [3] [7 8] [7 3] [9] [5 7 9] [8 2] [9 5] [3] [9 8] [7 1 4] [9 7] [4 5 9] [3 3] [3] [9 0] [7 8] [3] [9] [4] [7 2] [7 8] [0] [3 0] [8 2] [2] [7 3] [9 3] [2] [2] [9] [0] [8 5 4] [1 8] [5 5] [6] [2 0] [9] [2] [7 7 9] [2 7] [3 6] [1 2] [7 7] [4 4 2] [9]]
Leaderboards
Вот фрагмент стека, который генерирует как регулярную таблицу лидеров, так и обзор победителей по языкам.
Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:
# Language Name, N bytes
где N
размер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:
# Ruby, <s>104</s> <s>101</s> 96 bytes
<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51719</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>
Связанные проблемы
источник
[[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]]
или[["109" "138"] ["1" "09" "13" "8"]]
будет приемлемый формат ввода?Ответы:
CJam,
13109 байтПопробуйте онлайн в интерпретаторе CJam .
Спасибо @ MartinBüttner за предложение оригинального формата ввода @ edc65 .
Спасибо @ jimmy23013 за улучшение формата ввода и добавление 3 дополнительных байтов.
I / O
вход
Сублисты отделены
;
друг от друга,
:Выход
Как это устроено
Для строк разной длины
.-
в массиве останутся символы, которые не могут быть равны целым числам 0 или 15.источник
;
качестве разделителя ...ll.m27m0-!
.,
и;
оба являются общим синтаксисом массива (и ни один из них не используется CJam). Благодарность!Pyth, 19 байт
Попробуйте онлайн: демонстрация или тестовая привязь
Я использую формат кортежа / списка Пита в качестве входных данных. Просто замените пробелы на запятые.
Объяснение:
Поскольку псевдокод все еще немного сбивает с толку, я продемонстрирую алгоритм на примере ввода.
.u+NYdY
Часть вычисляет все непрерывные подсписки, которые содержат первый элемент.B
является уточнениемA
, если каждый непрерывный подсписокA
также является непрерывным подспискомB
(есть только одно исключение).Поэтому я просто проверяю, является ли множество непрерывных подсписков из
A
множества подмножеством непрерывных подсписков изB
(gF_m.u+NYdYQ
).Единственное исключение - если первый список ввода содержит меньше элементов, чем второй список ввода. Например
<Fm.u+YdYQ
, вернетсяTrue
для ввода[[1]],[[1],[2]]
.Поэтому я также проверяю, равны ли объединенные списки
&...qFsMQ
.источник
JavaScript ( ES6 ), 67
70редактировать 3 байта, сохраненные thx @apsillers
Запустите фрагмент ниже в Firefox, чтобы проверить
источник
OK
иKO
.С 69
75Функция с 2 строковыми параметрами, возвращающая 0 или 1.
Формат параметра: подсписок, разделенный пробелами (''), элементы списка, разделенные запятыми.
Пример:
"1,0,9 1,3,8"
"1,0 9,1,3,8"
Меньше гольфа
Тест Ideone (устаревший)
источник
Haskell, 76 байт
Возвращает
True
илиFalse
. Пример использования:[[1,0,9],[1,3,8]] # [[1,0],[9]]
->False
.Простой рекурсивный подход: если первые элементы совпадают, продолжайте с хвостами, иначе начните сначала, но объедините два элемента в начале второго списка. Базовые случаи: оба списка пустые ->
True
; оба списка с одним элементом -> сравнить их; только один список пуст ->False
.источник
CJam, 19 байтов
Попробуйте онлайн.
I / O
вход
Выход
идея
Каждый раздел может быть однозначно идентифицирован, соблюдая следующие два свойства:
Список формируется путем объединения всех подсписков.
«Точки разреза», включая крайности списка.
Мы можем объединить оба критерия в один, заменив каждую точку вырезания подсписком элементов от точки вырезания до конца списка.
Чтобы убедиться, что данный раздел более тонкий, чем другой, нам нужно только проверить, является ли более грубый раздел, представленный, как указано выше, подмножеством более тонкого и совпадают ли самые большие списки обоих разделов.
Код
Для ввода из примера ввода / вывода стек содержит
перед выполнением
-!
.Обратите внимание, что первый элемент каждого массива имеет завершающий пробел. Это гарантирует, что мы сравниваем полный список первого ввода с полным списком второго.
источник
CJam, 24 байта
Алгоритм
Здесь мы просто используем жадный алгоритм, чтобы увидеть,
N
можно ли объединить первые подсписки второго списка, чтобы сформировать первый подсписок первого списка. Как только такойN
найден, мы удаляем первыйN
подсписки из второго списка и первый подсписок из первого списка и повторяем процесс.В идеале, если второй список является уточнением первого, нам следует оставить 2 пустых списка в стеке. Мы просто проверяем это и печатаем,
1
если это так. В любой другой комбинации, после полной итерации по подспискам второго списка, мы не получим 2 пустых списка. Таким образом,0
будет напечатан для таких случаев.Расширение кода
Попробуйте онлайн здесь или запустите полный набор тестов здесь
источник
C
120114 байтовЯ не так много играл в гольф в последнее время, поэтому я решил попробовать это.
Мы определяем функцию,
R(char* s, char* t)
которая возвращает,1
еслиt
является уточненным разделомs
, и в0
противном случае.s
и,t
как ожидается, будут в формате,[DDDD...][DDDD...]...
где каждыйD
является другим однозначным элементом.Тестовый код:
Выше напечатано следующее:
Кажется, работает, по крайней мере.
источник
Haskell,
525053 байтаПолностью отличается от моего другого решения . Использует тот же умный формат ввода, что и в ответе @ edc65 , т.е. элементы разделяются
,
и списки с.
Пример использования:
"1,0,9,1,3,8" # "1,0,9 1,3,8"
->True
.Второй параметр - это уточнение первого, если они имеют одинаковые элементы в каждой позиции или первый
,
. Я должен добавить уникальный маркер конца (->..
) к обоим параметрам, потому чтоzipWith
усекает более длинный параметр и, например"1,2,3" # "1,2"
, также будетTrue
.источник
(\a b->a==b||a>b)
это просто(>=)
."."
вместо".."
работы тоже?"2"#"1"
потому что функции только проверяют, являются ли значения больше, а не равны"."
не будет работать, потому что это даст ложный положительный результат,"2,1" # "2"
который будет сначала расширяться до,"2,1." # "2."
а затем обрезатьсяzipWith
до"2," # "2."
. Запятая в первой строке соответствует всему.Mathematica, 65 байт
источник
Математика с регулярными выражениями это весело!
ES6 Javascript, 53 символа
Винтажный Javascript, 70 символов
Использует тот же формат ввода, что и в ответе edc65 .
Полное демо, включая все тестовые примеры здесь.
источник
Mathematica, 55 байт
Это определяет безымянную функцию, беря два раздела в одном списке , в обратном порядке (т.е.
Y
первый,X
второй).объяснение
Это проверяет, что оба раздела фактически являются разделами одного и того же списка.
Это форма моего подхода к Mathematica.SE , которая вдохновила меня на этот вопрос . По сути, раздел определяется как ряд индексов, в которые вставляются разделители, и это проверяет, что все позиции разделения
X
также появляютсяY
, накапливая длины подсписков.источник
Python 2,
6851 байтСпасибо xnor за значительную экономию байтов!
Анонимная функция, которая принимает две строки формы
"1,0,9 1,3,8"
(взяты из ответа C edc65 ) и возвращаетTrue
илиFalse
. Новая версияmap(None)
больше не работает в Python 3.Тестирование:
Предыдущее 92-байтовое решение, которое принимает входные данные как
"109 138"
:источник
None
а другой индекс имеет номер, посколькуi==j or"0">i>j
не может удерживаться.i==','
. Это позволяет вам комбинировать тесты какi in[',',j]
(мы не можем сделатьi in ','+j
), потому что этоj
может бытьNone
.b
есть номер в этом месте?" ... забыть, что с этим форматом ввода это невозможно.