19 January 2021

FLPoTD: Writing Checks

This problem was inspired by a puzzle on the 2021 Mystery Hunt:

Given a string S of characters from the latin alphabet (a-z), find the smallest nonnegative amount (dollars and cents) whose spelled-out representation contains S as a subsequence.

  • The dollar amount should not include 'and': 123 is "one hundred twenty three", not "one hundred and twenty three".
  • If the amount is less than $1.00 (one dollar and zero cents), then the dollar amount is omitted: $0.46 is "forty six cents"
  • The cents is always expressed: $46.00 is "forty six dollars and zero cents"
  • This table contains the names of powers of 10: https://en.wikipedia.org/wiki/Power_of_10#Positive_powers
Follow-up:
  • Given a list of strings, all of which use exclusively lowercase letters, find the most expensive word.