Expand description
§Handy Haversacks
A hashtable would be a natural data structure for this problem but is a little slow. To make things faster we implement the hashtable using an array and a combination of three perfect hash functions that map from each combination of bag descriptions to a unique index.
There are 18 different adjectives, for example shiny, bright, dark. Taking only the first two letters in enough to discriminate. For example the hash value for “shiny” is:
"sh" =>
26 * 's' + 'h' =>
26 * (115 - 97) + (104 - 97) =>
26 * 115 + 104 - 2619 =>
475
There are 33 different colors, for example white, gold, blue. The first two letters result in some duplicates, however incrementing the second letter if the length is odd is enough to discriminate.
These first two hash values are then used to lookup consecutive indices from 0 to 17 and 0 to 32 respectively, which are then combined into a third hash value from 0 to 593 to form a perfect minimal hash function.
Part one and part two are very similar. A recursive solution with memoization of previously seen values computes the result efficiently.
Structs§
Constants§
Functions§
Type Aliases§
- Bag 🔒