2·
4 days agoFSharp
I’m a month late, but eh. Compared to everyone else, it looks like my approach of preserving duplicates was unnecessary. I chose to use SortedSets (redundant since I sort the inputs) and cascade to the next best fit. The sorted sets also let me grab the Max/Min values and I thought that it was more in line with the intention than having a list that happens to be sorted.
I also sorted part 1 based on what I thought was the best fit, which was the same solution for part 3.
For part 2 I duplicated part 1’s logic but reversed the order to asc instead of desc, but I don’t know that that made a difference and excluded it here. The only difference is the “add if count < 20”.
type Crate = int
// sorted set because only one item can be in at a time. The SortedSet is unnecessary here since the inputs are already sorted
type CrateSet = SortedSet<Crate>
let inline newCrateSet crate =
let cs = CrateSet()
cs.Add(crate) |> ignore
cs
type Extensions() =
[<Extension>]
static member inline SmallestCrate (crates:CrateSet) : Crate option = match crates.Min with | 0 -> None | x -> Some x
[<Extension>]
static member inline LargestCrate (crates:CrateSet) : Crate option = match crates.Max with | 0 -> None | x -> Some x
/// take a sorted input (not verified) and prioritize insertion into the first found list.
/// This results in cascading to the "next best fit", but this approach relies on sorted inputs.
let packEfficiently allCrates =
allCrates
|> Seq.fold (fun sortedCrates next ->
// find the first crate set that can hold the next item and put it in there
match sortedCrates with
| [] -> [newCrateSet next]
| items ->
match List.tryFind (fun (i:CrateSet) ->
match i.SmallestCrate() with
| Some c when c > next -> true
| _ -> false) items with
| None ->
let cs = newCrateSet next
items@[cs] // appending to the end is less efficient for linked lists, but ensures that the first one gets the best goodies
| Some crates ->
if not (crates.Add(next)) then failwith "failed to add" // really wrong if this happens
items
) []
let part1 () =
parseInput "Inputs/Quest03/Q03_P01.txt"
|> Enumerable.OrderDescending
|> packEfficiently
|> _.Max(_.Sum())
let part2() =
parseInput "Inputs/Quest03/Q03_P02.txt"
|> Enumerable.Order
|> part2Impl
|> List.filter (fun x -> x.Count = 20)
|> _.Min(_.Sum())
let part3() =
parseInput "Inputs/Quest03/Q03_P03.txt"
|> Enumerable.OrderDescending
|> packEfficiently
|> _.Count()
that looks like a lot of fun to play with friends