Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
First attempt at implementing Tom Siergedas's solution to the question at http://stackoverflow.com/q/4075289
//http://stackoverflow.com/questions/4075289/race-car-puzzle
// shuffle an array (in-place)
let rand = new System.Random()
let shuffle a =
let swap (a: _[]) x y =
let tmp = a.[x]
a.[x] <- a.[y]
a.[y] <- tmp
Array.iteri (fun i _ -> swap a i (rand.Next(i, Array.length a))) a
let newShuffled n =
let arr = Array.init n id
shuffle arr
arr
let arrayOfArrays n arr = [|0..(n-1)|] |> Array.map (fun v -> Array.sub arr (v * n) n)
let prettyPrint aa highlight =
let inner arr = arr |> Array.map (sprintf "%4d")
|> Array.fold (+) ""
let outer = aa |> Array.map inner |> Array.reduce (sprintf "%s\n%s")
let find = string highlight
let outs = outer.Replace(" " + find + " ", "*" + find + "*")
printfn "%s" outs
open System.Text.RegularExpressions
let gridFromString (str:string) =
let split pattern input = Regex.Split(input, pattern, RegexOptions.None) |> Array.filter (fun s -> s.Length > 0)
let str = str.Replace("*", "")
let arr = str |> split "\n" |> Array.map (split " ")
arr |> Array.map (Array.map int)
module Array =
let skip n arr = if Array.length arr < n then [||] else Array.sub arr n ((Array.length arr) - n)
let keep n arr = if Array.length arr < n then arr else Array.sub arr 0 n
let safeget a n =
match (Array.length a) - n with
| -1 -> 999999
| mx when mx < n -> Array.get a mx
| _ -> Array.get a n
let TomSirgedas grid trace =
//Place the cars on a 7x7 grid, and race each row (7 races). Then, race the 3rd place finishers from each race (8th race),
// and sort the rows by the 3rd place finisher speeds.
let grid = grid |> Array.map Array.sort |> Array.sortBy (fun a -> Array.get a 2)
if trace then printfn "Races 1-8: race each row and sort by 3rd place"; prettyPrint grid 24
//Let's remove these 8 from future consideration.
//Our seven groups have sizes 4,4,5,7,7,7, and 7.
let grid = grid |> Array.map2 (fun n cars -> Array.skip n cars) [|3;3;2;0;0;0;0|]
if trace then printfn "Remove [|3;3;2;0;0;0;0|]"; prettyPrint grid 24
//Let's race the 2nd fastest remaining car of each group, and sort the rows accordingly (9th race).
let grid = grid |> Array.sortBy (fun a -> Array.get a 1)
if trace then printfn "Race 9: Sort by 2nd place"; prettyPrint grid 24
//Remove the "speedy" cars, and we look for the fastest 12 of the remaining cars. Our groups have sizes between 2 and 7.
let grid = grid |> Array.map2 (fun n cars -> Array.skip n cars) [|2;2;0;0;0;0;0|]
if trace then printfn "Remove [|2;2;0;0;0;0;0|]"; prettyPrint grid 24
//Let's race the 2nd fastest remaining car of each group, and sort the rows accordingly (10th race).
let grid = grid |> Array.sortBy (fun a -> Array.get a 1)
if trace then printfn "Race 10: Sort by 2nd place"; prettyPrint grid 24
// We identify 2 cars which are among the 12 fastest (i.e. "speedy"):
let grid = grid |> Array.map2 (fun n cars -> Array.skip n cars) [|2;0;0;0;0;0;0|]
if trace then printfn "Remove [|2;0;0;0;0;0;0|]"; prettyPrint grid 24
//We can repeat the previous step twice more (11th and 12th races). Each time we remove 2 more cars.
//However, note that a row/group might have 0 or 1 cars in it. If it has 1 car in it,
//we race that car instead of "the 2nd fastest remaining". If that car wins, we know that it
//is "speedy", as well as the next fastest 2nd place car.
let cleverRace grid sortByIndex toSkip =
let grid = grid |> Array.sortBy (fun a -> Array.safeget a sortByIndex)
if trace then printfn "Sort by col %d" sortByIndex; prettyPrint grid 24
//Edge case if there aren't enough elements in the first row to be able to delete toSkip
let len = Array.length grid.[0]
let grid =
if len >= toSkip then
if trace then printfn "Remove [|%A;0;0;0;0;0;0|]" toSkip;
grid |> Array.map2 (fun n cars -> Array.skip n cars) [|toSkip;0;0;0;0;0;0|]
else
if trace then printfn "Remove [|%A;%A;0;0;0;0;0|]" len (toSkip-len);
grid |> Array.map2 (fun n cars -> Array.skip n cars) [|len;toSkip-len;0;0;0;0;0|]
if trace then prettyPrint grid 24
grid
if trace then printf "Race 11: "
let grid = cleverRace grid 1 2
if trace then printf "Race 12: "
let grid= cleverRace grid 1 2
//Now let's simply race the fastest remaining car in each group (13th race), and sort the rows accordingly. The winner is "speedy". 5 left.
if trace then printf "Race 13: "
let grid = cleverRace grid 0 1
//After that last race, there are only 2 cars which could be the fastest remaining car.
//Let's race these 5 cars (14th race),
if trace then printf "Race 14: race 5 top-left cars: "
let race14 = grid |> Array.map2 (fun n cars -> Array.keep n cars) [|2;2;1;0;0;0;0;|] |> Array.concat |> Array.sort
if trace then printf "%A" race14
//and the top two finishers are certainly "speedy".
let toSkip = Array.sub race14 0 2
if trace then printfn " and remove winners: %A" toSkip
let grid = grid |> Array.map (fun a -> (set a - set toSkip) |> Set.toArray)
if trace then prettyPrint grid 24
//Let's repeat the last two steps/races to identify the last 3 speedy cars (15th and 16th race).
if trace then printf "Race 15: " //repeat of race 13
let grid = cleverRace grid 0 1
//Repeat of race 14
if trace then printf "Race 16: race 5 top-left cars: "
let race16 = grid |> Array.map2 (fun n cars -> Array.keep n cars) [|2;2;1;0;0;0;0;|] |> Array.concat |> Array.sort
if trace then printf "%A" race16
let toSkip = Array.sub race16 0 2
if trace then printfn " and remove winners: %A" toSkip
let grid = grid |> Array.map (fun a -> (set a - set toSkip) |> Set.toArray)
if trace then prettyPrint grid 24
if trace then printfn "Race 17:"
let grid = grid |> Array.sortBy (fun a -> Array.safeget a 0)
if trace then prettyPrint grid 24
grid.[0].[0]
let test iterations =
[1..iterations]
|> List.map (fun i -> newShuffled 49 |> arrayOfArrays 7)
|> List.map (fun grid -> TomSirgedas grid false)
|> List.forall (fun i -> i = 24)
let debug stop =
let rec iterate n =
if n > stop then
"Hit stop iterations"
else
printfn "========Test iteration %d=====" n
let grid = newShuffled 49 |> arrayOfArrays 7
match (TomSirgedas grid true) with
| 24 -> iterate (n + 1)
| _ -> "Hit a wrong result"
iterate 1
let retest() =
let str = @" 1 2 3 6 9 30 38
0 7 10 13 23 44 46
8 14 15 17 18 19 20
11 12 21 31 34 35 39
16 22 *24* 26 29 40 42
5 27 28 41 43 45 47
4 25 32 33 36 37 48"
let grid = gridFromString str
TomSirgedas grid true
(* Example result:
Races 1-8: race each row and sort by 3rd place
1 2 3 6 9 30 38
0 7 10 13 23 44 46
8 14 15 17 18 19 20
11 12 21 31 34 35 39
16 22 *24* 26 29 40 42
5 27 28 41 43 45 47
4 25 32 33 36 37 48
Remove [|3;3;2;0;0;0;0|]
6 9 30 38
13 23 44 46
15 17 18 19 20
11 12 21 31 34 35 39
16 22 *24* 26 29 40 42
5 27 28 41 43 45 47
4 25 32 33 36 37 48
Race 9: Sort by 2nd place
6 9 30 38
11 12 21 31 34 35 39
15 17 18 19 20
16 22 *24* 26 29 40 42
13 23 44 46
4 25 32 33 36 37 48
5 27 28 41 43 45 47
Remove [|2;2;0;0;0;0;0|]
30 38
21 31 34 35 39
15 17 18 19 20
16 22 *24* 26 29 40 42
13 23 44 46
4 25 32 33 36 37 48
5 27 28 41 43 45 47
Race 10: Sort by 2nd place
15 17 18 19 20
16 22 *24* 26 29 40 42
13 23 44 46
4 25 32 33 36 37 48
5 27 28 41 43 45 47
21 31 34 35 39
30 38
Remove [|2;0;0;0;0;0;0|]
18 19 20
16 22 *24* 26 29 40 42
13 23 44 46
4 25 32 33 36 37 48
5 27 28 41 43 45 47
21 31 34 35 39
30 38
Race 11: Sort by col 1
18 19 20
16 22 *24* 26 29 40 42
13 23 44 46
4 25 32 33 36 37 48
5 27 28 41 43 45 47
21 31 34 35 39
30 38
Remove [|2;0;0;0;0;0;0|]
20
16 22 *24* 26 29 40 42
13 23 44 46
4 25 32 33 36 37 48
5 27 28 41 43 45 47
21 31 34 35 39
30 38
Race 12: Sort by col 1
20
16 22 *24* 26 29 40 42
13 23 44 46
4 25 32 33 36 37 48
5 27 28 41 43 45 47
21 31 34 35 39
30 38
Remove [|1;1;0;0;0;0;0|]
22 *24* 26 29 40 42
13 23 44 46
4 25 32 33 36 37 48
5 27 28 41 43 45 47
21 31 34 35 39
30 38
Race 13: Sort by col 0
4 25 32 33 36 37 48
5 27 28 41 43 45 47
13 23 44 46
21 31 34 35 39
22 *24* 26 29 40 42
30 38
Remove [|1;0;0;0;0;0;0|]
25 32 33 36 37 48
5 27 28 41 43 45 47
13 23 44 46
21 31 34 35 39
22 *24* 26 29 40 42
30 38
Race 14: race 5 top-left cars: [|5; 13; 25; 27; 32|] and remove winners: [|5; 13|]
25 32 33 36 37 48
27 28 41 43 45 47
23 44 46
21 31 34 35 39
22 *24* 26 29 40 42
30 38
Race 15: Sort by col 0
21 31 34 35 39
22 *24* 26 29 40 42
23 44 46
25 32 33 36 37 48
27 28 41 43 45 47
30 38
Remove [|1;0;0;0;0;0;0|]
31 34 35 39
22 *24* 26 29 40 42
23 44 46
25 32 33 36 37 48
27 28 41 43 45 47
30 38
Race 16: race 5 top-left cars: [|22; 23; 24; 31; 34|] and remove winners: [|22; 23|]
31 34 35 39
*24* 26 29 40 42
44 46
25 32 33 36 37 48
27 28 41 43 45 47
30 38
Race 17:
*24* 26 29 40 42
25 32 33 36 37 48
27 28 41 43 45 47
30 38
31 34 35 39
44 46
*)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.