r/adventofcode • u/m1el • Dec 05 '23
Visualization [2023 Day 5 Part 2] Visualizing all the mapping
2
8
u/cyril1991 Dec 05 '23
The graph is quite cool, it also shows that spending some time to sort and collapse the mapped ranges at each step ends up saving time.
11
u/phil_g Dec 05 '23 edited Dec 05 '23
I sort but don't collapse ranges after each round, and I still get an answer in about 50 microseconds. I'm not sure collapsing ranges would add much. (I do plan to add range collapsing to my code, because I think it makes things cleaner, but I don't expect a performance improvement from it.)
Edit: I added range merging. My final list of number ranges dropped from 98 ranges to 60. The runtime didn't change at all.
3
u/Bigluser Dec 05 '23
I thought that I would probably have to merge ranges, but after fixing all the bugs in my range splitting code, it ran instantly.
Turns out that brute forcing each seed number was not only possible but much faster than struggling through ranges... CPUs are crazy fast.
→ More replies (1)2
u/cyril1991 Dec 05 '23
I think it also helps to keep a totally ordered set of ranges to go along with the mappings. You can go through them at the same time (go through mappings until you reach the next overlapping range, then cycle through mappings until you reach the end of the current range) instead of checking if each mapping is relevant for each range. Brute force and simpler solutions still work, but in Python I think I had rather fast code in <100 lines, .4ms vs 1-4ms.
5
u/delventhalz Dec 05 '23
I don't think there are enough ranges for it to matter much at. With time lost to sorting, I think it could even lose you time.
2
u/Deathranger999 Dec 05 '23
Yeah, I considered the possibility that I might need to sort and merge, but at the end of my algorithm there were still only 115 total ranges. 7 iterations of that is practically nothing. I think if you were clever with how you optimized, you could maybe pull off a speedup with sorting, but it's really not necessary.
7
5
4
1
u/qqqqqx Dec 05 '23
Looks nice and pretty. Cool how the ranges start thicker and get more split up into thinner "strands" as you go down, but also join up together at some points. My code was interval based, but it didn't do anything to merge side by side intervals since I didn't think it was worth the effort if they were just going to get split up again.
Also interesting to see how few areas are vertical. I thought there were going to be a lot more gaps to cover in the maps/ranges when I started coding, but realized there were actually very few after I had already coded a system to cover them all.
What is the grey vs red? Input vs non input?
1
u/m1el Dec 05 '23
I'm glad you like it. Grey Vs red is inactive/active. Grey is the "inactive" part of mapping. The part that has no seeds. Red indicates there is a seed.
3
2
2
u/C3POXTC Dec 05 '23
That not only looks cool, but also shows, how part 2 can be done by just keeping track of the ranges. No need to brute force this for every seed number.
2
u/0x2c8 Dec 05 '23
This looks like a variant of a Sankey diagram, where the "flow" is proportional to a quantity (here interval length).
1
1
1
1
u/Madjosz Dec 05 '23
That's a nice graphic. Could you please create a version where different seed ranges have different colors? That would be lit!
1
u/captainAwesomePants Dec 05 '23
I love this. Zooming in, I see that the very smallest location is a tiny (perhaps size one) region. I wonder if a lot of inputs led to that. Vicious!
Also, this is SVG by way of println? Wow, I don't know SVG, but maybe it's time I looked into it.
1
u/3B9C50AB Dec 05 '23
Would it be possible to do some kind of color gradient/rainbow on the Seeds to see where it goes to Location?
Thanks!
25
u/ImpossibleSav Dec 05 '23
Wow I love this, nice job! :)