4 kyu
Area of House from Path of Mouse
92 of 140docgunthrop
Loading description...
Strings
Puzzles
Algorithms
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.
Calculating the area was the "easy" part, compared to covering all the invalid path scenarios, especially properly handling the mousehole.
In the test example:
Looking at the picture, there is no consistency in moving forward. It appears, sometimes making a turn counts as moving forward, and sometimes not. What is this format?
Making a turn doesn't count as moving forward. In the test case you provided, the steps are move forward 4 units, turn right, move forward 2 units, turn left, move forward 1 unit, turn right, etc.
move forward 4 times, then the mouse is inside the wall on that pricture
I think your misunderstanding is thinking of the mouse being placed in the squares (like in chess) but the mouse should actually be thought of as on the lines (like in Go). The mouse starts exactly on that K, and moves 4, and ends up exactly at the next corner. There it turns right, and moves two, ending it exactly at the next corner, etc.
This is crucial information to understanding this kata, thanks.
When trying to run a full test suite I keep getting "DeprecationWarning: Sampling from a set deprecated". I'm not even using any sets in my solution, only lists and a dictionary.
This warning originates from the test suite, where random sampling from a set is performed. In the latest python version, this is a deprecated feature.
A fix is in order.EDIT: a fix ha already been published.I find it near impossible to check for invalid paths of the "C" type. One thing i tried to do is to document the coordinates of EVERY point I visit (not just corners), but it takes a while to process. Also, it looks like this website intentionally slows things down. Even the bruteforce solution runs pretty fast on my system, but here it times out after just 1 test.
Well this is strange. For me, it was not only posible to check for invalid paths of "C" type, but also the site did not seem to intentionally slow down anything for me. Interesting. At some point, the site apparently went malicious.
At least you understand the description, I can't make anything of those "invalid paths" cases. When I follow the directions from the mouse's position, I end up inside walls or outside the frame.
You forgot to turn off wallhack. Git gud.
Hi again,
Would be cool to have this in the fixed tests (both in test cases and sample tests):
"2R4R4R4R2". There are no fixed tests for now that checks that a mouse hole on a straight line of a valid path is considered invalid.Cheers
EDIT: btw, why this restriction??
That particular fixed test was included in the full test suite, not in the group of fixed tests run at the beginning, but as part of the fixed tests that get mixed in with the random tests (look for the section where this comment shows up:
# 13 MORE FIXED TESTS -- to be randomly comingled w/ randomly-generated tests).Seeing as how this level of detail can sometimes be overlooked, I've taken up your suggestion and added it to the sample tests as well. This should make it more clear for users at the onset of tackling this kata.
I added this restriction because, in my opinion, it adds to the challenge in a purposeful way without overcomplicating the concept of the task.
Ah? I just had to add the
if dx and...in the last line of my function, to switch from one behavior to the other, actually. :oAnyway. ;)
Hi doc,
I just stumbled on this, in python:
Seems like your generator is failing in some situations?
EDIT: it happens that the random tests go into an infinite loop too, from time to time (or at least, they cause a time out)
Hi B4B,
While debugging the random test generator, I did come across a very rarely-occurring error which I think is the same one you've encountered. But the error occurred very rarely, about 1 in 10_000 random tests (or 0.01%) when I ran it.
How often did you encounter bugs with the random tests?
yes, it's pretty rare. I got this error just once. Timed out 1 or 2 times accross something like... dunno 30-40 tries?
To clarify, it was back last year while this kata was still in beta when I had done the debugging. The random test generator was an ambitious endeavor and the most laborious part of writing this kata; it's got a lot of moving parts and, quite frankly, finding this rare bug will be like finding a needle in a haystack.
No bugs is better than one, but, considering how rarely it occurs and how much effort it would take to fix, I've accepted that this bug will exist so the issue will just remain unresolved (at least for now).
ok, sounds reasonnable.
Last question would be: do we keep the issue opened? (I guess if we don't, you'll see it pop up from time to time, but your call)
It's a tough call; the bug does exist, but given how rarely it occurs it's practically a non-issue. Maybe it'd make sense if I were to add a note to the Description so users are aware?
sounds good yes. Closing, then.
Thanks, I've added the note to the Description.
This is quite a nice Kata, capable of surprising you just when you think you've nailed it. :) Congrats to the author!
Happy coding! 😎✌️
I am having a problem runnning my result... The execution runs out, and I think it's because of the exmaple_test('1000000R1000000R1000000R1000000',1000000000000) Anything yoiu suggest I do? I am aware my algorithm isn't optimized, but it was calculating everything perfectly
Hey, guys and especially the author, case 2R4R4R4R2 - is normal case, so please review it , so it must be 16, but test says - null.
It's that case.
Ash Tree Lane, poor mouse
Have you read the book? You may notice some themes included in this kata (besides the obvious amorphous nature of the house) such as the encompassing blackness in the diagram images.
I finally did it!
pretty hard kata for 4kyu isn't it or I am just a noob?
I'd say 3 or 4, but everybody's got their opinions.
Thank you for this tough problem. I've been stuck with it for some time, and it's interesting to tackle this. At last I've done it. It's been the trickiest one so far.
This comment has been hidden.
I don't consider this a performance-focused kata. My solution completes in about 2 seconds or less and, while it's written with some optimizations, it has room for even more efficiency.
The primary focus of this kata is to find an algorithm that returns the correct answer, but you'll still want to find ways to avoid unnecessary/redundant computations.
Woah! So I finally did this.
Looking at the solutions. I think I get the wooden spoon for the solution which is the longest and messiest!
:-)
Issue: 500 Turns?
First off, a real fun challenge. Good Job. I'm new to codewars so still a noob.
Description says "K's path will always consist of fewer than 500 turns"
I failed a test with a token list of 2179, so over 1000 turns, but it wanted a length not None.
Am I missing something?
Thanks for flagging this issue. JS and Python translations have both been revised and now all test cases should have fewer than 500 turns.
Groovey. Thanks for the update. I'm not quite there yet, pretty close I think.
@doc: you have PMsssss on the gitter channel. Plz check! ;)
Update to random tests: there will be a few more random invalid tests provided. And thanks to folks for your helpful comments 👍
Approved
Cheers! 🖖
This solution is incorrect but it passes all tests without any problems. It does not check if the path is closed if the number of path segments is even (e.g.,
10L10). Please add tests to invalidate this solution.Nice catch! Added the edge case to the tests, revised the reference solution and updated kata description. A few solutions, including that one, have been made invalid.
No fixed tests related
You may consider add cases like
2R4R4R4R2, where the reference solution will failThanks for the suggestions.
But that 7kyu ranking? Classic ZED...
Haha :laughing:
At least 5 or 6 kyu :wink: That's ZED's normal reaction. At least he upvoted this one :relaxed:
A nice challenge and a very nice description! Kudos, @docgunthrop
Here's a function for visualizing the "house".
@docgunthrop: You can remove the "spoiler" flag if you want.
Well done and congrats on being the first,
@siebenschlaefer! I went ahead and removed the spoiler flag; it doesn't spoil the kata and others would surely appreciate it 👍EDIT: looks like I don't have the ability to remove the spoiler flag, so feel free to do so.
Looks like you got another hard one :smiley:
This one should be easier to solve than the last one (Folding Tiles Solver). The biggest challenge (for me) in getting this kata done was writing a random test generator that I was satisfied with.
When coming up with kata ideas, I tend to lean toward a problem that's simple to understand but challenging to solve. Looking forward to seeing some brilliant solutions, folks!
Yes, this one looks easier. No one has solved it yet tho
Probably too hard for me too.
It's still a new kata, but I predict someone will solve it in the next day or two. Probably ZED.CWT.
Yeah, he's very often the first one to solve something. Or at least some power user will probably be first
Two stars, that means 2 people bookmarked it to solve it later.
What's the difination of overlap? Like, are these valid?
For this kata, overlap is when any part of a path is met more than once. Below are three examples:
10R10L10L10L10R10one single point is touched upon twice.20R10R10R20, the path intersects itself.50R10R10R10L20L10, the path overlaps itself (for 20 units of distance).Does this clarify? I didn't use your diagrams as it could create further ambiguity.
o_O
Description updated with examples of paths invalidated by overlap/intersection.
I think the reasoning for the first image is: if cell (1,2) and cell (2,2) are both part of the house, then that's a contiguous space, and the mouse is actually running across an open floor (which it's not allowed to do).
In the second image, the corners of two cells touch, so you have the same "crossroads" form that you could also get from intersecting line segments. Arriving at the crossroads, the mouse COULD politely turn left/right to define a contiguous area -- OR it could squeeze straight through the infinitely tiny corner, loop around the central square, and then cross its own path again. So that shape isn't permitted to exist in the house either.
JavaScript translation to come.
JS translation added