Last active
December 8, 2018 04:11
-
-
Save tariknz/fcb2853228e61ea8ce490e8b1a1d631a to your computer and use it in GitHub Desktop.
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 | |
| open System.Text.RegularExpressions | |
| open System | |
| let input = File.ReadLines("2018-day-7.txt") | |
| let regexPattern = "^Step (\w) must be finished before step (\w) can begin\.$" | |
| let parser line = | |
| let groups = Regex.Match(line, regexPattern).Groups | |
| let captures = List.tail [ for g in groups -> g.Value ] | |
| (captures.[0], captures.[1]) | |
| let instructions = | |
| let groups = | |
| input | |
| |> Seq.map parser | |
| |> List.ofSeq | |
| |> List.groupBy (fun i -> snd i) | |
| |> List.map (fun (i, g) -> i, g |> List.map fst |> List.sort) | |
| // add children with no dependency | |
| let parents = groups |> List.map fst | |
| let children = groups |> List.map snd |> List.concat | |
| let orphans = children |> List.filter (fun g -> not(List.contains g parents)) |> List.distinct |> List.map (fun o -> (o, List.empty)) | |
| groups |> List.append orphans |> List.ofSeq | |
| let hasNoChildren list = | |
| list | |
| |> Seq.filter (fun i -> Seq.length (snd i) = 0) | |
| |> Seq.map (fun i -> fst i) | |
| |> Seq.sort | |
| |> List.ofSeq | |
| // part 1 | |
| let rec tasker instructions sequence = | |
| let task = hasNoChildren instructions |> List.head | |
| let newSequence = List.append sequence [task] | |
| let filteredInstructions = // remove new task as a dependency from other tasks | |
| instructions | |
| |> List.filter (fun (i, _) -> not(List.contains i newSequence)) | |
| |> List.map (fun (i, g) -> (i, g |> List.filter (fun child -> not (List.contains child newSequence)))) | |
| if (Seq.length filteredInstructions) = 0 then newSequence | |
| else tasker filteredInstructions newSequence | |
| tasker instructions List.empty | |
| |> String.concat "" | |
| |> printfn "%A" | |
| // part 2 | |
| let mapToSeconds task = | |
| task, task | |
| |> Array.ofSeq | |
| |> Seq.head | |
| |> fun c -> int c - 64 + 60 // 64 ascii pos, then add 60 seconds for the task | |
| // reduces the time left by the time worked for all tasks in factory | |
| let worked timeWorked factory = | |
| factory | |
| |> List.map (fun (task, timeLeft) -> task, timeLeft - timeWorked) | |
| let rec tasker2 instructions sequence factory timeEclipsed = | |
| let mutable updatedFactory = factory |> worked 1 // run down the clock for all tasks | |
| // get tasks that have completed | |
| let finishedTasks = updatedFactory |> List.filter (fun (_, timeLeft) -> timeLeft = 0) |> List.map (fun (task, _) -> task) | |
| let newSequence = List.append sequence finishedTasks | |
| updatedFactory <- updatedFactory |> List.filter (fun (task, _) -> not(List.contains task finishedTasks)) // filter out finished tasks | |
| let freeWorkers = 5 - updatedFactory.Length // 5 workers available | |
| let filteredInstructions = // remove new task as a dependency from other tasks | |
| instructions | |
| |> List.filter (fun (task, _) -> not(List.contains task newSequence)) | |
| |> List.map (fun (task, children) -> (task, children |> List.filter (fun child -> not (List.contains child newSequence)))) | |
| // get tasks that have no dependencies, and aren't already in factory | |
| let newTasks = | |
| hasNoChildren filteredInstructions | |
| |> List.filter (fun task -> not(updatedFactory |> List.map fst |> List.contains task)) | |
| |> List.map mapToSeconds | |
| |> List.truncate freeWorkers // only takes a maximum of the free workers available | |
| updatedFactory <- updatedFactory |> List.append newTasks | |
| if (Seq.length filteredInstructions) = 0 then timeEclipsed, newSequence | |
| else tasker2 filteredInstructions newSequence updatedFactory (timeEclipsed + 1) | |
| tasker2 instructions List.empty List.empty 0 | |
| |> fun (time, order) -> time, order |> String.concat "" | |
| |> printfn "%A" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment