Генератор карт Dobble / SpotIt

15

Вступление

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).
Джонатан Аллан

Ответы:

5

Python 2 , 192 162 байта

У меня есть аргумент, что это дает максимальный набор карт для каждого сценария, и он обрабатывает 3 тестовых случая.

from itertools import*
def m(a,s):
    C=["".join(x)for x in combinations(a,s)]
    while len(C):
        print C[0]
        C=list(set(A for A in C if len(set(A)&set(C[0]))==1<s))

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

Алгоритм

Учитывая алфавит 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будет максимальным решением, потому что мы ни разу не выбрали элемент, который можно было отличить от любого другого элемента.


Тестовые случаи

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

a=["a","b","c"]
b=2
c=3
d=m(a,b)
print d,len(d)==c
>> ['bc', 'ab', 'ac'] True

a=["a","b","c","d","e","f","g"]
b=3
c=7
d=m(a,b)
print d,len(d)==c
>> ['aef', 'abc', 'bde', 'ceg', 'adg', 'cdf', 'bfg'] True

a=["a","b","c","d","e"]
b=4
c=1
d=m(a,b)
print d,len(d)==c
>> ['abcd'] True

Обновить

  • +9 [16-12-07] Соответствует требованию печати
  • -11 [16-12-07] Вычеркнули мою Rпеременную
  • -30 [16-12-09] Гольф моя Kпеременная, спасибо @Leo !
NonlinearFruit
источник
1
Вы действительно должны вычитать множество K из C на каждом шаге? Я думаю, что фильтрация, которую вы делаете ( 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]
Лев
Я писал задачу Dobble в песочнице, и Дом Гастингс указал мне на этот вопрос как на возможный обман (который вполне может быть), однако я заметил одну вещь: гораздо сложнее сделать полную колоду Dobble из N * N + N + 1 карты (и символы) с N + 1 символами на карту, где N - не простое простое число. Для N = 4 = 2 ^ 2 это будет колода, использующая 4 * 4 + 4 + 1 = 21 символ и такое же количество карт; однако это решение дает колоду всего из 13 карт - но 21 возможна .
Джонатан Аллан
@JonathanAllan Только что добавил ссылку TIO. Я запустил функцию с алфавитом из 21 символа и по 5 символов на карту. В нем выведено 21 карт. Я думаю, что это правильно, если я не понял неправильно.
Нелинейно-
Хм, извините, я, должно быть, сделал какую-то ошибку, запустив ее локально ( Это полная колода Dobble 4-го порядка. :) )
Джонатан Аллан
2

Haskell, 175 156 байт

Мой первый опыт игры в гольф, дайте мне знать, если я что-то напутал.

import Data.List
f 0_=[[]]
f n a=g$c n a
c n a=[a!!i:x|i<-[0..(length a)-1],x<-f(n-1)(drop(i+1)a)]
g[]=[]
g(x:t)=x:g(filter(\z->length(z`intersect`x)<= 1)t)

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

Спасибо @Paul Mutser за улучшение и -19 байт


Оригинальная версия

ошибки
источник
1
Добро пожаловать в PPCG! Обратите внимание, что импорт засчитывается в ваш счет. Возможное улучшение: 156 байт, включая импорт
Пол Муцер
Спасибо за внимание, я не был уверен, что они сделали!
ошибки