Generating Repeatable, Pseudorandom Sequences

I'm working on a game called GeoMarin which is a Wordle-style guessing game that tests your geography knowledge of Marin county. Similar to how Wordle has a dictionary of thousands of words to use as possible solutions, one of the tasks I need to complete for GeoMarin is to essentially create a "dictionary" of locations to use as possible solutions. With this, I would generate one random solution per day which would be the same solution across all instances of the game; basically the same way Wordle works.

The challenge is that I'm hosting this on GitHub pages, and I don't have a server to query the API of. I could run a CRON job daily and publish a new answer, but I wanted a way to run the game with only a frontend. That way, it would be easier to test it while developing as well. (I know, I could use a Live Server. I do have one installed in VS Code!)

Indexing a Random Number

Basically, my idea was to use the number of days since the epoch (Jan. 1st, 1970) to use as some kind of "index", which will be a unique, sequential number each day. Also, this will be the same number across ALL games. I'm just not going to worry about time zones for now. So, this was a good start.

function daysSinceEpoch(): number {
    const msPerDay: number = 1000 * 60 * 60 * 24;
    return Math.floor(Date.now() / msPerDay);
}

Using this "index", I considered installing a seeded random number generator and setting a new seed each day, but that could (rarely) cause the same answer twice in a row. Also, it might repeat answers before exhausting the full "dictionary" of solutions. So basically, I wanted a way to "shuffle" the dictionary and use the function above to select the index for the daily solution.

Picking a Solution

Let's say my dictionary contains 10 solutions (indices 0 through 9). One way to exhaust all 10 solutions before repeating any would just be to take $d \mod 10$ (where $d$ is the number of days since the epoch.) This technically works, but basically just increments the index by 1 each time and then wrapping around after all 10 have been reached. This is not the best, because I won't be consciously randomizing my dictionary as I build it, so I'll have "clusters" of similar answers, and even if I did, keen players might memorize the sequence of solutions after all of them have been reached.

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 ...

The idea I finally settled on was to multiply $d$ by some factor, so instead of a simple increment by 1, now I have $(r \times d) \mod 10$ where $r$ is some special number. Now the question is how do I pick $r$ so that I get enough "randomness" and still ensure that my other conditions are met? Let's say I pick $r=2$.

0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 ...

Huh, interesting, the sequence repeated itself before exhausting all the possibilities. So it looks like you can't pick $r$ as just any arbitrary number, it has to be specifically chosen. $r=3$ seems to work.

0 3 6 9 2 5 8 1 4 7 0 3 6 9 2 5 8 1 4 7 ...

It used up all the numbers before repeating the pattern. So if $r=2$ doesn't work but $r=3$ works, what is the difference? As it turns out, if $r$ shares any factors with the number of solutions (10 in this case) then we'll have this early-repeating behavior. Since the factors of 10 are 2 and 5, if we set $r=5$ we'll see the same thing.

0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 ...

Even if they only share some factors, like $r=8$, we won't see all the possible solutions before it recycles.

0 8 6 4 2 0 8 6 4 2 0 8 6 4 2 0 8 6 4 2 ...

If you "reflect" $r$ (e.g. $r'=10-r$, like 2 and 8 for example) then you get the exact same sequence but just in reverse.

And in case you were wondering, if you set $r>10$, it will behave the same way as $r-10$ because of the modulo operator. The way I think of it is that you have $r$ numberlines of solutions, starting at the beginning, and incrementing each time by $r$. Notice how when $r=3$ and $r=13$, the second index (1) is 3 both times.

r=2

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0   1   2   3   4   5   6   7   8   9

r=3

0 1 2(3)4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 ...
0     1     2     3     4     5     6   ...

r=13

0 1 2 3 4 5 6 7 8 9 0 1 2(3)4 5 6 7 8 9 ...
0                         1             ...

The Most "Random"

So basically what I found out is that $r$ cannot share any factors with 10, being the number of dictionary solutions. Mathematically that makes them coprime.

That doesn't necessarily mean that either number is prime, it only means that they cannot share any factors. One of the numbers being prime can help, though!

So how do I pick the best $r$? Remember how I said earlier that if I set $r>\text{N}_\text{sln}$ then I get the exact same sequence as $r-10$. Also, if I "reflect" $r$ like $r'=10-r$, then I just get the same sequence in reverse. Lastly, I don't need to consider $r \le 0$. So, I only need to consider the following coprimes in this range for $r$.

$$1 \le r \le \left\lfloor \frac{1}{2}\cdot\text{N}_\text{sln} \right\rfloor$$

I've determined that somewhere in the middle is the ideal spot. To determine coprimes, I implemented Euclid's Algorithm to determine the greatest common divisor (GCD) of the two values. If $\text{GCD} = 1$, then they are coprime and I can generate repeatable, pseudorandom sequences using my formula.

$$ x = (r \times d) \mod \text{N}_\text{sln}$$