🍪 - 2023 DAY 14 SOLUTIONS -🍪

Day 14: Parabolic Reflector Dish

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)
Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

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

🔒 Thread is locked until there’s at least 100 2 star entries on the global leaderboard

Edit: 🔓 Unlocked

Image

Image alternative text

walter_wiggles, 5 months ago

Java

Custom bubble sort ftw!

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

cacheson, 5 months ago

Nim

Getting caught up slowly after spending way too long on day 12. I'll be busy this weekend though, so I'll probably fall further behind.

Part 2 looked daunting at first, as I knew brute-forcing 1 billion iterations wouldn't be practical. I did some premature optimization anyway, pre-calculating north/south and east/west runs in which the round rocks would be able to travel.

At first I figured maybe the rocks would eventually reach a stable configuration, so I added a check to detect if the current iteration matches the previous one. It never triggered, so I dumped some of the grid states and it became obvious that there was a cycle occurring. I probably should have guessed this in advance. The spin cycle is effectively a pseudorandom number generator, and all PRNGs eventually cycle. Good PRNGs have a very long cycle length, but this one isn't very good.

I added a hash table, mapping the state of each iteration to the next one. Once a value is added that already exists in the table as a key, there's a complete cycle. At that point it's just a matter of walking the cycle to determine it's length, and calculating from there.

Day 14, part 1

Day 14, part 2

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

capitalpb, 5 months ago

The first part was simple enough. Adding in the 3 remaining tilt methods for star 2 was also simple enough, and worked just how I figured it would. Tried the brute force solution first, but realized it was going to take a ridiculous amount of time and went back to figure out an algorithm. It was simple enough to guess that it would hit a point where it just repeats infinitely, but actually coding out the math to extrapolate that took way more time than I want to admit. Not sure why I struggled with it so much, but after some pen and paper mathing, I essentially got there. Ended up having to subract 1 from this calculation, and either I’m just missing something or am way too tired, because I don’t know why it’s one less than what I thought it would be, but it works so who am I to complain.

github.com/capitalpb/…/day14.rs


<span style="font-weight:bold;color:#a71d5d;">use crate</span><span style="color:#323232;">::Solver;
</span><span style="color:#323232;">
</span><span style="color:#323232;">#[derive(Debug)]
</span><span style="font-weight:bold;color:#a71d5d;">struct </span><span style="color:#323232;">PlatformMap {
</span><span style="color:#323232;">    tiles: Vec>,
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">impl </span><span style="color:#323232;">PlatformMap {
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">fn </span><span style="font-weight:bold;color:#795da3;">from</span><span style="color:#323232;">(input: </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">str</span><span style="color:#323232;">) -> PlatformMap {
</span><span style="color:#323232;">        PlatformMap {
</span><span style="color:#323232;">            tiles: input.</span><span style="color:#62a35c;">lines</span><span style="color:#323232;">().</span><span style="color:#62a35c;">map</span><span style="color:#323232;">(|line| line.</span><span style="color:#62a35c;">chars</span><span style="color:#323232;">().</span><span style="color:#62a35c;">collect</span><span style="color:#323232;">()).</span><span style="color:#62a35c;">collect</span><span style="color:#323232;">(),
</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;">fn </span><span style="font-weight:bold;color:#795da3;">load</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;self) -> </span><span style="font-weight:bold;color:#a71d5d;">usize </span><span style="color:#323232;">{
</span><span style="color:#323232;">        self.tiles
</span><span style="color:#323232;">            .</span><span style="color:#62a35c;">iter</span><span style="color:#323232;">()
</span><span style="color:#323232;">            .</span><span style="color:#62a35c;">enumerate</span><span style="color:#323232;">()
</span><span style="color:#323232;">            .</span><span style="color:#62a35c;">map</span><span style="color:#323232;">(|(row, tiles)| {
</span><span style="color:#323232;">                tiles.</span><span style="color:#62a35c;">iter</span><span style="color:#323232;">().</span><span style="color:#62a35c;">filter</span><span style="color:#323232;">(|tile| </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;">tile </span><span style="font-weight:bold;color:#a71d5d;">== &</span><span style="color:#323232;">amp;</span><span style="color:#183691;">'O'</span><span style="color:#323232;">).</span><span style="color:#62a35c;">count</span><span style="color:#323232;">() </span><span style="font-weight:bold;color:#a71d5d;">* </span><span style="color:#323232;">(self.tiles.</span><span style="color:#62a35c;">len</span><span style="color:#323232;">() </span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#323232;"> row)
</span><span style="color:#323232;">            })
</span><span style="color:#323232;">            .</span><span style="color:#62a35c;">sum</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;">fn </span><span style="font-weight:bold;color:#795da3;">tilt_north</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">mut </span><span style="color:#323232;">self) {
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> row </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#0086b3;">1</span><span style="font-weight:bold;color:#a71d5d;">..</span><span style="color:#323232;">self.tiles.</span><span style="color:#62a35c;">len</span><span style="color:#323232;">() {
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> col </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#0086b3;">0</span><span style="font-weight:bold;color:#a71d5d;">..</span><span style="color:#323232;">self.tiles[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">].</span><span style="color:#62a35c;">len</span><span style="color:#323232;">() {
</span><span style="color:#323232;">                </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">self.tiles[row][col] </span><span style="font-weight:bold;color:#a71d5d;">!= </span><span style="color:#183691;">'O' </span><span style="color:#323232;">{
</span><span style="color:#323232;">                    </span><span style="font-weight:bold;color:#a71d5d;">continue</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;">let mut</span><span style="color:#323232;"> new_row </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> row;
</span><span style="color:#323232;">                </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> check_row </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">(</span><span style="color:#0086b3;">0</span><span style="font-weight:bold;color:#a71d5d;">..</span><span style="color:#323232;">row).</span><span style="color:#62a35c;">rev</span><span style="color:#323232;">() {
</span><span style="color:#323232;">                    </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">self.tiles[check_row][col] </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#183691;">'.' </span><span style="color:#323232;">{
</span><span style="color:#323232;">                        new_row </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> check_row;
</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;">break</span><span style="color:#323232;">;
</span><span style="color:#323232;">                    }
</span><span style="color:#323232;">                }
</span><span style="color:#323232;">
</span><span style="color:#323232;">                self.tiles[row][col] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#183691;">'.'</span><span style="color:#323232;">;
</span><span style="color:#323232;">                self.tiles[new_row][col] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#183691;">'O'</span><span style="color:#323232;">;
</span><span style="color:#323232;">            }
</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;">fn </span><span style="font-weight:bold;color:#795da3;">tilt_west</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">mut </span><span style="color:#323232;">self) {
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> col </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#0086b3;">1</span><span style="font-weight:bold;color:#a71d5d;">..</span><span style="color:#323232;">self.tiles[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">].</span><span style="color:#62a35c;">len</span><span style="color:#323232;">() {
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> row </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#0086b3;">0</span><span style="font-weight:bold;color:#a71d5d;">..</span><span style="color:#323232;">self.tiles.</span><span style="color:#62a35c;">len</span><span style="color:#323232;">() {
</span><span style="color:#323232;">                </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">self.tiles[row][col] </span><span style="font-weight:bold;color:#a71d5d;">!= </span><span style="color:#183691;">'O' </span><span style="color:#323232;">{
</span><span style="color:#323232;">                    </span><span style="font-weight:bold;color:#a71d5d;">continue</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;">let mut</span><span style="color:#323232;"> new_col </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> col;
</span><span style="color:#323232;">                </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> check_col </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">(</span><span style="color:#0086b3;">0</span><span style="font-weight:bold;color:#a71d5d;">..</span><span style="color:#323232;">col).</span><span style="color:#62a35c;">rev</span><span style="color:#323232;">() {
</span><span style="color:#323232;">                    </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">self.tiles[row][check_col] </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#183691;">'.' </span><span style="color:#323232;">{
</span><span style="color:#323232;">                        new_col </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> check_col;
</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;">break</span><span style="color:#323232;">;
</span><span style="color:#323232;">                    }
</span><span style="color:#323232;">                }
</span><span style="color:#323232;">
</span><span style="color:#323232;">                self.tiles[row][col] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#183691;">'.'</span><span style="color:#323232;">;
</span><span style="color:#323232;">                self.tiles[row][new_col] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#183691;">'O'</span><span style="color:#323232;">;
</span><span style="color:#323232;">            }
</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;">fn </span><span style="font-weight:bold;color:#795da3;">tilt_south</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">mut </span><span style="color:#323232;">self) {
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> row </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">(</span><span style="color:#0086b3;">0</span><span style="font-weight:bold;color:#a71d5d;">..</span><span style="color:#323232;">(self.tiles.</span><span style="color:#62a35c;">len</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:#62a35c;">rev</span><span style="color:#323232;">() {
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> col </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#0086b3;">0</span><span style="font-weight:bold;color:#a71d5d;">..</span><span style="color:#323232;">self.tiles[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">].</span><span style="color:#62a35c;">len</span><span style="color:#323232;">() {
</span><span style="color:#323232;">                </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">self.tiles[row][col] </span><span style="font-weight:bold;color:#a71d5d;">!= </span><span style="color:#183691;">'O' </span><span style="color:#323232;">{
</span><span style="color:#323232;">                    </span><span style="font-weight:bold;color:#a71d5d;">continue</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;">let mut</span><span style="color:#323232;"> new_row </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> row;
</span><span style="color:#323232;">                </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> check_row </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">(row </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;">self.tiles.</span><span style="color:#62a35c;">len</span><span style="color:#323232;">() {
</span><span style="color:#323232;">                    </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">self.tiles[check_row][col] </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#183691;">'.' </span><span style="color:#323232;">{
</span><span style="color:#323232;">                        new_row </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> check_row;
</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;">break</span><span style="color:#323232;">;
</span><span style="color:#323232;">                    }
</span><span style="color:#323232;">                }
</span><span style="color:#323232;">
</span><span style="color:#323232;">                self.tiles[row][col] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#183691;">'.'</span><span style="color:#323232;">;
</span><span style="color:#323232;">                self.tiles[new_row][col] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#183691;">'O'</span><span style="color:#323232;">;
</span><span style="color:#323232;">            }
</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;">fn </span><span style="font-weight:bold;color:#795da3;">tilt_east</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">mut </span><span style="color:#323232;">self) {
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> col </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">(</span><span style="color:#0086b3;">0</span><span style="font-weight:bold;color:#a71d5d;">..</span><span style="color:#323232;">(self.tiles[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">].</span><span style="color:#62a35c;">len</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:#62a35c;">rev</span><span style="color:#323232;">() {
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> row </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#0086b3;">0</span><span style="font-weight:bold;color:#a71d5d;">..</span><span style="color:#323232;">self.tiles.</span><span style="color:#62a35c;">len</span><span style="color:#323232;">() {
</span><span style="color:#323232;">                </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">self.tiles[row][col] </span><span style="font-weight:bold;color:#a71d5d;">!= </span><span style="color:#183691;">'O' </span><span style="color:#323232;">{
</span><span style="color:#323232;">                    </span><span style="font-weight:bold;color:#a71d5d;">continue</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;">let mut</span><span style="color:#323232;"> new_col </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> col;
</span><span style="color:#323232;">                </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> check_col </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">(col </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;">self.tiles[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">].</span><span style="color:#62a35c;">len</span><span style="color:#323232;">() {
</span><span style="color:#323232;">                    </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">self.tiles[row][check_col] </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#183691;">'.' </span><span style="color:#323232;">{
</span><span style="color:#323232;">                        new_col </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> check_col;
</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;">break</span><span style="color:#323232;">;
</span><span style="color:#323232;">                    }
</span><span style="color:#323232;">                }
</span><span style="color:#323232;">
</span><span style="color:#323232;">                self.tiles[row][col] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#183691;">'.'</span><span style="color:#323232;">;
</span><span style="color:#323232;">                self.tiles[row][new_col] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#183691;">'O'</span><span style="color:#323232;">;
</span><span style="color:#323232;">            }
</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;">pub struct </span><span style="color:#323232;">Day14;
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">impl </span><span style="color:#323232;">Solver </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">Day14 {
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">fn </span><span style="font-weight:bold;color:#795da3;">star_one</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;self, input: </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">str</span><span style="color:#323232;">) -> String {
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">let mut</span><span style="color:#323232;"> platform_map </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">PlatformMap::from(input);
</span><span style="color:#323232;">        platform_map.</span><span style="color:#62a35c;">tilt_north</span><span style="color:#323232;">();
</span><span style="color:#323232;">        platform_map.</span><span style="color:#62a35c;">load</span><span style="color:#323232;">().</span><span style="color:#62a35c;">to_string</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;">fn </span><span style="font-weight:bold;color:#795da3;">star_two</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;self, input: </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">str</span><span style="color:#323232;">) -> String {
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">let mut</span><span style="color:#323232;"> platform_map </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">PlatformMap::from(input);
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">let mut</span><span style="color:#323232;"> map_history: </span><span style="color:#0086b3;">Vec</span><span style="font-weight:bold;color:#a71d5d;">>> = </span><span style="color:#323232;">vec![];
</span><span style="color:#323232;">
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> index </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#0086b3;">0</span><span style="font-weight:bold;color:#a71d5d;">..</span><span style="color:#0086b3;">1_000_000_000 </span><span style="color:#323232;">{
</span><span style="color:#323232;">            platform_map.</span><span style="color:#62a35c;">tilt_north</span><span style="color:#323232;">();
</span><span style="color:#323232;">            platform_map.</span><span style="color:#62a35c;">tilt_west</span><span style="color:#323232;">();
</span><span style="color:#323232;">            platform_map.</span><span style="color:#62a35c;">tilt_south</span><span style="color:#323232;">();
</span><span style="color:#323232;">            platform_map.</span><span style="color:#62a35c;">tilt_east</span><span style="color:#323232;">();
</span><span style="color:#323232;">
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">if let </span><span style="color:#0086b3;">Some</span><span style="color:#323232;">(repeat_start) </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> map_history
</span><span style="color:#323232;">                .</span><span style="color:#62a35c;">iter</span><span style="color:#323232;">()
</span><span style="color:#323232;">                .</span><span style="color:#62a35c;">position</span><span style="color:#323232;">(|tiles| tiles </span><span style="font-weight:bold;color:#a71d5d;">== &</span><span style="color:#323232;">amp;platform_map.tiles)
</span><span style="color:#323232;">            {
</span><span style="color:#323232;">                </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> repeat_length </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> index </span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#323232;"> repeat_start;
</span><span style="color:#323232;">                </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> delta </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">(</span><span style="color:#0086b3;">1_000_000_000 </span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#323232;"> repeat_start) </span><span style="font-weight:bold;color:#a71d5d;">%</span><span style="color:#323232;"> repeat_length;
</span><span style="color:#323232;">                </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> solution_index </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> repeat_start </span><span style="font-weight:bold;color:#a71d5d;">+</span><span style="color:#323232;"> delta </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="font-weight:bold;color:#a71d5d;">return</span><span style="color:#323232;"> PlatformMap {
</span><span style="color:#323232;">                    tiles: map_history[solution_index].</span><span style="color:#62a35c;">clone</span><span style="color:#323232;">(),
</span><span style="color:#323232;">                }
</span><span style="color:#323232;">                .</span><span style="color:#62a35c;">load</span><span style="color:#323232;">()
</span><span style="color:#323232;">                .</span><span style="color:#62a35c;">to_string</span><span style="color:#323232;">();
</span><span style="color:#323232;">            }
</span><span style="color:#323232;">
</span><span style="color:#323232;">            map_history.</span><span style="color:#62a35c;">push</span><span style="color:#323232;">(platform_map.tiles.</span><span style="color:#62a35c;">clone</span><span style="color:#323232;">());
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">
</span><span style="color:#323232;">        platform_map.</span><span style="color:#62a35c;">load</span><span style="color:#323232;">().</span><span style="color:#62a35c;">to_string</span><span style="color:#323232;">()
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">}
</span>

SteveDinn, 5 months ago

C#

Obviously, you can’t calculate 1 billion iterations, so the states must repeat after a while. My solution got to 154 different states and then started looping from state 92 to state 154 (63 steps). From there we can find the index in the state cache that the final state would be, and calculate the supported load from that.

code.dinn.ca/stevedinn/AdventOfCode/…/Program.cs

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

janAkali, 5 months ago (edited 5 months ago)

Nim

Part 1: I made the only procedure - to roll rocks to the right. First, I rotate input 90 degrees clockwise. Then roll rocks in each row. To roll a row of rocks - I scan from right to left, until I find a rock and try to find the most right available position for it. Not the best approach, but not the worst either.
Part 2: To do a cycle I use the same principle as part 1: (rotate clockwise + roll rocks right) x 4 = 1 cycle. A trillion cycles would obviously take too long. Instead, I cycle the input and add every configuration to a hashTable and once we reach a full copy of one of previous cycles - it means we’re in a loop. And then finding out in what configuration rocks will be after trillion steps is easy with use of a modulo.

Total Runtime: 60ms relatively slow today =(
Puzzle rating: 7/10
Code: <a href="">day_14/solution.nim</a>

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

mykl, 5 months ago (edited 5 months ago)

Dart

Big lump of code. I built a general slide function which ended up being tricksy in order to visit rocks in the correct order, but it works.


<span style="color:#323232;">int hash(List> rocks) =>
</span><span style="color:#323232;">    (rocks.map((e) => e.join('')).join('n')).hashCode;
</span><span style="color:#323232;">
</span><span style="color:#323232;">/// Slide rocks in the given (vert, horz) direction.
</span><span style="color:#323232;">List> slide(List> rocks, (int, int) dir) {
</span><span style="color:#323232;">  // Work out in which order to check rocks for most efficient movement.
</span><span style="color:#323232;">  var rrange = 0.to(rocks.length);
</span><span style="color:#323232;">  var crange = 0.to(rocks.first.length);
</span><span style="color:#323232;">  var starts = [
</span><span style="color:#323232;">    for (var r in (dir.$1 == 1) ? rrange.reversed : rrange)
</span><span style="color:#323232;">      for (var c in ((dir.$2 == 1) ? crange.reversed : crange)
</span><span style="color:#323232;">          .where((c) => rocks[r][c] == 'O'))
</span><span style="color:#323232;">        (r, c)
</span><span style="color:#323232;">  ];
</span><span style="color:#323232;">
</span><span style="color:#323232;">  for (var (r, c) in starts) {
</span><span style="color:#323232;">    var dest = (r, c);
</span><span style="color:#323232;">    var next = (dest.$1 + dir.$1, dest.$2 + dir.$2);
</span><span style="color:#323232;">    while (next.$1.between(0, rocks.length - 1) &amp;&amp;
</span><span style="color:#323232;">        next.$2.between(0, rocks.first.length - 1) &amp;&amp;
</span><span style="color:#323232;">        rocks[next.$1][next.$2] == '.') {
</span><span style="color:#323232;">      dest = next;
</span><span style="color:#323232;">      next = (dest.$1 + dir.$1, dest.$2 + dir.$2);
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">    if (dest != (r, c)) {
</span><span style="color:#323232;">      rocks[r][c] = '.';
</span><span style="color:#323232;">      rocks[dest.$1][dest.$2] = 'O';
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">  return rocks;
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">List> oneCycle(List> rocks) =>
</span><span style="color:#323232;">    [(-1, 0), (0, -1), (1, 0), (0, 1)].fold(rocks, (s, t) => slide(s, t));
</span><span style="color:#323232;">
</span><span style="color:#323232;">spin(List> rocks, {int target = 1}) {
</span><span style="color:#323232;">  var cycle = 1;
</span><span style="color:#323232;">  var seen = {};
</span><span style="color:#323232;">  while (cycle != target) {
</span><span style="color:#323232;">    rocks = oneCycle(rocks);
</span><span style="color:#323232;">    var h = hash(rocks);
</span><span style="color:#323232;">    if (seen.containsKey(h)) {
</span><span style="color:#323232;">      var diff = cycle - seen[h]!;
</span><span style="color:#323232;">      var count = (target - cycle) ~/ diff;
</span><span style="color:#323232;">      cycle += count * diff;
</span><span style="color:#323232;">      seen = {};
</span><span style="color:#323232;">    } else {
</span><span style="color:#323232;">      seen[h] = cycle;
</span><span style="color:#323232;">      cycle += 1;
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">  return weighting(rocks);
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">parse(List lines) => lines.map((e) => e.split('').toList()).toList();
</span><span style="color:#323232;">
</span><span style="color:#323232;">weighting(List> rocks) => 0
</span><span style="color:#323232;">    .to(rocks.length)
</span><span style="color:#323232;">    .map((r) => rocks[r].count((e) => e == 'O') * (rocks.length - r))
</span><span style="color:#323232;">    .sum;
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1(List lines) => weighting(slide(parse(lines), (-1, 0)));
</span><span style="color:#323232;">
</span><span style="color:#323232;">part2(List lines) => spin(parse(lines), target: 1000000000);
</span>

Gobbel2000, 5 months ago

Rust

The trick for part 2 is obviously to check when the pattern repeats itself and then jump ahead to 1000000000.

My code allocates an entire new grid for every tilt, some in-place procedure would probably be more efficient in terms of memory, but this seems good enough.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

sjmulder, 5 months ago (edited 5 months ago)

C

Chose not to do transposing/flipping or fancy indexing so it’s rather verbose, but it’s also clear and (I think) fast. I also tried to limit the number of search steps by keeping two cursors in the current row/col, rather than shooting a ray every time.

Part 2 immediately reminded me of that Tetris puzzle from day 22 last year so I knew how to find and apply the solution. State hashes are stored in an array and (inefficiently) scanned until a loop is found.

One direction of the shift function:


<span style="font-style:italic;color:#969896;">/*
</span><span style="font-style:italic;color:#969896;"> * Walk two cursors i and j through each column x. The i cursor
</span><span style="font-style:italic;color:#969896;"> * looks for the first . where an O can go. The j cursor looks
</span><span style="font-style:italic;color:#969896;"> * ahead for O's. When j finds a # we start again beyond it.
</span><span style="font-style:italic;color:#969896;"> */
</span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">(x</span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#0086b3;">0</span><span style="color:#323232;">; x</span><span style="font-weight:bold;color:#a71d5d;"><</span><span style="color:#323232;">w; x</span><span style="font-weight:bold;color:#a71d5d;">++</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;">=</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, j</span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#0086b3;">1</span><span style="color:#323232;">; i</span><span style="font-weight:bold;color:#a71d5d;"><</span><span style="color:#323232;">h </span><span style="font-weight:bold;color:#a71d5d;">&&</span><span style="color:#323232;"> j</span><span style="font-weight:bold;color:#a71d5d;"><</span><span style="color:#323232;">h; )
</span><span style="color:#323232;">	</span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">(j </span><span style="font-weight:bold;color:#a71d5d;"><=</span><span style="color:#323232;"> i) j </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> i</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;">else if </span><span style="color:#323232;">(g[j][x] </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#183691;">'#'</span><span style="color:#323232;">) i </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> j</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;">else if </span><span style="color:#323232;">(g[j][x] </span><span style="font-weight:bold;color:#a71d5d;">!= </span><span style="color:#183691;">'O'</span><span style="color:#323232;">) j</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;">else if </span><span style="color:#323232;">(g[i][x] </span><span style="font-weight:bold;color:#a71d5d;">!= </span><span style="color:#183691;">'.'</span><span style="color:#323232;">) i</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;">else </span><span style="color:#323232;">{ g[i</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:#183691;">'O'</span><span style="color:#323232;">; g[j</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:#183691;">'.'</span><span style="color:#323232;">; vis14_emit(); }
</span>

The main loop:


<span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">(nleft </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;">1000</span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#0086b3;">1000</span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#0086b3;">1000</span><span style="color:#323232;">; nleft; nleft</span><span style="font-weight:bold;color:#a71d5d;">--</span><span style="color:#323232;">) {
</span><span style="color:#323232;">	shift_all();
</span><span style="color:#323232;">
</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;">!</span><span style="color:#323232;">period) {
</span><span style="color:#323232;">		</span><span style="color:#62a35c;">assert</span><span style="color:#323232;">(nhist </span><span style="font-weight:bold;color:#a71d5d;">< </span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">int</span><span style="color:#323232;">)LEN(hist));		
</span><span style="color:#323232;">		hist[nhist</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;">hash_grid();
</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;">=</span><span style="color:#0086b3;">0</span><span style="color:#323232;">; i</span><span style="font-weight:bold;color:#a71d5d;"><</span><span style="color:#323232;">nhist</span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#0086b3;">1</span><span style="color:#323232;">; i</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;">if </span><span style="color:#323232;">(hist[i] </span><span style="font-weight:bold;color:#a71d5d;">==</span><span style="color:#323232;"> hist[nhist</span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#0086b3;">1</span><span style="color:#323232;">]) {
</span><span style="color:#323232;">				period </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> nhist</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;"> i;
</span><span style="color:#323232;">				nleft </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> nleft </span><span style="font-weight:bold;color:#a71d5d;">%</span><span style="color:#323232;"> period;
</span><span style="color:#323232;">				</span><span style="font-weight:bold;color:#a71d5d;">break</span><span style="color:#323232;">;
</span><span style="color:#323232;">			}
</span><span style="color:#323232;">	}
</span><span style="color:#323232;">}
</span>

Full solution: github.com/sjmulder/aoc/blob/master/…/day14.c

LeixB, 5 months ago

Haskell

Managed to do part1 in one line using ByteString operations:


<span style="color:#323232;">import Control.Monad
</span><span style="color:#323232;">import qualified Data.ByteString.Char8 as BS
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1 :: IO Int
</span><span style="color:#323232;">part1 =
</span><span style="color:#323232;">  sum
</span><span style="color:#323232;">    . ( BS.transpose . BS.split 'n'
</span><span style="color:#323232;">          >=> fmap succ
</span><span style="color:#323232;">          . BS.elemIndices 'O' . BS.reverse . BS.intercalate "#"
</span><span style="color:#323232;">          . fmap (BS.reverse . BS.sort) . BS.split '#'
</span><span style="color:#323232;">      )
</span><span style="color:#323232;">    &lt;$> BS.readFile "inp"
</span>

Part 2


<span style="color:#323232;">{-# LANGUAGE NumericUnderscores #-}
</span><span style="color:#323232;">
</span><span style="color:#323232;">import qualified Data.ByteString.Char8 as BS
</span><span style="color:#323232;">import qualified Data.Map as M
</span><span style="color:#323232;">import Relude
</span><span style="color:#323232;">
</span><span style="color:#323232;">type Problem = [ByteString]
</span><span style="color:#323232;">
</span><span style="color:#323232;">-- We apply rotation so that north is to the right, this makes
</span><span style="color:#323232;">-- all computations easier since we can just sort the rows.
</span><span style="color:#323232;">parse :: ByteString -> Problem
</span><span style="color:#323232;">parse = rotate . BS.split 'n'
</span><span style="color:#323232;">
</span><span style="color:#323232;">count :: Problem -> [[Int]]
</span><span style="color:#323232;">count = fmap (fmap succ . BS.elemIndices 'O')
</span><span style="color:#323232;">
</span><span style="color:#323232;">rotate, move, rotMov, doCycle :: Problem -> Problem
</span><span style="color:#323232;">rotate = fmap BS.reverse . BS.transpose
</span><span style="color:#323232;">move = fmap (BS.intercalate "#" . fmap BS.sort . BS.split '#')
</span><span style="color:#323232;">rotMov = rotate . move
</span><span style="color:#323232;">doCycle = rotMov . rotMov . rotMov . rotMov
</span><span style="color:#323232;">
</span><span style="color:#323232;">doNcycles :: Int -> Problem -> Problem
</span><span style="color:#323232;">doNcycles n = foldl' (.) id (replicate n doCycle)
</span><span style="color:#323232;">
</span><span style="color:#323232;">findCycle :: Problem -> (Int, Int)
</span><span style="color:#323232;">findCycle = go 0 M.empty
</span><span style="color:#323232;">  where
</span><span style="color:#323232;">    go :: Int -> M.Map Problem Int -> Problem -> (Int, Int)
</span><span style="color:#323232;">    go n m p =
</span><span style="color:#323232;">      let p' = doCycle p
</span><span style="color:#323232;">       in case M.lookup p' m of
</span><span style="color:#323232;">            Just n' -> (n', n + 1)
</span><span style="color:#323232;">            Nothing -> go (n + 1) (M.insert p' n m) p'
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1, part2 :: ByteString -> Int
</span><span style="color:#323232;">part1 = sum . join . count . move . parse
</span><span style="color:#323232;">part2 input =
</span><span style="color:#323232;">  let n = 1_000_000_000
</span><span style="color:#323232;">      p = parse input
</span><span style="color:#323232;">      (s, r) = findCycle p
</span><span style="color:#323232;">      numRots = s + ((n - s) `mod` (r - s - 1))
</span><span style="color:#323232;">   in sum . join . count $ doNcycles numRots p
</span>

cvttsd2si, 5 months ago

Scala3


<span style="font-weight:bold;color:#a71d5d;">type </span><span style="color:#323232;">Grid </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="font-weight:bold;color:#a71d5d;">Char</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:#795da3;">tiltUp</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">Grid</span><span style="color:#323232;">): </span><span style="color:#0086b3;">Grid </span><span style="font-weight:bold;color:#a71d5d;">= 
</span><span style="color:#323232;">    @tailrec </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">go</span><span style="color:#323232;">(c: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="font-weight:bold;color:#a71d5d;">Char</span><span style="color:#323232;">], acc: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="font-weight:bold;color:#a71d5d;">Char</span><span style="color:#323232;">]): </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="font-weight:bold;color:#a71d5d;">Char</span><span style="color:#323232;">] </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">shifted</span><span style="color:#323232;">(c: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="font-weight:bold;color:#a71d5d;">Char</span><span style="color:#323232;">]) </span><span style="font-weight:bold;color:#a71d5d;">= 
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">val</span><span style="color:#323232;"> (h, t) </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> c.splitAt(c.count(_ == </span><span style="color:#0086b3;">'O'</span><span style="color:#323232;">))
</span><span style="color:#323232;">            h.map(_ </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">'O'</span><span style="color:#323232;">) ++ t.map(_ </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">'.'</span><span style="color:#323232;">) ++ acc
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">val </span><span style="color:#323232;">d </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> c.indexOf(</span><span style="color:#0086b3;">'#'</span><span style="color:#323232;">)
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if</span><span style="color:#323232;"> d == -</span><span style="color:#0086b3;">1</span><span style="color:#323232;"> then shifted(c) </span><span style="font-weight:bold;color:#a71d5d;">else</span><span style="color:#323232;"> go(c.slice(d + </span><span style="color:#0086b3;">1</span><span style="color:#323232;">, c.size), </span><span style="color:#0086b3;">'#'</span><span style="color:#323232;">::shifted(c.slice(</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, d)))
</span><span style="color:#323232;">        
</span><span style="color:#323232;">    a.map(go(_, </span><span style="color:#0086b3;">List</span><span style="color:#323232;">()).reverse)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">weight</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">Grid</span><span style="color:#323232;">): </span><span style="font-weight:bold;color:#a71d5d;">Long =</span><span style="color:#323232;"> a.map(d </span><span style="font-weight:bold;color:#a71d5d;">=></span><span style="color:#323232;"> d.zipWithIndex.filter((c, _) </span><span style="font-weight:bold;color:#a71d5d;">=></span><span style="color:#323232;"> c == </span><span style="color:#0086b3;">'O'</span><span style="color:#323232;">).map(</span><span style="color:#0086b3;">1</span><span style="color:#323232;"> + _._2).sum).sum
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">rotateNeg90</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">Grid</span><span style="color:#323232;">): </span><span style="color:#0086b3;">Grid </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> a.reverse.transpose
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">runCycle </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Seq</span><span style="color:#323232;">.fill(</span><span style="color:#0086b3;">4</span><span style="color:#323232;">)(tiltUp andThen rotateNeg90).reduceLeft(_ andThen _)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">stateAt</span><span style="color:#323232;">(target: </span><span style="font-weight:bold;color:#a71d5d;">Long</span><span style="color:#323232;">, a: </span><span style="color:#0086b3;">Grid</span><span style="color:#323232;">): </span><span style="color:#0086b3;">Grid </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">    @tailrec </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">go</span><span style="color:#323232;">(cycle: </span><span style="font-weight:bold;color:#a71d5d;">Int</span><span style="color:#323232;">, state: </span><span style="color:#0086b3;">Grid</span><span style="color:#323232;">, seen: </span><span style="color:#0086b3;">Map</span><span style="color:#323232;">[</span><span style="color:#0086b3;">Grid</span><span style="color:#323232;">, </span><span style="font-weight:bold;color:#a71d5d;">Int</span><span style="color:#323232;">]): </span><span style="color:#0086b3;">Grid </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">        seen.get(state) </span><span style="font-weight:bold;color:#a71d5d;">match
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">case </span><span style="color:#0086b3;">Some</span><span style="color:#323232;">(i) </span><span style="font-weight:bold;color:#a71d5d;">=> if </span><span style="color:#323232;">(target - cycle) % (cycle - i) == </span><span style="color:#0086b3;">0</span><span style="color:#323232;"> then state </span><span style="font-weight:bold;color:#a71d5d;">else</span><span style="color:#323232;"> go(cycle + </span><span style="color:#0086b3;">1</span><span style="color:#323232;">, runCycle(state), seen)
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">case </span><span style="color:#0086b3;">None </span><span style="font-weight:bold;color:#a71d5d;">=></span><span style="color:#323232;"> go(cycle + </span><span style="color:#0086b3;">1</span><span style="color:#323232;">, runCycle(state), seen + (state -> cycle))
</span><span style="color:#323232;">    
</span><span style="color:#323232;">    go(</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, a, </span><span style="color:#0086b3;">Map</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:#795da3;">toColMajorGrid</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">String</span><span style="color:#323232;">]): </span><span style="color:#0086b3;">Grid </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> rotateNeg90(a.map(_.toList))
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">task1</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">String</span><span style="color:#323232;">]): </span><span style="font-weight:bold;color:#a71d5d;">Long =</span><span style="color:#323232;"> weight(tiltUp(toColMajorGrid(a)))
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">task2</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">String</span><span style="color:#323232;">]): </span><span style="font-weight:bold;color:#a71d5d;">Long =</span><span style="color:#323232;"> weight(stateAt(1_000_000_000, toColMajorGrid(a)))
</span>

hades, 5 months ago

Python

Also on Github


<span style="color:#323232;">import numpy as np
</span><span style="color:#323232;">
</span><span style="color:#323232;">from .solver import Solver
</span><span style="color:#323232;">
</span><span style="color:#323232;">
</span><span style="color:#323232;">def _tilt(row: list[int], reverse: bool = False) -> list[int]:
</span><span style="color:#323232;">  res = row[::-1] if reverse else row[:]
</span><span style="color:#323232;">  rock_x = 0
</span><span style="color:#323232;">  for x, item in enumerate(res):
</span><span style="color:#323232;">    if item == 1:
</span><span style="color:#323232;">      rock_x = x + 1
</span><span style="color:#323232;">    if item == 2:
</span><span style="color:#323232;">      if rock_x &lt; x:
</span><span style="color:#323232;">        res[rock_x] = 2
</span><span style="color:#323232;">        res[x] = 0
</span><span style="color:#323232;">      rock_x += 1
</span><span style="color:#323232;">  return res[::-1] if reverse else res
</span><span style="color:#323232;">
</span><span style="color:#323232;">class Day14(Solver):
</span><span style="color:#323232;">  data: np.ndarray
</span><span style="color:#323232;">
</span><span style="color:#323232;">  def __init__(self):
</span><span style="color:#323232;">    super().__init__(14)
</span><span style="color:#323232;">
</span><span style="color:#323232;">  def presolve(self, input: str):
</span><span style="color:#323232;">    lines = input.splitlines()
</span><span style="color:#323232;">    self.data = np.zeros((len(lines), len(lines[0])), dtype=np.int8)
</span><span style="color:#323232;">    for x, line in enumerate(lines):
</span><span style="color:#323232;">      for y, char in enumerate(line):
</span><span style="color:#323232;">        if char == '#':
</span><span style="color:#323232;">          self.data[x, y] = 1
</span><span style="color:#323232;">        elif char == 'O':
</span><span style="color:#323232;">          self.data[x, y] = 2
</span><span style="color:#323232;">
</span><span style="color:#323232;">  def solve_first_star(self) -> int:
</span><span style="color:#323232;">    for y in range(self.data.shape[1]):
</span><span style="color:#323232;">      self.data[:, y] = _tilt(self.data[:, y].tolist())
</span><span style="color:#323232;">    return sum((self.data.shape[0] - x) * (self.data[x] == 2).sum() for x in range(self.data.shape[0]))
</span><span style="color:#323232;">
</span><span style="color:#323232;">  def solve_second_star(self) -> int:
</span><span style="color:#323232;">    seen = {}
</span><span style="color:#323232;">    order = []
</span><span style="color:#323232;">    for i in range(1_000_000_000):
</span><span style="color:#323232;">      order += [self.data.copy()]
</span><span style="color:#323232;">      s = self.data.tobytes()
</span><span style="color:#323232;">      if s in seen:
</span><span style="color:#323232;">        loop_size = i - seen[s]
</span><span style="color:#323232;">        remainder = (1_000_000_000 - i) % loop_size
</span><span style="color:#323232;">        self.data = order[seen[s] + remainder]
</span><span style="color:#323232;">        break
</span><span style="color:#323232;">      seen[s] = i
</span><span style="color:#323232;">      for y in range(self.data.shape[1]):
</span><span style="color:#323232;">        self.data[:, y] = _tilt(self.data[:, y].tolist())
</span><span style="color:#323232;">      for x in range(self.data.shape[0]):
</span><span style="color:#323232;">        self.data[x, :] = _tilt(self.data[x, :].tolist())
</span><span style="color:#323232;">      for y in range(self.data.shape[1]):
</span><span style="color:#323232;">        self.data[:, y] = _tilt(self.data[:, y].tolist(), reverse=True)
</span><span style="color:#323232;">      for x in range(self.data.shape[0]):
</span><span style="color:#323232;">        self.data[x, :] = _tilt(self.data[x, :].tolist(), reverse=True)
</span><span style="color:#323232;">    return sum((self.data.shape[0] - x) * (self.data[x] == 2).sum() for x in range(self.data.shape[0]))
</span>

33.938 line-seconds (ranks 3rd hardest after days 8 and 12 so far).

Barsukis, 5 months ago

If you use numpy you could just take advantage of np.rot90 function to do the tilting for you:)

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

hades, 5 months ago

Oh yeah, great idea, thanks!

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

lwhjp, 5 months ago

Haskell

A little slow (1.106s on my machine), but list operations made this really easy to write. I expect somebody more familiar with Haskell than me will be able to come up with a more elegant solution.

Nevertheless, 59th on the global leaderboard today! Woo!

Solutionimport Data.List import qualified Data.Map.Strict as Map import Data.Semigroup rotateL, rotateR, tiltW :: Endo [[Char]] rotateL = Endo $ reverse . transpose rotateR = Endo $ map reverse . transpose tiltW = Endo $ map tiltRow where tiltRow xs = let (a, b) = break (== ‘#’) xs (os, ds) = partition (== ‘O’) a rest = case b of (‘#’ : b’) -> ‘#’ : tiltRow b’ [] -> [] in os ++ ds ++ rest load rows = sum $ map rowLoad rows where rowLoad = sum . map (length rows -) . elemIndices ‘O’ lookupCycle xs i = let (o, p) = findCycle 0 Map.empty xs in xs !! if i < o then i else (i - o) rem p + o where findCycle i seen (x : xs) = case seen Map.!? x of Just j -> (j, i - j) Nothing -> findCycle (i + 1) (Map.insert x i seen) xs main = do input <- lines <$> readFile “input14” print . load . appEndo (tiltW <> rotateL) $ input print $ load $ lookupCycle (iterate (appEndo $ stimes 4 (rotateR <> tiltW)) $ appEndo rotateL input) 1000000000

42.028 line-seconds

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

janAkali, 5 months ago

What’s a line-second? Never heard/seen this term before.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

Deebster, 5 months ago

There was a post about it a few days ago: lemmy.sdf.org/post/9116867

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

Day 14: Parabolic Reflector Dish

Megathread guidelines

FAQ

Add comment

Java

Nim

C#

Nim

Dart

Rust

C

Haskell

Part 2

Scala3

Python

Haskell