F# solutions to Google CodeJam 2012 Qualification Round Questions

Yan Cui

I help clients go faster for less using serverless technologies.

Table of Content

Problem A. Speaking in Tongues

Problem B. Dancing with the Googlers

Problem C. Recycled Numbers

Problem A. Speaking in Tongues

The problem is here.

	open System
	open System.IO

	let lines = File.ReadAllLines(@"C:\Temp\Google CodeJam\2012\A-small-attempt0.in")

	let mapping = [ ('y', 'a'); ('n', 'b'); ('f', 'c'); ('i', 'd'); ('c', 'e'); ('w', 'f'); ('l', 'g'); ('b', 'h');
	('k', 'i'); ('u', 'j'); ('o', 'k'); ('m', 'l'); ('x', 'm'); ('s', 'n'); ('e', 'o'); ('v', 'p');
	('z', 'q'); ('p', 'r'); ('d', 's'); ('r', 't'); ('j', 'u'); ('g', 'v'); ('t', 'w'); ('h', 'x');
	('a', 'y'); ('q', 'z'); (' ', ' ') ]
	\|> Map.ofList

	let output = lines \|> Seq.skip 1
	\|> Seq.map (fun line -> line.ToCharArray())
	\|> Seq.map (fun chars -> chars \|> Array.map (fun char -> mapping.[char]))
	\|> Seq.map (fun chars -> new String(chars))
	\|> Seq.mapi (fun idx str -> sprintf "Case #%d: %s" (idx+1) str)
	\|> Seq.toArray

	File.WriteAllLines(@"C:\Temp\Google CodeJam\2012\A-small-attempt0.out", output)

view raw GoogleCodeJam2012QA.fsx hosted with

by GitHub

Problem B. Dancing with the Googlers

The problem is here.

	open System.IO

	let lines = File.ReadAllLines(@"C:\Temp\Google CodeJam\2012\B-small-attempt0.in")

	type TestCase = { NumberOfGooglers : int; NumberOfSurprising : int; P : int; Scores : int list }

	type Triplet = \| Surprising of int * int list
	\| NotSurprising of int * int list

	let readTestCase (line : string) =
	let segments = line.Split([\| ' ' \|]) \|> Array.map int
	{
	NumberOfGooglers = segments.[0];
	NumberOfSurprising = segments.[1];
	P = segments.[2];
	Scores = segments \|> Seq.skip 3 \|> Seq.toList
	}

	let testCases = lines \|> Seq.skip 1 \|> Seq.map readTestCase \|> Seq.toArray

	let isValid scores = List.max scores - List.min scores <= 2
	let isSurprisingScores scores = List.max scores - List.min scores = 2
	let toTriplet scores = match isSurprisingScores scores with
	\| true -> Surprising((scores \|> List.sum), scores)
	\| false -> NotSurprising((scores \|> List.sum), scores)
	let isSurprisingTriplet triplet = match triplet with
	\| Surprising(_) -> true
	\| _ -> false
	let satisfiesP P triplet = match triplet with
	\| Surprising(_, lst)
	\| NotSurprising(_, lst) -> List.max lst >= P

	let scores =
	[ for i = 0 to 10 do
	for j = 0 to 10 do
	for k = 0 to 10 do yield [i; j; k] ]
	\|> List.filter isValid
	\|> List.map toTriplet
	let scoresMap = scores \|> Seq.groupBy (fun triplet -> match triplet with
	\| Surprising(total, _)
	\| NotSurprising(total, _) -> total)
	\|> Seq.map (fun (total, triplets) -> total, triplets \|> Seq.toList)
	\|> Map.ofSeq

	let rec getCombos (tripletsLst : Triplet list list) (acc : Triplet list) =
	match tripletsLst with
	\| hd::[] -> hd \|> Seq.map (fun triplet -> triplet :: acc)
	\| hd::tl -> hd \|> Seq.collect (fun triplet -> getCombos tl (triplet :: acc))

	let solveTestCase (testCase : TestCase) =
	// get the list of possible triplets for each googler
	let tripletsLst = testCase.Scores \|> List.map (fun score -> scoresMap.[score])

	getCombos tripletsLst []
	\|> Seq.filter (fun triplets -> triplets \|> Seq.filter isSurprisingTriplet \|> Seq.length \|> ((=) testCase.NumberOfSurprising))
	\|> Seq.map (fun triplets -> triplets \|> Seq.filter (satisfiesP testCase.P) \|> Seq.length)
	\|> Seq.max

	let output = testCases \|> Array.map solveTestCase
	\|> Array.mapi (fun idx ans -> sprintf "Case #%d: %d" (idx+1) ans)

	File.WriteAllLines(@"C:\Temp\Google CodeJam\2012\B-small-attempt0.out", output)

view raw GoogleCodeJam2012QB.fsx hosted with

by GitHub

Problem C. Recycled Numbers

The problem is here.

	open System
	open System.IO
	open System.Linq
	open System.Threading

	// Type abbreviation for parallel sequences.
	type pseq<'T> = ParallelQuery<'T>

	[<RequireQualifiedAccess>]
	module PSeq =
	// Converst a seq<'T> to a pseq<'T>.
	let inline toP (s : seq<'T>) =
	match s with
	\| null -> nullArg "s"
	\| :? pseq<'T> as p -> p
	\| _ -> s.AsParallel()

	let collect f s = ParallelEnumerable.SelectMany(toP(s), Func<_,_>(fun x -> (f x) :> seq<'U>))

	let distinct s = ParallelEnumerable.Distinct(toP(s), HashIdentity.Structural<_>)

	let length s = ParallelEnumerable.Count(toP(s))

	let lines = File.ReadAllLines(@"C:\Temp\Google CodeJam\2012\C-large.in")

	type TestCase = { A : int; B : int }

	let testCases = lines \|> Seq.skip 1
	\|> Seq.map (fun line -> let segments = line.Split([\| ' ' \|]) \|> Array.map int
	{ A = segments.[0]; B = segments.[1] })
	\|> Seq.toArray

	let rotate A B n =
	let charArr = n.ToString().ToCharArray()
	let len = charArr.Length
	seq { 0..(len-1) }
	\|> Seq.map (fun r -> Array.permute (fun i -> (i + r) % len) charArr)
	\|> Seq.map (fun arr -> String.Join("", arr))
	\|> Seq.map int
	\|> Seq.filter (fun m -> A <= n && n < m && m <= B)
	\|> Seq.map (fun m -> n, m)

	let solveTestCase testCase =
	[ testCase.A .. testCase.B ]
	\|> PSeq.collect (rotate testCase.A testCase.B)
	\|> PSeq.distinct
	\|> PSeq.length

	let output = testCases \|> Array.map solveTestCase
	\|> Array.mapi (fun idx ans -> sprintf "Case #%d: %d" (idx+1) ans)

	File.WriteAllLines(@"C:\Temp\Google CodeJam\2012\C-large.out", output)

view raw GoogleCodeJam2012QC.fsx hosted with

by GitHub

Enjoy!

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.

Problem A. Speaking in Tongues

Problem B. Dancing with the Googlers

Problem C. Recycled Numbers

Leave a Comment