Programming Challenge

I know this is old:

http://www.flownet.com/ron/papers/lisp-java/

....but I ran across it for the first time just yesterday and was
intrigued, especially when I read that Peter Norvig accomplished the
task in Lisp in just 45 lines of code, and that no C++ programmers
could even come close to that.

I did cheat a little bit, because I glanced at Norvig's solution (but
didn't study it) before realizing that I was interested in approaching
the problem myself. But it was also obvious to me, since the original
problem was designed to show off Lisp, that the most concise solution
was most likely a recursive one.

I spent about 2 hours on it total: I spent about 1.5 hours (with
concentration broken several times) last night. I went back to it
today and commented it and made some improvements (I'm not nearly as
tired today as I was last night) in about 30 minutes.

I'm probably not the first one in this newsgroup to do this, but this
is the result. About 50 lines of
non-comment/non-whitespace/80-chars-max-per-line code:

------------------
// Problem statement: http://www.flownet.com/ron/papers/lisp-java/
#include <fstream>
#include <iostream>
#include <map>
#include <string>
#include <cctype>

typedef std::multimap<std::string, std::string> Dictionary;
Dictionary dict;

// According to the problem statement, the input is assumed to be
correct, so
// there is little point in doing error checking here. Just map the
letter to
// the appropriate position in the array.
char lookup_digit(char const c) {
                             // abcdefghijklmnopqrstuvwxyz
  static char const digits[] = "57630499617851881234762239";
  return digits[std::tolower(c) - 'a'];
}

// Associate numbers to dictionary words (ignoring punctuation
characters).
// Do this by loading each word, converting it to its numeric
representation,
// then inserting the pair into the dictionary.
void create_dictionary() {
  std::ifstream fin("dictionary.txt");
  std::string word;
  while (fin >> word) { // could have used istream_iterator here
    std::string n = word;
    n.erase(std::remove_if(n.begin(), n.end(), ispunct), n.end()); //
strip "
    std::transform(n.begin(), n.end(), n.begin(), lookup_digit); // to
numeric
    dict.insert(std::make_pair(n, word));
  }
}

// Attempt to match numbers to words in the dictionary by looking up
each
// substring until a match is found. If a match is not found, insert a
single
// digit into the result, and continue searching. If that search
fails, then
// abort. This is done recursively because, for each phone number,
there is a
// possible "tree" of results.
void word_search(std::string const& display, std::string const& number,
    std::string const& acc, bool const is_number = false) {
  if (number.empty()) { // found a full representation of the number
    std::cout << display << ':' << acc << std::endl;
  } else { // continue matching
    bool found_match = false;
    for (int sz = 1; sz <= number.size(); ++sz) {
      std::string const sub = number.substr(0, sz);
      Dictionary::const_iterator i = dict.equal_range(sub).first;
      Dictionary::const_iterator const end =
dict.equal_range(sub).second;
      if (i != end) found_match = true;
      for (; i != end; ++i)
        word_search(display, number.substr(sz), acc + ' ' + i->second);
    }
    if (!found_match && !is_number)
      word_search(display, number.substr(1), acc + ' ' + number[0],
true);
  }
}

// For each phone number in the input, attempt to perform a
word/dictionary
// search for any possible matches. Strip '/' and '-' characters out
of the
// input first.
void associate_phone_numbers() {
  std::ifstream fin("input.txt");
  std::string number;
  while (fin >> number) {
    std::string s = number;
    s.erase(std::remove_if(s.begin(), s.end(), ispunct), s.end()); //
strip /-
    word_search(number, s, std::string());
  }
}

int main() {
  create_dictionary();
  associate_phone_numbers();
}

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]