2 kyu
Wumpus world
68 of 105FArekkusu
Loading description...
Artificial Intelligence
Algorithms
Game Solvers
.avif)
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
Very Very Enjoyable Kata, i enjoyed i a lot while solving, but i think it should be ranked as 1.
This comment has been hidden.
You need to know Wumpus's exact location to shoot it
How it can be False?
The agent cannot go past (2, 2) because they dont know whether wumpus is at (3, 2) or (2, 3).
I mistranslated the terms. Many thanks!
I fail to understand how this one could be True:
_ _ _ _
_ P _ _
_ _ _ _
_ W _ G
The agent feels the wind in (0,1) and (1,0), but pits could be at (2,0) and (0,2).
but there is one single pit, so it cannot be anywhere else than at (1,1)
I missed the point that I know the number of pits
Great kata!
Just to clarify, what exactly is meant by the agent "finding" the gold? Have they found the gold a) once they know where it is or b) once they've entered that room?
(As can easily be seen from this example
it may be possible to do a) but not b).)
Does the Wumpus cease to emit its odor once slain?
yes
I'm not sure I understand how this is false. The kata is very interesting, but I don't understand this one case. Here is my understanding so far: if you know there are 3 pits, you can safely move to 0,1 where you smell wumpus, 1,0, 1,1 where you get wind from a pit, but then you don't know if that pit is 1,2 so cannot move to 1,2 to smell wumpus again and kill him. You can also move to 2,0, where you can get wind from another pit, but as you know there are 3 pits, you cannot be sure that the wind is coming from a pit at 2,1 (when mixed with the wind from 1,1) - it could be pits at 1,2 and 3,0, so you cannot safely move from 2,0. How do you get enough information to get the gold?
At (0,1) you smell Wumpus, but you also went (1,0)->(1,1) with no sign of Wumpus, so you know Wumpus has to be on (0,2). You can kill it and continue through the north. Continue your quest from there ..
Ok, I'm late to the party -> same as what Madjosz said (but his coords are reversed)
Strange. I got the first one wrong and then oriented on that style...
Looks like a mistake
Expected: False
Markdown has made your message pretty illegible. Can you post again, but put it inside a code block?
```
write here
```
Sorry, this is my first time xD
I believe it is correct. I'll try explain the logic: consider the map, with some additional markers added by me:
1you can identify pitP2you can identify pitQHowever:3you feel wind, but that might just be coming fromP, you are unsure if there is also a pit atR4you can feel wind and smell Wumpus. But the wind might be just coming fromQ, so you cannot identify R, but you can identify Wumpus atWand shoot him.5, you feel wind again, but you cannot be sure where it is, is it atR? or in the corner? Since you cannot be sure, you cannot reach the exit.Thanks for the answer. Yes you are right)
Does Agent know that the cave is 4x4 and his start position is 0,0?
...just read the description? ;)
It doesn't actually say whether the agent knows this, however its also irrelevant. Either the agent eventually finds the exit, or not.
Javascript translation
.
C# Translation
@monadius, you're the only one that solved this kata that I know of can handle C#. Could you review this translation?
approved
Hey guys, can someone give me a hint on this one? I've been trying it for quite some time. I'm using a BFS, but at this point I'm not quite sure if this is a good approach. A DFS would be any better?
Edit: scrolling down I saw my old post, from 6 months ago, hahah wow
it's a 4x4 grid, neither BFS nor DFS should time out, but naive searching will :)
So I guess I'm missing how to create the sensors database for the agent, and how to query it properly.
I fail to see how this one is
TrueEDIT: I'm starting to wonder if I didn't forget to update properly the expected output, so surely they actually expect False...?
They both expect False.
'kay, thx
My solution (and a few others I tested) expects
Falsefor this.Edit: Oops too slow
the random tests must be splitted into smaller batches (more of them)... I'm currently facing this:
And I cannot FU..ING FIND the failing tests because the output panel isn't showing the whole console, now that kazk made it "lazy loaded"... x/
split into batches
'sure the changes got published? I don't see any diff, even after I reseted the kata
working now, thx
What an excellent kata! For the life of me I can't see why this test is true:
You can move to squares (0,1) and (1,0) but you can't tell anything after that can you?
At (1,0) you smell the wumpus and feel the wind of a bottomless pit. But you don't know which is which - so you can't do anything.
At (0,1) you feel the wind of a bottomless pit. But again, you don't know whether it's down or right - so you can't move any further.
And you can't use the knowledge that both of those squares feel windy, because there could be pits at (0,2) and (2,0). With the wumpus at (1,1).
A hint would be appreciated :)
the (1,0) implies that W is either at 2,0 or 1,1. When you feel the wind at 0,1, W cannot be at 1,1, so you can shoot it at 2,0
There is a problem with the tests and this needs to be corrected, such as this card:
I move down first.
The pit could probably be in the dots: (2, 0); (1, 1). Then I start moving like this:
The pit can be at points: (2,0); (2,2); (3,1).But now I know that the point (1,1) is beyond suspicion, because I visited it from the point (0,1). Consequently, I can try again to go from the point (1,0) and now I can definitely say that the pit is at the point (2,0). After that I mark that (2,0) is the pit and pass to the gold. Since I can now feel no wind at (2,1)!
Hi - I haven't solved this yet, but just started a notebook on it yesterday and making some early notes (I don't yet know how to solve).
But I think you are incorrect in your final reasoning: remember you are a "local" agent you don't have a global view. I think your reasoning about one pit being located at (2,0) is correct at that point, but then you say "Since I can now feel no wind at (2,1)" - this is incorrect AFAICT.
Why? At this state of knowledge you have accounted for 1 pit only. There are up to 3 pits possible in the grid. Therefore it is entirely possible that there is a Pit at (2,2) which also produces wind to its left, at (2,1), which "overlaps" the wind produced by the Pit at (2,0).
Similarly there could be a Pit at (3,1) which produces wind upwards into (2,1). Again, knowing that (2,0) is 100% sure to be a Pit does not allow you to rule out Pits in (2,2), (3,1).
A simpler illustrative example:
P _ Pin the above configuration, if you detect wind in the empty cell
_, and an Oracle told you with 100% confidence that there is a pit in (0,0) (leftmost cell), according to your logic it means that the wind at (0,1) "has been accounted for", but in fact the pit (0,2) also produces wind in cell (0,1).Yeah, okay, that makes sense, I'll rewrite the logic, since I was changing the map when I found the pit and it's really oracle help. Thank you.
I had a lot of fun while completing this kata, thank you! I also created a java translation, please review and accept, if you are satisfied with it. Thanks again!
Awesome kata! 👍
-P--
-W--
--G-
----
-P--
----
----
-GW-
Could someone please explain to me why these should be false? Can't the agent get to the gold safely?
in both cases you start feeling the wind of the pits, but you cannot know if it's south or east.
Lol, ty
I completely missed the point, I know that he can reach the gold, but the agent itself doen't know the entire layout of the map.
.
Looks true to meOK, it's false.The first sample test breaks the rule that there will always be
1-3pits.The first test was supposed to reprent a case where the only obstacle is Wumpus which must be identified to proceed further, and I forgot to add a random pit somewhere. Now it's correct.
Excellent kata, I had much fun! At least 3 kyu in my book.
@author: Are there already many attempts at this? Perhaps this kata is harder than initially thought. I'm trying to assess a correct difficulty level.
What do you mean? You can see
Warriors TrainedandTotal Code Submissionsstatistics for any kata (23 and 188 here, respectively).Oh really, I didn't know this, thanks.
3 pits still buggy:
Random test case expects False, but is True
if you need more details about the pathing, let me know
This and another bug are now fixed. I've run a huge amount of tests against your solution and none of them have failed, so everything should be fine now.
fixed
Why so many random tests? Is it meant to be a performance kata (tag needed), or are you hoping for sufficient variation in edge cases this way (perhaps a smart/biased random test generator should be provided, if feasible)? I'll log as issue, as either way, action should be taken.
This. Ideally, every possible input should be tested but that's infeasible since debugging would be impossible and this would add unwanted performance requirements (there are ~80,000 unique matrices and IIRC ~12,000 of them are a transposed version of a different matrix which leads to ~68,000 unique situations). Implementing a smart input generator would be incredibly hard, and even then I doubt it would provide very good test coverage. Having a few thousand "simple" tests seems to be the best choice IMO, and I don't see what can realistically be done about this.
I was afraid this would be the only feasible option. Unless someone comes up with a revolutionary method, I consider it solved.
Random test case expects False while it should be True:
This has been fixed, and I think that my solution should now be correct for all cases with 2 pits. (3-pit cases are likely to be buggy, but that would be a separate issue.)
fixed 1 and 2 pits
One sample test is bugging me:
I can take a step down, sensors for W and P go off. I can take a step right, sensor for P goes off. Since there are two pits and no location for W or any of the P can be determined (or can it?), what next move is there to make?
never mind, I found out, when going to the right, it forces W to be in the south.
But the text is : a wind sensor which signals about the presence of a bottomless pit in any of the neighboring rooms
and an answer after : No, the number of pits doesn't affect the sensor's output. Using it is equivalent to asking "is there at least 1 pit around me", exactly as you say at the end.
So : if going right, how to detect the direction of the pit ? As the sensor say only "at least one pit around". And going right and up, the sensor say pit around for both, but the situation is the same as for :
"--P-"
"----"
"P---"
"----"
so, after right/down move is not possible to detect a safe move.
This possibilities of Down and Right forces W on (0,2) and P on (1,1). So you can safely move to (0,1) and (0,2). If W could be on (1,1), Right would have sensor W on, which is not the case, so only (0,2) remains possible location for W.
Does the wind sensor measure intensity? In other words, does the agent know how many neighbouring pits there are for a given cell (when the sensor measures something), or just there is at least one?
No, the number of pits doesn't affect the sensor's output. Using it is equivalent to asking "is there at least 1 pit around me", exactly as you say at the end.
Am I missing something about why the second test case is false?
It seems to me that the agent could move to
(0, 1)and(1, 0)safely, and then, knowing that there's only one pit, determine that(0, 2)is safe (and from there progress to the goal).You're right. I originally wrote my code (which may still be buggy) to work with
2pits and forgot to change the logic to handle this special case. Tests and reference solution were fixed.The number of pits is not known and is 1-3 (according to rules). Or I'm missing somethig ?
you can count them in the input, so you know their number
Reference solution fails for
Actual result =
True, Reference solution result:FalseTrue/real pit locations, in this test case, can be inferred from wind signature and number of pits.
After reaching
(2, 2)you learn that Wumpus is either inside(2, 3)or(3, 2). The only way you can move forward is by taking a guess which direction to throw the spear. This contradicts the rules:Oops, sorry.