Clojurians Log v2

Part II was my last holdout and for the life of me I couldn’t get the right answer. After rebuilding my code from scratch, and testing carefully all the way (and, admittedly, finding a few places that could be improved and learning a thing or two) I realized I was still just adding the top three blueprints, when the instructions clearly said to multiply. Oh bothers. I don’t want to think about how much time I wasted and hairs I lost trying to figure out why I couldn’t get the right answer. At least now I can finally say that AoC 2022 is wrapped up.

^^^ © basically everyone on reddit kappa

Ha - yeah, seems like it. My first attempt was raw full search. Then I rewrote so that if you could build any bot it would build it, but that go stuck building ores and clays. Then I went back to full search trying to filter out previously seen states, thinking that would help prune enough. It didn't. I added the max geode check as a test to see if always building geodes worked but otherwise not constraining. It did, but it was slow. Then I added the max obsidian check for states that had the max geodes. Looking at the code this morning I don't think that check is exactly doing what I wanted. But it works. Weird. It didn't really speed things up much, but it gets to the answer. It seems lots of people are doing some variant of these checks, but I'm not seeing anything that stands out as a "good" way

https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2022/19.clj this one was a real beast, also unhappy with what feels like a huge pile of hacks and poorly justified "heuristics" 😅 • branch and bound with a truly awful bound of "assume you can build another geo robot in every remaining minute" • if you can afford a geo robot, always build it immediately • if we opted not to build a robot we could have built last turn, don't build it this turn either (it would have been better to build it before) • don't build a robot if we have more than 16 of its resource already (horrible hack, but cuts the search space down a lot) finishes in 4.6s for part 1 and 1.6s for part 2

(sort of) fast p1 solution gave wrong result for sample p2 => (42 62) instead of => (56 62) p1 "Elapsed time: 19290.007506 msecs" with heuristic p2 "Elapsed time: 23966.599927 msecs" with commented out heuristic

> The second blueprint has ID 2 and can open 12 geodes Anybody stuck with 10 geodes then figure it out? Or if anyone has the full path for the answer to the example ID2, I’d appreciate it. I get the correct answer “9” for ID1, and my answer path has the same as provided. I’m missing some case, data would help. (Edit: think I found it)

I'm sure this can all be expressed as a matrix of costs in materials/time, and solved in more or less constant time somehow

@tws do you still need the path for p2?

I was stuck on 10 for example 2 for a bit too, obviously a carefully chosen counter example!

For me, p2 on the example is many times slower than both parts on the real input

Whelp. First pass at part 1 overflows the stack on the first blueprint of the test data. And that's with some (weak) heuristics to prune the search-space.

@rjray sure you're not in an infinite loop somehow? I would have thought the recursion depth would be 24 at most even if you're doing a full on brute force? 🤔

I'm doing it as a BFS search, but I can't rule out an infinite loop. I'm basing this on a Python solution from reddit. The Python is slow, but it succeeds.

I just think my tail-recursion loop constructs are passing values that grow too large for the stack.

btw @tws here’s what i get for the p2 example for the second blueprint

0 wait
 1 wait
 2 ore
 3 wait
 4 ore
 5 clay
 6 clay
 7 clay
 8 clay
 9 clay
10 clay
11 obsidian
12 obsidian
13 obsidian
14 obsidian
15 ore
16 obsidian
17 geo
18 obsidian
19 geo
20 obsidian
21 geo
22 obsidian
23 geo
24 obsidian
25 geo
26 geo
27 geo
28 clay
29 geo
30 geo
31 geo

@rjray what are your loop variables? for collections, the size should not matter as the only thing on the stack is the pointer to them

if i had to guess, your stop condition is probably incorrect , e.g. it keeps going after time is zero, or doesn’t decrement time when recursing

Three elements: a list of moves, the current best value, and a set of seen states.

I had a similar problem with day 16, and just used my own Python code to get the points and stars for that one. I still don't have a Clojure version for that day.

Just using some simple prn-based debugging lines, I can see my queue of moves growing to almost 30000 before I stopped it.

where do you track time?

It's the last element of each move-value.

also, i might be wrong but i think in this puzzle there is no benefit to searching breadth first, so instead of a large queue, you could use a stack to conj/pop , or just use recursion

Dunno. Busy with my "real" job for now, will have to look at it later.

concat/cons (instead of into) of lazy seqs can overflow on fairly small amounts in loop s

Hmmm... I do have that. I use concat to ensure that the new moves go at the end of the list.

(first (loop [i 3500 xs []]
         (if (pos? i)
           (recur (dec i) (concat xs (range 0 i)))
           xs)))
Execution error (StackOverflowError) at (REPL:1).
null

use queue

(defn queue [init]
  #?(:cljs (into #queue[] init)
     :clj  (into PersistentQueue/EMPTY init)))

peek will take first, into will append

The worst day, even if you solve it for your input, it doesn’t mean that it will work for others. Hate these type of problems.

Well, that was educational. I replaced my makeshift-queue with PersistentQueue and got the first part correct. Once I've finished part 2, I'll try to fix Day 16 with PersistentQUeue, as well.

I wrote a solution similar as @norman did, and it looked like it worked fine until I got a wrong answer. Moreover, when I tested it with another input (for which I knew correct number of geodes), It turned out only for exactly one blueprint it got a wrong answer.

I just leave it here, some good ideas to try maybe later https://www.reddit.com/r/adventofcode/comments/zpy5rm/2022_day_19_what_are_your_insights_and/

Aaaand... part 2 results in an OutOfMemoryError in Java heap space...

Interesting. Bumped up the heap and restarted my CIDER REPL and it still dies on the test input. But run it from lein on the real data and I get the correct answer. I guess nREPL has it's own overhead...

I’m still working hard on this

That's not the right answer; your answer is too low.

I like my approach of doing a bfs one level at a time sorting the results via a geo heavy heuristic and taking the top 2000?

I’m still widening my heuristic until it stabilizes somewhere.

And part 1 is done!

and part2 rolls out https://github.com/bhauman/advent-of-code-2022/blob/main/src/adv2022/day19/sol.clj

I think that’s the trick, doing bfs level by level and sorting and trimming each level as input to the next level

(defn do-turn [blu robot]
  (cond-> blu
    robot (pay-for-robot robot)
    true robots-work
    robot (add-robot robot)))

(defn children [blu]
  (->> (conj (can-build? blu) nil)
       (map (partial do-turn blu))
       (map #(update % ::depth inc))))

(defn bfs-leveler [previous-level]
  (->> previous-level
       (mapv children)
       (reduce into #{})
       (sort-by blu-value >)
       (take 3000)))

(defn optimizing-game-player [blueprint minutes]
  (->> (iterate bfs-leveler [(assoc blueprint ::depth 0)])
       (take (inc minutes))
       last
       first))

I spent way too much time overthinking how to prune states and still haven’t come up with anything I like. (I’ve been skimming responses to avoid spoilers). I’ve gotten it down to ~3 minutes, but I’m not proud of it. I’m going to take that as a win for now and go back to Day 15 Part 2. I think I know what I need to do but I just can’t get motivated to write it.

Yeah I’m heading back to day 17 part 2

Today was brutal, but I ended up with something I'm not too embarrassed by: https://github.com/alexalemi/advent/blob/main/2022/clojure/p19.clj

Trick was to set a target machine and fast-forward potentially many steps

In the end, gets part 1 in 4 seconds and part 2 in 25 seconds

https://gitlab.com/maximoburrito/advent2022/-/blob/main/src/day19/main.clj This is really a terrible effort. The code is very slow - basically I'm searching the space with some really sketchy pruning out of states when geodes and obsidian can be made. But I'm doing the pruning kind of late. It's a mess... I started rewriting while waiting for part1 to finish, anticipating I'd need to do something better for part2, should my solution work at all. It turns out it did and that part2 required almost no changes, so I dropped it in favor of sleep. Almost ashamed to post this...