3 kyu
Knight's Attack!
95 of 98rsdah13
Loading description...
Algorithms
Graph Theory
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.
Few randomized tests has incorrect reference value. I can see the this is also reported a few years ago. Why this is not fixed yet?
Ie. the reference return value should be 34 hovever the shortest path is 32.
XXX__XXXXXXXXXXXXXXXXXXXXXX
XXX__XXXXXXXXXXXX____XXXXXXXXX
XXX_______________XXXXXXXXX______XXXXXXX
XXX__XXXXXXXXX__L____L
XXX____________L___L____E____
XX___________L_______L_XXXXXXXXX
_XXX_________L____XXXXXXXXX_XXXXXXXXXXXXX
XXX_______L_______XXXXXXXXX__XXXXXXXXXXXXX
XXX______LXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXX____XXXXXXXXXXXXXXXXXXXXXXXXXXX_
_XX______LXXXXXXXXX________________XXXXXXXXX
XXX_____XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX__XX
XXX_______L____________________________XXXXX
XX_________________________XXXXXXXXX____XXXX
XX_________LXXXXXXXXX___XXXXXXXXX___XXXXXXXX
XXX______________________________________XXXX
XXX__________L__________________________XXXXX
XX___________XXXXXXXXXXXXXX___________XXXXXXX
XX__________L__XXXXXXXXX______________XXXXXXX
XX___________________XXXXXXXXX__XXXXXXXXXXXXX
XXX_________L______XXXXXXXXX_XXXXXXXXXXXXXXXXX
XXX_____________XXXXXXXXXXXX____XXXXXXXXXXXXX
XXX________L_______________XXXXXXXXXXXXXXXXXXX
XXX______________XXXXXXXXX_____XXXXXXXXXXXXXXX
XXX_______LXXXXXXXXXXXXX_________XXXXXXXXX
XXX_________________XXXXXXXXX___XXXXXXXXX__XXX
XXX______L______XXXXXXXXX______XXXXXXXXXX
XXX__________________________XXXXXXXXXXXXX_XXX
XXX_____L___________________XXXXXXXXXX
XXX_______________XXXXXXXXXXXXXXXXXXXXX______X
XXX____L__XXXXXXXXX__XXXXXXXXXXXXXXXXX_____XXX
XXX_______XXXXXXXXX______XXXXXXXXXXXXXXXXXXXXX
XXX_____L___XXXXXXXXX___________XXXXXXXXXXXXXX
XXX_________XXXXXXXXX____________XXXXXXXXXXXXX
XXX______L________________________XXXXXXXXXXXX
XX______________________XXXXXXXXX_XXXXXXXXXX
XX_______L___XXXXXXXXXXXX__________XXXXXXXXX
XX________XXXXXXXXX_________________XXXXXXXX
_XXX_____L________XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXX______________XXXXXXXXXXXX_XXXXXXXXXXXXXX
XXXXXX__L___XXXXXXXXXXXXXXX_______XXXXX_XXXXXX
XXXXXXX___XXXXXXXXXXX____________XXXXXXXXXXXXX
XXXXXXXX_LXXXXXXXXX________XXXXXXXXXX__XXXXXXX
XXXXXXXXX__L___L___L___XXXXXXXXXXXXX____XXXXXX
XXXXXXXXXX___L___L___S___XXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXX__XXXXXXXXX__XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXX_______XXXXXXXXXXXXXXXXXXXXXXXXXX
__XXXXXXXXXXXXXXXXXX___XXXXXXXXXX__________XXX
duplicated issue. It's already known, no need to raise again.
I got it but I'd like to get a reasonable explanation to my question: "Why this is not fixed yet?" Or at least an advice for a workaround. It makes to complete this kata painful.
Normally it should occur very rarely, so it's not an actual problem to pass the kata (~70 completions dealt with this so far)
Now about the "why"... The original author isn't active anymore, and I already spent way too much time on this kata (I'm not talking about solving, there). So yeah, I'm not the one who would fix that, sorry...
edit: if it occurs very often for you, that would mean you're algo is actually incorrect.
Thanks for the info.
Get an error on ruby MRI 3.0.0:
or on tests:
should be good now. Reset the trainer, plz.
some tests 1: start(x, y) dest(x, y) obstacls(x, y)
some tests 2: start(x, y) dest(x, y) obstacls(y, x)
Why?
This comment has been hidden.
Input range should be specified.
I SOLVED IT! GREAT KATA!!! xDD
How do I know the limit in the attack function?
you don't. The board is infinite.
Python: the reference solution may return incorrect results in some rare cases. Here one example:
The optimal solution is
27and the reference solution returns29.Here is a picture corresponding to the test case above:
Ais the start position,Bis the destination,Xis an obstacle. The optimal solution looks like this:Moves are marked with numbers modulo 10.
Interestingly, I get this solution due to the heuristic that I used:
I think this issue is still there.
This comment has been hidden.
Same for me
This comment has been hidden.
late answer, but.... no, it's not the good way to solve this.
Is the board also infinite in the negative direction?
yes. Like... well, "infinite". ;)
This comment has been hidden.
not sure what you actually implemented... 'cause in
_-_ X _ _ _ _ Y for _ _, X and Y seems to be a "contradiction" (somehow) to me. You need something better than "X". Seems you're on the good path, but you need an efficient implementation of it.This comment has been hidden.
This comment has been hidden.
Hey everyone! Is it possible to solve this Problem with BFS? I got all of the right results, but I just can't pass the timing constraints. I'm starting to think I need another faster algorithm or I'm missing something that makes the problem easier.
you're right, you need something faster than BFS (a lot faster...)
gandalf you misled me :(
This comment has been hidden.
This comment has been hidden.
Hi,
You cannot use your computer as a reference. The only thing that matters is the timings done through codewars servers (which obviously perform slower than your machine).
You chose the correct approach, but it seems your code needs some other "micro"-optimizations in places you didnt think about.
I already encountered this kind of situation with another user: going through his code I made the ratio drop from x3.5 to like x1.8 without touching the underlying data structure, just hunting useless computations. So I bet you're encountering the exact same situation.
I'll let the issue opened for some time, but imo the problem is on your side. You can post your current version here (using correct markdowns et spoiler flag) and I'll try to come by to take a look (notification system being what it is on CW, I won't get any with your reply. You can poke at me on CW's gitter channel, possibly).
Cheers
no news, closing.
This comment has been hidden.
One of the best katas I have encoutered and such a demanding task!!!!!!!
Using python it is failing at one test,
Should not throw any exceptions inside timeout: NameError("name 'func' is not defined",)
Rest is running fine. Why's that?
Same result for me as for pindio58
There's just a typo in the unreachable cases sample test where start = (0,0), dest = (7, 7), and obstacles are the squares one knight's move away from dest. It shouldn't be calling func(s, e, o) -- it should be calling attack(s, e, o).
I'm hoping the kata author could respond to these test errors. I really want to complete this!
woops, didn't see that. I'll take a look.
The call to "func" is normal. There is an underlying structure in the tests you don't see. Func is actually the attack function, durign the tests. Now, if you get a "NameError" on this, this is clearly not normal... Since it is defined right at that beginning of the tests. Could you post your code with a spoiler flag, plz?
This comment has been hidden.
markdown formatting, plz... I cannot do anything with this... :/ https://github.com/Codewars/codewars.com/wiki/Markdown-Formatting
EDIT: Seems you used "func" in your code. I changed that already in the test suite. Are you still having troubles with that?
i'm sorry for fromatting but still the same issue. I din't use "func" . It is different name "func1"
I tired your code, It's timing out. No error about "func".
oh god... x. Why didn't you say that was in the sample tests... x/ Corrected soon.
i'm still facing the same error. is it corrected? and how is it timing out ? because just to verify that, i had put one condition at last. it could return None but wont timeout?
NameErrorthing, you need to reset the trainer to get the updated version (don't forget to copy your current code first)thanks! it's working now and actually failing with timeout while attempting. i'll work on that.
Python: @Blind4Basics
This test seems invalid - test.assert_equals(attack((7,1), (3,3), ((5,1),(5,2),(5,0),(4,2),(4,4),(7,5))), 4)
There is no way to get from (7,1) to (3,3) with those obstacles in 4 moves - agree?
It is possible
yep, possible.
My fault! I missed that the chessboard is infinite. Sorry :)
Can this currently be solved with Python?
Yes it can.
wait... From where does that ruby translation come from!??? It wasn't there before approval, no?
edit: I made the ruby version uncompletable for now. Waiting for an update from kazk about that.edit²: I'm translating the python version to ruby. But don't be in a hurry...done
approved to 3 kyu by comparison with all other related katas. It's of the same kind or harder than the hardest ones that are 3 kyu too, this one having requirements never asked for previously on cw (it's more complex than "find the cheapest path", for example).
Preloaded function's name and its parameters' names should be in snake_case.
woops... x)
done. Plz confirm that I didn't mess somthing in the sample tests.
'just tried, seems to be working ok.
just realized I fogot about the parameters.
so what about your ranking/vote? Still trying?
ok, kata fully revamped.
to every user having already solved it, plz either solve it again and rerank/revote accordingly, or just remove your votes: the difficulty has nothing in common with the original version...
enjoy
Hi,
The description is incorrect: you're not asking for the shortest path, but for its length (as number of steps)
.
Python:
I had to reload the kata before each attempt.
After that it would always timeout even without any computing on my side.
hi again, don't you think this should be considered a dup?
corrected (I believe). Can you check, plz? (edit: seems that's not enough. Or there is a flaw in your code? / EDIT²: ok, it's just too bad... I'll put my solution as a ref...)
done.
Your opinion about the dup aspect? (actually, maybe the only insterest of this versin could be to push the limits for performances... using an infinite board, for example? (to make the "pneumatic drill" useful x) ))
It seems corrected indeed. :)
Dunno about dup, I've seen so many I'm not sure what counts or not.
With an infinite board, it would be really different since the notation woulnd't work, my drill was created around it. x)
dup: pretty close to this one, but adding obstacles. Thing is, for now, considering the size of the board, the kata has close to no interest... :/
infinite board: yeah. The author isn't active anymore, so between having yet another dup sitting in beta and a complete rewrite, I'm ok for the latter if that can make it approvable. It would still be pretty close of other problems, but the situation might put some interest in it (because of the way the moves are done).
This comment has been hidden.
yep, that's the idea (spoilers! ;p)
I'm even asking myself if I couldn't try to enforce a variation of it, to hanlde more smoothly some edge cases (see message below)
This comment has been hidden.
Well, I would currently not be motivated enough to solve it but why not? x)
The description should has stated something like "If not possible, return None"
You're absolutely right. Thank you.
This comment has been hidden.
Thanks for this Kata, a very enjoyable problem. I found a fairly simple algorithm in the end.