C++ Implementation of Problem 17

View source code here on GitHub!

Includes

Solution

uint64_t p0017()
int main(int argc, char const *argv[])

Note

This function is only present in the Python test runner, or when compiling as a standalone program.

  1/*
  2Project Euler Problem 17
  3
  4I feel like there is a better way to recurse this problem, but I could not
  5think of one at the time
  6
  7Problem:
  8
  9If the numbers 1 to 5 are written out in words: one, two, three, four, five,
 10then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
 11
 12If all the numbers from 1 to 1000 (one thousand) inclusive were written out in
 13words, how many letters would be used?
 14
 15NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and
 16forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20
 17letters. The use of "and" when writing out numbers is in compliance with
 18British usage.
 19*/
 20#ifndef EULER_P0017
 21#define EULER_P0017
 22#include <stdint.h>
 23#include <iostream>
 24#include <stdexcept>
 25#include <string>
 26#include "include/macros.hpp"
 27
 28std::string ToString(uint64_t n);
 29std::string ToString(uint64_t n) {
 30    if (n >= 1000)
 31        return ToString(n / 1000 % 100) + " thousand";
 32    else if (n >= 100) {
 33        std::string hundreds = ToString(n / 100 % 10) + " hundred";
 34        if (n % 100)
 35            return hundreds + " and " + ToString(n % 100);
 36        return hundreds;
 37    }
 38    else if (n >= 20) {
 39        std::string tens = "";
 40        switch (n / 10) {
 41            case 2:
 42                tens = "twenty";
 43                break;
 44            case 3:
 45                tens = "thirty";
 46                break;
 47            case 4:
 48                tens = "forty";
 49                break;
 50            case 5:
 51                tens = "fifty";
 52                break;
 53            case 6:
 54                tens = "sixty";
 55                break;
 56            case 7:
 57                tens = "seventy";
 58                break;
 59            case 8:
 60                tens = "eighty";
 61                break;
 62            case 9:
 63                tens = "ninety";
 64                break;
 65            default:
 66                throw std::invalid_argument("n is not in the accepted range");
 67        }
 68        if (n % 10)
 69            return tens + "-" + ToString(n % 10);
 70        return tens;
 71    }
 72    switch (n) {
 73        case 1: return "one";
 74        case 2: return "two";
 75        case 3: return "three";
 76        case 4: return "four";
 77        case 5: return "five";
 78        case 6: return "six";
 79        case 7: return "seven";
 80        case 8: return "eight";
 81        case 9: return "nine";
 82        case 10: return "ten";
 83        case 11: return "eleven";
 84        case 12: return "twelve";
 85        case 13: return "thirteen";
 86        case 14: return "fourteen";
 87        case 15: return "fifteen";
 88        case 16: return "sixteen";
 89        case 17: return "seventeen";
 90        case 18: return "eighteen";
 91        case 19: return "nineteen";
 92        default: throw std::invalid_argument("n is not in the accepted range");
 93    }
 94}
 95
 96uint64_t EMSCRIPTEN_KEEPALIVE p0017() {
 97    uint64_t answer = 0;
 98    std::string filter[2] = {" ", "-"};
 99    size_t pos = 0, i;
100    for (uint32_t x = 1; x < 1001; x += 1) {
101        std::string str = ToString(x);
102        for (i = 0; i < 2; pos = 0, i++)
103            while ((pos = str.find(filter[i], pos)) != std::string::npos)
104                str.replace(pos, 1, "");
105
106        answer += str.length();
107    }
108    return answer;
109}
110
111PROGRAM_TAIL(p0017)
112#endif

Tags: word-problem, combinatorics