4 kyu

Determining if a graph has a solution

1,176 of 1,599damned3
Description
Loading description...
Algorithms
Data Structures
Graph Theory
View
AllIssues9Questions1Suggestions5Show Resolved
  • Please sign in or sign up to leave a comment.
  • ejini战神 Avatar

    JS function name should be camelCase, backward compatability fix is adviced !

  • dolamroth Avatar

    In Python version, reference solution sometimes expects false, when path exists

    sqj kvn [('zxz', 'kvn'), ('hbx', 'lkd'), ('wrv', 'njw'), ('ugm', 'ugm'), ('hmo', 'wrv'), ('tik', 'zdt'), ('tik', 'lxj'), ('wie', 'yzw'), ('oef', 'utn'), ('hmo', 'sae'), ('zdt', 'lsc'), ('zdt', 'liq'), ('wie', 'xlq'), ('rhk', 'liq'), ('njw', 'trh'), ('njw', 'tit'), ('tik', 'lsc'), ('zxz', 'qkw'), ('ucg', 'zdt'), ('zdt', 'gxq'), ('rhk', 'ywp'), ('lsc', 'vks'), ('tit', 'ucg'), ('utn', 'kvn'), ('lxj', 'sqj'), ('xvl', 'qkw'), ('gxq', 'xbu'), ('ugm', 'xvt'), ('aaj', 'vks'), ('ucg', 'vks'), ('ucg', 'xvt'), ('wno', 'sae'), ('fln', 'fln'), ('liq', 'pbk'), ('ugm', 'lxj'), ('oef', 'yyz'), ('wrv', 'ywp'), ('qkw', 'xbu'), ('wno', 'ucg'), ('lsc', 'gxq'), ('rhk', 'hmo'), ('hbx', 'vks'), ('wno', 'zdt'), ('qkw', 'bzn'), ('wno', 'hex'), ('rhk', 'bzn'), ('lxj', 'bzn'), ('ywp', 'wie'), ('wrv', 'rhk'), ('zxz', 'wrv'), ('bzn', 'hbx'), ('ucg', 'wno'), ('yyz', 'njw'), ('wno', 'ufy'), ('aaj', 'qkw'), ('sqj', 'lxj'), ('ufy', 'wno'), ('trh', 'njw'), ('oef', 'pbk'), ('aaj', 'bzn'), ('zxz', 'rhk'), ('njw', 'aaj'), ('lkd', 'lsc'), ('gxq', 'zdt'), ('fln', 'aaj'), ('lkd', 'rhk'), ('hbx', 'liq'), ('xlq', 'njw'), ('ywp', 'lkd'), ('wrv', 'trh'), ('tit', 'ywp'), ('gxq', 'njw'), ('liq', 'trh'), ('zdt', 'njw'), ('ywp', 'oef'), ('liq', 'fln'), ('tit', 'wrv'), ('hmo', 'hbx'), ('ywp', 'hex'), ('liq', 'yzw')]

    True should equal False

    Path: sqj > lxj bzn > hbx > lkd > rhk > ywp > oef > utn > kvn
  • Kacarott Avatar

    Python Fork

    • Switches to list of tuples for adjacency list
    • Adds random tests
  • KayleighWasTaken Avatar

    Python:

    • Each node can have at most one arc leaving it due to input format being a dict. Should use adjacency lists as in other languages.
  • saudiGuy Avatar

    Description should be language-agnostic.

  • runday198 Avatar

    "Should reach all nodes in a loop" What does this error mean?

  • PistachioCake Avatar
  • gustavoaca1997 Avatar

    This comment has been hidden.

  • Coldsewoo Avatar

    This comment has been hidden.

  • donaldsebleung Avatar

    PureScript Translation Kumited - please accept :D

  • donaldsebleung Avatar

    This comment has been hidden.

  • FArekkusu Avatar

    This comment has been hidden.

  • z y Avatar

    Error:

    tmp/haskell1171024-5-1qp9tq1.0mci9kke29/Graph.hs:1:1:
    File name does not match module name:
    Saw: 'Main'
    Expected: 'Graph'
  • haugk Avatar

    Haskell

    That was fun.

  • WhuerCoder Avatar

    what does "Should reach all nodes in a loop" mean? Is there an error in the last test code?

  • zebralan_prev_account Avatar

    The arcs in the Haskell version are actually directional. Please either change the description or modify the test cases.

  • Pocket-titan Avatar

    I really like this kata! Nice link with mathematics. However, you could make it a bit harder by requiring the user (in at least one test case) to actually jump to an earlier node, as in start > end. I was able to pass this kata by just ignoring all the loops.

  • wesley Avatar

    This comment has been hidden.

  • Ivana Avatar

    Nice Kata.

  • theycallmebruce Avatar

    Is there an error in the test code? I am only asking because I get all examples correct except for 'a to a' in the simple arcs section. But the arcs array looks to be missing something (either {start:b,end:a} or {start:a, end: a}) see below.

    describe("Simple graph with 1 arc", function() { var arcs = [ { start: "a", end: "b" }, ]

  • ZozoFouchtra Avatar

    This comment has been hidden.

  • amcaplan Avatar

    This comment has been hidden.

  • Retsam Avatar

    This comment has been hidden.

  • jacobb Avatar

    I was a tad confused what you were going for when I first scanned through the description. Some background on the data structure and the concept would greatly improve this kata IMO.

  • damned3 Avatar

    Thank you for your comment,

    As this is the first kata I make, I didn't know thesingle quote trick, I'll correct it.

    I've checked for similar katas on Codewars before creating mine, to avoid duplicating an existing one, and indeed there are similar ones, but they do not work quite the same. For example, there's a kata about finding the shortest path on a graph. But there was none about finding if a graph has a solution or not.

    As for the Solution Setup part, I thought it was only for setting up variables and stuff needed for both the correct solution and the user's solution. Now I know what it is about. I'll check it out

  • OverZealous Avatar

    You need to include the basic function signature in the Solution Setup part of the kata creator, like existing katas.

    You also should wrap code inline snippets in single backticks (`solve_graph(start, end, arc)`), so they stand out in the text, like this: solve_graph(start, end, arc). I recommend using it on values such as 0, true and false as well. It makes them stand out much better.

    I also recommend changing the last sentence to:

    Note that the solve_graph() method doesn't take a list of nodes as input: for simplicity's sake, let's assume that all nodes present in "arcs" are valid. However, the start or end node may not be in the list of arcs provided.

    I think it's a lot clearer, since you are specifying that a list of nodes isn't provided, that the list of arcs is not a conclusive list of nodes.

    (As a side note: I feel like I've already solved this on Codewars, but that doesn't mean anything. I couldn't find anything searching for graph, vertex, path, or edge, so maybe it's just similar to others. If anyone else can chime in, that would be great.)