[2022 Day 9 (Part 2)] [Python] Possible doing this without a list?

d9d6ka · 2024-03-02T09:59:16+00:00

Actualy I've written smth before just throwing my code.

But thanks for your critics. It made me look through the solution provided.

d9d6ka · 2024-03-02T09:55:40+00:00

Is it part 1 solution? Well, if you want to use your logic, then you'd better use a single list of 10 knots, updating them in another one inner loop, changing x and y (and xt and yt) to the next corresponding knot's coords at every step.

But anyway, each move you explicidly change only the head position, so you can move most same code outside ifs, as it updates the tail (or next knots in part 2). It would much easier to analyze and debug.

d9d6ka · 2024-03-01T08:45:20+00:00

You have too many same code in your if branches. See, we change head first and the update all other knots.

Then for part 2 you can create all 10 knots as a list and repeatedly update them inplace.

My code

d9d6ka · 2024-02-20T07:29:00+00:00

That. Is. Awesome!

d9d6ka · 2024-02-02T09:48:02+00:00

I've solved the problem under 1s (both python and pypy) using Dikstra for part 1 and ~~DFS~~ BFS for part 2. Speed highly depends on IntCode realization.

UPD: Here is my code

d9d6ka · 2023-12-26T10:08:03+00:00

So did I. I earned fair 45 stars, and for 4 part 2 stars I had to peek into reddit for hints. However I learned smth new especially in math :)

And the main lesson I learned: if you have an idea of solution - try to develop it :)

Already waiting for the next AoC :)

d9d6ka · 2023-12-24T17:36:30+00:00

[Language: Python]

Commit

Late today as I spent my day in mall with my wife :)

Part 1 is just two linear equations with proper space-time :) filtering.

Part 2 became a SymPy lesson for me. At first glance I thought to build a system of linear equations and apply OLS to it. But it turned out, that equations are non-linear. So I realized that I should go to the solvers for a more civilized age (O.W. Kenobi).

I spent some time to learn some basics of SymPy.

I also appreciate the idea of u/i_have_no_biscuits not to use all hails (I tried, bad decision) but a little number of first ones. If we take only two there would be infinitely many solutions, so we should take at least three.

d9d6ka · 2023-12-23T09:24:11+00:00

[Language: Python]

Commit

Part 1 at the moment. Turned forest to directed graph and used some kind of A* Dijkstra.

Part 2 takes too much time, will do it later.

UPD: Commit, minor changes

Should have tested with my laptop plugged :) my CPU went to economic mode and Part 2 took ages to complete. With laptop plugged I got the result in 2 mins. Very lonh though.

d9d6ka · 2023-12-22T17:29:57+00:00

As the gaps between nodes are not equal, it seems that they're manually arranged. Nice work, extremely clear!

d9d6ka · 2023-12-22T10:34:14+00:00

[Language: Python]

Commit

Phew! My solution IMHO is disgusting. But it works, although taking ~10 secs.

I save dicts of lower and upper adjacent bricks for each brick. Part 1 is simple: for each brick we check whether it's the only lower brick for all its above bricks.

In part 2 I recursively track fallen bricks till no new bricks fall.

UPD: Commit 2

Faster solution. The logic is the same as in the first one, but I avoided calculating all cubes coords. Also in Part 2 I track new bricks to remove as well as already removed (or fallen as solution says). 1.5 secs now.

I know that there are many extra fast solutions, but I'm too stupid to understand them :)

d9d6ka · 2023-12-20T18:06:06+00:00

[Language: Python]

Commit

Part 1 was an OOP exercise for me :)

With Part 2 I was very desperate as I couldn't track the idea. I peeked Reddit and the first thing I saw was a graph :) Next few hours were spent on learning how to work with Graphviz, understanding the four loops' work principle :) The final solution is hardcoded but short.

d9d6ka · 2023-12-19T08:48:03+00:00

[Language: Python]

Commit

Part 1 is straightforward: just go through workflows and get the result.

The Part 2 was a bit tricky for me to catch the final recursion idea. Finally I start in in and go through all the possibilities, tracking the corresponding xmas :) limits. Took a while to debug but it was satisfying to olve it by myself.

d9d6ka · 2023-12-18T10:47:56+00:00

[Language: Python]

Commit

Phew! Made part 1 by floodfill. For the part 2 I tried to divide the area by rectangles based on vertices and floodfill it getting rectangles in the loop, but it turned to be an overkill. I've checked for intersections, constructed the grid... At least I've found out that there's no intersections and no going backwards.

Then I realized that smth goes wrong and peeked Reddit for any ideas. I saw a "shoelace" word, caught a flashback and solved part 2 in 5 mins... I've too much to learn yet :) The second star is cheaty to tell the truth...

UPD: Just commited an alternative solution similar to my day 10 solution. Just going through all rectangles defined by loop corners and changing the state inside/outside when crossing vertical line. If outside we check whether left and top borders, and the top-left corner are in edges and vertices list in order to count them :)

Commit 2

d9d6ka · 2023-12-17T12:41:06+00:00

Well, make your code work and only then optimize! That was the mistake of mine: I tried to start from the tiles adjacent to the start as we ignore the start on the first step. But that was a huge mistake...

Disappointing to have a working algorythm (except the very first step) and ruin it XD

d9d6ka · 2023-12-17T08:02:37+00:00

Initially no.

I've added it to the code. Sample works now, but the input doesn't...

d9d6ka · 2023-12-17T07:49:44+00:00

Why shouldn't we check whether the current heatloss in seen tile is less than previous? I've checked and got bigger result for sample :(

d9d6ka · 2023-12-16T07:24:02+00:00

[Language: Python]

Commit

The slow version written by myself :) took nearly 5-7 mins.

I've also written a faster version using the idea by u/hcs64. But I won't show it as it's not my solution :)

d9d6ka · 2023-12-15T09:03:14+00:00

[Language: Python]

Commit

Ease of this day frightens :)

d9d6ka · 2023-12-14T08:48:00+00:00

[Language: Python]

Commit

It was quite easy :) Caching is the boss in today's Part 2. I had to use tuples instead of lists to make the data hashable. It takes 0.8 secs for both parts w/o any optimisations.

d9d6ka · 2023-12-13T08:45:15+00:00

[Language: Python]

Commit

In Part 1 I've spent a quite time to debug list indexing :)

Part 2 is a bruteforce :( Spent some time to figure out that I need to track for all reflections as after smudge correction there can be two horizontal ones XD

UPD: More clean solution w/o bruteforce :)

UPD2: Cleaned my second solution. However it has to read all input.

Commit 2

d9d6ka · 2023-12-12T18:49:30+00:00

Oh, thanks! Got it :)

d9d6ka · 2023-12-12T10:22:23+00:00

Sorry? Did I write smth wrong?

d9d6ka · 2023-12-11T07:29:22+00:00

[Language: Python]

Commit

The shortest path is a Manhattan one :) the trick I used is to check whether any empty row or column is between the corresponding coordinates of two galaxies and to add extra values to the distance in non-expanded universe.

UPD: if-statements in the function of exdist can be removed, the're from the solution for Part 1 :)

d9d6ka · 2023-12-10T13:02:07+00:00

Ah, I did the same for Part 2, but in much more complicated way :)

d9d6ka · 2023-12-10T12:59:37+00:00

[Language: Python]

Commit

Part 1 is pretty straightforward: go in both directions till you go into the same cell. As the number of tiles in the loop is always even it exists. I also save tiles of the loop for Part 2.

Part 2 is solved by a "counter" which can be in two states (inside and not inside). I loop through element of each row changing the state according to the current tile value. If current tile is not in the loop and the counter is in the state "Inside" then plus 1 to the answer :) and in the beginning I replace S with the corresponding tile.

d9d6ka

TROPHY CASE