Year: 2013

C++

The C++ version follows the same strategy as the Python program, using the C++ standard library equivalents of Python’s dictionaries and lists. I’ve left out the globbing, as the C++ STL doesn’t have functions for that. The typical use of this kind of commandline function would rely on the shell for globbing as I have here. Of course, if your shell is CMD.EXE you’re SOL. This program didn’t take that long to write, but it took ages to debug due to the heavy use of templates.

#include <iostream>
#include <map>
#include <string>
#include <cmath>
#include <fstream>
#include <iterator>
#include <vector>
#include <algorithm>

using namespace std;

bool value(const pair<string, int>& a, const pair<string, int>& b)
{ 
  return a.second > b.second;
}


int main (int argc, char *argv[]) {
  for (int i=1; i<argc; i++) {
    ifstream infile(argv[i]);
    map<string, int> counter[2];

    cout << argv[i] << endl;

    // read file
    string word, previousword;
    bool firstword=true;

    while (infile >> word) {
      counter[0][word]++;
      if (!firstword) {
        counter[1][previousword + " " + word]++;
        previousword = word;
      } else {
        firstword = false;
      }
    }

    for (int c=0; c<2; c++) {
      cout << "Words:" << c+1 << endl;

      // sort
      vector<pair<string,int> > wordlist;
      copy(counter[c].begin(), counter[c].end(), 
           back_inserter<vector<pair<string, int> > >(wordlist));
      sort(wordlist.begin(), wordlist.end(), &value);
    
      // write output
      for (int j=0; j < 10; j++) {
        cout << wordlist[j].first << ": " << wordlist[j].second << endl;
      }
    }
  }
}

Java

The guy had said that a typical Java program to do this was about 100 lines. Here is my attempt. Again, I have tried to keep the basic philosophy the same as with the Python program, using the Java standard library for maps and sorting rather than getting clever. Interestingly, this Java program is both the largest and the slowest of the lot. The Eclipse IDE cut a little of the time off writing this, and the Java generics are much easier to debug than C++ templates.

import java.io.*;
import java.util.*;

public class ngrammer {

  public static void main(String[] args) throws FileNotFoundException {

    class WordCounter extends HashMap<String, Integer> {

      class ValueComparator implements Comparator<Map.Entry<String, Integer>> {
        // Comparator to allow sorting on the value of the HashMap elements
        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
          return o2.getValue() - o1.getValue();
        }
      }

      void add(String word) {
        if (containsKey(word)) {
          put(word, get(word)+1);
        } else {
          put(word, 1);
        }
      }
        
      void printN(Integer N) {
        // Prints the top N elements of the counter
        // Make a list of the counter entries
        List<Map.Entry<String,Integer>> entries = new LinkedList<Map.Entry<String,Integer>>(entrySet());
        // Sort it on the value
        Collections.sort(entries, new ValueComparator());
        // Print out at most N items       
        int i=N;
        for (Map.Entry<String,Integer> entry: entries) {
          System.out.println(entry.getKey() + ": " + entry.getValue());
          if (--i == 0) break;
        }
      }
    }
        
    final int topN = 10;
    
    // Process each file in the input arguments
    for (int fi = 1; fi < args.length; fi++) {
      File file = new File(args[fi]);
      // Initialise new counters
      WordCounter[] counter = {new WordCounter(), new WordCounter()};
      String word, previousword="";
      // Tokenise file
      Scanner scanner = new Scanner(file);
      while (scanner.hasNext()) {
        word = scanner.next();
        counter[0].add(word);
        if (!previousword.isEmpty()) 
          counter[1].add(previousword + " " + word);
        previousword = word;
      }
      // Report
      System.out.println("Filename:" + file.getAbsolutePath());
      for (int i = 0; i < counter.length; i++) {
        System.out.println("Words: " + (i+1));
        counter[i].printN(topN);
      }
    }
  }
}

C#

Note that this is my least fluent language, so this may be inelegant. Also, before you say it, I did have a version that used Linq. This was much more succinct, but it was really dog slow. I was really surprised that this program was the fastest of all the ones on this page, especially since I was running it on Mono.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class MainClass
{

    class WordCounter : Dictionary<string, int>
    {
        public void CountWord (string word)
        {
            if (ContainsKey (word)) {
                this [word]++;
            } else {
                this [word] = 1;
            }
        }

        public void Report (int N)
        {
            var list = this.ToList ();
       
            list.Sort ((a, b) => { return b.Value.CompareTo (a.Value); });
            foreach (var item in list.Take(N)) {
                Console.WriteLine(item.Key + ": " + item.Value);
            }
        }
    }
    
    public static void Main (string[] args)
    {
      const int Ntop=10;

      foreach (string f in args) {
         WordCounter[] wordcounter = {new WordCounter(), new WordCounter()};

            string lastword = "";
            foreach (var word in File.ReadAllText(f).Split(' ')) {
                wordcounter[0].CountWord(word);
                if (lastword.Length > 0) {
                    wordcounter[1].CountWord (lastword + " " + word);
                }
                lastword = word;
            }

         Console.WriteLine(f);
         for (int i=1; i<2; i++) {
             Console.WriteLine ("Words: " + (i+1));
             wordcounter[i].Report (Ntop);
         }
      }
    }
}

$ grep "^...$" CSW12.txt

This gives you a full list of all the three letter words in the wordlist.

Of course, now we want to be able to figure out the scores of the words. The letter scores of the words are easily found on Wikipedia:

• 1 point: E ×12, A ×9, I ×9, O ×8, N ×6, R ×6, T ×6, L ×4, S ×4, U ×4
• 2 points: D ×4, G ×3
• 3 points: B ×2, C ×2, M ×2, P ×2
• 4 points: F ×2, H ×2, V ×2, W ×2, Y ×2
• 5 points: K ×1
• 8 points: J ×1, X ×1
• 10 points: Q ×1, Z ×1

BEGIN {score="0D1G1B2C2M2P2F3H3V3W3Y3K4J7X7Q9Z9"} # score table
/^...$/ { # Match three-letter words
   s=0; # accumulator for scores
   for(i=1;i<=length($0);i++) {
      # Find the current character in the score table
      # move one down for the score and add one
      s += 1+substr(score, 1+index(score, substr($1, i, 1)))}; 
      print s, $1
   }
}

$ awk 'BEGIN {score="0D1G1B2C2M2P2F3H3V3W3Y3K4J7X7Q9Z9"} /^...$/ {s=0; for(i=1;i<=length($0);i++) {s+=1+substr(score, 1+index(score, substr($1, i, 1)))}; print s, $1}' CSW12.txt | sort -nr | head

Notice that she missed out quite a few high-scoring words, and spent five years on this, while it took me a couple of minutes to bash out the script.

My observations are first, that it is clearly possible to compile a list like the article describes without using programming, but it would have taken her a lot less time to learn programming and then compile the list than it probably took her to compile it by hand. In this case, programming is avoidable, but definitely applicable.

I suppose she could also just have downloaded Zyzzyva (a scrabble word-lookup GUI program), but to be honest, I couldn’t get the list above as quickly, because the word scores weren’t in the program by default and I couldn’t figure out how to get them there.

Other implementations

I did a quick Python implementation as well, slightly less suited for one-liners on the commandline, but perhaps a little more legible:

table = {'A': 1, 'B': 3, 'C': 3, 'D': 2, 'E': 1, 'F': 4, 'G': 2, 'H': 4,
         'I': 1, 'J': 8, 'K': 5, 'L': 1, 'M': 3, 'N': 1, 'O': 1, 'P': 3,
         'Q': 10, 'R': 1, 'S': 1, 'T': 1, 'U': 1, 'V': 4, 'W': 4, 'X': 8,
         'Y': 4, 'Z': 1,
         }

wordsandscores = [(sum(table[c] for c in word), word) for word in
                  [w.strip() for w in open('CSW12.txt')] if len(word)==3]
wordsandscores.sort(reverse=True)

for s, w in wordsandscores[:10]:
    print s, w