(ns adventofcode2019.day14
- [:require [adventofcode2019.lib :refer :all]
- [adventofcode2019.intcode :as i]
- [clojure.string :as str]
- [clojure.set :as set]
- [clojure.core.match :refer [match]]
- [clojure.math.combinatorics :as combo]])
+ [:require [adventofcode2019.lib :refer :all]
+ [clojure.string :as str]
+ [clojure.core.match :refer [match]]])
(defn parse-reaction [reaction-text]
(let [parse-chemical (fn [text]
{chem (parse-int ct)}))
[inputs output] (str/split reaction-text #"=>")
[[out-chem out-ct]] (seq (parse-chemical output))]
- {out-chem {(reduce merge {} (map parse-chemical (str/split inputs #","))) out-ct}}))
-
-(defn normalize-reaction [reaction]
- (let [[output] (keys reaction)
- arrows (reaction output)
- inputs (keys arrows)
- normalize-arrow (fn [[akey aval]]
- {(reduce-kv (fn [m k v]
- (assoc m k (rationalize (/ v aval))))
- {} akey) 1})]
- {output (reduce merge {} (map normalize-arrow arrows))}))
+ {out-chem [(reduce merge {} (map parse-chemical (str/split inputs #","))) out-ct]}))
(defn make-graph [input]
(reduce (partial merge-with merge)
- (map (comp normalize-reaction parse-reaction) input)))
+ (map parse-reaction input)))
+
+(defn reduce-reaction [graph producing consuming]
+ (let [[inputs moles] (graph producing)
+ in-chems (keys inputs)
+ replace-term (fn [chem]
+ (if (or (= chem consuming)
+ (neg? (second (graph chem))))
+ {chem (inputs chem)}
+ (let [ch-req (inputs chem)
+ [ch-in ch-mo] (graph chem)
+ conversion (int (Math/ceil (/ ch-req ch-mo)))]
+ (assoc (mmap (partial * conversion) ch-in)
+ chem (- ch-req (* ch-mo conversion))))))
+ check-reduced (fn [[ch ct]] (and (not= ch consuming) (pos? ct)))
+ reduced-inputs (reduce (partial merge-with +)
+ (map replace-term in-chems))
+ new-graph (assoc graph producing [reduced-inputs moles])]
+ (if (some check-reduced reduced-inputs)
+ (recur new-graph producing consuming)
+ new-graph)))
-(defn find-lowest-exchange-rate [graph start end]
- (let [reactions (graph start)
- input-lists (keys reactions)
- input-chems (mapv keys input-lists)
- trade (fn [recv exch]
- (let [rx (if (ratio? exch) (numerator exch) exch)
- xc (if (ratio? exch) (denominator exch) 1)
- units (int (Math/ceil (/ recv xc)))]
- (* units rx)))
- find-terminal #(match [%]
- [({end v} :only [end])] v
- :else nil)
- calculate-er (fn [[chem ct]]
- (trade ct (find-lowest-exchange-rate graph chem end)))
- reaction-er #(reduce + (map calculate-er %))]
- (if (some #{[end]} input-chems)
- (->> input-lists
- (map find-terminal)
- (remove nil?)
- (reduce min))
- (->> input-lists
- (map reaction-er)
- (reduce min)))))
+(defn find-lowest-exchange-rate [graph producing consuming]
+ (get-in (reduce-reaction graph producing consuming)
+ [producing 0 consuming]))
(defn day14 []
(let [graphed (make-graph (get-list-from-file (input-file)))]
(:require [clojure.test :refer :all]
[adventofcode2019.day14 :refer :all]))
-(deftest check-make-graph
- (is (= (make-graph ["3 ORE => 2 ABC"
+(deftest test-make-graph
+ (is (= (make-graph ["3 ORE => 2 ABC"
"3 ABC => 1 FUEL"])
- {"ABC" {{"ORE" 3/2} 1}
- "FUEL" {{"ABC" 3} 1}})))
+ {"ABC" [{"ORE" 3} 2]
+ "FUEL" [{"ABC" 3} 1]})))
-(deftest simple-exchange
- (is (= 3 (find-lowest-exchange-rate {"FUEL" {{"ORE" 1, "ABC" 2, "DEF" 3} 1
- {"ORE" 3} 1
- {"GHI" 5/2} 1}}
- "FUEL" "ORE"))))
+(deftest test-reduce
+ (is (= (reduce-reaction (make-graph ["9 ORE => 2 A"
+ "8 ORE => 3 B"
+ "7 ORE => 5 C"
+ "3 A, 4 B => 1 AB"
+ "5 B, 7 C => 1 BC"
+ "4 C, 1 A => 1 CA"
+ "2 AB, 3 BC, 4 CA => 1 FUEL"])
+ "FUEL", "ORE")
+ {"A" [{"ORE" 9} 2]
+ "B" [{"ORE" 8} 3]
+ "C" [{"ORE" 7} 5]
+ "AB" [{"A" 3, "B" 4} 1]
+ "BC" [{"B" 5, "C" 7} 1]
+ "CA" [{"C" 4, "A" 1} 1]
+ "FUEL" [{"ORE" 165, "A" 0
+ "B" -1, "AB" 0
+ "C" -3, "BC" 0
+ "CA" 0} 1]})))
-(deftest trading-up
- (is (= 6 (find-lowest-exchange-rate (make-graph ["3 ORE => 2 ABC"
- "3 ABC => 1 FUEL"])
- "FUEL" "ORE"))))
-
-(deftest complicated-exchange
- (is (= 2 (find-lowest-exchange-rate (make-graph ["3 ORE => 2 ABC"
- "3 ABC => 1 FUEL"
- "2 ORE => 1 CDE"
- "1 CDE => 1 FUEL"])
- "FUEL" "ORE"))))
-
-(deftest very-tricky-exchange
- (is (= 3 (find-lowest-exchange-rate (make-graph ["3 ORE => 2 ABC"
- "3 ABC => 1 FUEL"
- "4 ORE => 1 CDE"
- "1 CDE => 1 FUEL"
- "3 ORE => 2 FGH"
- "1 FGH => 1 IJK"
- "1 IJK => 1 FUEL"])
- "FUEL" "ORE"))))
+(deftest examples
+ (is (= 31 (find-lowest-exchange-rate (make-graph ["10 ORE => 10 A"
+ "1 ORE => 1 B"
+ "7 A, 1 B => 1 C"
+ "7 A, 1 C => 1 D"
+ "7 A, 1 D => 1 E"
+ "7 A, 1 E => 1 FUEL"])
+ "FUEL", "ORE")))
+ (is (= 165 (find-lowest-exchange-rate (make-graph ["9 ORE => 2 A"
+ "8 ORE => 3 B"
+ "7 ORE => 5 C"
+ "3 A, 4 B => 1 AB"
+ "5 B, 7 C => 1 BC"
+ "4 C, 1 A => 1 CA"
+ "2 AB, 3 BC, 4 CA => 1 FUEL"])
+ "FUEL", "ORE")))
+ (is (= 13312 (find-lowest-exchange-rate (make-graph ["157 ORE => 5 NZVS"
+ "165 ORE => 6 DCFZ"
+ "44 XJWVT, 5 KHKGT, 1 QDVJ, 29 NZVS, 9 GPVTF, 48 HKGWZ => 1 FUEL"
+ "12 HKGWZ, 1 GPVTF, 8 PSHF => 9 QDVJ"
+ "179 ORE => 7 PSHF"
+ "177 ORE => 5 HKGWZ"
+ "7 DCFZ, 7 PSHF => 2 XJWVT"
+ "165 ORE => 2 GPVTF"
+ "3 DCFZ, 7 NZVS, 5 HKGWZ, 10 PSHF => 8 KHKGT"])
+ "FUEL", "ORE")))
+ (is (= 180697 (find-lowest-exchange-rate (make-graph ["2 VPVL, 7 FWMGM, 2 CXFTF, 11 MNCFX => 1 STKFG"
+ "17 NVRVD, 3 JNWZP => 8 VPVL"
+ "53 STKFG, 6 MNCFX, 46 VJHF, 81 HVMC, 68 CXFTF, 25 GNMV => 1 FUEL"
+ "22 VJHF, 37 MNCFX => 5 FWMGM"
+ "139 ORE => 4 NVRVD"
+ "144 ORE => 7 JNWZP"
+ "5 MNCFX, 7 RFSQX, 2 FWMGM, 2 VPVL, 19 CXFTF => 3 HVMC"
+ "5 VJHF, 7 MNCFX, 9 VPVL, 37 CXFTF => 6 GNMV"
+ "145 ORE => 6 MNCFX"
+ "1 NVRVD => 8 CXFTF"
+ "1 VJHF, 6 MNCFX => 4 RFSQX"
+ "176 ORE => 6 VJHF"])
+ "FUEL", "ORE")))
+ (is (= 2210736 (find-lowest-exchange-rate (make-graph ["171 ORE => 8 CNZTR"
+ "7 ZLQW, 3 BMBT, 9 XCVML, 26 XMNCP, 1 WPTQ, 2 MZWV, 1 RJRHP => 4 PLWSL"
+ "114 ORE => 4 BHXH"
+ "14 VRPVC => 6 BMBT"
+ "6 BHXH, 18 KTJDG, 12 WPTQ, 7 PLWSL, 31 FHTLT, 37 ZDVW => 1 FUEL"
+ "6 WPTQ, 2 BMBT, 8 ZLQW, 18 KTJDG, 1 XMNCP, 6 MZWV, 1 RJRHP => 6 FHTLT"
+ "15 XDBXC, 2 LTCX, 1 VRPVC => 6 ZLQW"
+ "13 WPTQ, 10 LTCX, 3 RJRHP, 14 XMNCP, 2 MZWV, 1 ZLQW => 1 ZDVW"
+ "5 BMBT => 4 WPTQ"
+ "189 ORE => 9 KTJDG"
+ "1 MZWV, 17 XDBXC, 3 XCVML => 2 XMNCP"
+ "12 VRPVC, 27 CNZTR => 2 XDBXC"
+ "15 KTJDG, 12 BHXH => 5 XCVML"
+ "3 BHXH, 2 VRPVC => 7 MZWV"
+ "121 ORE => 7 VRPVC"
+ "7 XCVML => 6 RJRHP"
+ "5 BHXH, 4 VRPVC => 5 LTCX"])
+ "FUEL", "ORE"))))
projects / adventofcode2019.git / commitdiff