/prog/ challenge

The Anus operation is defined as follows:


public static string Anus(string input, int repetitions)
{
    Random rand = new Random();
    string result = input;
    while(repetitions --> 0)
    {
        result = result.Insert(rand.Next(0, result.Length-1), input);
    }
    return result;
}

Little Ive was playing with his Anus and discovered that, when he knows the output string and the number of repetitions, he can determine the original string. Then The Suss joined Ive and told him that his method, written in LISP, was faster and that Ive was a faggot for using brute force. What method did Ive discover? What was The Suss's method?

I don't do Java nor Lisp, fagstorm.

Also, lisp is fucking gay and so are you.

forget it, it's np hard

Here's the brute-force way:
  - You know the last letter of result is the last letter of input.  Store this value in LL.  then (sorry, newfag, don't know how to do monospace/code):

orig := LL
while (orig.length < (result.length/(repetitions+1)):
    if (every occurrence of orig in result is preceded by LL):
        orig := (LL + orig)
    else:
        orig := (rightmost character that preceeds orig that isn't LL) + orig

return orig;

I bet there is a slick way to do this using a memoization table, like in the KMP algorithm, but I'd have to think about that and don't want to.

>>4
[code]code[/code]
[m]monospace[/m]

nvm, my answer from before is wrong.

Counterexample:
xyxzx -> xyxxyxzxzx
Then my solution generates xzxzx, which is wrong.

This is definitely about finding repeating suffixes though.  Have to think through it.

The problem is boring and the description is poorly written

Since Random rand = new Random(); is not seeded, rand.Next() will return a repeatable set of numbers.  So you just:


public static string DeAnus(string result, int repetitions)
    Random rand = new Random();
    int len = result.Length / repetitions;
    int tempLen = result.Length;
    while(repetitions --> 1)
    {
        rand.Next(0, tempLen-1);
        tempLen -= len;
    }
    return result.Substring(rand.Next(0, len-1), len);
}

>>7
It's a fucking source code. How much more precise do you want it to be written? Fuck you.

>>8
Since Random rand = new Random(); is not seeded
It is implicitly seeded with current time, homosexual.

Anyway, the bruteforce approach is obvious:

def penis(s, repetitions):
    assert not (len(s) % repetitions)
    orig_len = len(s) / repetitions
    def rec_check(s, word):
        print 'rec', s, word
        if not s: return True
        start = 0
        while True:
            start = s.find(word, start)
            end = start + orig_len
            if start < 0:
                return False
            if rec_check(s[:start] + s[end:], word):
                return True
            start = end
    for start in xrange(0, len(s) - orig_len + 1):
        end = start + orig_len
        word = s[start:end]
        if rec_check(s[:start] + s[end:], word):
            return word
    return None
I wonder if the solution has to be unique, I guess it's directly related to any kind of search optimization.

>>10
It is implicitly seeded with current time, homosexual.
Don't be so pedantic, faggot.

DYNAMIC PROGRAMMING

AGILE MODEL DRIVEL DEVELOPMENT

Geehrte Damen und Herren wären sie bereit für einen Augenblick die Augen zu schließen und sich vorzustellen wie ich langsam meinen Penis in ihren Mund führe, halten sie kurz inne, riechen sie diesen Würzigen strengen Duft ein ungewaschenen Glieds? Nähmen sie sich zeit und lassen sie es auf sich wirken während ich langsam weiter ihren Rachen runter gleite merken sie die plötzlich Luftknappheit?  Erschrecken sie sich nicht sie werden sich schnell dran gewöhnen weinen sie ruhig wen ihn danach zumute spüren sie dem Rhythmus des pochenden Gliedes konzentrieren sie einzig und allein auf die würzige Zwiebelwurst die ihren brechreiz wieder und abermals auf die probe stellt. Und dann werden sie eins, eins mit dem Moment der Vollkommenen Entleerung genießen sie jeden einzigen klebrigen tropfen der ihr Kehle herunter tropft und werden sie sich dem Leben in seiner vollen Wonne  bewusst.

What's the answer?  This is killing me

Ive read sicp

>>15
It would be a challenge if I told you the answer.

def solve(string, repetitions, attempt=None):
    if repetitions == 0:
        return True
   
    l = len(string)/repetitions
   
    if not attempt:
        for i in range(len(string)-l):
            attempt = string[i:i+l]
            r = solve(string, repetitions, attempt)
            if r:
                return attempt
        return False
   
    i = -1
    while 1:
        i = string.find(attempt,i+1)
        if i == -1:
            break
       
        r = solve(string[:i]+string[i+l:], repetitions-1, attempt)
        if r:
            return True
    return False


print solve("aacaaacacabaccabacaacaacacabacaaacacabaccabaaacacabaaaacacabacacacaaacacabacbaccaacacabacc",10)

>>18
No, I wanted the fast way.  I should probably just dl SICP.

One idea I had, you could look at the sting as a CFG, so that if your original string is xyxzx, then you add a symbol S, and the following two production rules:

S -> SxSySxSzSx
S -> ""


So basically, you iterate through the original string, and try each character as the starting character, construct a grammer using the two rules above, convert it to chomsky form and use the CYK algorithm to see if the long string parses.  I think this works, and I think it goes in O(m*n^2) time, like the brute force solution, but you don't need to tell it how many repetitions there are.

Sadly that wasn't the question.  Maybe I'm just retarded but this puzzle is good.

>>1
Ive quickly replied that The Suss was a faggot for using LISP. The Suss started crying and kill himself.

>>20
HERESY!

^{:GJS1M 67dcbdbce4a0b67c4b48e86a6ae29205a95e4b83024a9d947213d1231800e8d9
:32 f970c6b48446b35ff9c910dacf94534b
:1309115412 1309373864}
>>20
dubz

>>21
Go fuck an autistic nigger.