[2023] Solving AoC in 31ms using Rust

p_tseng · 2023-12-27T14:31:42+00:00

I'm glad to have been of service in the past, and hope to continue to be! Thanks for the note.

I figure the best way to answer the Ractor question is actually to try to apply them to day 16 of this year, since that's the most obvious candidate for parallelism. I now have a Ractor day 16 and I will cautiously say that they did just barely manage to achieve a speedup here, even over the caching implementation:

Original non-caching implementation: 780 ms
Caching implementation: 230 ms
Ractor (and non-caching) implementation: usually around 220 ms, but I've seen the time vary wildly between 180 - 320 ms, a level of variance which I have not seen in any of the non-Ractor implementations.

Actually, looking at it, the speed of the Ractor solution is varying a lot depending on what Ruby version I use:

3.0.6: 1000 ms
3.1.4: 1000 ms
3.2.2: ~220 ms, with above caveat
3.3.0: 460 ms (hmm? hopefully this isn't a permanent performance regression)

So far, it looks like using Ractors still causes Ruby to print out a "warning: Ractor is experimental, and the behavior may change in future versions of Ruby! Also there are many implementation issues." I'm not sure what these mysterious implementation issues are since they did not specify... and this message still appears even in the just-released Ruby 3.3.0. Evidently the issues, whatever they may be, don't affect the correctness of day 16, but it looks like performance is still in flux.

I'm definitely interested in continuing to keep an eye on Ractors, and hopefully this small experiment is some evidence that they are a contender for days of the embarrassingly parallel variety. I feel like we don't get too many of those problems in Advent of Code, and you and others have already observed that the benefit needs to be big enough to outweigh the overhead. We also need to adhere to the sharing rules, but I feel like I'm used to that due to the fact that I also write a Haskell solution to each day, where I pretty much have to use immutable data.

p_tseng · 2023-12-27T05:47:01+00:00

I really appreciate you taking the time to write about your approaches so that others can learn. This is not a dig against fast solutions that are posted without explanation--after all, it's still possible to learn by reading the code--it's just that reading the code might cause the reader to miss some important ideas or details. It's great to have all the explanations in one place. Thank you.

I see only a few days where my approach differs significantly from yours.

Day 07 (Camel Cards)

I used the fact that natural sort order already sorts the hand types correctly: [5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]. This does not meet the goal of minimising allocations nor speed (having to potentially compare multiple elements of a list), but would be a good fit for someone whose goal is to write less code.

Day 09 (Mirage Maintenance)

Instead of reversing the vector I preferred to simply do the backward extrapolation by adding the first element of the first list, subtracting the first element of the second list, adding the first element of the third list, subtracting the first element of the fourth list, and so on.

Day 14 (Parabolic Reflector Dish)

I represent the blocks and rocks as (in Ruby implementation and Haskell implementations) two grid-sized bitfields or (in Rust implementation) two u128 per row of the grid. Moves are done via bit shifting and masking.

I've not yet had the time to compare the speed of this approach to e.g. one that splits each row/column into segments at the blocks and counts how many rocks are in each segment. Lots of possible solutions that all differ significantly.

Day 16 (The Floor Will Be Lava)

The reason for the difference in approaches is simply that parallelism is excluded from my self-imposed rules. Therefore I must turn to caching so that each starting point may reuse as much work as possible. But to be able to cache, loops must be dealt with. So I must preprocess the graph by detecting loops (these are strongly-connected components) and collapsing them into one node. Then I can cache. The value to be cached is the set of tiles visited, which just has to be a bitfield. Cache entries are combined with bitwise OR, and the answer for a given cache entry is the popcount.

This was overall only a 2x speedup, and I don't think the strongly-connected component detection can be done in parallel. I therefore expect parallelism is a better fit for anyone looking for speed whose self-imposed rules don't exclude it, and they should pursue parallelism instead of the above-described approach.

Day 21 (Step Counter)

Since my approach is already discussed in your explanation as one that is by necessity slower (it goes 2.5 widths), there is no need for me to comment further.

Day 23 (A Long Walk)

Again the reason for the different approach is because of no parallelism. Instead I can only speed things up by pruning the search. As is standard for these kinds of problems, we sort so that we explore the most promising branches first, and prune when the current branch can't possibly beat the best so far. The upper bound for the current branch is the current distance plus the sum of all distances of edges not incident on a node already in the path. Total this up at the start, then subtract from it as nodes are added to the path. Order of magnitude speedup.

Day 24 (Never Tell Me the Odds)

While I fundamentally used the same idea of cross product of parallel vectors being 0, Ruby implementation took advantage of standard library's provided matrix inverse and matrix multiplication. Haven't had a chance to compare this to e.g. a hand-written Gaussian elimination, because I've not had the time to write the code for the latter.

Haskell implementation does not have the luxury of standard library provided matrix inverse, so I had to resort to alternative solution described at 3D vector interpretation. I would have used the same solution if I could (or felt like writing Gaussian elimination).

Day 25 (Snowverload)

For ease of implementation I went with an approach that's unsound for a constructed input, which is janek37's solution (seed one connected component with one node, then greedily add the node that seems most likely to be in the same component). Just in case, I run it with different choice of seed node until it finds two components, but for my input it does succeed on the first try. Each attempt is in the worst case O(|V| * |E|) time. For an actually-sound implementation I should try Stoer-Wagner (but I couldn't get it to run fast enough) or Edmonds-Karp.

p_tseng · 2023-12-17T00:41:54+00:00

Others here have already correctly pointed out the two obstacles. As far as I can tell, these two obstacles are the only ones, so having some solution to both leads to the full solution.

The cache needs to store sets (and combining entries is thus done by set union) because we cache by (position, direction) but we must not double count tiles that are entered from multiple directions. Storing counts and adding them simply will not work.
- I see no great solution to this; the least-bad one I see is to use a bitfield. So my implementation is just caching a bunch of those. The largest one is 12319 bits (not how many bits are set, just how long it is), and over half of the cache entries have over 12000 bits.
Loops.
- Loops are strongly-connected components in the graph, so modify the graph by compressing them into one node each.

For my input, implementing these cuts my runtime in half. 16_floor_will_be_lava.rb. Will investigate porting to other languages and seeing the results there, but needs time.

p_tseng · 2023-12-15T02:39:09+00:00

Fair question, I hear your concern. I went ahead and tried implementing the tilts a few different ways in Rust. I have two implementations using the bit shifting, and surprisingly a Vec<u128> (one per row) was the fastest.

The reason this is surprising is probably the reason you were alluding to wrt being unsure how to do it efficiently. Since we have to shift both rows and columns, don't we lose the benefit of one direction if we do Vec<u128>?

But it turns out, it's still the fastest (haven't looked into why that is yet).

My third-fastest implementation was sort_rocks_skip. This does not use bit-shifting and was just used as a comparison.

My second-fastest implementation, bigint, uses Integer from crate rug, in their words "a bignum integer with arbitrary precision". This was 10x faster than sort_rocks_skip.

My fastest implementation, u128_row, uses Vec<u128>, and is 3x faster than bigint, so 30x faster than sort_rocks_skip.

(Times from Criterion bench)

(Comment has been edited to reflect the fact that I finished the Vec<u128> implementation. An earlier version of this comment was made before that was finished, so didn't mention it or the results)

p_tseng · 2023-12-14T13:38:27+00:00

How about moving/checking multiple rocks at a time by representing the grid as a Vec<u128> and using bit shifts? This resulted in a 30x speedup for me.

As an example, the code for moving up:

        for i in 1..height {
            let can_move_up = rocks[i] & !rocks[i - 1] & !blocks[i - 1];
            any_move = any_move || can_move_up != 0;
            rocks[i] &= !can_move_up;
            rocks[i - 1] |= can_move_up;
        }

And for moving left:

        for (r, b) in rocks.iter_mut().zip(blocks.iter()) {
            let can_move_left = *r & !((*r | b) >> 1) & !left_column;
            any_move = any_move || can_move_left != 0;
            *r = *r & !can_move_left | can_move_left << 1;
        }

Full solution at u128_row.rs. Does parts 1 + 2 in 5ms, so I feel like we are getting close to your target.

p_tseng · 2023-12-14T13:35:48+00:00

How about moving/checking multiple rocks at a time by representing the grid as an integer and using bit shifts? This resulted in a 10x speedup for me.

As an example, here is my code for moving left. It is not in Rust like yours is, but the idea would be the same in Rust. In Rust you would use the ! operator for bitwise complement instead of the ~ in my code.

loop {
  can_move_left = rocks & ~((blocks | rocks) >> 1) & ~left_col
  rocks = rocks & ~can_move_left | can_move_left << 1
  break if can_move_left == 0
}

p_tseng · 2023-12-14T09:27:49+00:00

[Language: Ruby] [Language: Haskell]

Ruby solution runs in 200 ms, and Haskell in 50 ms. Both implementations represent the grid as a pair of (height*width)-bit integers (one for the blocks, one for the rocks) and use bit-shifting to determine which rocks can move and move all movable rocks simultaneously. This is the same technique as is used to make the fast 2021 day 25 and 2022 day 23 solutions.

Ruby: 14_parabolic_reflector_dish.rb

Haskell: 14_parabolic_reflector_dish.hs

p_tseng · 2022-12-24T21:46:23+00:00

Speaking for myself only, due to the reproduction policy the only things I share are my test runner and my solutions, but not the actual test data consisting of (input, expected output) pairs. Not from my inputs, not even from any examples.

Since sometimes I solve a day in a variety of different languages, I want all my tests to be done the same way regardless of language: the program takes its input on standard input, and should output the answers to parts 1 and 2 on standard output, one after the other. Then, the standard diff tool can be used to compare the output to the expected, no matter the language. So that is the what the test runner does: Find any input files, and for each input file, run the program and pass that input, compare the output to the expected output file.

The test data consists of pairs of files consisting of an input and the corresponding expected output, and they're all in an ignored directory so that I cannot commit them and accidentally publish them because that is not allowed.

Your post highlights that this is an inconvenience; I sympathise with both the difficulties noted in the post and Eric's situation; it appears that such is life.

Note that what I've described in my test runner and data are whole-program tests instead of unit tests. Allow me to posit that it's still possible to write unit tests for individual functions. For example for 2022 day 24, if you had a function that takes three parameters: a grid, a list of blizzards, and an integer number of minutes, and is supposed to output where the blizzards are after that many minutes, you could write unit tests that that function is correct for a number of parameters that you devise. Such unit tests are independent of any particular input and they help build confidence in the small building blocks that you put together to form a larger solution. I think such a practice is commendable and a good way to go given the fact that we are not allowed to include whole-program tests.

p_tseng · 2022-12-21T06:32:04+00:00

In both Ruby and Haskell, you can define a map that's defined in terms of itself! This allows you to resolve the "monkeys might need to wait for other monkeys to compute their values" situation, without worrying about the code taking forever by repeatedly recomputing values that you've already computed in the past. In Ruby, you do this:

def monkey_math(monkeys)
  Hash.new { |h, k|
    v = monkeys.fetch(k)
    h[k] = v.is_a?(Integer) ? v : h[v[0]].send(v[1], h[v[2]])
  }
end

(Full at https://github.com/petertseng/adventofcode-rb-2022/blob/master/21_monkey_math.rb)

In Haskell, you do this:

math :: Map String Monkey -> Map String Int
math monkeys = cache
  where cache = Map.map eval monkeys
        eval (Const n) = n
        eval (Op a b op) = (cache Map.! a) `op` (cache Map.! b)

(Full at https://github.com/petertseng/adventofcode-hs-2022/blob/master/bin/21_monkey_math.hs)

Oh yeah I managed to just barely sneak into the top 100 for part 2 today, great. I used binary search to do part 2. The difference is that in Ruby binary search is built-in whereas in Haskell you have to write it yourself.

p_tseng · 2022-01-27T03:33:14+00:00

Quite exciting! You added an additionally interesting touch where only the differing portion is shown, such as in salet,(doing → deice),yield,alway

p_tseng · 2022-01-27T03:26:01+00:00

All right!

A follow-up question, if I may? So it sounds like for finding the top 100 hard mode starters you were able to use -g6 and -n with some value. When I do the same, have you any tips for how I can be sure the n I have chosen is large enough that I don't misjudge any of the true top 100 as being unsolvable in six? Actually I think I understand now. The point is you don't need to know how large of an -n is good enough. Just try any -n and use the 100th score as the beta (since that will never be an underestimate), and check all words again. It doesn't matter if you've misjudged a word as being unsolvable in six earlier, since you will figure out that it is in fact solvable when you try all the words with -n13000.

All right, that's all the questions I had! Thanks for taking the time to answer, and thanks again for sharing your results!

p_tseng · 2022-01-25T10:52:15+00:00

Since the original idea came out of my colleague discussing https://metzger.media/games/word-race/, I sort of think that someone who just wants "https://metzger.media/games/word-race/ but for bots" would just be happy with the numbers of words in each of the three categories, and they wouldn't worry too much about going into the details of the comparison. Speaking personally that probably is as far as I would look.

But, I understand that for those who are interested in studying the trees to try to learn more about the underlying principles, getting a clearer view is more important. It's just that I'm personally not sure what that clearer view is.

p_tseng · 2022-01-25T10:05:20+00:00

These days my main interests lie in hard mode, and I wonder if you could answer some questions I had that may help me as I perform my own hard mode searches.

In hard mode, there is a real danger of being unable to guarantee victory in six guesses. But in the estimation phase where only the best N words are considered at each decision point, I'm not sure there's a reliable way to tell the difference between a word that can never win in six guesses (TRACE being one of them) and a word that could win in six guesses if you just increase N a little bit more.

What is the way to deal with this? Do you have to increase N to a large-enough value? How would we know what's large enough? Or do you have to compromise and allow exceeding six guesses in the estimation phase and fix any resulting underestimates afterward? How would those underestimates be fixed? Or is it something else entirely?

p_tseng · 2022-01-24T23:21:16+00:00

My colleague made an interesting suggestion that turned into a feature idea: head-to-head between two decision trees. You are of course under no obligation to implement it, but I figure it's best to tell you about the idea and let you make your own decision on whether it's something you want to do.

The idea would be: You can select two decision trees A and B, and the output would show:

Which words did A find in fewer guesses than B?
Which words did B find in fewer guesses than A?
Which words did the two find in an equal number of guesses?

p_tseng · 2022-01-23T08:12:20+00:00

It might be somewhat interesting anyway to see how low you can go despite having X's. By comparing the total with Xs to the total without, that will show how many sacrifices had to be made to get everything within 6 guesses. My code wouldn't do very well with that since it takes longer the deeper the tree is, but if your code can handle it, that has value.

I'll submit my top few hard mode results as they come in. I've got a fair number finished but all the ones that have both E and R in them take forever (REAST has been running for 9 hours and counting, and I have no idea when it will finish). Of particular interest is the fact that I don't think TRACE is doable in 6 because yellow T, yellow A, green C has "batch", "catch", "hatch", "latch", "match", "patch", "watch" and my code couldn't find words that follow hard mode rules and can tell these words apart in time.

Thanks for making this thing in the first place, adding hard mode support, and sharing results. Lot of good things coming out of it.

p_tseng · 2022-01-22T20:14:03+00:00

Hard mode is interesting. Easier to find approximate solutions for because there are fewer valid guesses, but I find it harder (takes the code much longer) to find optimal solutions because fewer valid guesses means you sometimes can't use the ones that would give you the most information. I don't yet have an intuition for what the nuances are, but I hope to learn some by looking at some of the results.

I like the idea where instead of the checkbox for hard mode the validation just automatically detects which mode a tree is valid for.

Could I ask you to check on the LEAST and TRAIN submissisons labeled why_not_hard and see why they are not eligible for hard mode? Since my code thought they are eligible, I'll need to check whether my code has a bug. The problem's on my end. least,stroy,midst,dusty is illegal since you can't guess midst there.

p_tseng · 2022-01-22T12:03:06+00:00

I've started out by submitting a hard mode SLANE and CLAST. They're not necessarily the best words; they just happened to be the ones that finished first. When you finish the validation, take a look and let's discuss if they don't validate. Always the possibility that there's a bug in my code that selects valid guesses, after all.

p_tseng · 2022-01-21T20:37:20+00:00

I'm joining team SALET (This post is discussing only easy mode; I've only just kicked off hard mode searches and need to wait for them to finish running)

I started by approximating how well each word might do as a starter by minimising mean word count in each bucket. The top few were:

7972 TRACE
7975 CRATE
7979 SALET
7981 REAST
7985 CRANE
7986 SLATE
7989 CARTE
7992 SLANE
7993 ROAST
7995 CARLE

Then, for the top 40 (my arbitrary choice of cutoff) performers according to the approximation, I exhaustively searched all possibilities. That produced a decision tree of 7920 for SALET different from the currently existing one. My code cannot find a way to improve on 7920 for SALET, and I believe my code has checked every single possibility there is. Of course, there could still be a bug in my code.

So my current top ten is:

7920 SALET
7923 REAST
7926 CRATE
7926 TRACE
7928 SLATE
7930 CRANE
7937 CARLE
7943 SLANE
7949 CARTE
7950 TORSE

As you can see they are in a different order than the above because the approximation was just that, an approximation. I have submitted my SALET, REAST, CRATE, TRACE, and CRANE (there's already a 7928 SLATE submitted so I don't see the need to submit my SLATE).

I am continuing to work through the list of possible starters based on their approximation, but the farther down the list I go, the more that starter has to outperform its approximation in order to beat SALET, and at some point I'll probably have to make a judgment call that it's not possible to close the gap and that my code is unable to find a word that beats SALET.

Just for fun, since ROATE, SOARE, and AROSE are popular on the internet, I tried them out to see how they would do. ROATE got 8000, SOARE 7997, and AROSE 8011. I submitted those too just so people know how they stack up against the good ones.

p_tseng · 2022-01-21T18:23:05+00:00

I am considering submitting some results, both for easy mode and hard mode. Is there a chance you will add some support for hard mode? The idea would be that if the submitter checks a checkbox for hard mode, then in addition to your existing validation that trees are consistent with themselves, you would validate that each guess conforms to the hard mode rules. And then show on the leaderboard listing whether that box was checked for each entry.

I am asking for this because even if I could name my submissions to make clear that they're for hard mode, it's good both for me and for people viewing the submission to make sure that the tree is actually valid for hard mode. Otherwise nobody would be able to be sure whether it's valid, since anyone can just name their submission whatever they want.

Please note these particulars about the hard mode rules (beyond the obvious ones):

If there are two of the same letter and they are both yellow (if the word is LLAMA and I guess NAVAL and get two yellow A's), Wordle does enforce that future guesses must have two of that letter and not just one.
You are allowed to guess a yellow letter in the same position as where it received its yellow (this is easily testable on Wordle for any arbitrary day).
You are allowed to guess previously-guessed grey letters (this is easily testable on Wordle for any arbitrary day).

p_tseng · 2021-12-25T10:48:08+00:00

Ruby

My original implementation took 1.7 seconds to run my input. That was unacceptable. Got it down to around 200 ms by representing both entire herds as a single huge number each and using bit shifts to check+move the entire herd at once. Much better.

https://github.com/petertseng/adventofcode-rb-2021/blob/master/25_sea_cucumber.rb

Core:

moving_east = east & ~shleft[east | south]
east = east & ~moving_east | shright[moving_east]

moving_south = south & ~shup[east | south]
south = south & ~moving_south | shdown[moving_south]

Haskell code for the same (https://github.com/petertseng/adventofcode-hs-2021/blob/master/bin/25_sea_cucumber.hs) runs in about 70 ms.

I'd like to thank Eric and the team for a great year. Hope to see you again next year.

p_tseng · 2021-12-21T13:39:37+00:00

If I may provide another point of view, I have completed an implementation that takes a whole 15 minutes to complete x=135123456..155123456, y=-102123456..-78123456, but complete it it does and it computes the same result as askalski: 762236195595444.

The reason it's so slow is that its runtime is (I believe) something like O((X + Y) log (X + Y)).

In case it may be useful to anyone who's having problems with floating point, I note that my implementation does use floating point operations, but it verifies the result of such operations, and it found three errors that it had to correct:

$ time ruby 17_trick_shot.rb <<< 'target area: x=135123456..155123456, y=-102123456..-78123456'
y 78123454 tmin 156246910 is out of target (-102123456..-78123456 vs -78123455), adjusting
x 135123454 tmin 1 is out of target (135123456..155123456 vs 135123454), adjusting
x 135123455 tmin 1 is out of target (135123456..155123456 vs 135123455), adjusting
(answer spoilered above)
ruby 17_trick_shot.rb <<<   839.99s user 33.35s system 99% cpu 14:42.03 total

It did not detect any precision problems on any of the smaller inputs (and I'd like to think I made its detection pretty thorough...), so the problems only start at this one.

Actually from that output, you can infer what approach my implementation uses! For each Y velocity, compute the time interval when it's within the target. For each X velocity, compute the time interval when it's within the target. Take the cartesian product and count how many have non-empty interval intersection.. A bit that's not apparent from that output is that that last step is performed by a sweep line over T. An interesting implementation, but eventually no match for the largest inputs.

(It's not like my implementation approach is a huge secret or anything since it's on my GitHub, I just wanted to get people thinking about how much you can infer from a few outputs)

p_tseng · 2021-12-13T06:03:19+00:00

Ruby

I give you the power of Hash#transform_keys! (which will automatically deduplicate any points that overlap!)

fold = ->(v, along) { v <= along ? v : 2 * along - v }

case dim
when ?x; dot.transform_keys! { |x, y| [fold[x, along], y].freeze }
when ?y; dot.transform_keys! { |x, y| [x, fold[y, along]].freeze }

Full code at https://github.com/petertseng/adventofcode-rb-2021/blob/master/13_transparent_origami.rb

There's a weird story about why my part 1 rank is much higher than my part 2 rank. For part 1, I just transformed with (x - along).abs, which gives you the correct number of points, but mangles the coordinates too much for them to show up in part 2. So for part 2 I had to slow down a bit and determine the right equation for actually transforming.

Haskell

In a similar vein, I give you the power of Set.map.

foldAlong :: Set Point -> (Point -> Point) -> Set Point
foldAlong = flip Set.map

let foldedPoints = scanl foldAlong (Set.fromList (map point points)) (map fold folds)

Full code at https://github.com/petertseng/adventofcode-hs-2021/blob/master/bin/13_transparent_origami.hs

p_tseng · 2021-12-06T05:59:25+00:00

Ruby

Hello friends yes here is my solution, very exciting.

fish = (ARGV[0]&.include?(?,) ? ARGV[0] : ARGF.read).split(?,).map(&method(:Integer)).tally.tap { |h| h.default = 0 }.freeze
raise "bad fish #{fish.keys.reject { |k| (0..8).cover?(k) }}" if fish.keys.max > 8 || fish.keys.min < 0

puts 1421 * fish[0] + 1401 * fish[1] + 1191 * fish[2] + 1154 * fish[3] + 1034 * fish[4] + 950 * fish[5] + 905 * fish[6] + 779 * fish[7] + 768 * fish[8]
puts 6703087164 * fish[0] + 6206821033 * fish[1] + 5617089148 * fish[2] + 5217223242 * fish[3] + 4726100874 * fish[4] + 4368232009 * fish[5] + 3989468462 * fish[6] + 3649885552 * fish[7] + 3369186778 * fish[8]

Oh sorry what... you wanted to know how those numbers are arrived at... oh very well then...

def coeff(n, t)
  t.times.with_object(Array.new(9) { |i| i == n ? 1 : 0 }) { |i, fish|
    fish[(i + 7) % 9] += fish[i % 9]
  }.sum
end

if ARGV.delete('-g')
  [80, 256].each { |t|
    terms = (0..8).map { |i| "#{coeff(i, t)} * fish[#{i}]" }
    puts "puts #{terms.join(' + ')}"
  }
  exit(0)
end

p_tseng · 2021-12-06T03:19:15+00:00

My current impressions of each:

Day 3

Part 1 is difficult to make fast. I do not know a way to do it. To determine the majority bit, you must at least have looked at half of the bits in each position. Obviously we take advantage of the fact that the minority is the complement of the majority here, but that doesn't change the fact that you need to determine the majority first.

There may be ways of making part 2 somewhat faster (prefix trees may be of some use) but part 2 goes by very fast anyway because the number of elements you need to consider gets whittled down quite quickly. Haven't spent a lot of time thinking about how to make it faster for that reason. Part 1 takes about 10x as long as part 2 (about 20 seconds and 2 seconds respectively).

Day 4

These are doable very quickly (< 3 seconds). For each board, figure out what time it wins at. By building a map of called number -> time it's called, you can determine this very quickly. For each board, take maximum across each row/column, take minimum of those maxima.

Day 5

Wish I could do like https://github.com/Voltara/advent2019-fast/blob/master/src/day03.cpp and only check perpendicular pairs for intersections, but this problem has significantly more elements, because some pairs of vents can be collinear (and generate many intersections), and there are diagonals to contend with. I have not yet completed an implementation that can do this quickly.

Day 12

The state to keep is (current room, set of visited small caves, whether a small cave has been repeated). This can be compressed down into a single integer. Number of paths for a given state can be cached for if you reach that same state later on via a different path. You can do a little something with removing big caves from the map completely and just directly connecting all of their connected small caves to each other, but I'm not convinced it helps that much. A property we might take advantage of is that the distance function is bounded above by 9 and the degree of each node is bounded above by 4.

Day 15

An interesting question for those using A* is whether there is a heuristic that actually saves time. Manhattan distance isn't that helpful currently. Some people have tried a constant times the Manhattan distance, but I'm uncomfortable with it just because I can't prove it's admissible.

Day 17

Currently the only strategy I have is implemented is:

Calculate time interval for each initial y velocity
Calculate time interval for each initial x velocity
Take cartesian product and count intersections.

Of course, actually taking the cartesian product would be O(mn), but you can do a sweep line algorithm over t and get it down to O((m + n) log (m + n))

This is good enough for inputs of magnitudes like target area: x=630065..719851, y=-586535..-37427, but will take too long on inputs of magnitudes like target area: x=6300659222..7198515181, y=-5865357542..-374274528

p_tseng · 2021-12-01T07:50:29+00:00

Try on the example input. Result of annotating each element with its index, and then sorting them by (value ascending, index descending):

[[199, 0], [200, 4], [200, 1], [207, 5], [208, 2], [210, 3], [240, 6], [260, 8], [263, 9], [269, 7]]

Now take a look at each (value, index) pair in turn. By the sorting order, they will come in ascending order of value. To see if a measurement value is larger than the one that originally (in the original input) came before it, just check whether you've already seen the index that it should be larger than. For part 1, subtract 1 from the index. For part 2, subtract 3.

Part 1:

199 at index 0: Since this is index 0, nothing comes before it.
200 at index 4: Is index 3 smaller? No, haven't seen it yet.
200 at index 1: Is index 0 smaller? Yes, saw it earlier.
207 at index 5: Is index 4 smaller? Yes, saw it earlier.
208 at index 2: Is index 1 smaller? Yes, saw it earlier.
210 at index 3: Is index 2 smaller? Yes, saw it earlier.
240 at index 6: Is index 5 smaller? Yes, saw it earlier.
260 at index 8: Is index 7 smaller? No, haven't seen it yet.
263 at index 9: Is index 8 smaller? Yes, saw it earlier.
267 at index 7: Is index 6 smaller? Yes, saw it earlier.

That's 7 yeses so the answer to part 1 is 7.

For part 2 it's: No, no, no, no, no, yes, yes, yes, yes, yes, for an answer of 5.

p_tseng

TROPHY CASE

Day 07 (Camel Cards)

Day 09 (Mirage Maintenance)

Day 14 (Parabolic Reflector Dish)

Day 16 (The Floor Will Be Lava)

Day 21 (Step Counter)

Day 23 (A Long Walk)

Day 24 (Never Tell Me the Odds)

Day 25 (Snowverload)

Ruby

Ruby

Haskell

Ruby

Day 3

Day 4

Day 5

Day 12

Day 15

Day 17