code golf - wordCount

An example for one of the courses taught here, was a program that counts the number of occurrences of unique words in a file. It was written in Python, and was clean and concise enough.

Following is a Haskell version:

import Control.Arrow((&&&))

import Data.List(group,sort)

wordCount :: String -> [(String,Int)]
wordCount = map (head &&& length)
          . group . sort . words

haskell - lack of debugging and stack tracing

Haskell is a wonderful language. It provides a great level of abstraction and a fruitful ground for programming languages research.

But it lacks some certain things that other environments naturally have, like advanced debugging tools or to the least stack traces. Since the evaluation of a haskell program is a bit strange, conventional techniques are not generally applicable.

I've seen this video however, and if they do manage to integrate the tool into GHC with a reasonable degree of robustness and reliability, I think Haskell will have a great stack tracing toolkit. Moreover, since it is a playground for CS geeks, the proposed system will provide another fruitful ground to hack around.

I quite liked the approach.



Finding the needle: Stack Traces for GHC
Tristan Allwood, Simon Peyton-Jones and Susan Eisenbach
Haskell Symposium
Edinburgh 2009
ACM SIGPLAN

RE: eve/did=.talktalktalk... - haskell is just as good

RE: http://ozgurakgun.blogspot.com/2010/04/evedidtalktalktalk.html

If you implement a simple algorithm usings haskell's list comprehensions, the performance turns out to be just as good. Of course the tools mentioned in the previous post are a) general purpose tools, b) would be far better in harder problems.

Anyway, the interesting part of the haskell code is the following:

evedidtalk =
    [
        [e,v,d,i,t,a,l,k] |
        e <- [1..9],
        v <- [0..9] \\ [e],
        d <- [1..9] \\ [e,v],
        i <- [0..9] \\ [e,v,d],
        t <- [0..9] \\ [e,v,d,i],
        a <- [0..9] \\ [e,v,d,i,t],
        l <- [0..9] \\ [e,v,d,i,t,a],
        k <- [0..9] \\ [e,v,d,i,t,a,l],
        digitsToInt [e,v,e] * 9999 ==
        digitsToInt [d,i,d] * digitsToInt [t,a,l,k]
    ]

Here, evedidtalk is a list of digits, that satisfy the only constraint we have. The key to performance is limiting the number of alternatives generated using the \\ (list difference) operator.
A poor-in-performance alternative would be generating all possibilities and then checking for the second constraint we had, the alldiff.

Compiled with -O2 using ghc, this finds the two possible solutions in under a second (yet, slightly slower than tailor+minion).

eve/did=.talktalktalk...

I've stumbled across this problem recently: http://www.jimloy.com/puzz/evedid.htm

It is very much like the SEND + MORE = MONEY problem, but I thought it would be more interesting (=harder to solve). Nope, not at all.

OK, the problem is the following:

Find the digits E,V,D,I,T,A,L,K such that this equation holds: EVE/DID=.TALKTALKTALK...
EVE and DID are 2 numbers with 3 digits each, and .TALKTALKTALK... is a floating point number.

After exploiting the following property, the problem gets simpler:

0.TALKTALKTALK... = TALK/9999 (try it with a 4 digit number, if you want to see it in action: http://lmgtfy.com/?q=1234/9999)

Thus, the equation turns into EVE/DID = TALK/9999 and then to EVE*9999 = DID*TALK.

Now it is easy to write this as a constraint model. If we choose to model in Essence Prime, use Tailor[1] to generate a Minion[2] input file from it, and then use Minion to actually solve the problem, it is solved almost instantaneously. Thanks to these two great tools!

The model I used is the following:

ESSENCE' 1.0
    find E : int(1..9)
    find V : int(0..9)
    find D : int(1..9)
    find I : int(0..9)
    find T : int(0..9)
    find A : int(0..9)
    find L : int(0..9)
    find K : int(0..9)
such that
    (E*100 + V*10 + E*1) * 9999 = (D*100 + I*10 + D*1) * (T*1000 + A*100 + L*10 + K*1),   
    alldiff([E,V,D,I,T,A,L,K])

If you have tailor and minion installed, just run the following commands to solve the problem.

java -jar tailor.jar -aux-info -out evedidtalk.minion evedidtalk.eprime

minion evedidtalk.minion -findallsols

It only takes less than 1 sec (both commands together) to find all two possible solutions.

[1] http://www.cs.st-andrews.ac.uk/~andrea/tailor
[2] http://sourceforge.net/projects/minion