Yan Cui
I help clients go faster for less using serverless technologies.
Table of Content
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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.