Day 19 - Linen Layout

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • @[email protected]English
    2•1 month ago

    I don’t know much about Rust but I assume the HashMap<String, i64> requires hashing on insertion and lookup, right? I realized that, for every design, all the strings you’ll see are substrings of that design from different starting positions, so I made my lookup table int pos -> int count. The table is reset after every design.

    • @[email protected]OPM
      2•1 month ago

      That does mean that if two or more strings end with the same substring, you’d recalculate those substrings? Would be a faster lookup cost though, clever.

      My code ran in 120ms, so its pretty damn fast as is, especially compared to the non-memoised version

      edit: Tried the array of lengths method, shaved about 20ms off. Not bad, but probably not my main issue either

      • @[email protected]English
        3•1 month ago

        That does mean that if two or more strings end with the same substring, you’d recalculate those substrings?

        I hadn’t really considered that, but yes. I’m inclined to think that replacing hash table lookups with plain array indexing (which this allows) outweighs that downside but I’m not sure. Indeed 120ms is pretty damn fast!

        • @[email protected]OPM
          1•1 month ago

          It saved me 20ms, and given your using C, saved you dealing with uthash or similar, so probably worth it.

          The hashmap is probably a more generic solution though

          • @[email protected]English
            2•1 month ago

            Certainly more generic and less prone to user error too. Indeed dealing with hash maps or any advanced data structure is a pain with C, this is where generics or templates really shine, especially if you have control over lifetime aspects as you do with C++ or Rust (e.g. moves, lvalue references, constness, etc).