First clear solution for Open Labyrinth by kumagi - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

First solution in Clear category for Open Labyrinth by kumagi

def checkio(data):
    result = []
    dirs = [[-1, 0, "W"], [+1, 0, "E"], [0, -1, "N"], [0, +1, "S"]]
    def move(path, x, y, field):
        field[y][x] = 1
        if x == 10 and y == 10:
            result.append(path)
        for d in dirs:
            if field[y + d[1]][x + d[0]] == 0:
                move(path + d[2], x + d[0], y + d[1], field)
    move("", 1, 1, data)
    return result[0]

#This code using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
        [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],
        [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1],
        [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
        [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]))
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    ]))
    #be careful with infinity loop
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    ]))
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    ]))
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1],
        [1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1],
        [1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1],
        [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
        [1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    ]))

Feb. 15, 2014

Comments:

hidekih on March 30, 2014, 6:31 a.m.
Beautiful! I wanted to do the same thing, but it took me triple number of lines as yours... orz

tetedemerou on April 23, 2014, 4:42 p.m.
I like your solution very much!

SandeepManilal on May 4, 2014, 9:37 a.m.
Wonderful! I love it.

veky on Sept. 28, 2014, 4:05 p.m.
Since so many people here adore your solution, I won't spend too much words about how beautiful it is. Instead I'll give you some advice how to make it better. ;-) Line 3: This should really be a tuple of tuples. List kinda implies it will be changed, and it won't. At least the inner elements should be 3-tuples, since they represent "records" of heterogenous types. Also, when you iterate through it (line 8), you can just inline the above. It doesn't really help understanding when you give a (not really accurate) name to something, and then only refer to it 7 lines later. If you want to name it separately, that's ok, but at least move the line 3 closer to the loop referring to it. Also2, those d[0], d[1] and d[2] are really ugly and hard to read. Much better is to use unpacking. See: <pre class='brush: python'>for dx, dy, way in (-1,0,"W"), (+1,0,"E"), (0,-1,"N"), (0,+1,"S"): if not data[y + dy][x + dx]: move(path + way, x + dx, y + dy) </pre> Also3, even better structure for dirs would be a {str: complex} (I mean dict(W=-1,E=1,N=1j,S=-1j)), but that's wizardry. ;-D Line 6: == can be chained. "if x == y == 10". Last argument of move: it shows lack of understanding of at least one of two different things. ;-) Either you mistakenly thought you must refer to (and mutate) data inside move as a separate parameter (you don't, see above), or you mistakenly thought that data will be deepcopied into field when calling move (in line 11, and recursively) (it won't, you still change data itself, just under a different name). And most importantly: you have result, then append to it deep inside recursion, then return only its first element out of outer function. I think I don't need to tell you how wrong it feels. :-) You in fact need, as soon as you find one path to (10,10), to return it from outer function, to "longjmp through" all these stack frames you've accumulated. Really nice and hackerish way to do it is to raise Exception(path) from move, and catch it from checkio. Long jumping through stack frames is what Exceptions are really good at. ;-) You can even use some subclass of Exception to better indicate what's going on, I usually use StopIteration which is a bit tongue-in-cheek but works nicely. ;-) But I understand if you are uneasy for using Exception in such a way. And in fact there is an "ordinary" way to do it, and that is to use a generator chaining. Just delete line 2, replace result.append(path) with yield path, insert "yield from" in front of recursive call in line 10, and return next(move(...)) at the end. Here is your solution pythonified;-), with few more details added to make you think: <pre class='brush: python'>def checkio(data): def move(path="", x=1, y=1): data[y][x] = 1 if x == y == 10: yield path for x, y, way in (x-1,y,"W"), (x+1,y,"E"), (x,y-1,"N"), (x,y+1,"S"): if not data[y][x]: yield from move(path + way, x, y) return next(move()) </pre>

hanpari on Feb. 4, 2015, 7:31 p.m.
I second Vekys recommendation to check complex numbers. They are pretty useful for similar tasks.

veky on Feb. 5, 2015, 7:14 a.m.
They are naturally 2D. And for small integer real and imaginary parts, they are exact, so you don't have to thing about float uglyness.

hanpari on Feb. 5, 2015, 10:22 a.m.
I start to use them inspired by your clock solution.

veky on Feb. 5, 2015, 11:27 a.m.
Now is better than never (from Zen:). Of course, clock there is continuous, so inexactness is not a problem at all. Here we're talking about Gaussian integers, really, but as I said, complex is ok with that too.

Nelo_Angelo on May 14, 2017, 4:46 p.m.
Hi Veky i wanted to ask why this solution help us to avoid the return calls in this deep recursion?

veky on May 15, 2017, 6:58 a.m.
Please read <a href="https://www.python.org/dev/peps/pep-0380/.">https://www.python.org/dev/peps/pep-0380/.</a> If after that you still have questions, feel free to ask. TL;DR: `yield from` chains generators (`move`s), so path from line 5 is yielded directly ("tunnelled") to the `next` call in the last line.

lsdda on July 29, 2020, 12:49 p.m.
These are gold comments. Thanks for your time, many years later.

BasedKips on Nov. 24, 2014, 1:41 a.m.
This looks really nice and interesting. Any chance of an explanation please? Specifically on the parameters in the move function? Thank you and very nice work!

veky on Feb. 4, 2015, 4:14 p.m.
Have you read my comment above? At its end is a much more straightforward variant of a solution. See if it helps you. About (other than last one) parameters to `move`: first is "path so far" (path that takes you from the beginning to the current point), and (second, third) is the current point.

GiForce on Sept. 19, 2016, 10:36 p.m.
very compact and for me it's totally readable. I wish I'd figured it out solid like this.

donchev_cf875240892c49c395b2d3 on March 23, 2017, 3:12 p.m.
Very nice. It doesn't necessarily find the shortest path, but shortest path was not required in fact...

abehad701 on June 6, 2017, 12:37 a.m.
wow. much shorter than mine. i did this creating a class to manage each run through (path, x, y) and used a stack of run throughs. i like your recursive call to the move function instead

mazocomp on June 20, 2019, 7:14 a.m.
Wow, your solution is so simple compared to mine and it's faster. I didn't even read about BFS, but I implemented one via loops without realizing that.

GitHub

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!