Knobelaufgabe

[NicTheQuick]

Hi Leute,

ich habe eine Knobelaufgabe für euch, die ich übrigens selbst noch nicht gelöst habe. Folgender Code:

Code: Alles auswählen

EnableExplicit

Procedure.q breakIt(r.q, s.s)
	Protected rMul.q = 1, hash.q = 0
	Protected l.i = Len(s)
	Protected *c.Character = @s + (l - 1) * SizeOf(Character)
	Protected i.i
	For i = 1 To l
		hash ! ((*c\c - 'a') * rMul)
		*c - SizeOf(Character)
		rMul * r
		rMul & $ffffffff
	Next
	ProcedureReturn hash
EndProcedure

Debug breakIt(35476431, "aaaababaaaaaaabbaaaaaabbbbbaaaaa")
Debug breakIt(35476431, "aaaaabaabbbbbbbaabbaabaaababbaab")
Debug breakIt(443, "aaabbabbabbbbbababababababbaaaaaaaaaaa")
Debug breakIt(443, "aaabbababbababaabaabbbbbbaababbabaabab")

Wir ihr seht, gibt es eine Funktion 'breakIt()', die laut Aufgabenstellung eine Zahl zwischen 0 und 2.000.000.000 bekommt und als zweiten Parameter einen String, der nur die Buchstaben 'a' und 'b' enthält. Die Funktion berechnet dann einen Hash des Strings 's' in Abhängigkeit zu 'r', der zwischen 0 und 2^32 liegt.
An dem Beispiel sieht man, dass zwei unterschiedliche Strings den selben Hash generieren können. Es gibt aber auch Strings, bei denen das nicht so ist.

Aufgabe ist nun eine Funktion zu schreiben, die zu einem 'r' und einem String 's' einen weiteren String 's2' generiert, der in Zusammenhang mit 'r' den selben Hash hat wie 's', wobei 's' ungleich 's2' und Len(s2) = Len(s) sein muss. Falls ein solcher String 's2' nicht existiert, soll einfach nichts ausgegeben werden.

So, ihr habt Zeit bis morgen Abend. Ich übrigens auch.

[man-in-black]

moin,

der Code ist in keinster Weise optimiert; konnte bloß den PC nicht aus machen, ohne mich der Aufgabe zu stellen^^
(keine Garantie für Nichts )

MFG
MIB

Code: Alles auswählen

Procedure solve2(string.s,hash.q,r.q,exp.b)
  
  If exp=>1
    rMul.q = 1
    For x=1 To exp
      rMul.q*r
      rMul & $ffffffff
    Next
    
    ; ->Fall: char="a" (0)
    
    fac.b = 0
    string1.s = string.s+Str(fac)
    
    hash1.q = hash ! (rmul*fac)
    solve2(string1.s,hash1.q,r,exp-1)
    
    ; ->Fall: char="b" (1)
    
    fac.b = 1
    string2.s = string.s+Str(fac)
    
    hash2.q = hash ! (rmul*fac)
    
    solve2(string2.s,hash2.q,r,exp-1)
    
  Else
    
    If Len(Bin(hash)) = 1
      string.s = string.s+Bin(hash)
      
      Debug ">>"+ReplaceString(ReplaceString(string,"0","a"),"1","b")
    EndIf
    
  EndIf
    
EndProcedure


Procedure solve1(r.q,s1.s,hash.q)
  
  exp= Len(s1)-1
  
  
  rMul.q = 1
  For x=1 To exp
    rMul.q*r
    rMul & $ffffffff
  Next
  
 ;->Fall: char="a" (0)
  hash1.q = hash ! (rmul*0)
  
  solve2("0",hash1,r,exp-1)
  
  ;->Fall: char="b" (1)
  hash2.q = hash ! (rmul*1)
  
  solve2("1",hash2,r,exp-1)
  
EndProcedure


solve1(35476431,"aaaababaaaaaaabbaaaaaabbbbbaaaaa",2918098977)

PS: kann unoptimiert echt ewig dauern (mit dieser Abfrage ~10min)...
/Edit:
PS2: sorry, hab mich verguckt. PB ist noch schön am rechnen^^ (hat aber deine beiden Lösungen schon ausgespuckt)

[NicTheQuick]

Hehehe, das sieht mir stark nach Bruteforce und Rekursion aus.

Was ich vielleicht nicht erwähnt habe: Der String kann bis zu 1.000.000 Zeichen enthalten und das Problem ist in weniger als einer Sekunde lösbar.

[man-in-black]

moin,

kein Bruteforce? Da hat man mal nen seltenen Grund, heutige PC's an ihre Grenzen zu bringen und "darf" es nicht...

(unwissend, wie ich bin:) Wie kann man denn in kürzester Zeit eine schwer zu definierende Menge aus möglichen Lösungen
errechnen, wenn man xor nicht durch ne handlichere Formel (math. Ausdruck) ersetzen kann? Mir ist schon klar,
dass meine Lösung noch zu viele Möglichkeiten untersucht, aber bis auf die letzten beiden Zeichen (in s2), kann man den Hash nicht vorhersagen.
Und ja, mir ist schon bewusst, dass genau deshalb xor genommen wird^^
Daher: Her mit der Auflösung, um mich einerseits eines besseren zu belehren und andererseits, damit ich wieder ruhig schlafen kann!
Bin was Verschlüsselungen/Hashs betrifft noch ziemlich grün hinter den Ohren...

(hast noch mehr Aufgaben von dem Kaliber?^^+Lösungen)

MIB

[Franky]

Nabend, also ich würde sagen, wir gehen das mal Schrittweise an.

Zunächst hat mich das "a" und "b" verwirrt, wir können das aber schonmal rauskürzen, es kommt zu 1 und 0, ergo können wir ja mal einen "Gedankentable" aufbauen

BeispielCode sei "aabbabab", r sei 5

Code: Alles auswählen

a ->0  *  10011000100101101
a ->0  *  00011110100001001
b ->1  *  00000110000110101   =>    00000110000110101
b ->1  *  00000001001110001   =>    00000001001110001
a ->0  *  00000000001111101
b ->1  *  00000000000011001   =>    00000000000011001
a ->0  *  00000000000000101 
b ->1  *  00000000000000001   =>    00000000000000001

Summe  10022221202444301  =>     00000111001231104
%2        10000001000000101  =>     00000111001011100

Ergo muss man jetzt "nur noch" eine Kombination aus X Werten finden, bei denen die Anzahl gesetzter Bits für jedes Bit eine gerade Zahl ergibt.
Daraus kann man dann an einigen Stellen von a nach b bzw. umgekehrt umswitchen.

So, den letzten Schritt müsst ihr alleine machen, ich geh nu pennen

Gruß

Franky

[NicTheQuick]

Die Lösung habe ich jetzt, allerdings bisher nur als Text und nicht in Code. Man kann ein lineares Gleichungssystem mit 32 Variablen aufstellen, das man lösen kann, solange mindestens 32 Buchstaben im String vorkommen. Das löst man dann mittels Gaußverfahren, wie man es eventuell aus der Schule kennt oder auf jeden Fall aus dem ersten Semester Mathe an der Uni.

Hier auch nochmal die vollständige Aufgabe, allerdings auf englisch: