Problem 17: Anzahl von Buchstaben von Zahlen

Gesucht wird die Anzahl von Buchstaben, die alle Zahlen, von 1 bis 1000 in englischen Worten geschrieben, benötigen! [ das englische Original ]

Interessant bei diesem Problem ist sicherlich die englische Schreibweise, bei der aber alle Leerzeichen und Bindestriche ignoriert werden sollen. Wenn man sich die Zahlen genauer anschaut, stellt man fest, dass nur der Bereich von 1 bis 19 außergewöhnlich ist. Alle anderen Zahlen setzen sich aus wiederkehrenden Worten zusammen. Daher habe ich mir erst einmal eine Tabelle mit Basisworten erstellt:

@Override
public void prepare() {
   super.prepare();

   Cache = new Hashtable< Integer, Integer >();

   SpokenNumbers = new Hashtable< Integer, String >();
   SpokenNumbers.put(    1, "one" );
   SpokenNumbers.put(    2, "two" );
   SpokenNumbers.put(    3, "three" );
   SpokenNumbers.put(    4, "four" );
   SpokenNumbers.put(    5, "five" );
   SpokenNumbers.put(    6, "six" );
   SpokenNumbers.put(    7, "seven" );
   SpokenNumbers.put(    8, "eight" );
   SpokenNumbers.put(    9, "nine" );
   SpokenNumbers.put(   10, "ten" );
   SpokenNumbers.put(   11, "eleven" );
   SpokenNumbers.put(   12, "twelve" );
   SpokenNumbers.put(   13, "thirteen" );
   SpokenNumbers.put(   14, "fourteen" );
   SpokenNumbers.put(   15, "fifteen" );
   SpokenNumbers.put(   16, "sixteen" );
   SpokenNumbers.put(   17, "seventeen" );
   SpokenNumbers.put(   18, "eighteen" );
   SpokenNumbers.put(   19, "nineteen" );
   SpokenNumbers.put(   20, "twenty" );
   SpokenNumbers.put(   30, "thirty" );
   SpokenNumbers.put(   40, "forty" );
   SpokenNumbers.put(   50, "fifty" );
   SpokenNumbers.put(   60, "sixty" );
   SpokenNumbers.put(   70, "seventy" );
   SpokenNumbers.put(   80, "eighty" );
   SpokenNumbers.put(   90, "ninety" );
   SpokenNumbers.put(  100, "hundred" );
   SpokenNumbers.put( 1000, "thousand" );
}

Die Ermittlung der Anzahl der Buchstaben für eine gegebene Zahl konnte ich auf dieser Basis in eine private Methode auslagern:

private int getLetterCount( int num ) {

   if( Cache.containsKey( num ) )
      return Cache.get( num );

   int res = 0;

   if( num < 20 ) {
      res = SpokenNumbers.get( num ).length();
   } else if( num < 100 ) {
      int digit = num % 10;
      if( digit > 0 ) {
         res = getLetterCount( digit );
      }
      res += SpokenNumbers.get( num - digit ).length();
   } else if( num < 1000 ) {
      int digits = num % 100;
      if( digits > 0 ) {
         res = getLetterCount( digits );
         res += "and".length();
      }
      res += SpokenNumbers.get( ( num - digits ) / 100 ).length();
      res += SpokenNumbers.get( 100 ).length();
   } else {
      res = SpokenNumbers.get( 1 ).length();
      res += SpokenNumbers.get( 1000 ).length();
   }

   return res;
}

Die eigentliche Lösung war nun kein Problem mehr.  Einen kleinen Cache musste ich dennoch einbauen:

@Override
public String solve() {
   long res = 0;

   for( int i=1; i<=1000; i++ ) {
      int cnt = getLetterCount( i );
      Cache.put( i, cnt );
      res += cnt;
      IO.debugln( i + " => " + cnt + " => " + res );
   }

   return IO.l2s( res );
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 17 kann man sich hier anschauen!

<< Problem 16 Übersicht Problem 18 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: