3 kyu

Knight's Attack!

95 of 98rsdah13
Description
Loading description...
Algorithms
Graph Theory
  • Please sign in or sign up to leave a comment.
  • KYLAN Avatar

    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

  • dead_pluto Avatar

    Get an error on ruby MRI 3.0.0:

    An error occurred while loading ./spec/solution_spec.rb.
    Failure/Error: o = Set.new if o.nil?
    
    NameError:
      uninitialized constant Set
    # ./spec/solution_spec.rb:391:in `circleWithHole'
    # ./spec/solution_spec.rb:695:in `block in <top (required)>'
    # ./spec/solution_spec.rb:682:in `<top (required)>'
    

    or on tests:

    ./lib/preloaded.rb:5:in `display': uninitialized constant Set (NameError)
    ./spec/solution_spec.rb:102:in `block (2 levels) in <top (required)>'
    
  • minakovskiy Avatar

    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?

  • Voile Avatar

    This comment has been hidden.

  • Voile Avatar

    Input range should be specified.

  • Ciprian Amza Avatar

    I SOLVED IT! GREAT KATA!!! xDD

  • brrandon13 Avatar

    How do I know the limit in the attack function?

  • monadius Avatar

    Python: the reference solution may return incorrect results in some rare cases. Here one example:

    start = (1, 57)
    end = (25, 20)
    obstacles = [(1, 45), (1, 46), (1, 47), (1, 48), (1, 49), (1, 50), (1, 51), (2, 41), (2, 42), (2, 43), (2, 44), (2, 45), (2, 46), (2, 47), (2, 48), (2, 49), (2, 50), (2, 51), (2, 52), (2, 53), (2, 54), (2, 55), (3, 40), (3, 41), (3, 42), (3, 43), (3, 53), (3, 54), (3, 55), (3, 56), (4, 39), (4, 40), (4, 41), (4, 42), (4, 54), (4, 55), (4, 56), (4, 57), (5, 38), (5, 39), (5, 40), (5, 56), (5, 57), (5, 58), (6, 38), (6, 39), (6, 40), (6, 56), (6, 57), (6, 58), (7, 37), (7, 38), (7, 39), (7, 57), (7, 58), (7, 59), (8, 37), (8, 38), (8, 58), (8, 59), (9, 36), (9, 37), (9, 38), (9, 58), (9, 59), (9, 60), (10, 37), (10, 38), (10, 58), (10, 59), (11, 37), (11, 38), (11, 39), (11, 57), (11, 58), (11, 59), (12, 38), (12, 39), (12, 40), (12, 56), (12, 57), (12, 58), (13, 38), (13, 39), (13, 40), (13, 56), (13, 57), (13, 58), (14, 39), (14, 40), (14, 41), (14, 42), (14, 54), (14, 55), (14, 56), (14, 57), (15, 40), (15, 41), (15, 42), (15, 43), (15, 53), (15, 54), (15, 55), (15, 56), (16, 10), (16, 11), (16, 12), (16, 13), (16, 41), (16, 42), (16, 43), (16, 44), (16, 45), (16, 46), (16, 47), (16, 48), (16, 49), (16, 50), (16, 51), (16, 52), (16, 53), (16, 54), (16, 55), (17, 11), (17, 12), (17, 13), (17, 14), (17, 43), (17, 44), (17, 45), (17, 46), (17, 47), (17, 48), (17, 49), (17, 50), (17, 51), (17, 52), (17, 53), (18, 12), (18, 13), (18, 14), (18, 15), (18, 16), (18, 45), (18, 46), (18, 47), (18, 48), (18, 49), (18, 50), (18, 51), (19, 14), (19, 15), (19, 16), (19, 17), (19, 18), (20, 16), (20, 17), (20, 18), (20, 19), (20, 20), (20, 21), (20, 37), (20, 38), (21, 18), (21, 19), (21, 20), (21, 21), (21, 22), (21, 23), (21, 24), (21, 25), (21, 26), (21, 27), (21, 28), (21, 29), (21, 30), (21, 31), (21, 32), (21, 33), (21, 34), (21, 35), (21, 36), (21, 37), (21, 38), (21, 39), (21, 40), (22, 20), (22, 21), (22, 22), (22, 23), (22, 24), (22, 25), (22, 26), (22, 27), (22, 28), (22, 29), (22, 30), (22, 31), (22, 32), (22, 33), (22, 34), (22, 35), (22, 36), (22, 37), (22, 38), (23, 24), (23, 25), (23, 26), (23, 27), (23, 28), (23, 29), (23, 30), (23, 31), (23, 32), (23, 33), (23, 34)]
    

    The optimal solution is 27 and the reference solution returns 29.

  • rfyoro Avatar

    This comment has been hidden.

  • rcfroggatt786 Avatar

    Is the board also infinite in the negative direction?

  • the_Hamster Avatar

    This comment has been hidden.

  • Ottstar Avatar

    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.

  • Zevgon Avatar

    This comment has been hidden.

  • fibonaccios Avatar

    One of the best katas I have encoutered and such a demanding task!!!!!!!

  • pindio58 Avatar

    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?

  • tomset Avatar

    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?

  • Davo36 Avatar

    Can this currently be solved with Python?

  • Blind4Basics Avatar

    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...

  • Blind4Basics Avatar

    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).

  • FArekkusu Avatar

    Preloaded function's name and its parameters' names should be in snake_case.

  • Blind4Basics Avatar

    ok, kata fully revamped.

    • infinte board
    • huge performances constraints.

    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

  • Blind4Basics Avatar

    Hi,

    The description is incorrect: you're not asking for the shortest path, but for its length (as number of steps)

  • Mercy Madmask Avatar

    Python:

    I had to reload the kata before each attempt.

    After that it would always timeout even without any computing on my side.

  • maipatana Avatar

    The description should has stated something like "If not possible, return None"

  • siebenschlaefer Avatar

    This comment has been hidden.

  • daddepledge Avatar

    Thanks for this Kata, a very enjoyable problem. I found a fairly simple algorithm in the end.