Вступление
Dobble / SpotIt - это карточная игра, в которой люди должны в кратчайшие сроки найти один и тот же символ на паре карт, указать его и перейти к следующей паре. Каждая карта имеет несколько символов (8 в обычной версии), но ровно один является общим для каждой пары карт.
Пример из физической копии игры:
Вызов
Напишите программу, в которой по заданному набору символов (одиночные символы ascii) и количеству символов на одной карточке будут выводиться списки карточек с символами для каждой карточки. Очевидно, есть много эквивалентных комбинаций, ваша программа просто должна написать любую из комбинаций, которая производит наибольшее количество карт для заданного ввода.
Это код-гольф, поэтому чем короче код, тем лучше.
Было бы также здорово, если бы вычисление закончилось до тепловой смерти вселенной для самого сложного случая.
вход
Два аргумента для функции / stdin (ваш выбор)
Во-первых, это набор символов, например, «ABCDE» или ['A', 'B', 'C', 'D', 'E'] - ваш выбор формата, будь то строка, набор, список, поток или что-либо идиоматическое для выбранного языка. Символы будут заданы из набора [A-Za-z0-9], без дубликатов (поэтому максимальный размер входного набора символов равен 62). Они не будут упорядочены в ( так что вы можете получить "yX4i9A" также для случая с 6 символами).
Второй аргумент - целое число, указывающее количество символов на одной карточке. Это будет <= чем размер набора символов.
Выход
Выведите несколько строк, разделенных символами новой строки, каждая из которых содержит символы для одной карточки.
Примеры
ABC
2
>>>>
AB
BC
AC
Или
ABCDEFG
3
>>>>
ABC
BDE
CEF
BFG
AEG
CDG
ADF
Или
ABCDE
4
>>>>
ABCD
Советы
- Количество выпущенных карт не может быть больше количества различных символов, и во многих комбинациях оно будет значительно меньше.
- Возможно, вы захотите прочитать некоторые математические знания, если вам нужна помощь с математической стороной проблемы
Это мое первое испытание для игры в гольф, поэтому, пожалуйста, простите возможные проблемы с форматированием / стилем - я постараюсь исправить ошибки, если вы укажете их в комментариях.
источник
('abcdefghijklmnopqrstu', 5)
->['abcde', 'afghi', 'ajklm', 'anopq', 'arstu', 'bfjnr', 'bgkpt', 'bhlou', 'bimqs', 'cfkqu', 'cgjos', 'chmpr', 'cilnt', 'dfmot', 'dglqr', 'dhkns', 'dijpu', 'eflps', 'egmnu', 'ehjqt', 'eikor']
или другое 21-карточное рабочее решение. (Обратите внимание, что это проективная конечная плоскость порядка 4).Ответы:
Python 2 ,
192162 байтаУ меня есть аргумент, что это дает максимальный набор карт для каждого сценария, и он обрабатывает 3 тестовых случая.
Попробуйте онлайн!
Алгоритм
Учитывая алфавит
a
и размер картыs
, возьмите все комбинацииs
элементовa
и назовите ихC
, затем:C
, называйC0
C0
C
которых есть объединение сC0
не равным1
C
C
не опустеетЗатем распечатайте сохраненные элементы.
аргументация
Некоторое непустое подмножество
C
является нашим максимальным решениемK
. Поскольку он содержит как минимум один элемент, а любые два элемента неразличимы, выберите произвольный элементC0
, из которогоC
следует указатьK
. Для любого элементаe
вK
, количество элементовe
объединенияx
равно 1 дляx != e
вK
; поэтому исключите все элементы, вC
объединении которыхC0
нет кардинального числа 1. По тем же соображениям выберите новый произвольный элементC
, добавьте егоK
и уменьшитеC
. В конце концовC
это пустое множество иK
будет максимальным решением, потому что мы ни разу не выбрали элемент, который можно было отличить от любого другого элемента.Тестовые случаи
Эти тестовые случаи были написаны до того, как я понял, что печать была требованием.
Обновить
R
переменнуюK
переменная, спасибо @Leo !источник
A for A in C if len(set(A)&set(C[0]))==1
), уже удаляет выбранные элементы, если только s == 1 (в этом случае len (set (C [0]) & set (C [0])) будет равно 1). Вы можете сыграть в гольф со своей второй до последней линии, чтобы:C=[A for A in C if len(set(A)&set(C[0]))==1<s]
Haskell,
175156 байтМой первый опыт игры в гольф, дайте мне знать, если я что-то напутал.
Попробуйте онлайн!
Спасибо @Paul Mutser за улучшение и -19 байт
Оригинальная версия
источник
Perl 6 ,
8877 байтПопробуйте онлайн!
источник