
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
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:
- 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.
- 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.
- Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.