Quote:Original post by GenuineXP
I know it would probably be a pain, but could you explain this pseudocode? I'm having a hard time understanding it, especially the way you use "let" to assign to several values at once (at least, that what it looks like to me [lol] ).
Am not... Multiple assignment happens using let a,b = 1, 2, wheread let a b = ... defines a function 'a' with a parameter 'b'.The complete explanation:
(* Define a function "find" with parameters "numbers" (which is the string we are analysing) and "t" (which is the target number *)let find numbers t = (* A printing function. Here, p 3 "*" "1+2+" outputs "1+2+3*". *) let p a b c = c^string_of_int a^b in (* Duh. *) let n = length numbers in (* Convert a character to its integer representation by transforming it to its ASCII code and substracting the ASCII code of '0'. *) let v c = code c - code '0' in (* The last character in the string. This is our starting value, since we process the string right-to-left to make parsing easier. *) let l = v numbers.[n-1] in (* The recursive function which processes everything. In order to evaluate the value computed so far without having to build and parse a string, it implements a recursive descent parser (here, "sum", "prod", "cat" and "k" are the unrolled stack contents for grammar rules "+", "*" and ""). Parameter 's' represents the previously applied operation: it's used for printing the result once it is found. Parameter 'i' is the current index within the string. *) let rec aux sum prod cat k s i = (* Fold the stack to simulate receiving an EOF right now. *) let tot = sum + prod * cat in (* Overflow heuristic. If the sum so far (which can never decrease) exceeds the target, we have to stop and backtrack. *) if sum > t then None (* We've reached the beginning of the stream, so there's nothing else to do. Check if the target is reached. *) else if i < 0 then (* If we reached the target, return a "do nothing" string because we're at the beginning of the string with no characters.*) if tot = t then Some (s "") else None (* We have to read another character. This computes its value. *) else let c = v numbers. in (* This code attempts concatenation, multiplication and addition. Since they all behave the same, we just put them in a list of functions to be called, then call them until we have a solution. *) fold_left (* This function receives parameter 'r' representing the results so far, and 'f' representing the next function we can try. If 'r' is a valid result, we return it. Otherwise, we look to see if 'f' finds a solution (decreasing the index as this happens). If a solution is found, we print the previous character and return it. *) (fun r f -> if r <> None then r else match f (i-1) with None -> None | Some x -> Some (s x)) None [ (* First try: concatenation. This multiplies the character by the current multiplier, then multiplies the multiplier by 10 *) aux sum prod (c*k + cat) (10*k) (p c "" ) ; (* Second try: multiplication. We go back once on the stack, multiply the previous number with the multiplier, then push the character on the stack as beginning a new number. *) aux sum (prod * cat) c 10 (p c "*") ; (* Third try: addition. We go back twice on the stack and add everything up, then push "1" as the "current product value" and c as the "current number value". *) aux tot 1 c 10 (p c "+") ] (* We apply the recursive function, with a starting "current sum value" of 0, a "current product value" of 1, and using the first character as the "current number value". *) in aux 0 1 l 10 (p l "") (n-2)
