At World Cup Season…

Some people think — and I agree — that the UEFA Champions League is a more relevant tournament than the World Cup itself, but we cannot deny that an event of this magnitude is really awesome to keep an eye on. Even those who doesn’t love the sport tend to follow the teams, the matches, the celebration.

And with the World Cup comes the sweepstakes. Lots of.

Although the rules might change from one place to another, these are the ones we use the most here in Brazil:

1. Everyone try to predict the score of a particular match, paying a fixed amount for each guess (eg $1.00).
2. At the end, the ammount collected is divided equally among the winners. If there are no winners: (a) the sweepstake “accumulates”¹, or (b) everyone get their money back, or (c) you-crazy-rule-here.

I like this kind of sweepstake, but it could be better in some respects.

First, not everybody has the habit of carrying small bills around, so the sweepstakes manager (a.k.a. YOU) loses a lot of time chasing change. Besides, I think the fixed-valued bet is kind of boring since the amount collected is divided equally among the winners. I think things get more exciting when people can choose how much to pay for each guess, so the amount collected is divided proportionally among the winners. In this case, when several people win, earns more who bets more.

Since I don’t like to do the math myself, here’s the challenge: create a program that receives a list with all guesses and returns the list of winners along with the proportional amount to be paid to each one of them.

So, shall we?

Solving the problem… with Clojure

Write more code than necessary is going out of style these days, so I decided to code a solution in Clojure, a functional programming language that makes this sort of “problem” really easy to solve. Just launch the REPL and profit!

The first thing to do is define how to represent each guess:

(defstruct bet :name :amount :guess :rate)

All guesses has the same information. That’s why we defined a StructMap with the keys :name, :amount, :guess, and :rate.

A list of possible guesses might be:

(def pool
     [(struct bet "Daniel" 2.0 [2 0]) ;; Daniel bets $2.00 on score 2x0
      (struct bet "John"   4.0 [0 0]) ;; John bets $4.00 on score 0x0
      (struct bet "Maria"  1.0 [2 0]) ;; Maria bets $1.00 on score 2x0
     ])

Okay, we already know how each guess is represented. Now, how to find the sweepstake’s total amount? Simple, all we have to do is to sum the amount of all guesses:

(defn pool-amount [poolseq]
  (reduce + (map :amount poolseq)))
 
;; testing
(pool-amount pool)
=> 7.0

Great, but how much each guess represent in relation to the whole, that is, what’s the proportion of each guess? All we have to do is to divide the amount of each guess by the sweepstake’s total amount:

(defn pool-rates [poolseq]
  (let [sum (pool-amount poolseq)]
    (map #(assoc % :rate (/ (:amount %) sum)) poolseq)))
 
;; testing
(map :rate (pool-rates pool))
=> (0.285 ..., 0.571 ..., 0.142 ...)
 
(reduce + (map :rate (pool-rates pool)))
=> 1.0

Note that, if everyone wins, the amount earned by John would be the double of the amount earned by Daniel, which would be the double of the amount earned by Maria. Justice, finally!

To finish the code, we just need a function that filters the winners and calculates how much to pay to each winner:

(defn pool-winners [poolseq result]
  (let [sum (pool-amount poolseq)
        winners (filter #(= (:guess %) result) poolseq)]
    (map #(assoc % :amount (double (* (:rate %) sum))) (pool-rates winners))))
 
;; testing
(pool-winners pool [1 0]) ;; no winners
=> ()
 
(pool-winners pool [0 0]) ;; just one winner
=> ({:name "John", :amount 7.0, :guess [0 0], :rate 1.0})
 
(pool-winners pool [2 0]) ;; several winners
=> ({:name "Daniel", :amount 4.66 ..., :guess [2 0], :rate 0.66 ...}
    {:name "Maria", :amount 2.33 ..., :guess [2 0], :rate 0.33 ...})

A major advantage of this solution is that it allows you to bet on anything. Want to bet on the sex of a baby shortly after the good news (or bad news, whatever)?

(def pool [(struct bet "Daniel" 3.0 :male)
           (struct bet "John"   5.0 :female)
           (struct bet "Maria"  1.0 :female)])
 
(pool-winners pool :female)
=> ({:name "John", :amount 7.5, ...} {:name "Maria", :amount 1.5, ...})

There you go, a simple solution for a simple problem.

The code

Although it’s possible to solve this problem in Lisp/Clojure with a one-liner (the Reader works with data structures after all), I decided to write a code that is as readable as possible for those who are starting with Clojure:

(defstruct bet :name :amount :guess :rate)
 
(defn pool-amount [poolseq]
  (reduce + (map :amount poolseq)))
 
(defn pool-rates [poolseq]
  (let [sum (pool-amount poolseq)]
    (map #(assoc % :rate (/ (:amount %) sum)) poolseq)))
 
(defn pool-winners [poolseq result]
  (let [sum (pool-amount poolseq)
        winners (filter #(= (:guess %) result) poolseq)]
    (map #(assoc % :amount (double (* (:rate %) sum))) (pool-rates winners))))

Your turn

Do you program in Haskell? Python? Ruby? Brainfuck? How would you solve such problem in your favorite programming language?

Update (Nov 3, 2010). Common Lisp solution, using copy-* to avoid changes in state:

(defstruct bet name amount guess rate)
 
(defun pool-amount (pool)
  (reduce #'+ (mapcar #'bet-amount pool)))
 
(defun pool-rates (pool)
  (let ((sum (pool-amount pool)))
    (mapcar (lambda (bet)
              (let ((x (copy-bet bet)))
                (setf (bet-rate x) (/ (bet-amount x) sum))
                x)) pool)))
 
(defun pool-winners (pool result)
  (let ((sum (pool-amount pool))
        (winners (loop for bet in pool when (equal (bet-guess bet) result) collect bet)))
    (mapcar (lambda (winner)
              (let ((x (copy-bet winner)))
                (setf (bet-amount x) (* (bet-rate x) sum))
                x)) (pool-rates winners))))