What are you coding?

Not Games
282

I have now created a generic Dijkstra or rather A* for Day16 because I expect this to come up again and also I really want to go back and get the same one working for the day I stole it from.

I was sure I had it. And then I learned that
turning on a valve has a cost of 1 minute.
I’ve been tracking “turned on valves” just by “being on the path”. and now my heuristic is all wrong.

I really loved Day15 by comparison. Neat problem. This: meh.

I have a dislike for having to implement “classic uni algorithms.” Just like sorting I expect them to be part of the standard library that I don’t have to think about. Somebody already solved this problem and I am unlikely to find a better solution.

3 Likes
283

Yes, I’m inclined to agree. Even so, working out which pack of algorithms can be fun.

There have been a lot of path search problems in previous AoCs, but if I were to write a generic implementation I’d want to hook it everywhere: callback functions at every step to tweak it for the specific situation.

3 Likes
284

Apparently, I am too [something] to implement this. Hmf.

I am looking for the best path of actions to take
So the cost of each “action” is 1 as in 1 minute
Possible actions:

  • move , value=0
  • turn on valve, value/heuristic for valve = (MAX_TIME-totalCost)*flowRate
  • I have ensured that each valve can only be turned on once.
  • so F = totalCost of path - value (minus because higher values are good here)

And still my algorithm does not get the correct total for the test data. And I am now leaving to do some errands and maybe when I get back I’ll have some kind of Geistesblitz.

1 Like
285

That was my pass 1 and it didn’t work. Then I worked out that the only points on the path that matter are the ones where you turn on a valve, and the only valve-turnings that matter are the ones with flow > 0 which means the network to evaluate is not “all visits to all valves” but “AA, and turnings of valves with flow > 0”

Not feeling enthused about day 17, mind.

3 Likes
286

I’ve pretty much scrapped everything I wrote yesterday for Day 16 part 1 and cribbed a Python implementation of the A* algorithm from the net because I didn’t fancy debugging my own alongside the rest of what’s needed. Just sitting looking at it now not sure how to proceed.

3 Likes
287

I did the same for Java back on Day 12 and now generified it. But I was doing errands so still haven’t solved how to parametrize it. Took me hours though to get to where I am now. But errands are done and apparently I want to code more than I want to play Ark Nova

3 Likes
288

I read you and I think I tried part of that yesterday when I tried shrinking the problem. I am at the limit of my abstraction ability with Day16 I think. Or Brett vorm Kopf.

edit: I am thinking that I need to run a “precalculation” of minimum distance between valves then I can run a “simple” calculation which valve is best to go to next with the same formula I am using now.

edit2: I think this means that I run repeated searches each time with a new start node and I am building a path of valves or just the sum of those through subsearches. Mostly I hate running into more and more complicated dead-ends.

PS: sometimes grumbling is part of the “fun” :stuck_out_tongue:

3 Likes
289

I think this is where I’m ending up.

I’m using the cribbed A* search as a tool to translate the starting graph into a new graph of just the working valves (and AA) with their respective weights to all the other working valves. Then I ought to be able to traverse those nodes with the appropriate maximisation.

In theory.

Edit: Ah, greedily searching doesn’t work :cry:

3 Likes
290

Sounds pretty good. I used to like graphs. We had a good relationship. But now that graphs apparently need to be translated into matrices I am breaking up with graphs.

3 Likes
291

(day 16) I went a step further than that:

I precalculate the distances between all valves. Then my graph nodes are “visits to a valve which I turn on” (plus valve AA), path weights are distances between them, and I can pathfind in that without having to worry about repetition - just generate all paths that fit in the time, and keep the one with maximum release.

(day 17)

So yeah. The shapes were the discouraging bit, so I converted them to bitfield of each row: so #### is 15, ..# is 4. Yes, left side is low bit. It seemed like a good idea at the time, largely for reasons which ended up not being relevant. Sequence of bitfields is bottom to top. Also precalculate the width of each shape.

My “chute” is also one bitfield per row, extended upwards as needed. So a collision check is:

  • check for left and right side excursions
  • check for bottom edge excursion
  • check each row against that row of the chute for any overlaps (yay bitwise and).

Once a shape has come to rest, write its patterns into the chute and prune off any empty rows at the top.

That’s part 1. For part 2, which feels like a classic AoC “now do it with a number that’s far too large”, I look for repetitions - I store the height and the jet index each time the rock index comes round to zero. When I see a jet index for the second time, I’ve got a periodicity. Then the total height is the sum of

  • height at the start of the periodicity
  • height gained by the periodicity × number of repetitions
  • height gained by the last fragment of the periodicity at the top
2 Likes
292
Day 16

First I tried a recursive, mostly-naïve, bruteforce method using just BGP-style loop prevention.

This method produces consistent segfaults in python3, likely due to me using yield in the recursive loop generation (is yield still pythonic? I dunno. I thought it might be slightly more memory friendly than creating a bunch of anonymous list objects.

Sadly, I ran out of time working on it yesterday and won’t have enough screen time this weekend to really work on it some more so I’ll be really behind by Monday.

Re-attempt plan: move to an iterative approach with more short-circuiting and focusing on only opening non-zero valves… but probably still permuting between the options because I can’t, at the moment, conceptualize how to accurately prioritize which valve to open in which order.

2 Likes
293

I caved and made a matrix for the input for Day 16:

Testinput Output 
    AA  BB  CC  DD  EE  FF  GG  HH  II  JJ  
AA   0   1   2   1   2   3   4   5   1   2  
BB   1   0   1   2   3   4   5   6   2   3  
CC   2   1   0   1   2   3   4   5   3   4  
DD   1   2   1   0   1   2   3   4   2   3  
EE   2   3   2   1   0   1   2   3   3   4  
FF   3   4   3   2   1   0   1   2   4   5  
GG   4   5   4   3   2   1   0   1   5   6  
HH   5   6   5   4   3   2   1   0   6   7  
II   1   2   3   2   3   4   5   6   0   1  
JJ   2   3   4   3   4   5   6   7   1   0

Now I need to parametrize the A* with that as base. If this is not it, I am giving up.

2 Likes
294

I did it! Now onto part 2.

Getting the max value out of my depth-first-search wasn’t elegant, but I don’t really care.

2 Likes
295

Been mulling over part 2 while I’ve been cooking, etc. Still none the wiser about how to tackle it. So much for catching up today.

3 Likes
296

OMG… after probably 8 hours of coding I have solved part 1. Not great that it feels like part 2 is some additional fiddly stuff. But sunk-cost fallacy. Now I need to solve this. My solution ended up somewhat of a mix of brute force and A* and many thanks to @RogerBW for the clue that reminded me of my initial hunch (which I ignored) to reduce the problem space. I really wasn’t sure anymore I could solve this. So many stupid mistakes.

Part 1 (minus the fiddly bits -.-) 
List<Path<Valve>> paths= new ArrayList<>(List.of(new Path<Valve>( null, VALVES.get(START),0,0 )));
            List<Path<Valve>> results = new ArrayList<>();
            while(!paths.isEmpty()){
                List<Path<Valve>> candidates = new ArrayList<>();
                for(Path<Valve> path : paths){
                    List<Path<Valve>> childPaths = getLegalChildPaths( path );
                    if(childPaths.isEmpty()){
                        results.add(path);
                    } else {
                        candidates.addAll(childPaths);
                    }
                }
                paths = candidates;
            }
            return results.stream().map(Path::getTotalHeuristic).max(Integer::compareTo).orElse( 0 );
2 Likes
297

Holy crap. I’ve got part 2 working for the sample.

Was avoiding working on it so I refactored my part 1 to be a bit tidier, then spotted how I might expand it for more travellers. Kind of surprised it worked.

Do I try the full input at this hour?

2 Likes
298

I think I’ll just go to sleep now. The elephants können mich mal (short for something I am definitely not going to translate).

image

3 Likes
299

I hate elephants.

Behold my first ever parallelStream and it really makes a difference, I can't quite believe it 
results.keySet().parallelStream().forEach( path -> {
      results.keySet().parallelStream().forEach ( compare -> {
          if ( results.get(path).stream().noneMatch(a -> results.get( compare ).contains( a ) ) ) {
            unions.add( path.getTotalHeuristic() + compare.getTotalHeuristic() );
      }
   });
});
2 Likes
300

Oh look at you with your fancy noneMatch(). In my day we used bitfields, in the snow, uphill, both ways…

:slight_smile:

2 Likes
301

I tried using retainAll on the sets it probably worked because at that point I had other errors.
I used your information from far up on how to solve this I admit. I couldn’t have got there this fast (this word is covered in a thick coat of irony and yet has truth in it, too) on my own.

Both parts together of Day16 now run in 13.5 seconds…

2 Likes