F# solutions to Google CodeJam 2010 Qualification Round Problems

Yan Cui

I help clients go faster for less using serverless technologies.

I found out about Google CodeJam the other day, and looking at their info page, there’s a number of interesting problems you can solve as practice for the real thing coming up, and here are my F# solutions to the qualification round questions from the 2010 event, enjoy Smile

 

Problem A. Store Credit

The outline of the problem can be found here.

open System.IO
type Case = { Credits : int; Items : int[] }
// read the test cases from the input file
let lines = File.ReadAllLines(@"C:\Temp\Google CodeJam\2010\A-small-practice.in")
let cases =
[| 1..3..lines.Length-1 |]
|> Array.map (fun idx ->
{
Credits = (int)lines.[idx];
Items = lines.[idx+2].Split([| ' ' |]) |> Array.map int
})
// work out solution for each test case
let solutions =
cases |> Array.mapi (fun idx case ->
let solution =
seq { 0..case.Items.Length-2 }
|> Seq.collect (fun l -> seq { l+1..case.Items.Length-1 } |> Seq.map (fun r -> l, r))
|> Seq.filter (fun (l, r) -> case.Items.[l] + case.Items.[r] = case.Credits)
|> Seq.map (fun (l, r) -> l+1, r+1)
|> Seq.head
sprintf "Case #%d: %d %d" (idx+1) (fst solution) (snd solution))
File.WriteAllLines(@"C:\Temp\Google CodeJam\2010\A-small-practice.txt", solutions)

 

Problem B. Reverse Words

The outline of the problem can be found here.

open System.IO
let lines = File.ReadAllLines(@"C:\Temp\Google CodeJam\2010\B-small-practice.in")
let revLines =
lines
|> Seq.skip 1
|> Seq.mapi (fun idx line ->
line.Split([| ' ' |])
|> Array.rev
|> Array.reduce (fun state elem -> state + " " + elem)
|> sprintf "Case #%d: %s" (idx + 1))
File.WriteAllLines(@"C:\Temp\Google CodeJam\2010\B-small-practice.txt", revLines)

 

Problem C. T9 Spelling

The outline of the problem can be found here.

open System.Collections.Generic
open System.IO
let keyMap = [ ('2', [|'a'; 'b'; 'c'|]);
('3', [|'d'; 'e'; 'f'|]);
('4', [|'g'; 'h'; 'i'|]);
('5', [|'j'; 'k'; 'l'|]);
('6', [|'m'; 'n'; 'o'|]);
('7', [|'p'; 'q'; 'r'; 's'|]);
('8', [|'t'; 'u'; 'v'|]);
('9', [|'w'; 'x'; 'y'; 'z'|]);
('0', [|' '|]) ]
// function to get the sequence of key inputs, e.g. 222 for 'c'
let getKeyInput char =
keyMap |> List.pick (fun (num, charArr) ->
try
let idx = charArr |> Array.findIndex ((=) char)
[|0..idx|] |> Array.map (fun _ -> num) |> Some
with :? KeyNotFoundException -> None)
let lines = File.ReadAllLines(@"C:\Temp\Google CodeJam\2010\C-small-practice.in")
let keyInputs =
lines
|> Seq.skip 1
|> Seq.mapi (fun idx line ->
line
|> Seq.fold (fun acc elem ->
let newInputs = getKeyInput elem
match acc with
| [] -> [ newInputs ]
| hd::tl when hd.[0] <> newInputs.[0] -> newInputs :: acc
| _ -> newInputs :: [| ' ' |] :: acc) []
|> List.rev
|> List.fold (fun acc elem -> acc + new string(elem)) (sprintf "Case #%d: " (idx+1)))
|> Seq.toArray
File.WriteAllLines(@"C:\Temp\Google CodeJam\2010\C-small-practice.txt", keyInputs)

Whenever you’re ready, here are 3 ways I can help you:

  1. Production-Ready Serverless: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for quickly levelling up your serverless skills.
  2. I help clients launch product ideas, improve their development processes and upskill their teams. If you’d like to work together, then let’s get in touch.
  3. Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.

Leave a Comment

Your email address will not be published. Required fields are marked *