0

I would like to know what I might be doing wrong in trying to find the number of nodes connected in a loop. Here is my implementation in python.

# Defined Node class
class Node(object):
    data = 0
    def __init__(self, data=None, next_node=None):
        self.data = self.increment()
        self.next = next_node

    def increment(self):
        Node.data += 1
        return Node.data

    def setNext(self, next_node = None):
        self.next = next_node

I defined a function to create a node chain by taking on an arbitrary number of nodes and also a desirable loop length as parameters.

def create_chain(num_of_nodes, loop_size):
    nodes = [Node() for _ in range(num_of_nodes)]
    if loop_size == 0:
        return nodes[0]
    else:
        for node, next_node in zip(nodes, nodes[1:]):
            node.next = next_node
            # cleaned_nodes.append(node)
        nodes[num_of_nodes-1].next = nodes[(num_of_nodes - loop_size)-1]
        return nodes[0]

I then defined a function to determine the size of a loop given the initial node which passed as a parameter to the function.

def loop_size(node):

    count = 0
    if node == None:
        return 1

    if node.next == None:
        return 1


    slow = fast = node

    while(slow or fast or node.next):
        count += 1
        if fast.next == None:
            #count += 1
            break

        if slow == fast.next or slow == fast.next.next:
            count += 1
            break

        slow = slow.next
        fast = fast.next.next

    return count

I wrote a few tests but this particular assertion did not work, and I'd like to understand why.

def test_very_long_chain(self):
    self.chain = create_chain(3904, 1087)
    self.assertEqual(loop_size(self.chain), 10, 'Loop size of 10 expected')

I get this assertion error;

AssertionError: 3264 != 10 : Loop size of 10 expected

I'd really appreciate some guidance on this. Thanks

emalinga
  • 58
  • 6
  • You called create_chain with loop_size = 1087 and assert that the resulting graph has a loop of size 10. That... doesn't seem right. – Norrius Jan 28 '19 at 09:20
  • Crap, that's not what I meant, I meant to assert the result against `1087`, not `10`. But as you can tell from the result of the `AssertionError` it returns `3264` instead. Thanks for catching that @Norrius – emalinga Jan 28 '19 at 16:56
  • That makes more sense, but I don't think I'll be able to help you. It is difficult to follow the logic of that code in my head, and you also did not use the standard solution for the problem. Have you tried debugging, using a [debugger](https://stackoverflow.com/q/25385173/1983772) or simple prints/asserts of internal state at different points? I can't debug it for you, but here's the first question you should ask yourself: is the problem in `create_chain` or `loop_size`, i.e. is the generated graph what you expect it to be? – Norrius Jan 28 '19 at 18:13
  • True. I think the problem is in `create_chain`. I have tried and just wasn't able to see what was causing the problem. I will keep looking though. – emalinga Jan 28 '19 at 21:17

1 Answers1

1

I see some problems in create_chain as well as in loop_size.

In create_chain, the logic is not clear, when loop_size == 0, there is no chain created, but I suppose chain should be created whatever the loop size is?

Also the definition of loop size in function create_chain is not strict, suppose there are 300 nodes, is it possible to create a loop of length 300? If it is , this line "nodes[num_of_nodes-1].next = nodes[(num_of_nodes - loop_size)-1]" should change.

The biggest issue is the loop_size function, I see you used the fast slow pointers method to try to calculate the loop length, but the fast and slow method is mainly used for detecting loops, and it can find the entrance of the loop. When you find the entrance to the loop, calculate the loop length should be easy, so I added this helper function within loop_size function.

Within the while loop bracket in function loop_size it should be 'and' instead of 'or'. Below is my rewrite of the class and method. I hope this is what you wanted!

class Node(object):
  def __init__(self, data=None, next_node=None):
    self.data = data
    self.next = next_node

  def increment(self):
    self.data += 1
    return self.data

  def setNext(self, next_node=None):
    self.next = next_node




def create_chain(number, loop):
  if number <= 0 or loop > number:
    print("Error")
    return
  nodes = [Node(i) for i in range(number)]
  for i in range(number-1):
    nodes[i].setNext(nodes[i+1])
  if loop > 0:
    nodes[number-1].setNext(nodes[number-loop])
  return nodes[0]


def loop_size(node):
  def helper(node):
    #print(node.data)
    count = 1
    temp = node
    while(temp.next != node):
      temp = temp.next
      count += 1
    return count

  if not node:
    return 0
  slow = fast = node
  while(slow and fast and fast.next):
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
      return helper(slow)
  return 0


chain = create_chain(300, 300)
print(loop_size(chain))
chain = create_chain(300, 0)
print(loop_size(chain))
chain = create_chain(300, 130)
print(loop_size(chain))
Danny Fang
  • 3,843
  • 1
  • 19
  • 25