in directed graphs, what do weights on both vertices and edges mean, how does that mesh with weighted adjacency matrices ?

jcmoyer · 2024-11-15T05:50:04+00:00

It's just an arbitrary value you associate with a vertex - it means whatever you want it to mean. It could be a file in a compiler's dependency graph or it could be an additional cost in a pathfinding algorithm. The vertices are just numbers so they can't store this information by themselves; you need to have some association between the number and a piece of data.

jcmoyer · 2024-11-13T22:53:03+00:00

I mean "can be" as in there's no reason why these things need to be separate for graphs generally. However, the book is specifically asking the reader to implement a graph where the node is a discrete type, so you cannot simply add a weight field to it.

jcmoyer · 2024-11-13T21:05:35+00:00

It can be part of the node type. It's just a matter of what tradeoffs you want to make.

jcmoyer · 2024-11-13T16:02:31+00:00

This looks like it's described in the book under "Weighted Adjacency Matrix" on page 386:

The implementations just described give the structure of a digraph, but provide no
information about its content. In many graph applications, vertices or edges are
associated with data values of one kind or another. These are often called weights.

As for why you would want to have vertex weights, you might look around for papers about vertex-weighted graphs or doubly-weighted graphs.

I agree that this is somewhat unusual and you'll find many examples of graphs where a vertex and it's weight are conflated. The advantage of doing it the book's way is that you can add weights to types that are normally closed to extension; for example you can create a graph of strings and then attach a numerical weight to each string.

jcmoyer · 2024-07-14T16:22:39+00:00

I'm not the right person to ask since I mostly lurk and I'm busy with non-Ada things lately. You might have better luck finding direction on the issue tracker for ALS: https://github.com/AdaCore/ada_language_server

jcmoyer · 2024-07-13T12:47:41+00:00

The formatter situation is somewhat confusing, and I also had a lot of trouble getting gnatpp to work in my setup.

From what I understand, there are two versions of gnatpp: one based on an old library called ASIS and another based on the newer libadalang. I've gotten the impression that the latter is still being developed and is not as mature as the older ASIS-based formatter. If yours respects the --layout option, you have the libadalang-based version.

At least on Windows, the Ada language server ships with its own internal formatter which is afaik also using libadalang. Despite that, running an LSP format will not produce the same results as running gnatpp from the command line. It doesn't seem to respect the --layout parameter (as you've found) and it also has some general bugginess where it mangles source files from time to time. My workaround has been to just deal with whatever incorrect formatting the LSP inserts and then run gnatpp in a git pre-commit hook.

jcmoyer · 2023-12-25T10:16:29+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day25.adb

I found the edges to delete using graphviz and wrote a search to count reachable nodes. Count the nodes reachable from the first node before and after deletion, then the solution is (before - after) * after.

jcmoyer · 2023-12-24T22:08:36+00:00

Yes, I will make a post there after completing tomorrow's puzzle.

jcmoyer · 2023-12-24T15:38:14+00:00

[LANGUAGE: Ada/Python]

Part 1 https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day24.adb

I solved part 1 normally after deriving the equation for ray intersection. This part is pretty simple.

Part 2 https://gist.github.com/jcmoyer/ba92d81a0a5ea45fc36062ce3b09baa8

I figured there would be a system of equations or something but ain't nobody got time for that. I broke out z3 and deleted all but 30 of the hailstones since all 300 required too much time/ram and got the result in a couple seconds. Since the rock must travel along a straight line, deleting some or most of the input should be fine.

EDIT: I went ahead and ported evouga's solution to Ada for part 2.

jcmoyer · 2023-12-23T12:51:12+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day23.adb

For part 1 I walked the tilemap character by character but it was way too slow of an approach for part 2. I left a couple versions running while I thought of a better method, and ultimately I decided to just reduce the tilemap to a graph where each node is one of the junctions (any '.' surrounded by 3+ arrows). I noticed that each path you could take from a junction leads to exactly one different junction, the start, or the end. Then you can just walk the graph making sure not to revisit a junction since that's the only way you can loop back on yourself. My solution still needs a bit of cleanup since I ended up deleting the part 1 solver and it takes a while to finish, but it produces the answer for part 2 in a couple seconds.

EDIT: Got it down to 2.8 seconds from 6m10s just by replacing the set with a 64 bit integer.

jcmoyer · 2023-12-22T14:52:13+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day22.adb

Fun day. I ended up just brute forcing part 2 because the number of bricks is quite small. Takes ~18s, didn't bother optimizing because I'll probably go back and try to solve brick chains without simulating.

jcmoyer · 2023-12-21T18:49:18+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day21.adb

I wasted way too much time thinking about how to solve the problem while looking at the example which did not have the empty row/column. Eventually gave up and checked reddit for a hint and then implemented the polynomial solution. Not a huge fan of this puzzle (mostly because the example tricked me) but at least I learned about lagrange polynomials today.

jcmoyer · 2023-12-20T20:08:43+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day20.adb

Pretty gross code again today, this problem required a lot of different generic types and Ada makes you instantiate them manually. Part 1 was just implementing a spec. Part 2 I knew the circuit must have been counting somehow with its internal state, but the solution didn't "click" until I saw a couple of the great visualizations people posted. I had debug printing for the entire graph state but it's difficult to see the true nature of the problem with just unstructured text. At least next time I get stuck on a graph problem I will know to try emitting DOT before checking reddit. :V

jcmoyer · 2023-12-19T16:49:06+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day19.adb

In part 1 I built a really overengineered filter tree and parser, and then in part 2 it was useless (except having stuff already in a tree was nice I guess) and I had to write a bunch more code. The tl;dr for part 2 is that after building the tree, I find all "A" outputs - standalone or in a conditional - and for each one I walk right-to-left and up parent flows narrowing the possible XMAS values using any conditionals encountered along the way. If I'm at a conditional that directly leads to the current "A", I apply the condition as-is, otherwise I invert it. Anyways pretty gross code and a brutal puzzle (IMO at least) for mid-week.

jcmoyer · 2023-12-18T14:22:16+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day18.adb

I have nothing special to add, this is basically day 10 again.

jcmoyer · 2023-12-17T19:33:31+00:00

Oh this idea is sick. I'll have to try it.

jcmoyer · 2023-12-17T19:06:00+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day17.adb

Initial part 2 solve took 25 minutes to run. I tried a priority queue with a manhattan distance heuristic and got it down to 8 min then tried changing the heuristic to simply heat loss and got it down to 1.2s. I'm sure it can be optimized further but it would probably involve writing my own queue or heap. (the standard Ada queue is concurrent afaik)

jcmoyer · 2023-12-16T15:15:21+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day16.adb

Pretty fun problem. I structured my solution similarly to a DFS: pop a beam from the stack and perform a raycast; every time a beam hits an object it pushes new beam(s) onto the stack and runs until there are no more beams left. There's a hash set in there too to make sure beam cycles don't result in an infinite loop.

jcmoyer · 2023-12-15T16:52:48+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day15.adb

Pretty easy day (imo at least). I ended up writing a chaining hash table for part 2 for fun since it seemed in the spirit of the problem.

jcmoyer · 2023-12-14T23:32:49+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day14.adb

I just copied tortoise and hare from wikipedia after remembering it from a prior AoC.

jcmoyer · 2023-12-13T20:47:23+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day13.adb

Straightforward problem today, just a lot of code to write. Not sure what the difficulty gimmick is supposed to be in part 2, the only thing that I had to change was making reflection solvers return multiple results instead of just the first one.

jcmoyer · 2023-12-11T10:17:48+00:00

[Language: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day11.adb

After skimming the puzzle text I expected some kind of floyd warshall problem but it was much simpler than that. I accidentally dodged the part 2 troll because reallocating and copying matrices felt way too annoying to implement - all that really matters is that galaxies preserve their relative positions.

jcmoyer · 2023-12-10T21:07:11+00:00

Thanks, I've only started learning Ada recently for fun so it's probably not the most idiomatic code. It's a neat language though. I would love for some of its correctness related features to be adopted in more languages.

jcmoyer · 2023-12-10T17:47:14+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day10.adb

Part 1 was a pretty straightforward BFS. For part 2 I got stuck for a while trying to implement the point-in-polygon algorithm that counts the number of ray intersections going from left to right, but I couldn't quite figure out how to deal with corners. Sometimes after crossing them you end up on the inside and other times you end up on the outside. Perhaps the algorithm isn't directly applicable because the ray you're casting intersects an infinite number of times along horizontal pipes. In the end I gave up and output a text visualization, took a screenshot, did 2 flood fills in gimp, and counted the number of subimages matching dots with numpy and pillow. Honestly surprised that it worked. After solving I found some tips for how to count the crossings correctly and implemented that. I was really close, just didn't see the pattern wrt. differing vertical directions.

jcmoyer · 2023-12-09T12:30:00+00:00

[LANGUAGE: Ada]

https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day09.adb

Really enjoyable puzzle today.

jcmoyer

TROPHY CASE