grodin / countdown Goto Github PK

Deploying to Railway on the free tier means a max memory usage of 512Mb, which is quite low for a JVM app.

There are a few different options to make this run in constrained memory:

1. Rewrite it in Rust. Most comprehensive control of memory and not too tricky really.
2. Make the http4k app use less memory. Options here include:
   • using streaming deserialization,
   • creating an inline wrapper class for chars so they have a 1 byte representation (possibly won't actually decrease memory usage if every allocation uses 64 bits in reality),
   • use a smaller dictionary

A note about some ideas for further development once the basics are in place:

An idea to implement a single player version of a Countdown game:

To keep the server as stateless as possible, the game state is passed to the client, signed by the server. To play the next round, the client has to send the signed state token back to the server, which verifies the signature.

The disadvantage with this is that a client can just resend the same state token again to replay their latest round. So the state should include an opaque token which can only be used once. This creates state on the server, which is what this whole state-passing rigmarole is supposed to avoid.

However, if we also have a time limit to submit the next game request from when a given state is issued, the server only has to hold the state for the time limit. The traditional time limit for a Countdown round is 30s, so that with some leeway is a good default.

There are some ugly edge cases around DST and similar clock changes but these can probably be avoided by using a completely monotonic time for the time limit checking.

The functions subListsByBitSet is tricky to understand. There are tests that exercise it, so it's covered but it's still tech debt.

This issue is just to record the tech debt so it's not forgotten about.

One call I want to have is to get all words which can be formed from a given multiset of letters. The naive algorithm (check each word in the dictionary, and check if the multiset of letters for that word is a subset of the given one) is clearly slow.

Approaches I'm considering:

• a form of perfect hashing: calculate the set with multiplicity of letters for each word, and for each letter in the alphabet, take a prime to the power of the multiplicity, and take the product of all of these. This is unique for each distinct multiset of letters. We can use this as a hash function for a hash table.

  Computing all possible subsequences is then the same as computing this hash for the given sequence, computing all divisors of this (quick because we already have the prime-power decomposition) and looking them up in hash table.

  The main con for this method is that the maximum hash value of words in the dictionary I've got doesn't fit in a 64 bit Long. This wouldn't be a problem in rust but would be in Kotlin. All words of 12 or fewer letters works though.

  A big pro is that all the hashes can be precomputed (possibly even the hash table).

• using the algorithms from this paper. Requires writing the data structure from scratch and it's not clear how straightforward it would be to serialise/deserialise the built data structure. If it requires building it every time then it's potentially less useful.