Exercise - Self Insertion

arithma

This is exercise is an original, so please work with me to see if there is any mishaps.
Given any string, choose a random position in this string, and place a copy of the original string there.
Example: "abcd" -> "ababcdcd". It could have equally likely been "abcabcdd" or "aabcdbcd" or even "abcdabcd".

Now given a string resulting from this operation, return the possible original strings:
Example: "xyxyzz". The solution will contain this item: xyz (from "xyxyzz). There will not be any other alternative in this case.

The algorithm data specification is to take a string as input and to return a list of strings as output. Each item in the output should be mappable through the self copy operation to the input string.

scatman

i assume that there could be duplicate letters right?
ie aaabcabc has a single copy operation of: aabc?
if its not the case (ie no duplicates) the problem is trivial!

arithma

Yes of course. It's trivial in all cases really, as I've just discovered with a friend at work. But let's probe our thinking styles and esoteric solutions.

ali-koubeissi

Ummmm. Sleep Sort to the rescue!.

xterm

The hatred grows.

input = "aabaabcc"; input.toList().subsequences().find { input - it.join() == it.join() }.join()

Test here

xterm

ali.koubeissi wroteUmmmm. Sleep Sort to the rescue!.

Oh lord, this is incredibly funny!

jsaade

xterm wroteThe hatred grows.

input = "aabaabcc"; input.toList().subsequences().find { input - it.join() == it.join() }.join()
Test here

damn.

xterm

Here's one that's exponentially more performant:

input = "aabaabcc"; (0..input.size()/2).collect { input[it..it+input.size()/2-1] }.find { input - it == it }

MSD

private List<string> FindOriginals(string input)
{
	List<string> result = new List<string>();
	if(input.Length % 2 != 0) return result;
	int halfSize = input.Length / 2;
	for(int i = 0; i < halfSize; i++)
	{
		string selection = input.Substring(i, halfSize);
		if(input.Replace(selection, string.Empty) == selection)
			result.Add(selection);
	}
	return result;
}

arithma

When I reread the title, I figured that I didn't notice the comedy that it is.
Here's little bit of C# that looks a bit much like Groovy

var input = "I inserted it iI inserted it in my selfn my self";
var hLength = input.Length / 2;
var results = 
    Enumerable
    .Range(0, input.Length / 2)
    .Select(i => new { i = i,
        insert = input.Substring(i, hLength),
        rest = input.Substring(0, i) + input.Substring(i + hLength) })
    .Where(x => x.insert == x.rest)
    .Select(x => x.insert)
    .ToList();
MessageBox.Show(String.Join(",\n", results));

Ok, it's a bit inflated with ceremony.
[EDIT] Will I ever be able to post without having to edit it a second later!

xterm

You know, i refrained from commenting on the title, but i chuckled when i read it.

arithma

While exercise may be a little easy, try this for a brain scratch: Try to prove (or disprove, I haven't reached a solution) that there can at most one unique solution for any input string.

Joe

Although xterm's solution is very elegant, it actually fails to address the performance issue. It's easy to brute force (I'm not saying Groovy does, but it might), but coming up with the best algorithm for the current issue can be very tricky.

The exercise is far from easy. There are just two ways to think about it. The "dynamic" Groovy/Perl/Python way is not easy or cheap. It just addresses the issue differently.

If you think of the algorithm to solve that issue, it becomes different. Enumerable/Range/Where, doesn't tell doesn't tell you anything about the complexity. How many loops? how many checks? If you care about this stuff, this exercise is actually pretty interesting.

MSD

Now this is an informal proof, not tidy you have been warned.

Assume abcde has 2 solutions (a b c d and e are not letters, they represent substrings of input)

sol 1:
abe = cd

sol 2:
ade = bc

a, c, and e have a common start
d, e, and c have a common end

so

xAxBEy = xCyDy

xADyEy = xBxCy

AxBE = CyD
ADyE = BxC

now
A, C, and B have a common start
D, E, and C have a common end

XA'xXB'E'Y = XC'YD'Y
XA'D'YyE'Y = XB'xXC'Y

A'xXB'E' = C'YD'
A'D'YyE' = B'xXC'

simplifying
AxBE = CyD
ADzE = BxC

repeating like this leads to equality of A, B, C, D, E

I think this means that there is one solution only.

arithma

@rahmu: My code is line for line equivalent to MSD's. Additionally its parallelizable. So not only is the complexity deterministic, it also encodes the parallesim of the problem.
I think I cooked up a little proof, but it needs some peer review. I'll share the scratch with you.
The idea is to start with an already factored string, assume there is another factoring out, and then proving that the other factoring must equal the first one.
The following works based on the assumption that XXYY is a valid factorization. Then it assumes UUVV is another valid factorization where |U| (length) is greater or equal to that of |X|. It then splits X into two parts such that U = X1+X2+X1. It proves the property that U = X by determining that the length of X1 is 0.
The sketch of the proof follows:

arithma

The above proof is a little bit off.
The correct way is:
X1X1X2X1Y1Y2Y1Y1 = X1X2Y1Y2
in terms of length: 3*X1+X2+3*Y1+Y2=X1+X2+Y1+Y2
2*X1+2*Y1=0. Since X1 and Y1 are not negative, they both have to be 0 to satisfy the equation.

xterm

Edit: Pointless blabber about pointless things

arithma

@xterm: Does groovy evaluate the lambda's inside lazily or eagerly?
This is for the sake of comparison with LINQ's lazy technique.
Since we just proved that there should only be one solution, my algorithm should return a single string or null, and should use SingleOrDefault(...) instead of Where(...). SingleOrDefault will halt the preceding enumeration of integers. Interesting stuff would happen in the Parallel case, if they have implemented things exhaustively performace oriented (which you would expect from a parallel implementation).

xterm

In groovy anything involving an iterator is lazily evaluated. I'll find the source code for you soon.

arithma

I dreamt that I was xterm. In the dream I said to my machine:

"this is how the forward function works, and this is what the output looks like. figure out the input string and fetch me a capuccino"