First, I just made up the name, sorry if it refers to something else. In the “games you didn’t finish” I said regarding Kingdom Hearts Re: Chain of Memories:
A very brief problem statement is that we’re drawing from an arbitrary pool of cards with various properties to create an ordered queue. Each consecutive set of three cards in this queue must satisfy some (invariant) constraint. After every consecutive triple is determined to have been met successfully, the second and third cards of each triple are re-enqueued. We continue doing this constraint check until we either have fewer than 3 cards after re-enqueing, or a triple fails to meet the given constraint.
The trick is, each card has a weight, and the deck has a weight limit. The trick is to create a deck from your pool within the weight limit that satisfies the constraint a maximal number of times.
Here’s a more thorough description:
You are given an ordered deck c ∈ D with n slots, and have a (non-unique) collection of cards c∈C where each c is represented by an ordered triple (v,w, t) where v represents the value of the card in the range [0,9], w represents the “weight”, and t represents the “type” (similar to suits in normal cards – this is only important for certain sleights).
The limits of the deck are such that (Σ[sub]c ∈ D[/sub] c.w) <= n. That is, the sum of the weights of all cards in the deck must not exceed the number of slots n. For simplicity’s sake, a deck is also a queue. That is, any operation on the deck must draw the cards from the top of the deck in order, you cannot seek to an arbitrary card*. For instance, in the deck of cards with values v (5,4,4,2,5), the next sleight (see below) must take 5,4,4 in order.
Our goal is to make a “sleight” deck. A sleight (s) is an operation on 3 consecutive cards** such that if constraint(c1,c2,c3) is met, the sleight executes. One example is the Blitz sleight, which checks if all 3 cards have a type in the attack class (a “class” is kind of like “red” or “black” in cards – it’s an arbitrary group of multiple types/suits) and that the sum of the values of c1,c2, and c3 are in the range [10,15]. So in the example above, assuming all cards are attack cards, the deck (5,4,4,2,5) we would add 5+4+4=13 and check if it’s within the sleight threshold, which it is.
A more complicated example is the “Sonic Blade” sleight which checks if the values are between 20-23 and all cards are “attack” cards, and the type t of c1,c2, and c3 are all different.
So why is this a “cascading” constraint? Well, we have to introduce another operation: reloading. When the size of the deck stack drops below 3, we “reload” the deck. It’s a bit hard to explain this in words, but I’ll try. In programming terms, the easiest way to think of it is this: consider a second, initially empty temporary deck D2. When a sleight is executed, it will enqueue the second and third arguments into the new deck. “Reloading” will enqueue all cards remaining in D into D2 and swap D and D2 as the active deck. Again, using the example above –
D = (5,4,4,2,5)
sleight(D)
// D is now (2,5)
reload(D)
// D is now (4,4,2,5), because the sleight got rid of the first card
So now we can get to the actual problem statement:
Given a pool of cards, write an algorithm to construct a deck that does not exceed some weight limit n that executes the maximal number of sleights across all reloads. The end-state is when a sleight is no longer possible. That is, either the current triad in the deck does not satisfy the conditions for a sleight (e.g. the deck (3,3,3) would not satisfy a Blitz deck because 9 is not in the range [10,15]) or there are fewer than 3 cards in the deck after reloading.
Again, here’s the example I made in my post in the Game Room:
5 5 3 5 2 4 6 2 -> 5 3 2 4 6 2 -> 3 2 6 2 -> 2 6 2
This deck executes the Blitz sleight. First it executes the sleights (5,5,3),(5,2,4). After reload its state is (5,3,2,4,6,2) and executes the sleights (5,3,2),(4,6,2). Then it reloads into (3,2,5,2) and executes (3,2,5). Then it reloads to (2,6,2) and executes (2,6,2). Then it reloads to (6,2) and we’ve halted after executing 6 sleights.
I’ve mostly glossed over the card weights w and the deck size limit n, mostly because I don’t know the weights off the top of my head and the deck limits are way too big to facilitate simple examples. However, do note that the deck limit is absolutely imperative to the challenge. Generally, higher value cards have bigger weights, except the 0 value card which is the most weighty***. I think this is at least as hard as the Knapsack problem, and I honestly have no idea where to begin constructing a non-naive algorithm for it.
This is mostly for fun, but I thought I’d post it for ideas.
Here is a Go script that simulates our Blitz deck, as well as having commented code examples of a few other sleights.
- This isn’t actually true in the game, but sleight decks aren’t very useful if you have to seek to execute them.
** There are actually a couple sleights in the game that use 2 cards, but they’re not good enough to actually build decks around so I’m omitting them for simplicity.
*** This is because in-game 0 is a “trump card”. This is mostly irrelevant to sleights
