Deduct format string from given results

user_2280305 0
Viewed 59

Is there an existing algorithm to do something like this, from a number of results, recreate the original format string.

For example, here are the input:

"the fox jumps over the lazy brown dog"
"the man jumps over the lazy black cat"
"the dolphin jumps over the big wave"

=> output:

output="the {} jumps over the {}"

There are multiple format strings that work, but we should get the one with highest number of characters that do not belong to place holders, and lowest number of place holders.

since in python, we have:

"the fox jumps over the lazy brown dog" = output.format('fox', 'lazy brown dog')
"the man jumps over the lazy black cat" = output.format('man ', 'lazy black cat')
"the dolphin jumps over the big wave" = output.format('dolphin', 'big wave')

or even better in C, assuming with enough inputs, we can get

output = "the %s jumps over the %s"
printf format algorithm
1 Answers

There is no such algorithm in the standard libraries to my knowledge. We can look at it as a variant of the Longest Common Substring problem, here is an idea on how to do it.

A naive algorithm would be something like this:

1. Split the first string, with ' ' (space) as split character and keep this array
   (base_array)

2. For each following input :
    a. Split string with ' ' as split character, let's call this array curr_array

    b. Compare, from left to right, each curr_array entry with the base_array entries and 
       apply the following rule: 
         - match at curr_array[i] and base_array[j]:
               compare curr_array[i+1] and base_array[j+1]

         - no match at curr_array[i] and base_array[j]:
               recurse b. with curr_array[i+1] and base_array[j], if recursion found a
               match at curr_array[i+k], continue algorithm from the top of the recursion
               from curr_array[i+k+1] and base_array[j+1],

               if recursion was not successful update base_array[j] = "" and continue
               algorithm with curr_array[i] and base_array[j+1]

Let say you have two inputs:

"this is a very poor and long example"
"this is a good and short example"

When the algorithm ends, base_array will contain entries like this:

[this][is][a][][][and][][example]

Then just regroup the neighboring empty entries:

[this][is][a][][and][][example]

Replace the remaining empty entries with the characters of your choice, and join the list to obtain the desired result

this is a {} and {} example

Hope it helped!

user_113168840
Related