🛶 - 2023 DAY 18 SOLUTIONS -🛶

Day 18: Lavaduct Lagoon

Megathread guidelines

Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

What is this?: Here is a post with a large amount of details: programming.dev/post/6637268
Where do I participate?: adventofcode.com
Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: programming.dev/post/6631465

Image

Image alternative text

cacheson, 5 months ago (edited 5 months ago)

Nim

I am not making good time on these anymore.

For part 1, I walked through the dig plan instructions, keeping track of the highest and lowest x and y values reached, and used those to create a character grid, with an extra 1 tile border around it. Walked the instructions again to plot out the trench with #, flood-filled the exterior with O, and then counted the non-O tiles. Sort of similar to the pipe maze problem.

This approach wouldn't have been viable for part 2, due to the scale of the numbers involved. Instead I counted the number of left and right turns in the trench to determine whether it was being dug in a clockwise or counterclockwise direction, and assumed that there were no intersections. I then made a polygon that followed the outer edge of the trench. Wherever there was a run of 3 inward turns in a row, that meant there was a rectangular protrusion that could be chopped off of the main polygon. Repeatedly chopping these off eventually turns the polygon into a rectangle, so it's just a matter of adding up the area of each. This worked great for the example input.

Unfortunately when I ran it on the actual input, I ran out of sets of inward turns early, leaving an "inside out" polygon. I thought this meant that the input must have intersections in it that I would have to untwist somehow. To keep this short, after a long debugging process I figured out that I was introducing intersections during the chopping process. The chopped regions can have additional trench inside of them, which results in those parts ending up outside of the reduced polygon. I solved this by chopping off the narrowest protrusions first.

Day 18, part 1

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

cacheson, 5 months ago

Day 18, part 2

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

zarlin, 5 months ago

Good job on persevering with this one. Your approach for part 2 sounds quite viable, it is very similar to the Ear clipping method for triangulating a polygon.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

cacheson, 5 months ago

Yeah, I read up on ear clipping for a small game dev project a while back, though I don't remember if I actually ended up using it. So my solution is inspired by what I remember of that.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

zarlin, 5 months ago

Nim

Decided to go for a polygon approach for part 1 using the Shoelace formula to calculate the area. This meant part 2 only resulted in larger values, no additional computation.

Code runs in <1ms for part 1 and 2 combined

Source

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

cacheson, 5 months ago

Shoelace formula

This would have been really useful to know about. I've committed to a certain level of wheel-reinvention for this event unless I get really stuck, but I'm sure it'll come up again in the future.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

zarlin, 5 months ago

This was actually something I learned for my job, it was nice to be able to apply it here.

I like your commitment to wheel-reinvention, it can be a lot more fun than going for an existing or ‘intended’ approach.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

cacheson, 5 months ago

Yep, I figure it's good exercise to make me think through the problems thoroughly.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

cvttsd2si, 5 months ago

C++

No scala today


<span style="font-weight:bold;color:#a71d5d;">#include 
</span><span style="font-weight:bold;color:#a71d5d;">#include 
</span><span style="font-weight:bold;color:#a71d5d;">#include </span><span style="color:#183691;"><map>
</span><span style="font-weight:bold;color:#a71d5d;">#include 
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">#include 
</span><span style="font-weight:bold;color:#a71d5d;">#include 
</span><span style="font-weight:bold;color:#a71d5d;">#include 
</span><span style="font-weight:bold;color:#a71d5d;">#include 
</span><span style="font-weight:bold;color:#a71d5d;">#include 
</span><span style="font-weight:bold;color:#a71d5d;">#include 
</span><span style="font-weight:bold;color:#a71d5d;">#include 
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">struct </span><span style="color:#323232;">HorizontalEdge { boost::icl::discrete_interval x; </span><span style="font-weight:bold;color:#a71d5d;">long</span><span style="color:#323232;"> y; };
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">long </span><span style="font-weight:bold;color:#795da3;">area</span><span style="color:#323232;">(std::vector he) {
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">if</span><span style="color:#323232;">(he.empty())
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#0086b3;">0</span><span style="color:#323232;">;
</span><span style="color:#323232;">
</span><span style="color:#323232;">    boost::icl::interval_set intervals;
</span><span style="color:#323232;">    std::ranges::sort(he, std::less{}, </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;HorizontalEdge::y);
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">long</span><span style="color:#323232;"> area{};
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">long</span><span style="color:#323232;"> y </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> he.front().y;
</span><span style="color:#323232;">
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">auto const&</span><span style="color:#323232;">amp; e </span><span style="font-weight:bold;color:#a71d5d;">:</span><span style="color:#323232;"> he) {
</span><span style="color:#323232;">        area </span><span style="font-weight:bold;color:#a71d5d;">+=</span><span style="color:#323232;"> intervals.size() </span><span style="font-weight:bold;color:#a71d5d;">* </span><span style="color:#323232;">(e.y </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#323232;">std::exchange(y, e.y));
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if</span><span style="color:#323232;">(intervals.find(e.x) </span><span style="font-weight:bold;color:#a71d5d;">!=</span><span style="color:#323232;"> intervals.end())
</span><span style="color:#323232;">            intervals.erase(e.x);
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">else 
</span><span style="color:#323232;">            intervals.add(e.x);
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return</span><span style="color:#323232;"> area;
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">struct </span><span style="color:#323232;">Instruction {
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">long</span><span style="color:#323232;"> l;
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">int</span><span style="color:#323232;"> d;
</span><span style="color:#323232;">    std::string color;
</span><span style="color:#323232;">};
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">enum </span><span style="color:#323232;">Dir { R</span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, U</span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#0086b3;">1</span><span style="color:#323232;">, L</span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#0086b3;">2</span><span style="color:#323232;">, D</span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#0086b3;">3 </span><span style="color:#323232;">};
</span><span style="color:#323232;">std::unordered_map char_to_dir </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">{{</span><span style="color:#183691;">'R'</span><span style="color:#323232;">, R}, {</span><span style="color:#183691;">'U'</span><span style="color:#323232;">, U}, {</span><span style="color:#183691;">'L'</span><span style="color:#323232;">, L}, {</span><span style="color:#183691;">'D'</span><span style="color:#323232;">, D}};
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">auto </span><span style="font-weight:bold;color:#795da3;">transcode</span><span style="color:#323232;">(std::vector </span><span style="font-weight:bold;color:#a71d5d;">const&</span><span style="color:#323232;">amp; is) {
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">flux::from(std::move(is)).map([](Instruction in) {
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">long</span><span style="color:#323232;"> v </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">std::stoul(in.color.substr(</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">5</span><span style="color:#323232;">), </span><span style="color:#0086b3;">nullptr</span><span style="color:#323232;">, </span><span style="color:#0086b3;">16</span><span style="color:#323232;">);
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">return</span><span style="color:#323232;"> Instruction{.l </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> v, .d </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">(</span><span style="color:#0086b3;">4 </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#323232;">(in.color.at(</span><span style="color:#0086b3;">5</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#183691;">'0'</span><span style="color:#323232;">)) </span><span style="font-weight:bold;color:#a71d5d;">% </span><span style="color:#0086b3;">4</span><span style="color:#323232;">, .color</span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#183691;">""</span><span style="color:#323232;">};
</span><span style="color:#323232;">    }).to</span><span style="font-weight:bold;color:#a71d5d;">></span><span style="color:#323232;">();
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">std::vector </span><span style="font-weight:bold;color:#795da3;">read</span><span style="color:#323232;">(std::string path) {
</span><span style="color:#323232;">    std::ifstream in(std::move(path));
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">flux::getlines(in).map([](std::string </span><span style="font-weight:bold;color:#a71d5d;">const&</span><span style="color:#323232;">amp; s) {
</span><span style="color:#323232;">        Instruction i;
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">char</span><span style="color:#323232;"> dir;
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">auto</span><span style="color:#323232;"> r </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">scn::scan(s, </span><span style="color:#183691;">"{} {} (#{:6})"</span><span style="color:#323232;">, dir, i.l, i.color)) {
</span><span style="color:#323232;">            i.d </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> char_to_dir[dir];
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">return</span><span style="color:#323232;"> i;
</span><span style="color:#323232;">        } </span><span style="font-weight:bold;color:#a71d5d;">else </span><span style="color:#323232;">{
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">throw</span><span style="color:#323232;"> std::runtime_error{r.error().msg()};
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">    }).to</span><span style="font-weight:bold;color:#a71d5d;">></span><span style="color:#323232;">();
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">auto </span><span style="font-weight:bold;color:#795da3;">turns</span><span style="color:#323232;">(std::vector is) {
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">if</span><span style="color:#323232;">(is.empty()) </span><span style="font-weight:bold;color:#a71d5d;">throw</span><span style="color:#323232;"> std::runtime_error{</span><span style="color:#183691;">"Too few elements"</span><span style="color:#323232;">};
</span><span style="color:#323232;">    is.push_back(is.front());
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">flux::from(std::move(is)).pairwise_map([](</span><span style="font-weight:bold;color:#a71d5d;">auto const&</span><span style="color:#323232;">amp; lhs, </span><span style="font-weight:bold;color:#a71d5d;">auto const&</span><span style="color:#323232;">amp; rhs) { </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">(rhs.d </span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#323232;"> lhs.d </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#0086b3;">4</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">% </span><span style="color:#0086b3;">4 </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#0086b3;">1</span><span style="color:#323232;">; });
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">std::vector </span><span style="font-weight:bold;color:#795da3;">toEdges</span><span style="color:#323232;">(std::vector is, </span><span style="font-weight:bold;color:#a71d5d;">bool </span><span style="color:#323232;">left) {
</span><span style="color:#323232;">    std::vector res;
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">long</span><span style="color:#323232;"> x{}, y{};
</span><span style="color:#323232;">
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">auto</span><span style="color:#323232;"> t </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">turns(is).to</span><span style="font-weight:bold;color:#a71d5d;">></span><span style="color:#323232;">();
</span><span style="color:#323232;">
</span><span style="color:#323232;">    </span><span style="font-style:italic;color:#969896;">// some magic required to turn the ### path into its outer edge
</span><span style="color:#323232;">    </span><span style="font-style:italic;color:#969896;">// (which is the actual object we want to compute the area for)
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;">(</span><span style="color:#0086b3;">size_t</span><span style="color:#323232;"> j </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">0</span><span style="color:#323232;">; j </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; is.size(); </span><span style="font-weight:bold;color:#a71d5d;">++</span><span style="color:#323232;">j) {
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">auto const&</span><span style="color:#323232;">amp; i </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> is.at(j);
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">bool</span><span style="color:#323232;"> s1 </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> t.at((j </span><span style="font-weight:bold;color:#a71d5d;">+</span><span style="color:#323232;"> t.size() </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#0086b3;">1</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">%</span><span style="color:#323232;"> t.size()) </span><span style="font-weight:bold;color:#a71d5d;">==</span><span style="color:#323232;"> left;
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">bool</span><span style="color:#323232;"> s2 </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> t.at(j) </span><span style="font-weight:bold;color:#a71d5d;">==</span><span style="color:#323232;"> left;
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">long</span><span style="color:#323232;"> sign </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">(i.d </span><span style="font-weight:bold;color:#a71d5d;">==</span><span style="color:#323232;"> U </span><span style="font-weight:bold;color:#a71d5d;">||</span><span style="color:#323232;"> i.d </span><span style="font-weight:bold;color:#a71d5d;">==</span><span style="color:#323232;"> L) </span><span style="font-weight:bold;color:#a71d5d;">? -</span><span style="color:#0086b3;">1 </span><span style="font-weight:bold;color:#a71d5d;">: </span><span style="color:#0086b3;">1</span><span style="color:#323232;">;
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">long</span><span style="color:#323232;"> old_x </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> x;
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if</span><span style="color:#323232;">(i.d </span><span style="font-weight:bold;color:#a71d5d;">==</span><span style="color:#323232;"> R </span><span style="font-weight:bold;color:#a71d5d;">||</span><span style="color:#323232;"> i.d </span><span style="font-weight:bold;color:#a71d5d;">==</span><span style="color:#323232;"> L) {
</span><span style="color:#323232;">            x </span><span style="font-weight:bold;color:#a71d5d;">+=</span><span style="color:#323232;"> i.l </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;"> sign;
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">auto </span><span style="color:#323232;">[l, r] </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> old_x </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; x </span><span style="font-weight:bold;color:#a71d5d;">?</span><span style="color:#323232;"> std::tuple{old_x </span><span style="font-weight:bold;color:#a71d5d;">+ !</span><span style="color:#323232;">s1, x </span><span style="font-weight:bold;color:#a71d5d;">+</span><span style="color:#323232;"> s2} </span><span style="font-weight:bold;color:#a71d5d;">:</span><span style="color:#323232;"> std::tuple{x </span><span style="font-weight:bold;color:#a71d5d;">+ !</span><span style="color:#323232;">s2, old_x </span><span style="font-weight:bold;color:#a71d5d;">+</span><span style="color:#323232;"> s1};
</span><span style="color:#323232;">            res.push_back(HorizontalEdge{.x </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">{l, r, boost::icl::interval_bounds::right_open()}, .y </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> y});
</span><span style="color:#323232;">        } </span><span style="font-weight:bold;color:#a71d5d;">else </span><span style="color:#323232;">{
</span><span style="color:#323232;">            y </span><span style="font-weight:bold;color:#a71d5d;">+= </span><span style="color:#323232;">(i.l </span><span style="font-weight:bold;color:#a71d5d;">+</span><span style="color:#323232;"> s1 </span><span style="font-weight:bold;color:#a71d5d;">+</span><span style="color:#323232;"> s2 </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#0086b3;">1</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;"> sign;
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return</span><span style="color:#323232;"> res;
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">long </span><span style="font-weight:bold;color:#795da3;">solve</span><span style="color:#323232;">(std::vector is) {
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">auto</span><span style="color:#323232;"> tn </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">turns(is).sum() </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#323232;">ssize(is);
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">area(toEdges(std::move(is), tn </span><span style="font-weight:bold;color:#a71d5d;">> </span><span style="color:#0086b3;">0</span><span style="color:#323232;">));
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">int </span><span style="font-weight:bold;color:#795da3;">main</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">int </span><span style="color:#323232;">argc, </span><span style="font-weight:bold;color:#a71d5d;">char* </span><span style="color:#323232;">argv[]) {
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">auto</span><span style="color:#323232;"> instructions </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">read(argc </span><span style="font-weight:bold;color:#a71d5d;">> </span><span style="color:#0086b3;">1 </span><span style="font-weight:bold;color:#a71d5d;">?</span><span style="color:#323232;"> argv[</span><span style="color:#0086b3;">1</span><span style="color:#323232;">] </span><span style="font-weight:bold;color:#a71d5d;">: </span><span style="color:#183691;">"../task1.txt"</span><span style="color:#323232;">);
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">auto</span><span style="color:#323232;"> start </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">std::chrono::steady_clock::now();
</span><span style="color:#323232;">    fmt::print(</span><span style="color:#183691;">"task1={}</span><span style="color:#0086b3;">n</span><span style="color:#183691;">task2={}</span><span style="color:#0086b3;">n</span><span style="color:#183691;">"</span><span style="color:#323232;">, solve(instructions), solve(transcode(std::move(instructions))));
</span><span style="color:#323232;">    fmt::print(</span><span style="color:#183691;">"took {}</span><span style="color:#0086b3;">n</span><span style="color:#183691;">"</span><span style="color:#323232;">, std::chrono::steady_clock::now() </span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#323232;"> start);
</span><span style="color:#323232;">}
</span><span style="color:#323232;">```</span><span style="font-weight:bold;color:#a71d5d;"></</span><span style="color:#323232;">map</span><span style="font-weight:bold;color:#a71d5d;">>
</span>

cvttsd2si, 5 months ago

looks like some broken XSS protection is killing the includes, can’t really fix that

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

sjmulder, 5 months ago (edited 5 months ago)
C

Fun and interesting puzzle! In part 1 I fumbled a bit trying to implement even/odd outside/inside tracking before realizing that wouldn’t work for this shape and just did the flood fill.

For part 2 I correctly guessed that like the intersecting cuboids (2021 day 22) it would be about finding a better representation for the grid or avoiding representing it entirely. Long story shorter:
/*
 * Conceptually: the raw map, which is too large to fit directly in
 * memory for part 2, is made much smaller by collapsing (and counting)
 * identical rows and columns. Another way to look it at is that a grid
 * is fitted to make 'opaque' cells.
 * | |#|##|#
 * For example: -+---+-+--+-
 * #|###|#| |#
 * #### ### 1 -+---+-+--+-
 * ##### # ### # 1 #| | | |#
 * # # becomes # # 2 or: #| | | |#
 * # # ##### 1 -+---+-+--+-
 * ######## 13121 #|###|#|##|#
 *
 * To avoid a lot of complex work, instead of actually collapsing and
 * splitting rows and columns, we first generate the wall rectangles and
 * collect the unique X and Y coordinates. Those are locations of our
 * virtual grid lines.
 */

Despite being quite happy with this solution, I couldn’t help but notice the brevity and simplicity of the other solutions here. Gonna have a look what’s happening there and see if I can try that approach too.

(Got bitten by a nasty overflow btw, the list of unique X coordinates was overwriting the list of unique Y coordinates. Oh well, such is the life of a C programmer.)

github.com/sjmulder/aoc/blob/master/…/day18.c
reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

lwhjp, 5 months ago

Oh, just like day 11! I hadn’t thought of that. I was initially about to try something similar by separating into rectangular regions, as in ear-clipping triangulation. But that would require a lot of iterating, and something about “polygon” and “walking the edges” went ping in my memory…

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

hades, 5 months ago

Python

Also on Github

0.09 line-seconds (third simplest after days 6 and 2).


<span style="font-weight:bold;color:#a71d5d;">from .</span><span style="color:#323232;">solver </span><span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">Solver
</span><span style="color:#323232;">
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">class </span><span style="color:#0086b3;">Day18</span><span style="color:#323232;">(</span><span style="color:#0086b3;">Solver</span><span style="color:#323232;">):
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#62a35c;">__init__</span><span style="color:#323232;">(self):
</span><span style="color:#323232;">    </span><span style="color:#62a35c;">super</span><span style="color:#323232;">().</span><span style="color:#62a35c;">__init__</span><span style="color:#323232;">(</span><span style="color:#0086b3;">18</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">presolve</span><span style="color:#323232;">(self, input: </span><span style="color:#0086b3;">str</span><span style="color:#323232;">):
</span><span style="color:#323232;">    self.lines </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#62a35c;">input</span><span style="color:#323232;">.splitlines()
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">solve_first_star</span><span style="color:#323232;">(self):
</span><span style="color:#323232;">    commands </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">[]
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">line </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">self.lines:
</span><span style="color:#323232;">      direction, distance, </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;">_ </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">line.split(</span><span style="color:#183691;">' '</span><span style="color:#323232;">)
</span><span style="color:#323232;">      commands.append((direction, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">(distance)))
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">self._solve(commands)
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">solve_second_star</span><span style="color:#323232;">(self):
</span><span style="color:#323232;">    commands </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">[]
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">line </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">self.lines:
</span><span style="color:#323232;">      _, _, command </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">line.split(</span><span style="color:#183691;">' '</span><span style="color:#323232;">)
</span><span style="color:#323232;">      distance </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">int</span><span style="color:#323232;">(command[</span><span style="color:#0086b3;">2</span><span style="color:#323232;">:</span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#0086b3;">2</span><span style="color:#323232;">], </span><span style="color:#0086b3;">16</span><span style="color:#323232;">)
</span><span style="color:#323232;">      direction </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">(</span><span style="color:#183691;">'R'</span><span style="color:#323232;">, </span><span style="color:#183691;">'D'</span><span style="color:#323232;">, </span><span style="color:#183691;">'L'</span><span style="color:#323232;">, </span><span style="color:#183691;">'U'</span><span style="color:#323232;">)[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">(command[</span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#0086b3;">2</span><span style="color:#323232;">])]
</span><span style="color:#323232;">      commands.append((direction, distance))
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">self._solve(commands)
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">_solve</span><span style="color:#323232;">(self, commands: </span><span style="color:#0086b3;">list</span><span style="color:#323232;">[</span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">str</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">]]):
</span><span style="color:#323232;">    points: </span><span style="color:#0086b3;">list</span><span style="color:#323232;">[</span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">]] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">[(</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">)]
</span><span style="color:#323232;">    perimeter_integer_points </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">1
</span><span style="color:#323232;">    x, y </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">direction, distance </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">commands:
</span><span style="color:#323232;">      dx, dy </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">{</span><span style="color:#183691;">'R'</span><span style="color:#323232;">: (</span><span style="color:#0086b3;">1</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">), </span><span style="color:#183691;">'L'</span><span style="color:#323232;">: (</span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#0086b3;">1</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">), </span><span style="color:#183691;">'U'</span><span style="color:#323232;">: (</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#0086b3;">1</span><span style="color:#323232;">), </span><span style="color:#183691;">'D'</span><span style="color:#323232;">: (</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">1</span><span style="color:#323232;">)}[direction]
</span><span style="color:#323232;">      x, y </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">x </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">dx </span><span style="font-weight:bold;color:#a71d5d;">* </span><span style="color:#323232;">distance, y </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">dy </span><span style="font-weight:bold;color:#a71d5d;">* </span><span style="color:#323232;">distance
</span><span style="color:#323232;">      perimeter_integer_points </span><span style="font-weight:bold;color:#a71d5d;">+= </span><span style="color:#323232;">distance
</span><span style="color:#323232;">      points.append((x, y))
</span><span style="color:#323232;">    last_x, last_y </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">points[</span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#0086b3;">1</span><span style="color:#323232;">]
</span><span style="color:#323232;">    perimeter_integer_points </span><span style="font-weight:bold;color:#a71d5d;">+= </span><span style="color:#62a35c;">abs</span><span style="color:#323232;">(last_x) </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#62a35c;">abs</span><span style="color:#323232;">(last_y) </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#0086b3;">1
</span><span style="color:#323232;">    area_x2 </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#62a35c;">sum</span><span style="color:#323232;">((points[i][</span><span style="color:#0086b3;">1</span><span style="color:#323232;">] </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">points[(i</span><span style="font-weight:bold;color:#a71d5d;">+</span><span style="color:#0086b3;">1</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">% </span><span style="color:#62a35c;">len</span><span style="color:#323232;">(points)][</span><span style="color:#0086b3;">1</span><span style="color:#323232;">]) </span><span style="font-weight:bold;color:#a71d5d;">*
</span><span style="color:#323232;">                  (points[i][</span><span style="color:#0086b3;">0</span><span style="color:#323232;">] </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#323232;">points[(i</span><span style="font-weight:bold;color:#a71d5d;">+</span><span style="color:#0086b3;">1</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">% </span><span style="color:#62a35c;">len</span><span style="color:#323232;">(points)][</span><span style="color:#0086b3;">0</span><span style="color:#323232;">])
</span><span style="color:#323232;">                  </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">i </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#62a35c;">range</span><span style="color:#323232;">(</span><span style="color:#62a35c;">len</span><span style="color:#323232;">(points)))
</span><span style="color:#323232;">    interior_integer_points </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">(area_x2 </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#323232;">perimeter_integer_points) </span><span style="font-weight:bold;color:#a71d5d;">// </span><span style="color:#0086b3;">2 </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#0086b3;">1
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">interior_integer_points </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">perimeter_integer_points
</span>

LeixB, 5 months ago

Haskell


<span style="color:#323232;">import Data.ByteString.Char8 (unpack)
</span><span style="color:#323232;">import Data.Char (isDigit, isHexDigit)
</span><span style="color:#323232;">import Relude
</span><span style="color:#323232;">import qualified Relude.Unsafe as Unsafe
</span><span style="color:#323232;">import Text.ParserCombinators.ReadP
</span><span style="color:#323232;">
</span><span style="color:#323232;">data Dir = R | D | L | U deriving (Show, Eq)
</span><span style="color:#323232;">
</span><span style="color:#323232;">type Pos = (Int, Int)
</span><span style="color:#323232;">
</span><span style="color:#323232;">data Action = Action Dir Int deriving (Show, Eq)
</span><span style="color:#323232;">
</span><span style="color:#323232;">parse :: ByteString -> Maybe [(Action, Action)]
</span><span style="color:#323232;">parse = fmap fst . viaNonEmpty last . readP_to_S (sepBy1 parseAction (char 'n') &lt;* char 'n' &lt;* eof) . unpack
</span><span style="color:#323232;">  where
</span><span style="color:#323232;">    parseAction = do
</span><span style="color:#323232;">      dir &lt;- choice [U &lt;$ char 'U', D &lt;$ char 'D', L &lt;$ char 'L', R &lt;$ char 'R'] &lt;* char ' '
</span><span style="color:#323232;">      x &lt;- Unsafe.read &lt;$> munch1 isDigit &lt;* char ' '
</span><span style="color:#323232;">      y &lt;- char '(' *> char '#' *> (Unsafe.read . ("0x" ++) &lt;$> count 5 (satisfy isHexDigit))
</span><span style="color:#323232;">      dir' &lt;- choice [R &lt;$ char '0', D &lt;$ char '1', L &lt;$ char '2', U &lt;$ char '3'] &lt;* char ')'
</span><span style="color:#323232;">      return (Action dir x, Action dir' y)
</span><span style="color:#323232;">
</span><span style="color:#323232;">vertices :: [Action] -> [Pos]
</span><span style="color:#323232;">vertices = scanl' (flip step) origin
</span><span style="color:#323232;">  where
</span><span style="color:#323232;">    step (Action U n) = first $ subtract n
</span><span style="color:#323232;">    step (Action D n) = first (+ n)
</span><span style="color:#323232;">    step (Action L n) = second $ subtract n
</span><span style="color:#323232;">    step (Action R n) = second (+ n)
</span><span style="color:#323232;">
</span><span style="color:#323232;">origin :: Pos
</span><span style="color:#323232;">origin = (0, 0)
</span><span style="color:#323232;">
</span><span style="color:#323232;">area, perimeter, solve :: [Action] -> Int
</span><span style="color:#323232;">area a = (`div` 2) . abs . sum $ zipWith (-) x y
</span><span style="color:#323232;">  where
</span><span style="color:#323232;">    (p, rp) = (origin :) &amp;&amp;&amp; (++ [origin]) $ vertices a
</span><span style="color:#323232;">    x = zipWith (*) (fst &lt;$> p) (snd &lt;$> rp)
</span><span style="color:#323232;">    y = zipWith (*) (snd &lt;$> p) (fst &lt;$> rp)
</span><span style="color:#323232;">perimeter = sum . fmap ((Action _ n) -> n)
</span><span style="color:#323232;">solve = area &amp;&amp;&amp; (`div` 2) . perimeter >>> uncurry (+) >>> succ
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1, part2 :: [(Action, Action)] -> Int
</span><span style="color:#323232;">part1 = solve . fmap fst
</span><span style="color:#323232;">part2 = solve . fmap snd
</span>

lwhjp, 5 months ago

Haskell

Wasn’t able to start on time today, but this was a fun one! Got to apply the two theorems I learned from somebody else’s solution to Day 10.

Solutionimport Data.Char import Data.List readInput :: String -> (Char, Int, String) readInput s = let [d, n, c] = words s in (head d, read n, drop 2 $ init c) boundary :: [(Char, Int)] -> [(Int, Int)] boundary = scanl’ step (0, 0) where step (x, y) (d, n) = let (dx, dy) = case d of ‘U’ -> (0, 1) ‘D’ -> (0, -1) ‘L’ -> (-1, 0) ‘R’ -> (1, 0) in (x + n * dx, y + n * dy) area :: [(Char, Int)] -> Int area steps = let a = – shoelace formula (abs . (quot2) . sum) . (zipWith ((x, y) (x’, y’) -> x * y’ - x’ * y) <*> tail) $ boundary steps in a + 1 + sum (map snd steps)quot 2 – Pick’s theorem part1, part2 :: [(Char, Int, String)] -> Int part1 = area . map ((d, n, _) -> (d, n)) part2 = area . map ((_, _, c) -> decode c) where decode s = (“RDLU” !! digitToInt (last s), read $ “0x” ++ init s) main = do input <- map readInput . lines <$> readFile “input18” print $ part1 input print $ part2 input

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

abclop99, 5 months ago

Rust

CodeRust use std::fs; use std::path::PathBuf; use clap::Parser; #[derive(Parser)] #[command(author, version, about, long_about = None)] struct Cli { /// A file containing the input input_file: PathBuf, #[arg(short, long)] part: Option, } fn main() { // Parse CLI arguments let cli = Cli::parse(); // Read file let input_text = fs::read_to_string(&cli.input_file) .expect(format!(“File ”{}" not found", cli.input_file.display()).as_str()); let (run_part_1, run_part_2) = if let Some(part) = cli.part { match part { 1 => (true, false), 2 => (false, true), _ => unimplemented!(), } } else { (true, true) }; let (it1, it2) = preprocess(&input_text); if run_part_1 { let solution = solve(it1); println!(“Part 1: {solution}”); } if run_part_2 { let solution = solve(it2); println!(“Part 2: {solution}”); } } /// Preprocessing for solving /// Extracts important information from the input /// partspecifies which part to preprocess for. /// Returns a vector for each part containing a direction and amount fn preprocess(input: &str) -> (Vec<((isize, isize), isize)>, Vec<((isize, isize), isize)>) { let it = input.lines().map(|l| { let line: Vec<_> = l.split(’ ').collect(); let direction: char = line[0].chars().nth(0).unwrap(); let amount: isize = line[1].parse().unwrap(); let color: &str = &line[2][2…8]; let direction = match direction { ‘R’ => (1, 0), ‘L’ => (-1, 0), ‘U’ => (0, 1), ‘D’ => (0, -1), _ => unreachable!(), }; ((direction, amount), { let amount: isize = isize::from_str_radix(&color[…5], 16).unwrap(); let direction = match &color[5…] { “0” => (1, 0), “1” => (0, -1), “2” => (-1, 0), “3” => (0, 1), _ => unreachable!(), }; (direction, amount) }) }); let it1 = it.clone().map(|(i1, _i2)| i1).collect(); let it2 = it.map(|(_i1, i2)| i2).collect(); (it1, it2) } /// Finds the area using the shoelace formula fn solve(it: Vec<((isize, isize), isize)>) -> isize { // Get coordinates from it let mut coords: Vec<(isize, isize)> = Vec::with_capacity(it.len() + 1); // Start at (0, 0) coords.push((0, 0)); // Needs to be at both begining and end let (mut x, mut y) = (0, 0); let mut perimeter_length = 0; // Compute and add the coords for (direction, amount) in it { let translation = (direction.0 * amount, direction.1 * amount); x += translation.0; y += translation.1; coords.push((x, y)); perimeter_length += amount; } // Should end where it started assert_eq!(coords.last().unwrap(), &(0, 0)); // Shoelace formula let a = coords .iter() .zip(coords.iter().skip(1)) .map(|((x1, y1), (x2, y2))| (x1 * y2) - (x2 * y1)) .sum::() / 2; // Found by drawing, then trial and error // Shoelace area missing 1/2 of perimeter // Inside and outside corners cancel out except for one a.abs() + perimeter_length / 2 + 1 }

Yay math!- Shoelace Formula

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

Day 18: Lavaduct Lagoon

Megathread guidelines

FAQ

Add comment

Nim

Nim

C++

C

Python

Haskell

Haskell

Rust