Created
January 25, 2026 07:08
-
-
Save chreke/d553e030218af42dfc5391e33ba0f40f 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
| let parse (recipe: string) = | |
| recipe.Split "\n" | |
| |> Array.map (fun line -> | |
| match line.Split " requires " with | |
| | [| ingredient; prerequisites |] -> | |
| ingredient, Set.ofArray(prerequisites.Split ", ") | |
| | _ -> failwith $"Badly formatted ingredient: %s{line}") | |
| |> Map.ofArray | |
| let rec craft prerequisites (ingredients: string list) (crafted: string list) = | |
| if ingredients.Length = crafted.Length then | |
| crafted | |
| else | |
| let craftedSet = Set.ofList crafted | |
| List.filter (fun x -> not (Set.contains x craftedSet)) ingredients | |
| |> List.fold | |
| (fun acc x -> | |
| let prs = | |
| Map.tryFind x prerequisites |> Option.defaultValue Set.empty | |
| if Set.isSubset prs craftedSet then x :: acc | |
| else acc) | |
| [] | |
| |> List.rev | |
| |> (@) crafted | |
| |> craft prerequisites ingredients | |
| let solve recipe = | |
| let prerequisites = parse recipe | |
| let ingredients = | |
| Set.unionMany (Map.values prerequisites) | |
| |> Set.union (Map.keys prerequisites |> Set.ofSeq) | |
| |> Set.toList | |
| |> List.sort | |
| craft prerequisites ingredients [] | |
| |> String.concat ", " |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment