Posts Tagged ‘cup’

Programming Praxis – Facebook Hacker Cup 2013, Round 1, Problem 1

February 15, 2013

In today’s Programming Praxis exercise, our goal is to solve the first problem of the 2013 Facebook hacker cup, which is to give the sum of the highest values of all possible subsequences of length k of a given list of integers. Let’s get started, shall we?

A quick import:

import Data.List

For this problem, we’re going to need to calculate a lot of binomial coefficients, i.e. the amount of ways to choose k out of n items. This involves calculating factorials. The trivial way to do this in Haskell is to use product [1..n], but that’s not very efficient when you need to calculate many different factorials. So instead we create a lazy lookup table of all factorials, so that we save a lot of duplicated effort.

facts :: [Integer]
facts = scanl (*) 1 [1..]

The brute force way to solve the problem would be to simply enumerate all possible subsequences and sum their maximums. Unfortunately there are a LOT of combinations once you get to the maximum number of 10000 possible values (just printing 10000 choose 5000 takes several terminal screens), so clearly that’s not going to work. Instead, we can solve the problem in O(n) by realizing that each number will be the highest in every combination with lower numbers, e.g. the highest number will occur (n-1) choose (k-1) times, the second highest (n-2) choose (k-2) times, etc. Since the answer needs to be given modulo 1000000007, we do this at every step in order to keep the total down.

facebook :: Int -> [Int] -> Integer
facebook size = foldr (\(i,x) a -> mod (a + x * choose (size-1) i) 1000000007) 0 .
        drop (size - 1) . zip [0..] . map fromIntegral . sort where
    choose k n = div (facts!!n) (facts!!k * facts!!(n-k))

Some test cases to see if everything is working properly:

main :: IO ()
main = do print $ facebook 3 [3,6,2,8] == 30
          print $ facebook 2 [10,20,30,40,50] == 400
          print $ facebook 4 [0,1,2,3,5,8] == 103
          print $ facebook 2 [1069,1122] == 1122
          print $ facebook 5 [10386,10257,10432,10087,10381
                             ,10035,10167,10206,10347,10088] == 2621483
          print $ facebook 1 [3,4] == 7
          print $ facebook 3 [3,4,5] == 5
          print $ facebook 5000 [1..10000]

The worst-case scenario, 5000 cards and 10000 numbers, takes just under 5 seconds. Since there’s a maximum of 25 test cases, the total time should be about two minutes at most. Not too bad.

Programming Praxis – World Cup Prognostication

June 29, 2010

In today’s Programming Praxis exercise, the goal is to write a simulator for the knockout stage of the World Cup. Let’s get started, shall we?

We’re going to be using a language pragma that I’ll get back to later. Also, some imports.

{-# LANGUAGE BangPatterns #-}

import Control.Monad
import qualified Data.List.Key as K
import qualified Data.Map as M
import System.Random

First, we define the teams and their elo ratings.

teams :: [(String, Float)]
teams = [ ("URU", 1890), ("KOR", 1746), ("USA", 1785), ("GHA", 1711)
        , ("NED", 2045), ("SVK", 1654), ("BRA", 2082), ("CHI", 1883)
        , ("ARG", 1966), ("MEX", 1873), ("GER", 1930), ("ENG", 1945)
        , ("PAR", 1771), ("JPN", 1744), ("ESP", 2061), ("POR", 1874)]

The formulas for determining which team is more likely to win and calculating the new elo rating after a match:

winChance :: Float -> Float -> Float
winChance eloA eloB = 1 / (1 + 10 ** ((eloB - eloA) / 400))

update :: Float -> Float -> Float
update winner loser = winner + 60 * (1 - winChance winner loser)

Match determines the winner of a match given a random number.

match :: Float -> (a, Float) -> (a, Float) -> (a, Float)
match r (a, ea) (b, eb) | r < winChance ea eb = (a, update ea eb)
                        | otherwise           = (b, update eb ea)

A round consists of playing a match for each pair of teams.

simround :: [(a, Float)] -> [Float] -> [(a, Float)]
simround (a:b:xs) (r:rs) = match r a b : simround xs rs
simround _        _      = []

And a tournament is nothing more than a series of successive rounds until there is only one team left.

tournament :: [(a, Float)] -> IO a
tournament [(w,_)] = return w
tournament xs      = tournament . simround xs . randoms =<< newStdGen

And when simulating, we run the desired number of tournaments, keeping a count of the winners. Note the bang pattern in the first argument of foldM, which prevents the stack from exploding. This way, the map gets updated after each tournament instead of ending up with a thunk of a million nested updates.

simulate :: Int -> IO ()
simulate n = print . K.sort (negate . snd) . M.assocs =<<
    foldM (\ !m _ -> fmap (\x -> M.adjust succ x m) $ tournament teams)
          (M.map (const 0) $ M.fromList teams) [1..n]

As usual, a test to if everything works:

main :: IO ()
main = simulate 1000000

Here is a sample simulation, which shows Brazil edging out Spain for first place, just like in the Scheme solution.

[("BRA",224546),("ESP",220703),("NED",191913),("ARG",80102),
 ("ENG",60613),("URU",53444),("GER",49686),("POR",27086),
 ("MEX",24714),("CHI",23611),("USA",14887),("PAR",9225),
 ("KOR",7558),("JPN",6081),("GHA",5009),("SVK",822)]