16
\$\begingroup\$

Introduction

Dobble/SpotIt is a card game, where people have to spot same symbol on pair of cards in shortest time, indicate it and move to next pair. Each card has multiple symbols (8 in normal version), but exactly one is common between each pair of cards.

Example from physical copy of game: Cards with examples of pairs

Challenge

Write a program, which given set of symbols (single ascii characters) and number of symbols on single card will produce output listing cards with symbols for each card. There are obviously many equivalent combinations, your program just has to write any of combinations which produces largest amount of cards for given input.

It is a code-golf, so shorter the code, better.

It would be also great if computation will finish before heat death of universe for most complicated case.

Input

Two arguments to function/stdin (your choice)

  • First of them being collection of symbols, something like 'ABCDE" or ['A','B','C','D','E'] - your choice of format, be it string, set, list, stream, or whatever is idiomatic for language of choice. Characters will be given from set of [A-Za-z0-9], no duplicates (so maximum size of input symbol set is 62). They won't be neccesarily ordered in (so you can get "yX4i9A" as well for 6-symbol case).

  • Second argument is integer, indicating amount of symbols on single card. It will be <= than size of symbol set.

Output

Print multiple lines separated by newlines, each one of them containing symbols for single card.

Examples

ABC
2
>>>>
AB
BC
AC

Or

ABCDEFG
3
>>>>
ABC
BDE
CEF
BFG
AEG
CDG
ADF

Or

ABCDE
4
>>>>
ABCD

Hints

  • Number of cards produced cannot be larger than amount of distinct symbols and in many combinations it will be considerably smaller
  • You might want to read up Some math background if you need help with math side of the problem

This is my first code golf challenge, so please forgive possible issues with formatting/style - I'll try to correct errors if you point them in comments.

\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – Peter Taylor Nov 27 '16 at 16:02
  • \$\begingroup\$ Suggested test-case ('abcdefghijklmnopqrstu', 5) -> ['abcde', 'afghi', 'ajklm', 'anopq', 'arstu', 'bfjnr', 'bgkpt', 'bhlou', 'bimqs', 'cfkqu', 'cgjos', 'chmpr', 'cilnt', 'dfmot', 'dglqr', 'dhkns', 'dijpu', 'eflps', 'egmnu', 'ehjqt', 'eikor'] or some other 21-card working-solution. (Note that this is the projective finite plane of order 4). \$\endgroup\$ – Jonathan Allan May 29 '18 at 22:39
5
\$\begingroup\$

Python 2, 192 162 bytes

I have an argument that this produces the maximum set of cards for every scenario and it does handle the 3 test cases.

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))

Try it online!

Algorithm

Given an alphabet a and a card size s, take all combinations of s elements in a and call it C, then:

  • Take the first element of C, call it C0
  • Save C0
  • Remove all elements fromC that have a union with C0 not equal to 1
  • Repeat with second element of C
  • Continue until C is empty

Then print the saved elements.

Argument

Some non-empty subset of C is our maximal solution, K. Since it contains at least one element and any two elements are indistinguishable, choose an arbitrary element, C0, of C to be in K. For any element e in the K, the cardinality of e union x is 1 for x != e in K; so eliminate all elements in C whose union with C0 does not have cardinallity 1. By the same reasoning, choose a new arbitrary element in C, add it to K, and reduce C. Eventually C is the empty set and K will be the maximal solution because at no point did we choose an element that was distinguishable from any other element.


Test Cases

These test cases were written before I realized that the printing was a requirement.

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

Update

  • +9 [16-12-07] Fit the print requirement
  • -11 [16-12-07] Golfed out my R variable
  • -30 [16-12-09] Golfed out my K variable, Thanks to @Leo!
\$\endgroup\$
  • 1
    \$\begingroup\$ Do you really need to subtract the set K from C at every step? I think the filtering you do (A for A in C if len(set(A)&set(C[0]))==1) already removes the chosen elements, unless s==1 (in this case len(set(C[0])&set(C[0])) would be 1). You could golf your second to last line to: C=[A for A in C if len(set(A)&set(C[0]))==1<s] \$\endgroup\$ – Leo Dec 9 '16 at 8:26
  • \$\begingroup\$ I was writing a Dobble challenge in the sandbox and Dom Hastings pointed me to this question as a possible dupe (which it may well be), however one thing I noticed is that it is much harder to make a full Dobble deck of N*N+N+1 cards (and symbols) with N+1 symbols per card with N being a non-prime prime-power. For N=4=2^2 this would be a deck using 4*4+4+1=21 symbols and the same number of cards; however this solution produces a deck of only 13 cards - yet 21 is possible. \$\endgroup\$ – Jonathan Allan May 29 '18 at 22:30
  • \$\begingroup\$ @JonathanAllan Just added a TIO link. I ran the function with an alphabet of 21 characters and with 5 characters per card. It output 21 cards. I think this is correct unless I misunderstood. \$\endgroup\$ – NonlinearFruit Jul 11 '18 at 17:31
  • \$\begingroup\$ Hmm, sorry, I must have made some mistake running it locally then! (That's a Full Dobble Deck of Order 4. :)) \$\endgroup\$ – Jonathan Allan Jul 11 '18 at 17:43
2
\$\begingroup\$

Haskell, 175 156 bytes

My first take at golfing, let me know if I've messed something up.

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)

Try it online!

Thank to @Paul Mutser for improvement and -19 bytes


Original version

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 88 bytes

{my@c=combinations $^a,$^n;while @c {my \d=@c.pop;say d.join;@c=grep {+($_∩d)==1},@c}}

I swear the byte count wasn't intentional.

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.