Day 20 - Race Condition | Emulator Development | Page 1

thorny hull Dec 20, 2024, 5:01 AM

#

https://adventofcode.com/2024/day/20

wintry sigil Dec 20, 2024, 5:12 AM

#

Advent of Grids

thorny hull Dec 20, 2024, 5:13 AM

#

grid has a border so I don't need to bounds check
:D
the puzzle lets you go through walls
D:

wintry sigil Dec 20, 2024, 5:14 AM

#

haha getOrDefault go brr

#

if out of bounds return wall and don't worry about it :)

thorny hull Dec 20, 2024, 5:16 AM

#

I could make a mdspan mapping that does that, but eh
if (InBounds(course, pos)) it is

wintry sigil Dec 20, 2024, 5:44 AM

#

I should really write a a premade "walk along this path" function

#

because every time I need to write one I make some stupid bug despite how it should be simple

thorny hull Dec 20, 2024, 5:45 AM

#

glue I wasn't paying attention and solved the wrong problem
I hope I just accidentally wrote part 2

#

digging through my cmake files from last year for stack increase compiler options

#

"right answer for someone else"

#

!@#$%

wintry sigil Dec 20, 2024, 6:24 AM

#

alright part 1 done with a solution that I think is fairly decent

thorny hull Dec 20, 2024, 6:58 AM

#

You gotta be s***ing me

#

||I was stuck for an hour because I was only checking the walls [2:end-2]. I was only thinking about skipping outward/inward and not around.||

thorny hull Dec 20, 2024, 7:43 AM

#

man, off day for me
I got it but I made about a dozen blunders

wintry sigil Dec 20, 2024, 7:49 AM

#

I thought I had something promising but then I didn't

#

I think I can get my solution to work but it's so slow that it's a dead end anyway

#

it'll never finish for the real input

thorny hull Dec 20, 2024, 8:13 AM

#

||```cpp
namespace {

struct Course {
mdarray<int32_t, dextents<int32_t, 2>> courseStorage;
Pos2D startPos{};
Pos2D endPos{};

Course(std::string_view input) {
    const mdspan inputGrid = ToGrid(input);

    const size_t startIdx = input.find('S');
    startPos              = {static_cast<int32_t>(startIdx / inputGrid.stride(0)),
                             static_cast<int32_t>(startIdx % inputGrid.stride(0))};
    const size_t endIdx   = input.find('E');
    endPos                = {static_cast<int32_t>(endIdx / inputGrid.stride(0)),
                             static_cast<int32_t>(endIdx % inputGrid.stride(0))};

    courseStorage = {inputGrid.extents()};
    const mdspan<int32_t, dextents<int32_t, 2>> course{courseStorage};

    for (int32_t y{0}; y < course.extent(0); ++y) {
        for (int32_t x{0}; x < course.extent(1); ++x) {
            course(y, x) = (inputGrid(y, x) == '#') ? -1 : std::numeric_limits<int32_t>::max();
        }
    }
}

void pathFind() {
    const mdspan<int32_t, dextents<int32_t, 2>> course{courseStorage};
    int32_t distance{0};
    Pos2D pos{startPos};
    while (pos != endPos) {
        course(pos) = distance;
        Pos2D nextPos{pos};
        for (Vec2D offset : {Vec2D{-1, 0}, Vec2D{0, -1}, Vec2D{0, 1}, Vec2D{1, 0}}) {
            Pos2D offsetPos         = pos + offset;
            const int32_t maybeNext = course(offsetPos);
            if (maybeNext > distance) {
                nextPos = offsetPos;
            }
        }
        pos = nextPos;
        ++distance;
    }
    course(pos) = distance;
}

size_t cheatCount(int32_t minSkip, const int32_t radius) const {
    const mdspan<const int32_t, dextents<int32_t, 2>> course{courseStorage};
    size_t count{0};
    for (int32_t y1{1}; y1 < course.extent(0) - 1; ++y1) {
        for (int32_t x1{1}; x1 < course.extent(1) - 1; ++x1) {
            const int32_t start = course(y1, x1);
            if (start < 0) {
                continue;
            }
            for (int32_t y2 = std::max(0, y1 - radius); y2 <= std::min(y1 + radius, course.extent(0) - 1); ++y2) {
                const int32_t yDist   = std::abs(y2 - y1);
                const int32_t xRadius = radius - yDist;
                for (int32_t x2 = std::max(0, x1 - xRadius); x2 <= std::min(x1 + xRadius, course.extent(1) - 1);
                     ++x2) {
                    const int32_t taxicab = yDist + std::abs(x2 - x1);
                    const int32_t saved   = (course(y2, x2) - start) - taxicab;
                    if (saved >= minSkip) {
                        ++count;
                    }
                }
            }
        }
    }
    return count;
}

};

} // namespace

void AocMain(std::string_view input) {
Course course = StopWatchstd::micro::Run("Parse", Constructor<Course>{}, input);
StopWatchstd::micro::Run("Pathfind", &Course::pathFind, course);
logger.solution("Part 1: {}", StopWatchstd::micro::Run("Part 1", &Course::cheatCount, course, 100, 2));
logger.solution("Part 2: {}", StopWatchstd::micro::Run("Part 2", &Course::cheatCount, course, 100, 20));
}

Could definitely make part one faster but it's too late in the night

lilac crag Dec 20, 2024, 12:27 PM

#

thorny hull >grid has a border so I don't need to bounds check :D >the puzzle lets you go th...

those were exactly my first two thoughts xD

normal remnant Dec 20, 2024, 2:11 PM

#

thorny hull ||```cpp namespace { struct Course { mdarray<int32_t, dextents<int32_t, 2>>...

https://github.com/Redcrafter/AdventOfCode/blob/master/c++/2024/day-20.hpp

normal remnant Dec 20, 2024, 2:11 PM

#

thorny hull ||```cpp namespace { struct Course { mdarray<int32_t, dextents<int32_t, 2>>...

i'm basically doing exactly the same.

thorny hull Dec 20, 2024, 2:31 PM

#

Really feels like there should be a better way but when I saw that it was only ||20|| I figured this would be easily fast enough.

normal remnant Dec 20, 2024, 2:35 PM

#

there is another option which i haven't tested || since the path is just a straight line it's possible just to check all valid positions against each other. these checks would probably get vectorized very well ||

thorny hull Dec 20, 2024, 2:36 PM

#

Ah hmm, could work

delicate jasper Dec 20, 2024, 3:19 PM

#

Weird day. The second time we've seen ||"day 16 but easier". The first time being day 18.||

wintry sigil Dec 20, 2024, 3:19 PM

#

took a break from this for a while and came back and solved it

#

after realizing that ||my part 1 literally solves part 2, all I had to change was un-hardcoding the distance and making a function to generate a "diamond" of neighbors||

delicate jasper Dec 20, 2024, 3:20 PM

#

yep, just went through the same deal

umbral idol Dec 20, 2024, 3:54 PM

#

thorny hull "right answer for someone else"

I've gotten this before and it's such a funny message to get. It's like, thanks? Doesn't really help me. I guess maybe it's a deterrent to try and push you away from taking answers from other people?

wintry sigil Dec 20, 2024, 4:44 PM

#

here's a visualization of today's part 2

vestal veldt Dec 20, 2024, 6:31 PM

#

omg, totally misread today, I did part 1 so you can remove any 1 wall at any one time - slow, but OK it worked and I got the right answer, then saw part 2 and thought it meant ||you can remove ANY 10 walls ffs|| - I'll have another go later, as I've completely messed this up lol

#

I literally did part 1 by ||running a loop across EVERY wall, removing it, getting a path, then putting the wall back|| 😄 I mean, it worked...

#

in my defence, I did read the puzzle while at work, so I was quite distracted

#

also totally missed this bit there is only a single path from the start to the end

#

wow, not sure I couldn't have gotten this more wrong if I'd have tried 😄

umbral idol Dec 20, 2024, 7:43 PM

#

I had originally solved part 1 with the assumption that it was a maze, then noticed that "single path" bit

#

which sped up the solution quite a bit

urban junco Dec 20, 2024, 9:25 PM

#

how difficult is day 20? i missed the midnight start line and i'm burning out a little bit 😬

delicate jasper Dec 20, 2024, 9:40 PM

#

urban junco how difficult is day 20? i missed the midnight start line and i'm burning out a ...

I found it similar to day ||18|| and easier than day ||16||

thorny hull Dec 21, 2024, 1:19 AM

#

Reading comprehension challenge. Doesn't seem so complicated after finishing it.

vestal veldt Dec 21, 2024, 6:26 PM

#

finally got round to cleaning up my code for this

#

I did get part 1 in a few minutes, albeit in a very roundabout way, but part 2 was waaaay wrong as I misread the Q 😄

#

all done now

#

well, I say a few minutes for p1, it was quite a few lol

#

urban junco Dec 23, 2024, 2:22 AM

#

is it possible to "cheat" through a corner in multiple paths?

#

or is cheating more of: hit a wall, then keep traveling in the same direction?

#

#######
#...#.#
#S#.#.#
###...#

like here.... we could cheat from S heading rightward, then move upward as one path

#

but also we could cheat rightward, through the wall and continue righrward to the path

#

those are technically 2 unique paths going through the same wall piece

thorny hull Dec 23, 2024, 2:34 AM

#

Yeah →↑ is valid

urban junco Dec 23, 2024, 2:37 AM

#

What about cheating backwards? from a shorter path to a longer path (making a loop)

#Day 20 - Race Condition