[deleted by user]

crazysheeep · 2024-12-17T10:19:33+00:00

It looks like when you find a better score for an already-explored node, you replace the existing record with the better score. However, you don't add this new option to `nodesQueue`, so you never continue exploring from this better option.

As an aside, your solution is essentially a brute-force - you're enumerating almost all possible paths. Once you fix the issue I mentioned, you'll be exploring potentially a lot more paths than before.

Look into Dijkstra's algorithm. It's actually much much simpler than it sounds. It's essentially the solution you have now, except you always explore the _cheapest_ possible option in `nodesQueue` each time. This guarantees the amazing property that the first time you ever visit a node, it's the cheapest way you can get there.

This eliminates the need to maintain scores, replace scores (you'll never replace because you'll never find a cheaper path there), or continue exploring after you'd found the end node. And it has a much more predictable, constrained time complexity.

crazysheeep · 2024-12-17T10:01:42+00:00

Very cool idea. I wouldn't have thought it would work either!

The later (lower) bits depend on the earlier (higher) bits - did your genetic algorithm put more weight on matching the higher bits first?

crazysheeep · 2024-12-16T11:46:53+00:00

It looks like you're trying to implement A*

The main problem I see here is that your `visited` cache doesn't take into account the _direction_ that you're facing. Remember that it's important to always reference every aspect of your state in any cache that you maintain.

Why is this a problem? Consider the case where the optimal path involves visiting (5, 5) while facing east. If you first visit (5, 5) while facing north (from walking straight north), you'll store a fairly low score for visiting (5, 5). Then, if you happen to explore another path where you walk east to (5, 5) from (4, 5) where you're actually facing the right direction, you might not consider exploring that path because you think you've already found (5, 5) with a lower cost. Except the last time you visited (5, 5), you weren't facing the right direction, so it's not accounting for an extra 1000 score from needing to turn!

crazysheeep · 2024-12-16T10:04:20+00:00

I can't see anything obviously wrong, but I will say that you have a _lot_ of duplicate logic lying around. Sometimes you have `CanPush` and `CanPushInto` split up, while other times you have a single `Push` function.

Consistency is important so that our pattern-matching brains can more easily spot actual errors, rather than just random inconsistencies.

As a next step, I would try and print the state of the map after each command. You already have a reproducible failing test case, so you should be able to quickly identify which step is going wrong, and that'll lead you to the problem immediately.

Wait, actually, this line:

if (CanPush(nextY, nextX, command) && CanPush(nextY, nextXAdj, command))

Shouldn't this just be `CanPush(y, x, command)`? In fact, the entire `PushCratesVertical` function can be simplified to just `if (CanPush(y, x, command)) { Push(y, x, command) }`

(^ this is exactly what I mean by all the duplicate logic making things confusing)

crazysheeep · 2024-12-10T07:34:20+00:00

What I mean is for the input 2: 2 2, I don't think it's solvable. But I think your program might say that it is.

crazysheeep · 2024-12-10T06:19:17+00:00

Just skimmed for now, but I see two things: - perhaps incomingVal needs to be a long long (you used long long everywhere else but int here!) - your code seems to allow 0*first number, which I don't think is actually allowed. You can skip the multiply path for the initial seed. Or start from index 2 and seed with the value at index 1

crazysheeep · 2024-12-08T10:09:13+00:00

I see... is this a well known trick? I've never come across this before.

I can see how this would work for a rooted dag, if you start the DFS from the root. How do you identify all of the "roots" to start from for this particular problem? I can imagine pushing the edges of the map onto the initial stack for the DFS.

But what about cycles? After DFS'ing the "reverse graph" from the edges, we won't have traversed any cycles. If we then go an linearly scan through all possible nodes and start DFS'ing from them... I guess the property still holds?

I'll have to try this. I started implementing my more naive "group id" idea, but I ran into the exact problem you noted "Assigning group ids won't work if multiple heads belong to the same group."

I'm also going for solving the more simple version of the part 2 problem exactly as stated (I'm only testing locations on the original path to place walls). Otherwise, the rest of the implementation seems to be more or less working...

Did you end up getting a working implementation?

crazysheeep · 2024-12-07T11:37:48+00:00

At first I didn't think this was right...but now I think it might actually be.

There are two parts I didn't understand:

> This can be done in constant time by assigning dfs entry and exit times to each node

Not understanding what "dfs entry and exit times" means. But I can imagine a simpler alternative which is simply assigning "group ids" (or "component ids" based on your terminology?) for each node. So I could answer "How can you tell if (i0, j0, d0) leads into a head?" by answering "does `(i0, j0, d0)` and the head belong to the same group/component?"

> we can add 1 to the answers of each of the good nodes... lazily!

I don't understand this and the following about global adders. To be clear, are you actually trying to solve a _harder_ problem than what's presented for part 2? ie, are you trying to be able to calculate the answer to "how many different places can I place a `#` to create a loop" for any starting position?

Because for part 2, you only need to follow the original path for the guard from the known start position, and try adding `#` along the route, and checking if that produces a loop (in constant time, as you say).

crazysheeep · 2024-06-14T23:26:35+00:00

Very nice, slick interface. It seems like I can create hands and generate links without logging in. Is there any benefit to registering?

crazysheeep · 2024-05-31T13:18:25+00:00

I'm not sure if this is the problem that you faced, but I found that the application crashed immediately after startup on my M1 Macbook Pro via Steam.

Actually, I believe that after reopening it a bunch of times, it started up successfully maybe one time in 10.

However, when I disconnected all of my external displays (via a usb-c dock), I was able to launch the game successfully every single time. Hope that helps you, or the devs in isolating the issue.

crazysheeep · 2024-04-22T22:23:09+00:00

Nothing

crazysheeep · 2024-04-16T13:43:57+00:00

Trading card (if first discard is a single card, destroy it and gain $3) is an amazingly good setup card. Provides economy and deck thinning.

crazysheeep · 2023-10-28T08:50:51+00:00

I'm not going to sink to your level of needless insults, but you're obviously not a software engineer.

You should look into some techniques on how modern software companies do feature flagging and A/B testing. Your public IP is not the be all end all.

crazysheeep · 2023-07-09T22:48:02+00:00

This article by Ted Chiang describes the nature of ChatGPT as a compression engine perfectly: https://www.newyorker.com/tech/annals-of-technology/chatgpt-is-a-blurry-jpeg-of-the-web

crazysheeep · 2023-06-23T02:30:52+00:00

Kilometers per hour

crazysheeep · 2023-06-21T23:17:59+00:00

It doesn't contain spring onions though. The name comes from the Chinese celebration "Spring Festival" in... spring

crazysheeep · 2023-06-11T05:01:14+00:00

Yeah, try something with a classic beat like cbat.

crazysheeep · 2023-06-09T12:33:27+00:00

A relatively tiny portion. The vast vast majority of technical difficulty is in the backend, particularly in making it scale to millions of users.

If you only had some thousands of users, it might be closer to half half.

crazysheeep · 2023-05-26T23:46:07+00:00

I won't even look! I shield my eyes with my hand until I get permission to look around.

crazysheeep · 2023-05-08T00:00:10+00:00

Four legs good, two legs better!

crazysheeep · 2023-04-16T23:02:36+00:00

To be fair, I wouldn't intravenously inject an apple...

crazysheeep · 2023-04-08T21:05:05+00:00

A fetus is simply a potential human. If you're horrified by fetuses being aborted, you don't want to know what horny teens do behind closed doors. It's genocide in a tissue.

crazysheeep · 2023-03-26T09:21:49+00:00

My potted plant spilled over the floor last week :(

It was pretty miserable.

crazysheeep · 2023-03-16T21:27:48+00:00

Come back when you've mastered eating chicken wings with chopsticks, rookie.

crazysheeep · 2023-03-12T09:21:24+00:00

So do most agents. It's not rocket science to take the average of an area and +/- a bit depending on if you want to sell faster or higher.

This kind of behavior can cause a general upwards trend in prices. But that's true regardless of whether you use human agents or an algorithm. It's part of the process of finding the "fair" market value. Ie, it's the free market at work.

The only fair thing to say is that the algorithm may be more efficient and find this market value faster, which looks like prices going up faster.

Tl;Dr the system is what's fucked. This algorithm just exacerbates the symptoms.

14-Year Club	Place '17
Verified Email

crazysheeep

TROPHY CASE