Infinite loop exception

Question

I'm trying to generate an exception for an infinite loop while folding a map.

module X=Map.Make(Int)

The problem goes like this: Determine the max rank for which the function "f" doesn't lead into an infinite loop. We have a map [(1,2);(2,3);(5,6);(6,7);(7,6)]

The function goes through all the pairs of the map like this:

for the first pair (1,2) => f(1)=2 Now I'll try f(2) = 3 (As it exists in the pair (2,3)) now I'll try f(3) => Cannot find any key = 3 so the rank is the number of times I could call the function f, in this case, it's 2.

for the pair (5,6) => f(5)=6 I'll try f(6) = 7 (the pair (6,7) exists) I'll try f(7) = 6 (The pair (7,6) exists) I'll try f(6) = 7 goes into a loop, because I have already used the pair (6,7) once, so the rank in this case is 0;

Conclusion: The max rank of the function f if it does not go into an infinite loop is 2.

How can I define my exception, as well as what reasoning can I use to solve the problem?

ivg · Accepted Answer · 2016-10-26 19:25:09Z

3

It took me some time to understand the task... it basically resembles me the rules of the World Chain game. A more scientific description would be: find the length of a simple path, starting from the given node.

How can I define my exception

This is simple:

exception Loop_detected

what reasoning can I use to solve the problem

The easiest way to detect a loop would be to maintain a set of all visited nodes. As soon, as you hit a node, that you have already seen, you should bail out with Loop_detected exception, e.g., if Ints.mem dst visited then raise Loop_detected. You can create an Ints set module for ints with the following definition:

 module Ints = Set.Make(Int)

Using a set of all visited nodes is a common but not the only way of detecting loops. You can use a Tortoise and Hare algorithm for this. It is also described more formally in Stepanov's Elements of Programming book, in the Transformations and their Orbits chapter, that is available online.

edited Oct 26, 2016 at 19:25

answered Oct 26, 2016 at 16:17

ivg

35.4k2 gold badges43 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

coredump Over a year ago

The "two racing cars" approach is best known as Floyd's Tortoise and the Hare algorithm: en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare.

ivg Over a year ago

yeah, I was striving to recall it, but my memory has taken an absence day)) Thanks, will update the post.

Collectives™ on Stack Overflow

Infinite loop exception

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related