BFS clear solution for Digits Doublets by bryukh - python coding challenges

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

BFS solution in Clear category for Digits Doublets by bryukh

def count_diff(first, second):
    """
    Count how many digits are distinguished in the two numbers.
    """
    return len(str(first)) - sum(f == s for f, s in zip(str(first), str(second)))


def list_to_graph(numbers):
    """
    Convert a list of numbers in the dict graph representation,
    where each key is a node and values are "neighbour" numbers.
    """
    res = {}
    for node in numbers:
        res[node] = []
        for second_node in numbers:
            if count_diff(node, second_node) == 1:
                res[node].append(second_node)
    return res


def checkio(numbers):
    """
    I'm using "Breadth-first search" algorithm here.
    http://en.wikipedia.org/wiki/Breadth-first_search
    """
    graph = list_to_graph(numbers)
    goal = numbers[-1]
    # the queue contains positions and paths for they.
    queue = [(numbers[0], (numbers[0],))]
    # the visited numbers we store in the set, because it faster
    closed = set()
    while queue:
        current, path = queue.pop(0)
        if current in closed:
            continue
        closed.add(current)
        if current == goal:
            return list(path)
        for neigh in graph[current]:
            if neigh in closed:
                continue
            queue.append((neigh, path + (neigh,)))
    return []

Feb. 8, 2014

Comments:

nickie on Feb. 8, 2014, 11:53 a.m.
Two comments: <ol> <li>The combination of list_to_graph and count_diff takes O(N^2*D) time to compute the adjacency list, if D is the numbers' length in digits. It is much better to find all possible neighbors for each number and check if they are indeed present. This costs O(N*D*log(N)) if numbers are stored in a data structure that allows searching in logarithmic time (e.g., a set).</li> <li>Using a queue, as you do, is the standard implementation for BFS. However, in Python, I hear that using lists as queues with pop(0) is inefficient. This is the reason I'm using a heap in my solution; this is still not satisfactory, as it requires O(log(N)) time both for pushing and popping, instead of the intended O(1). Can someone more knowledgeable (than me) in Python enlighten us here?</li> </ol>

bryukh on Feb. 8, 2014, 12:04 p.m.
Thanks. <ol> <li>Yes, and that is why i placed it in the "Clear" category (We have "Speedy" for algorithmic)</li> <li>I should check it, but in Python lists are not real lists, it's an array.</li> </ol>

bryukh on Feb. 8, 2014, 12:19 p.m.
<ol> <li><a href="http://stackoverflow.com/a/10477910/767046">The post from stackoverflow about it</a></li> </ol> For this case we can use collection.deque

bryukh on Feb. 8, 2014, 12:25 p.m.
Just for example :) <pre class='brush: python'>MacBookBryukh:~ bryukh$ python -m timeit 'from heapq import heappop;l = list(range(10000))' 'while l: heappop(l)' 10 loops, best of 3: 49.7 msec per loop MacBookBryukh:~ bryukh$ python -m timeit 'l = list(range(10000))' 'while l: l.pop(0)' 100 loops, best of 3: 15.7 msec per loop MacBookBryukh:~ bryukh$ python -m timeit 'from collections import deque;l = deque(range(10000))' 'while l: l.popleft()' 1000 loops, best of 3: 1.43 msec per loop </pre>

nickie on Feb. 8, 2014, 12:35 p.m.
OK, deque seems to be the winner, but I think you're not using heapq properly. You should have a <pre class='brush: python'>heapify(l) </pre> before your loop.

bryukh on Feb. 8, 2014, 12:40 p.m.
You are right. <pre class='brush: python'>MacBookBryukh:~ bryukh$ python -m timeit 'from heapq import heappop,heapify;l = heapify(range(10000))' 'while l: heappop(l)' 100 loops, best of 3: 8.07 msec per loop </pre> But as i already said -- i didn't try to reach performance (as minimum i use A* for it). The main goal was a clear readable solution.

veky on Feb. 12, 2014, 10:34 a.m.
count_diff is very nonclear IMO. :-P Much simpler would be to do what the name says, instead of complement_of_count_eq :-P <pre class='brush: python'>sum(f != s for f, s in ...) </pre> + what nickie said. Python list is really an array, but that precisely means that pop(0) is O(n). deque is what you need (or better a prioque:). ... an interesting thing to note: you don't have to mess with deques, and can use ordinary list, just don't pop from it, have an index where you're reading that starts from 0 and increment it. You pay in memory, but only a factor <=2 (since you already hold all these numbers in "numbers" list), which industrial practice considers negligible.

bryukh on Feb. 12, 2014, 11:01 a.m.
Thanks for advices. Very interesting notes about "index".

bryukh on Feb. 12, 2014, 11:10 a.m.
Now with advices from Veky and Nickie i should make the new solution, because i can not see this after advices :-D

wiking on March 12, 2014, 11:43 a.m.
I have been confused about how to do BFS efficiently using python, the discussions here gives me some hint, thank you guys!

veky on July 28, 2014, 7:10 a.m.
DFS is to stack as BFS is to queue. So the only question (I assume you can do DFS:) is how to use efficient queues in Python. Here the documentation is a bit lacking, since if you google "Python queue", you get all these nice complicated classes like synchronized queues, heap queues, but not the ordinary abstract data structure of a queue. No wonder, since it lives under a name of collections.deque (from "Double-Ended QUEue"; they tried to generalize both stack and queue, which is nice in itself, but the naming is suffering:). Once you know about the name, documentation for it is pretty clear: you use popleft for picking up an element, and append for adding one at the other end.

mknecht on July 28, 2014, 5:36 a.m.
Generally clear. I find it a bit confusing, that queue always consists of tuples (node, others + [node]). Is redundant, which always makes me search for the bit of code that I'm missing. And I second veky's proposal for clearing up count_diff. :) Thanks for publishing/writing!

bryukh on July 28, 2014, 5:58 a.m.
Honestly, I don't remember why I used tuples :-)

The Game is Worth it!

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.