Algorithm to build tri-nodes in MapleStory



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 (2×9=3×6). 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 3×6=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.