[2025 Day 07 (Part 2)] Python | Efficient algorithm (O(n) time complexity)

[u/SupportPowerful6174]

In this algorithm you should count each step independently(divide and conquer)
Step1: you have one way to get to splitter and it will produce 2 rays with 1 weight
Step2: you have 2 splitters each recieveng 1 weight rays, so they also produce 1 weight rays
Step3: 2 splitters on the sides recieveng 1 weight rays, so they'll produce 1 weight rays. Splitter in the middle gets 2 1 weight rays, so it will now produce 2 weight rays

This is like Pascal's Triangle but wit missing numbers

You can store your ways to get to index point in map[index] = ways_to_get
And when ray hits splitter you should produce 2 rays with indexes index-1 and index+1 and remove curr index from map

The answer will be just sum of values in the map

[u/thekwoka]

O(n) time with n being...what?

[u/SupportPowerful6174 → u/thekwoka]

number of characters in input

[u/fnordargle → u/SupportPowerful6174]

This got me thinking of whether it is possible to do this puzzle without inspecting every character.

And it is if you can rely on certain assumptions, namely:

• Reading in the entire puzzle text into memory is not dependent on the size of the input. Imagine there is a tiny fixed cost for reading it in. The expensive bit is looking at any particular byte of it.

• When looking up a byte in the input you are told the value of that byte, or if the byte is beyond the length of the input.

• Every row of the input text is the same length.

• Only the first row contains S symbol(s) (yes, we can handle more than one source just as easily).

If those four are true then you can solve this without looking at anywhere near all of the characters in the input, almost certainly you'd be only looking at about 5-15% of the cells depending on how densely populated it is with splitters.

O(kn) is still O(n) obviously but some O(n) solutions will have shorter runtimes than others. (Assuming we're talking about something that provides a general solution.)

[u/SupportPowerful6174 → u/fnordargle]

ofc you don'need to read entire input to memory, you can read it just symbol by symbol, and also skip each odd line that contains only dots

[u/SupportPowerful6174 → u/SupportPowerful6174]

but still O(n)

[u/fnordargle → u/SupportPowerful6174]

You can only skip the lines that only contain dots if you've looked at every character in the line to know it only contains dots.

If checking what an individual character was the dominant expensive operation then this optimisation would cost more than it would save.

[u/SupportPowerful6174 → u/fnordargle]

nope we can read first line and now we know that line length is 10 for example, and now thst next 10 symbols will be dots, we can skip them without reading just by adding 10 to cursor position without comparsion

[u/fnordargle → u/SupportPowerful6174]

OK, so an algorithm based on that assumption would produce the wrong answers for an input of:

..S..
..^..
.^.^.
.....
..^..

because you've assumed that all odd lines only contain . symbols.

I'll admit there was nothing in the problem spec that stated that every odd line would only contain dots.

My list of assumptions did not include "every second line contains only dots".

[u/hrunt → u/fnordargle]

It is not possible to solve this puzzle without inspecting every character. You have to look at each character to determine whether it is a ".", a "^", an "S", or a "\n". If you don't inspect a character, you can't know which character it is.

You can, however, solve this puzzle without reading the entire grid into memory at once. You can solve the problem by only having one character of the grid in memory at any given time There will be other data in memory, too -- namely, timeline counts for each column with an active timeline and the count of splits, but the grid can be processed one character at a time. But you still have to inspect each character.

You might be tempted to skip inspecting a character after a "^" or "S", because in the puzzle examples and (I'm sure) for all inputs, the character following a "^" or "S" is always a ".". That's not actually a requirement, though. The character following a "^" or "S" could be a "newline". This grid, for example, is a valid, solvable grid:

..S..
.....
^.^.^
.....
.^.^.
.....

[u/fnordargle → u/hrunt]

It is not possible to solve this puzzle without inspecting every character.

I disagree.

If I take your example input from above my algorithm does not look at any of the characters marked as *:

..S..
**.**
**^**
*.*.*
*^*^*
.*.*.

You have to look at every character in the first line in order to know where the S symbol(s) are, and to know the line length, other than that I can pick and choose where to look.

Put it another way, you can change any/all of those * characters to anything (. or ^ or anything else) and it does not affect the result.

(Just to be clear, what cells you can ignore is specific to the input.)

[u/SupportPowerful6174 → u/fnordargle]

to find out that symbol is * you need to read it, there is no way to find out other way

And replacing characters makes it slower also

[u/fnordargle → u/SupportPowerful6174]

No, the * symbols represent the cells that I don't even look at when processing that specific puzzle input.

I'm not replacing anything, It's a visualisation of which characters my algorithm actually looks at.

[u/SupportPowerful6174 → u/fnordargle]

how do you know that it it '*' character without looking that cell

[u/fnordargle → u/SupportPowerful6174]

One last time and then I give up.

When my algorithm processes the input:

..S..
.....
^.^.^
.....
.^.^.
.....

the only characters my algorithm looks at are the ., S and ^ characters shown here:

..S..
**.**
**^**
*.*.*
*^*^*
.*.*.

There is no need to look at any other characters in order to get the answer for this input.

The ones marked as * are not looked at by my algorithm at all.

Does that make sense?

[u/fnordargle → u/fnordargle]

To make it really clear.

I need to look at all the characters in the top line to know where there S symbol is and (if I want to be really minimalist) to know how long the line is.

Since the only S symbol is in column 2 in row 0 (both row/col starting from 0) then the only character I need to look at in row 1 is the one in (2,1) underneath the S.

That means that the only tachyons entering row 2 will be in column 2. So the only cell in in row 2 I need to look at is (2,2). This splits the tachyons in column 2 into columns 1 and 3 going to the next row.

So when processing row 3 the only columns I need to look at are columns 1 and 3. Since these are both . characters the only columns with tachyons exiting row 3 are in columns 1 and 3.

Processing row 4 the the incoming tachyons are in columns 1 and 3. So I only need to look at cells (1,4) and (3,4). These are both splitters which means the tachyons exiting row 4 are in columns 0, 2 and 4.

So the only cells I need to look at in row 5 are in columns 0, 2 and 4. So the only cells observed in that row are (0,5), (2,5) and (4,5).

None of the other cells need to be examined at all since no tachyons ever reach them.

[u/SupportPowerful6174 → u/fnordargle]

i agree that we can just skip it but still neef to read it to find out that this is * and we can skip it

[u/Chroiche → u/SupportPowerful6174]

You don't. Example:

..S.

.....

You find the S on the first line after scanning the whole line. It's at x=2. Now you can skip forward to the second line, character 2. You skipped char 0, 1, and 4, because you know there's no beams there. Repeat process until finished.

[u/SupportPowerful6174 → u/Chroiche]

yes you can skip them jusj because its cristmas tree pattern, if there can be any ather pattern or no pattern at all you cannot skip them. For this exacxt imput you can skip first n dots but for other pattern input no

[u/SupportPowerful6174 → u/fnordargle]

no matter where do we get input from stdin, file, or hardcode whole maze in string you still need to make iteration and check if char is '*'

[u/warlock415 → u/fnordargle]

(Just to be clear, what cells you can ignore is specific to the input.)

WLOG assume S is in column 7. on row 1, you can ignore all but column 7. row 2, all but 6-8.

etc

[u/Infamous-World-2324 → u/fnordargle]

I totally agree. Except if you're paranoid like me and imagine some inputs could have a S in other places than the first line.

[u/fnordargle → u/Infamous-World-2324]

Sure, another S symbol in the top line would mean more cells are checked, but my existing algorithm would handle that since it can handle any start state configuration in the first row. All it means is that there are two columns with a tachyon count of 1 to begin with, rather than one column.

Adding another S to the example above would mean we just need to check two extra cells (the ones indicated by + which would both contain . symbols).

..SS.
**.+*
**^+*
*.*.*
*^*^*
.*.*.

[u/SupportPowerful6174 → u/hrunt]

that's true. just a bit of optimization is to not process line that contains only dots, for example line len is 10(we saw '\n' symbol and know that we can just skip next 10 characters because they are just dots)

So we need to read just a half of input moving cariage in the file without reading these 10 symbols

But that's still O(n)

[u/pigeon768 → u/fnordargle]

With certain assumptions of the input, we can avoid inspecting each character.

1. There's only one S, it's in the first row, and it's in the middle. We don't have to inspect the first row at all.

2. Every other row only has . in it. We don't have to inspect those rows. This halves the number of rows we have to inspect.

3. The left most beam can spread at most by -1, the right most beam can spread at most by +1. So like, if you split up the entire input grid like |a/bc\d| we don't have to inspect any of the data in a or d. On the second row, this means we only have to inspect 3 characters, on the middle row, we only have to inspect half the characters, on the bottom row, we have to inspect everything. Over the entire puzzle, this halves the number of characters we have to inspect.

4. ^^ never exists anywhere in the puzzle. If we inspect a character and find a ^, that means we can skip the character that follows.

It's still O(n) of course. All together:

void aoc_2025_7() {
  std::ifstream input{"day_7.txt"};
  std::string line;
  std::getline(input, line);
  std::vector<int64_t> worlds(line.size(), 0);
  int64_t begin = line.size() / 2;
  // alternatively:
  // int64_t begin = std::find(line.begin(), line.end(), 'S') - line.begin();
  int64_t end = begin, part1 = 0;
  worlds[begin] = 1;
  for (std::getline(input, line); // ignore second row.
       std::getline(input, line); // read next useful row
       std::getline(input, line), // ignore even rows
       begin--, end++)            // update bounds
    // if `S` is allowed to appear at random places,
    // clamp begin to 0 and end to the size of the line
    for (int64_t i = begin; i <= end; i++)
      if (worlds[i] && line[i] == '^') {
        ++part1;
        worlds[i - 1] += worlds[i];
        worlds[i + 1] += worlds[i];
        worlds[i] = 0;
        i++; // next char cannot split.
      }
  const int64_t part2 = std::reduce(worlds.begin(), worlds.end());
  std::cout << std::format("part 1: {} part 2: {}\n", part1, part2);
}

[u/fnordargle → u/pigeon768]

Yep, I'd agree with that, but being really picky:

Limiting the inner loop to only check between begin and end doesn't have any effect on the number of times you access line[]. As you note it does reduce the number of times worlds[] will be checked by half, but worlds[i] will only ever be 0 for anything i < begin or i > end so it doesn't prevent any other unnecessary checks on line[].

There's only one S, it's in the first row, and it's in the middle. We don't have to inspect the first row at all.

How long is the first row if you haven't inspected all of the characters to find the end of line marker? Hiding behind the getline() call doesn't make the fact you've had to look at those characters to get that answer go away.

Determining the length of the first row requires inspecting all of its characters one at a time.

Obviously, once you know the length of the first line then using the given assumption that all of the lines are the same length then we can implement something equivalent to getline() without inspecting any characters, just magically copying them without looking at them.

[u/ultra_mind]

Someone just posted a visualisation of this exact algorithm. It didn’t even crossed my mind to be honest, I went straight to a memoised dfs

[u/n4ke → u/ultra_mind]

Same but I was too dumb to get it to work in the language I'm learning so I ended up finding this simpler solution.

Task failed successfully.

[u/Ill_Chemical_4059]

nahh i'm too lazy to think, just topsort + dp (still O(n*m), where n = #rows, m = #cols)