2
$\begingroup$

This problem is originated from the game MapleStory, where the player needs to build "tri-nodes" to enhance there skills, and each skill should appear in two different tri-nodes. For my character, kanna, I want to enhance 9 skills with 6 tri-nodes (2x9=3x6). After thinking a while for an optimal strategy, it seems to me that the problem isn't that easy. I henceforth abstracted it into an algorithm problem showing below. Please let me know if there is anything unclear in the problem description. Thanks.

A card is a tuple of three letters in [a,b,c,d,e,f,g,h,i], and the three letters within a card are different. For example, (a,b,c) could be a card, but (a,a,c) can't be because there are two same elements.

We can take exactly 6 cards to acquire 3x6=18 letters, and we want each letter in [a..i] appears exactly twice. However, we cannot take two cards that share the same first element. For example, the following set of cards satisfy the requirement. Each letter appeared exactly two times, and the first elements of these cards are unique.

[(a,b,c)(b,c,a)(d,e,f)(e,f,d)(g,h,i)(h,g,i)]

For a deck of $n$ cards ($n$ can be any integer), if there is a set of 6 cards that satisfies the above requirement, we say that this deck is complete, otherwise we say it's incomplete.

Given a deck of cards,

  • (a) determine if the deck is complete.

if the deck is complete, find an algorithm to

  • (b) find a solution.
  • (c) find all solutions.

If the given deck is incomplete, the requirement cannot be satisfied with the cards in the deck. In such case, a randomly generated new card will be added into the deck. The new card is generated randomly, meaning that [a..i] are equally probable at each position of the card tuple (but still the three positions will be different). After adding a random card, if the deck is still incomplete, another new random card will be added again. As such, we can expect that as the number of cards -> $\infty$, the deck will eventually become complete.

  • (d) Find an algorithm to take $m$ cards ($m<6$) from the deck, such that
    1. $m$ is as large as possible;
    2. each letter appears at most twice;
    3. it is possible to take $(6-m)$ new cards that may be added in the future to satisfy the requirement. List these new cards.

For example, the following deck is incomplete: (a,b,c)(d,a,e)(f,d,c)(b,e,f)(g,c,b) We cannot take all of them because there will be more than 2 b's and c's.

we can have two solutions:

  1. (a,b,c)(d,a,e)(f,d,c)(b,e,f)

with the appearance count [a:2,b:2,c:2,d:2,e:2,f:2,g:0,h:0,i:0]

and the needs count [g:2,h:2,i:2]

  1. (d,a,e)(f,d,c)(b,e,f)(g,c,b)

    with the appearance count [a:1,b:2,c:2,d:2,e:2,f:2,g:1,h:0,i:0]

    and the needs count [a:1,g:1,h:2,i:2]

For the former solution, we want the new cards, for example, (g,h,i)(h,g,i). For the latter one, we want the new cards, for example, (h,a,i)(i,g,h). The possibilities of getting the needed cards might be different.

  • (e) There might be multiple solutions for (d). Find one that has the maximum possibility to satisfy the requirement with fewest new cards.
$\endgroup$
3
  • $\begingroup$ You talk about the "first" element of a card. Is a card always in sorted order? Or is (b,c,a) a possible card? $\endgroup$ – D.W. Sep 8 '20 at 7:54
  • $\begingroup$ You don't state any requirements on the algorithm. In particular, you have no requirements on its efficiency, and no information on how algorithms should be evaluated. Do you care about asymptotic running time? Practical performance? If practical performance, how large is a deck (typically), i.e., how many cards are typically in the deck? $\endgroup$ – D.W. Sep 8 '20 at 7:57
  • $\begingroup$ @D.W. no it's not sorted. (b,c,a) is possible, though the order of the latter two elements doesn't matter. $\endgroup$ – Ruixing Wang Sep 8 '20 at 9:06
0
$\begingroup$

Problems (a),(b),(c) can be solved in polynomial time; simply enumerate all possible ways of choosing a subset of 6 cards and test each subset to see whether it satisfies all of the constraints.

If you care about a practical algorithm, I would suggest using a SAT solver. It is easy to express this problem as an instance of SAT. Use boolean variable $x_i$ to represent whether the $i$th card in the deck is chosen or not. Then you can write boolean constraints that express each of your constraints. I suggest using an off-the-shelf solver like Z3 to solve this instance of SAT; they will tell you whether any solution exists, and if so, give you one example. If you want to find all solutions, look up algorithms to find all satisfying instances to SAT.

Problems (d),(e) are more challenging but can also be solved in the same way. Iterate over $m=5,4,3,\dots$ and for each $m$ use a SAT solver to test whether there exists a solution for that value of $m$. There are at most 120 different cards, so you can imagine having a deck and a sidebar of all the other cards not in the deck; let $x_i$ represent whether the $i$th card in the deck is chosen, and $y_i$ represent whether the $i$th card in the sidebar is chosen, and express as an instance of SAT.

$\endgroup$
0
$\begingroup$

I have written a python code for (c) find all solutions. (I am not sure but am I doing dynamic programming?).

(d) and (e) may be difficult.. let's see..

letters = [
    'a', 'b', 'd', 'f', 'e', 'c', 'h', 'i',
    'g'
]

current_deck = [['c', 'f', 'd'], ['a', 'b', 'h'],
                ['e', 'a', 'f'], ['d', 'h', 'e'],
                ['c', 'i', 'g'], ['i', 'g', 'c'],
                ['a', 'c', 'g'], ['d', 'c', 'b'],
                ['i', 'd', 'h'], ['g', 'b', 'd'],
                ['g', 'a', 'i'], ['c', 'e', 'f'],
                ['b', 'd', 'f'], ['i', 'b', 'g'],
                ['g', 'c', 'i']]

needs_dict = {}
for i in letters:
    needs_dict[i] = 2


count = [0]

def find_all_solutions(current_deck, needs_dict, first_blacklist, cards_taken,
                    sol):
    count[0] += 1
    if all(v == 0 for v in needs_dict.values()):
        sol.append(cards_taken)
        return cards_taken
    if len(current_deck) == 0:
        return False

    card = current_deck.pop()

    # we cannot take it
    if card[0] in first_blacklist or \
    card[0] not in needs_dict or card[1] not in needs_dict or card[2] not in needs_dict or  \
    needs_dict[card[0]] == 0 or needs_dict[card[1]]==0 or needs_dict[card[2]]==0:
        return find_all_solutions(current_deck, needs_dict, first_blacklist,
                               cards_taken, sol)
    else:
        # we can but don't take it
        donttake = find_all_solutions(current_deck[:], needs_dict,
                                   first_blacklist[:], cards_taken[:], sol)
        # we take it, update needs_dict
        dic = needs_dict.copy()
        for i in card:
            dic[i] = dic[i] - 1
        take = find_all_solutions(current_deck[:], dic,
                               first_blacklist + [card[0]],
                               cards_taken + [card], sol)

        return sol


def check_a_solution(sol, needs_dict):
    dic = needs_dict.copy()
    for i in sol:
        for j in i:
            dic[j] -= 1
    return all(v == 0 for v in dic.values())


solutions = find_all_solutions(current_deck, needs_dict, [], [], [])

for i in solutions:
    assert check_a_solution(i,needs_dict)

print(solutions)
print(count)
$\endgroup$
1
  • $\begingroup$ We discourage code-only answers. We'd prefer that you get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. We're not a coding site. See here and here for related meta discussions. $\endgroup$ – D.W. Sep 10 '20 at 6:47

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.