CODEWITHSUNDEEP
recursionocaml
Pandemonium
Pandemonium

Reputation: 8390

Recursive function stop processing a conditional branch

I have a function can_obtain to proof if a string init can be transformed to string target with the the following conditions:

Here is the function, with trivial operations such as contains and reverse removed for terseness. 

let can_obtain init target = 
  let final = 
    let rec reduce i text =
      if i >= String.length target then text
      else 
        let next = 
          let branchX = text ^ "X" in
          let branchY = (reverse text) ^ "Y" in
          if contains target branchX then branchX
          else if contains target branchY then branchY
          else text
        in 
          reduce (i+1) next
     in
       reduce (String.length init) init
   in
     final = target
;;

Problem is with these transitions it returns true, which is correct

(* concat "X" only *)
(* "XY" -> "XYX" -> "XYXX" *)
can_obtain "XY" "XYXX";;

(* reverse and concat "Y" only *)
(* "XY" -> "YXY" -> "YXYY" -> "YXYYY" *)
can_obtain "XY" "YXYYY";;

(* reverse and concat "Y", then concat "X" lastly *)
(* "XY" -> "YXY" -> "YXYY" -> "YYXYY" -> "YYXYYX" *)
can_obtain "XY" "YYXYYX";;

However, if at some point in the transition "X" is concatenated, the function would refuse to switch to the reverse branch and just return false:

(* concat "X", then tries to reverse then concat "Y" *)
(* "XY" -> "XYX" -> "XYXY" *)
can_obtain "XY" "XYXY";;  (* false *)

I know I'm missing just a small piece here, and the code looks really messy too. I would really appreciate some help.

Upvotes: 0

Views: 415

Answers (2)

Pierre G.
Pierre G.

Reputation: 4441

can_obtain is a recursive function - so let's define the stop conditions first :

stop conditions:

  • if n=i then this is a success
  • if length i > length n then failure

If stop conditions are not met, then we have to go further and try with the 2 hypothesis : (init ^ "X"), ((reverse init) ^ "Y")

So the code results in :

let rec can_obtain init target = 
  if init = target then
    true
  else if String.length init >= String.length target then
    false 
  else
    (can_obtain (init ^ "X") target) || (can_obtain ((reverse init) ^ "Y") target)

Upvotes: 2

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

Just looking at your code the obvious problem is that N might contain both branchX and branchY. In that case (it seems to me) you want to pursue both possibilities, but you're pursuing only the first.

Update

Another observation is that you probably want to pursue a branch if N contains the branch or its reverse. One of your operations reverses the string, and this operation might be applied an odd number of times for all you know.

Upvotes: 1

Related Questions