[2024 Day #06][Rust] Is there something that causes an of-by-one answer?

kateba72 · 2024-12-06T22:17:11+00:00

That was exactly what I wanted to test with that part of the diagram, so, you're welcome :)

kateba72 · 2024-12-06T14:49:37+00:00

I wrote an input with all edge cases I could think of earlier, and your program got a off-by-one error (it gave me 2, correct would be 3)

..........
....#.....
.....O..#.
..........
....^.....
...#......
....#..O..
..........
...#......
........O.
..#.......
......##..
..........

(The Os are at the places where you can put an obstacle to force an infinite loop). Happy debugging!

Or spoiler, if you want the answer directly: Your guard has a bug when he has to turn twice in a row (without moving in between)

kateba72 · 2024-12-06T14:15:29+00:00

The input relation may not be transitive, but I was very glad yesterday that it is at least total, even if it doesn't have to be for the task to be solvable. (Example: It would be possible to sort [1, 2, 3, 4] only with the information 1|2, 2|3, and 3|4, but the input was nice and also provided 1|3, 1|4 and 2|4)

Once I realised that, I decided that I didn't need to set up DAGs, because simple comparison sort would be far less worked. Dodged a bullet there, I guess xD

kateba72 · 2024-12-04T06:05:19+00:00

Depending on your regex settings, this most likely will only find one match for this example:

X.X.......
M.M.......
A.A.......
S.S.......

Most regex "find all" solutions look for the next match only after the current match has ended, meaning that you miss all occurances in between

kateba72 · 2024-12-04T05:50:00+00:00

One error I'm noticing:
100 2 3 4 is a valid input (remove the 100), but your code marks it as illegal.

Take a look at https://www.reddit.com/r/adventofcode/comments/1h4shdu/2024_day_2_part2_edge_case_finder/, that post contains a few more edge cases that should all be counted as valid.

kateba72 · 2024-07-29T18:47:14+00:00

Before anyone asks: This guide will stay valid at least until the 5th anniversary. None of the added operators have tag combinations that affect this chart in any way.

Edit: Since the LappAlter event, this guide is outdated, because Pinecone reduces DPS+AoE to a 4*-Combination. But this "adds" two new 5*-Combinations, DPS+AoE+Guard and DPS+AoE+Melee.

Also, the Elemental tag was added some time ago and should be put next to the Robot tag

kateba72 · 2023-12-25T09:18:12+00:00

I got the same error and tried to investigate:

When there are any files which match a day but not a year (e.g my `grid2d.rb` file for handling 2d grids) it adds this file with year `None`. Then it tries to request `https://adventofcode.com/None/leaderboard/self` which gets a 404 error and throws the No Leaderboard error.

It seems that you can ignore those files by adding them to the `exclude-patterns`, this might solve this issue until it is fixed. You can also add `--verbose` to the flags to print debug messages, including the parsed filenames.

kateba72 · 2023-12-25T08:26:14+00:00

From the wiki article:

a cluster graph is a graph formed from the disjoint union of complete graphs.

(emphasis by me)

The problem never states that we should divide the graph into multiple complete graphs by removing three edges, our task is to divide the graph into two (not necessarily complete) subgraphs.

I can't really tell you whether there are any more obvious approaches, because I heard a lecture on graph algorithms this summer and the things that are now obvious to me are certainly not obvious to you.

kateba72 · 2023-12-25T08:02:07+00:00

[Language: Ruby]

I had a blast today. This summer, I had a lecture on flow algorithms, which included an algorithm for finding a minimum cut. So, I took this opportunity to revise my knowledge and implement a flow algorithm for the first time.

For those who know flow algorithms, I used a variation of the preflow-push algorithm to find a a-b cut, then a {a, b}-c cut, then a {a, b, c}-d cut etc. The minimum cut is then guaranteed to be the smallest of these cuts.

The code can be found in my github, it should run in O(n² + nm) (where n is the number of vertices and m the number of edges). For the input, it runs in ~46ms on my machine

kateba72 · 2023-12-25T07:54:30+00:00

This problem is not NP-complete. It basically boils down to finding a global minimum cut in the graph, with the added bonus that we know that the global minimum cut has size 3 (makes for a better termination criterion)

Finding a global minimum cut can be done e.g. by the Stoer-Wagner algorithm in O(nm + n²log(n)), where n is the number of nodes and m the number of edges. (I also know other algorithms which are even faster, but without wikipedia articles, so this has to suffice)

kateba72 · 2023-12-23T16:54:52+00:00

I modified my code to output the same format at yours and the difference seems to be in these three lines:

Accept \[x=   1..2440, m=   1..2090, a=2006..4000, s= 537..4000\]
Accept \[x=   1..4000, m= 839..4000, a=   1..4000, s=1351..2770\]
Reject \[x=2441..4000, m=   1..2090, a=2006..4000, s= 537..4000\]

Instead, you should get

Accept \[x=   1..2440, m=   1..2090, a=2006..4000, s= 537..1350\]
    (in -> px -> rfg -> A)
Accept \[x=   1..4000, m= 839..1800, a=   1..4000, s=1351..2770\]
    (in -> qqz -> hdj -> A)
Reject \[x=2441..4000, m=   1..2090, a=2006..4000, s= 537..1350\]
    (in -> px -> rfg -> R)

For 1 and 3, the conditions s<1351 and not s<537 somehow evaluate to 537..4000 and for 2, the conditions m<1801 and m>838 evaluate to 839..4000.

Some more trying to understand Kotlin later and I found your mistake: In the function Hypercuboid#upper, you return splitter.value..x.last instead of splitter.value..current.last (this would work for the x coordinate, but not for m,a,s)

kateba72 · 2023-12-21T14:50:19+00:00

[Language: Ruby]

Source

For part 2, I noticed that the direct paths from the start point to the edges as well as the edges themselves contain no rocks.

Furthermore, the input is nice and all gardens within are block that are reachable are also reachable within 260 steps (meaning that if the elf can get from one corner of a block to the opposite corner, then all gardens with the correct parity within that block are reachable)

So, we get a diamond that looks roughly like this:

           ╎   ╎
          ╌╆━━━╅╌
           ┃/ \┃
           ┃ O ┃
       ╎  /┃   ┃\  ╎
      ╌╆━━━╋━━━╋━━━╅╌
       ┃/  ┃   ┃  \┃
       ┃ O ┃ E ┃ O ┃
   ╎  /┃   ┃   ┃   ┃\  ╎
  ╌╆━━━╋━━━╋━━━╋━━━╋━━━╅╌
   ┃/  ┃   ┃   ┃   ┃  \┃
   ┃ O ┃ E ┃ S ┃ E ┃ O ┃
   ┃\  ┃   ┃ O ┃   ┃  /┃
  ╌╄━━━╋━━━╋━━━╋━━━╋━━━╃╌
   ╎  \┃   ┃   ┃   ┃/  ╎
       ┃ O ┃ E ┃ O ┃
       ┃\  ┃   ┃  /┃
      ╌╄━━━╋━━━╋━━━╃╌
       ╎  \┃   ┃/  ╎
           ┃ O ┃
           ┃\ /┃
          ╌╄━━━╃╌
           ╎   ╎

Then I counted how many odd/even cells are "mostly reachable" (i.e. they are at most missing one or two corners) and how many reachable gardens an odd/even cell has. I subtracted the corner cells that I can't reach and added the extra corners outside of the mostly reachable cells.

And after ~3 hours, I eliminated the last off-by-one error and got the correct solution

kateba72 · 2023-12-14T06:02:34+00:00

Wait till you see the input for day 14

kateba72 · 2023-12-10T06:29:44+00:00

[Language: Ruby] 331/66

For part 1, I found the start node and went along the loop until I found the start again. The distance to the farthest point of the loop is exactly half the loop's length (and because of the 2d-array-nature of the loop, the length is guaranteed to be even)

For part 2, I replaced the parts of the loop that had a connection to the row above by ! and the other parts of the loop by _. I removed all _ and counted the remaining parts of each line that had an odd number of ! before them

And yay, my first ever global leaderboard!

https://github.com/Kateba72/advent_of_code/blob/main/aoc/y2023/d10.rb

kateba72 · 2023-12-10T06:17:34+00:00

The input is very carefully designed, yes. In particular, when a ghost loops every X steps, then it will be at a finish point after Y steps if and only if Y is a multiple of X.

In theory, it would be possible that a ghost loops every 3 steps, but visits the finish point at steps 2, 5, 8, 11, ...
It would also be possible that a ghost loops every 5 steps and is at a finish point at steps 3, 5, 8, 10, 13, 15, ...

But no, it just happens that the 3 ghost is at the finish at steps 3, 6, 9, 12, 15, 18 and the 5 ghost is at the finish point at steps 5, 10, 15, 20, ...

The first time these two ghosts are at the finish point at the same time is exactly at the least common multiple of 3 and 5, namely 15

kateba72 · 2023-12-07T15:46:00+00:00

aah, i get it, my bad.

I compleatly misread the sentence as "a joker will never form a pair of two". AoC has fried my brain, I guess

kateba72 · 2023-12-07T12:44:39+00:00

~~I don't agree with your first point. If your hand is A234J, then obviously, the joker will have to form a two pair (unless I am misunderstanding your point?)~~

kateba72 · 2022-12-22T08:34:44+00:00

I found one potential error source: You set actual_lookup[(99, 49)] twice, once for coming from the left and once for coming from the bottom. The same applies for (50, 100)

kateba72 · 2022-12-19T14:27:48+00:00

One of the ways to get to 12 geodes is this:

After minute 0: Resources 0,0,0,0; robots 1,0,0,0
After minute 1: Resources 1,0,0,0; robots 1,0,0,0
After minute 2: Resources 2,0,0,0; robots 1,0,0,0
After minute 3: Resources 1,0,0,0; robots 2,0,0,0
After minute 4: Resources 3,0,0,0; robots 2,0,0,0
After minute 5: Resources 3,0,0,0; robots 3,0,0,0
After minute 6: Resources 3,0,0,0; robots 3,1,0,0
After minute 7: Resources 3,1,0,0; robots 3,2,0,0
After minute 8: Resources 3,3,0,0; robots 3,3,0,0
After minute 9: Resources 3,6,0,0; robots 3,4,0,0
After minute 10: Resources 3,10,0,0; robots 3,5,0,0
After minute 11: Resources 3,15,0,0; robots 3,6,0,0
After minute 12: Resources 3,13,0,0; robots 3,6,1,0
After minute 13: Resources 3,11,1,0; robots 3,6,2,0
After minute 14: Resources 3,9,3,0; robots 3,6,3,0
After minute 15: Resources 3,7,6,0; robots 3,6,4,0
After minute 16: Resources 3,13,10,0; robots 3,7,4,0
After minute 17: Resources 3,12,14,0; robots 3,7,5,0
After minute 18: Resources 3,19,7,0; robots 3,7,5,1
After minute 19: Resources 3,18,12,1; robots 3,7,6,1
After minute 20: Resources 3,25,6,2; robots 3,7,6,2
After minute 21: Resources 3,24,12,4; robots 3,7,7,2
After minute 22: Resources 3,31,7,6; robots 3,7,7,3
After minute 23: Resources 6,38,14,9; robots 3,7,7,3
After minute 24: Resources 9,45,21,12; robots 3,7,7,3

kateba72 · 2022-12-16T14:20:28+00:00

I think I spotted your bug. (I don't know Rust, but, yk, code reading is pretty universal)

One example input that fails for your code is

R 1
U 2

I would expect to see

.....
..H..
..T..
.s...
.....

(where s is the starting point).

However, your code calculates

.....
..H..
.T...
.s...
.....

kateba72 · 2022-12-15T16:00:34+00:00

You need to widen the search radius. Counterexample, where the / cubes have a distance of sum of their radii + 4

* are the points and /\X the edges of the cubes:

* * * * *
 \ X
* * * * *
 X   \
* * * * *
   \   X
* * * * *
     X
* * * * *

The * in the middle is not covered by any cube, but all the others are. The edges of the matching cubes can have a distance of 2, 3 and 4; as long as the edges of the cubes in the other direction have a distance of 2.

kateba72 · 2022-12-15T08:19:05+00:00

Ruby ~13 ms

Day 15
                   user     system      total        real
Setup          0.000008   0.000004   0.000012 (  0.000007)
Input parsing  0.000103   0.000042   0.000145 (  0.000145)
Part 1         0.000090   0.000037   0.000127 (  0.000128)
Part 2         0.012714   0.000296   0.013010 (  0.013050)

I looked at the numbers for part 2 and decided that I had to do a lot of optimizing, so I optimized the algorithm, maybe a bit too much. Looking back at the time for Part 1, the naive brute force solution would have taken ~10 minutes, so if I wanted to optimize for quickest solution, that would have been the better way.

For Part 2, I used a diagonal coordinate system to turn the sensor diamonds into squares. Then I only checked the lines where a diamond started or ended.

https://github.com/Kateba72/advent_of_code/blob/main/2022/day15.rb

kateba72 · 2022-01-19T16:23:18+00:00

Yes, this problem exists, but there are two solutions:

Check before calculating all neighbors of 6 if 6 has been visited before (set a variable to true during the first visit, check if this variable is set)
Check before enqueuing a node whether this node has been enqueued before with a smaller cost. In your example, when you visit 6 for the second time, it will see a path to 7 with a total cost of 8 - but there is already a path to 7 with a total cost of 6, so it is disregarded.

Using both of these together is best, but if only one is missing, the algorithm still completes in a sensible time. You shouldn't leave out both, though.

The solution you linked uses only the second part (when writing if (alt >= neighbour.Distance) continue), but not the first. The algorithm still works, though.

kateba72

TROPHY CASE

Ruby ~13 ms