Skip to content

Instantly share code, notes, and snippets.

@hickford
Created May 10, 2018 13:57
Show Gist options
  • Save hickford/58919847464567f0ccc5dfa3a3f2033b to your computer and use it in GitHub Desktop.
Save hickford/58919847464567f0ccc5dfa3a3f2033b to your computer and use it in GitHub Desktop.
let solve words =
let words = words |> List.sort
let r = words.[0] |> String.length
let iths i = words |> List.map (fun s -> s.[i]) |> List.sort |> List.distinct
let letters = [0..r-1] |> List.map iths
let bases = letters |> List.map List.length
let sequence x =
let folder d (x, digits) =
(x/d, x%d :: digits)
List.foldBack folder bases (x, []) |> snd
let ordinal x =
let mapping i j = letters.[i].[j]
x |> sequence |> List.mapi mapping |> List.toArray |> System.String
let n = bases |> List.reduce (*)
let agrees i =
i < words.Length && (ordinal i) = words.[i]
let rec binarySearch f low high =
if high = low + 1 then
high
else
let mid = (high + low) / 2
if f mid then
binarySearch f mid high
else
binarySearch f low mid
if n = List.length words then
"-"
else if agrees 0 then
binarySearch agrees 0 n |> ordinal
else
0 |> ordinal
// The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with two integers N and L: the number of Vincent's words, and the length of each word. Then, N more lines follow. The i-th of these lines contains a string of L uppercase English letters representing the i-th of Vincent's words.
let T = System.Console.ReadLine() |> int
for case in [1..T] do
let N = System.Console.ReadLine().Split() |> Array.map int |> Array.head
let words = [1..N] |> List.map (fun _ -> System.Console.ReadLine())
let solution = solve words
printfn "Case #%d: %s" case solution
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment