Short uncategorized solution for Disposable Teleports by altarfinch - python coding challenges

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

Short solution in Uncategorized category for Disposable Teleports by altarfinch

def explore(n,t,s):
    return [n] if not s and n == '1' else [n + c for l in [l for l in t if l[0] == n] for c in explore(l[1],list(set(t) - set([l]) - set([l[::-1]])),s.replace(n,''))]

def checkio(str):
    return explore('1',str.split(',') + str[::-1].split(','),'2345678')[0]
    
if __name__ == "__main__":
    print(checkio("12,23,34,45,56,67,78,81")) #"123456781"
    print(checkio("12,28,87,71,13,14,34,35,45,46,63,65")) #"1365417821"
    print(checkio("12,15,16,23,24,28,83,85,86,87,71,74,56")) #"12382478561"
    print(checkio("13,14,23,25,34,35,47,56,58,76,68")) #"132586741"

June 21, 2013

Comments:

veky on Aug. 3, 2013, 8:31 p.m.
Very cool. :-) But could be made much shorter. ;-)

JackSchneider on Aug. 14, 2013, 8:42 p.m.
<pre class='brush: python'> print(checkio("12,23,34,45,56,67,78,81")) #"123456781" </pre> Short but there is no reeel learning posibility for the unexperieced .

nickie on Nov. 3, 2013, 9:32 p.m.
This solution is a simple recursive DFS and it would be much easier to understand if it was written in a less cryptic style. I'm re-writing it here, in case someone wants to study it: <pre class='brush: python'>def explore(here, edges, remaining): if not remaining and here == '1': return [here] else: return [here + rest for u, v in edges if u == here for rest in explore(v, list(set(edges) - set([u+v, v+u])), remaining.replace(here, '')) ] </pre> Notice that, in line 2 of the original version, there is no need for the extra "for" in "for l in [for l in ...]". One is enough. This particular implementation of DFS has the drawback that it does not keep an adjacency list for each vertex. Thus, from each vertex, it has to traverse all remaining edges to find the ones that can be followed next. This gives a O(V*E) worst case complexity, instead of O(V+E) which would be possible with an adjacency list (or an adjacency matrix). Instead of a DFS, a BFS strategy could also be applied, or any other search strategy, e.g. A* with some appropriate heuristic to speed things up. Both can be found in the list of solutions. Due to the nature of the problem, the selection of another search strategy would not make it any different from DFS, as we are looking for solutions of a specific length which cannot be exceeded. This problem, which amounts to determining if a graph contains a spanning trail cycle is NP complete, so there is not much you can do to solve it quicker than by exhaustive search.

shreekar on Dec. 26, 2013, 2:48 a.m.
Looks like simple DFS, but very cryptic to understand.

Ice Base

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.