The implementation of the algorithm is the function
multiset_unrank in src/seed.rs of the source code.
The subroutine combination_unrank:
There are 24 stages in The Adventures of Captain Comic, with one item slot per stage.
There are 24 items in the game, not all distinct. There are 8 unique items (Corkscrew, Door Key, Boots, Lantern, Teleport Wand, Gems, Crown, Gold), 5 Blastola Colas, and 11 Shields.
The items with their multiplicities form a multiset. The output of the randomizer is a permutation of this multiset; i.e., an assignment of one item to each of the 24 item slots. We are looking for a way to assign a number to each distinct permutation. That number is called a rank and the process of recovering a permutation from a rank is unranking. A seed encodes a rank which determines the item assignment.
There's a straightforward way to rank and unrank permutations, the factorial number system.
Let's try unranking an item assignment from the rank r = 123456789012345678901234. We start with 24 empty item slots, numbered 0 to 23.
To place the Corkscrew, we take r mod 24, which will be a number between 0 and 23. In this case, 123456789012345678901234 mod 24 = 10, so we put the Corkscrew in item slot 10. Then we renumber the 23 remaining slots from 0 to 22, and divide out the Corkscrew's contribution to the rank by dividing r by 24 and rounding down. The new r = 123456789012345678901234 / 24 = 5144032875514403287551.
The next item to place is the Door Key, and there are 23 slots it might go in. Now we take r mod 23 and find 5144032875514403287551 mod 23 = 16, so the Door Key goes in the item slot that is now numbered 16. We divide r by 23 to get the new r = 5144032875514403287551 / 23 = 223653603283234925545. We renumber the 22 remaining slots from 0 to 21.
We repeat this process for every item. The assigned slot refers to the renumbered slots at each step; e.g. when the assigned slot is 0, it means to choose the leftmost slot that has not yet been assigned.
|item||r||# slots||assigned slot|
Here is the item assignment that results from the initial rank r = 123456789012345678901234:
The problem with using the factorial number system for unranking a seed is that it treats all the items as distinct—and they are not. There are multiple ranks that result in the same permutation, because the algorithm thinks each Blastola Cola is different from the other Blastola Colas, and each Shield is different from the other Shields. Because of this multiple counting, seeds are longer than they need to be—the number of seeds is 24! = 620448401733239439360000 ≈ 79 bits. Next, we will see that by not multiply counting indistinguishable permutations, we can reduce the size of the seed space to 24! / 5! / 11! = 129529505064960 ≈ 47 bits.
Only a small change is needed to make the above algorithm work for a multiset. Instead of assigning one item at a time, we will assign one group of distinct items at a time. We'll start by assigning the 8 unique items—up to this point the algorithm is unchanged. When we come to the point that we need to assign the 5 Blastola Colas into 16 remaining slots, we use what's left of r to select one of the = 4368 possible combinations of 16 items taken 5 at a time. We convert an integer into a combination using the combinatorial number system, which provides an unrank function for combinations. I won't go into detail on the combinatorial number system, but you can see the combination_unrank subroutine in the algorithm description.
We'll work through an example of unranking r = 123456789012345. We start with 24 empty item slots, numbered 0 to 23.
We handle each unique item as a "group" of 1 item. There are = 24 ways to choose 1 slot from 24 slots. To place the Corkscrew, we take r mod 24 = 9. We place the Corkscrew in item slot 9, renumber the remaining slots from 0 to 22, and divide out the Corkscrew's contribution to the rank by dividing r by 24 and rounding down. The new r = 123456789012345 / 24 = 5144032875514.
The process continues like this for all 8 unique items. Up to this point, the algorithm has been the same as the one using the factorial number system.
Now r = 4163, and we have to assign the 5 Blastola Colas into 16 remaining slots. The number of ways to do the assignment is = 4368. We take r mod 4368 = 4163, so we call combination_unrank(4163, 5) to get [15, 14, 10, 9, 3], and assign Blastola Colas to those slots. Then we renumber the remaining slots and set r = 4163 / 4368 = 0.
Now we have to assign the final item group of 11 Shields to 11 remaining slots. = 1 tells us there is only one way to do that. combination_unrank(0, 11) gives us that single combination, [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]. We assign the Shields to those slots and we are done.
Here is the trace of unranking 123456789012345.
|item group||r||# combinations||assigned slots|
|5×||4163||4368||[15, 14, 10, 9, 3]|
|11×||0||1||[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]|
The number of distinct item assignments, and therefore the number of ranks needed to represent them all, is 24! / 5! / 11! = 129529505064960. Another way to understand this number is as × × × × × × × × × .
A rank is an integer; for input to the program we have to encode it as a string. I defined two seed encodings, which are distinguished by their first character.
Originally, I only had the
But encoding the rank so directly makes it possible to mentally calculate some information about the item assignment.
To find the location of the Corkscrew, you just have to take the rank mod 24,
which is just about possible to do mentally when the rank is represented as a hexadecimal numeral.
The number of distinct item assignments is x = 129529505064960,
and x + 1 just happens to be a prime number, which means
the multiplicative group of integers mod x + 1
is a cyclic group.
43 is a generator of this group,
so 43n for 0 ≤ n < x
gives a permutation of the integers between 1 and x + 1 inclusive.
From there we subtract 1 to put it back into the range 0 to x − 1.
The randomizer now generates
2-format seeds by default,
but it still accepts
So that's your reward for reading this page,
you know that the randomizer accepts an additional seed format not documented on the main page.
of the live coding videos covers the implementation of
If you want the
2-format seed for a specific item assignment,
you have to do a discrete log,
but a discrete log on 48 bits is no big deal.
I got the rank of the vanilla item assignment, 7697433249082,
by running the algorithm in reverse.
Then I converted it to a
2-format seed as follows:
While developing the randomizer,
I found that the
unrank methods of
in SageMath 9.0
use an inefficient algorithm
unrank(r), for example,
works by enumerating every permutation starting from 0 and taking the rth one.
I wanted to improve them;
however Sage's functions are specified to number permutations in
and the algorithm I developed produces some other order,
so it's not a drop-in replacement.
After some more research I came up with more efficient algorithms.
It's in Sage ticket