CODEWITHSUNDEEP
ocaml
Stevie
Stevie

Reputation: 149

Infinite loop exception

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?

Upvotes: 1

Views: 232

Answers (1)

ivg
ivg

Reputation: 35210

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.

Upvotes: 3

Related Questions