Home > Reflections | ⏮️ ⏭️

2024-06-08

🧠 Education

🦵🏻 SHIN SPLINTS for Runners: Challenges, Causes, and Rehab
🦴 How to Reduce Bone Injury Risks | Running Science

🏋️ Revisiting numberToWords

While planning my solution to numberToWords yesterday, I mentioned that there was a recursive feel to the problem.
However, I implemented an iterative solution.
In practice, iterative solutions are safer and tend to be more performant.
But recursive solutions can be more elegant, intelligible, and easier to write.
This is partly because recursion allows us to leverage the implicit function call stack provided by the language runtime.
If we’re skilled at identifying recursive problems and implementing recursive solutions, we can save ourselves the time, effort, and complexity of implementing the stack that the corresponding iterative solution will require.

Here’s my recursive solution.

const UNDER20_WORDS = [  
  'Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six',  'Seven', 'Eight', 'Nine', 'Ten',  
  'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen'  
]  
const DECADE__WORDS = [,, 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']  
  
const nonZeroNumberToWords = (n: number): string[] => n ? [numberToWords(n)] : []  
  
const numberToWords = (n: number): string =>  
    n < 2e1  
  ? UNDER_20_WORDS[n]  
  : n < 1e2  
  ? [DECADE__WORDS[Math.floor(n / 1e1)], ...nonZeroNumberToWords(n % 1e1)].join(' ')  
  : n < 1e3  
  ? [numberToWords(Math.floor(n / 1e2)), 'Hundred', ...nonZeroNumberToWords(n % 1e2)].join(' ')  
  : n < 1e6  
  ? [numberToWords(Math.floor(n / 1e3)), 'Thousand', ...nonZeroNumberToWords(n % 1e3)].join(' ')  
  : n < 1e9  
  ? [numberToWords(Math.floor(n / 1e6)), 'Million', ...nonZeroNumberToWords(n % 1e6)].join(' ')  
  : [numberToWords(Math.floor(n / 1e9)), 'Billion', ...nonZeroNumberToWords(n % 1e9)].join(' ')  

If we squint at the recursive implementation, we may notice some repetition.
We can leverage the common pattern to derive a more data-driven implementation.
This version highlights the sparsity of unique logic required.
A couple of lookup tables, some threshold comparisons, division, string concatenation, and recursion are all we need to convert numbers to English words.
I probably wouldn’t go this far in an interview, though.

const UNDER20_WORDS = [  
  'Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six',  'Seven', 'Eight', 'Nine', 'Ten',  
  'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen'  
]  
const DECADE__WORDS = [,, 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']  
const PATTERN = {  
  2e1: { divisor: 1e0, lookup: n => UNDER20_WORDS[n], suffix: [] },  
  1e2: { divisor: 1e1, lookup: n => DECADE__WORDS[n], suffix: [] },  
  1e3: { divisor: 1e2, lookup: n => numberToWords(n), suffix: ['Hundred'] },  
  1e6: { divisor: 1e3, lookup: n => numberToWords(n), suffix: ['Thousand'] },  
  1e9: { divisor: 1e6, lookup: n => numberToWords(n), suffix: ['Million'] },  
  5e9: { divisor: 1e9, lookup: n => numberToWords(n), suffix: ['Billion'] },  
}  
const THRESHOLDS = Object.keys(PATTERN)  
  
const nonZero = (num: number): string[] => num ? [numberToWords(num)] : []  
  
function numberToWords(n: number): string {  
  const { suffix, lookup, divisor } = PATTERN[THRESHOLDS.find(threshold => n < +threshold)]  
  return [lookup(Math.floor(n / divisor)), ...suffix, ...nonZero(n % divisor)].join(' ')  
}