WordNumbers: Counting letters of number names, alphabetized and concatenated
3 days ago
- #Haskell
- #Puzzles
- #Monoids
- ITA Software uses puzzles to recruit computer scientists, such as finding the 51 billionth letter when numbers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated.
- The solution involves using Haskell and concepts like monoids and differentiation.
- The approach involves specifying how to write integers as English words, exploiting repetitive structure in these strings.
- Lists of strings form a seminearring, which is a monoid with an additional associative operation, useful for concatenating strings efficiently.
- The seminearring properties allow for concise expression of number words, leveraging Haskell's type classes and operators.
- The strategy includes writing a program to specify the problem and creatively interpreting it to find a solution efficiently.
- The post introduces initial Haskell code to define number words up to 999,999,999, but brute-force computation for higher numbers is impractical.