PHP-Junkies hier klicken - Fiese Aufgabe
lima-city → Forum → Programmiersprachen → PHP, MySQL & .htaccess
apache
ausgeben
bedingung
bit
devise
dritte
ergebnis
funktion
hauptteil
minute
nachtrag
permutation
schleifen
sekunde
sen
skript
stellen
test
variante
warte
-
Sooo, nach l?ngerer lc-Abstinenz will ich euch hier mal bisschen ?rgern.
Viel Spass beim L?sen folgender Aufgabe:
Regel 1: $r soll nur ein einziges Mal ausgegeben werden
Regel 2: Bis auf den Wert von $i darf nichts an dem Skript ge?ndert werden
Hier das Skript:
<?php
$i=1;
$r="Ein Mal ist ausreichend<br>\n";
$s="";
function z(){global $i;$i^=14;return $i;}
function y(){global $i;$i=($i>>5)+14;return $i;}
function x($j){$j++;$j<7?($j<0?$j=y():$j=z()):($j>100?$j-=99:$j=z());return $j;}
$i=x($i);for($t=0;$t<$i;$t++)$s.=$r;
echo "<html><body>$s</html></body>";
?>
Es gibt nur eine L?sung. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Also, ich hab es schon bis auf zwei Ausgaben geschafft. Da d?rfte der Rest nur noch ein Kinderspiel sein. Allerdings muss ich sagen: Ziemlich unsauberer Code (Absicht?). Und mit PHP hat das auch wenig zu tun. Mehr mit Mathematik, oder?
MfG
alopex
edit:
Ja, das mit den seltenen Operatoren habe ich auch mitbekommen
-
Die Anzahl der Ausgaben folgt keinem strikt linearen Muster, also heisst zwei Ausgaben nicht unbedingt nahe dran :-p
Der Code ist nicht unsauber, sondern sehr unfreundlich *g*
Und mit PHP hat das schon was zu tun:
1. Bringt ?bung zum Verst?ndnis zu seltener gebrauchten Operatoren
2. Man kann den ganzen L?sungsweg per PHP ausrechnen -
Ist das nicht einfach l?sbar mit einer IF-Schleife ??
Da braucht man doch die Funktionen gar nicht!
Gru -
$i = 15; und fertig... 8)
*gel?st*
@Vorposter: Ich glaube es ging ums Verst?ndnis...
H2O -
AAAAAAAAAAAAAAAAAAAAAAAAARRRRRRGH
Leute, tut mir Leid. Da ist ein fieser Bug drin.
Dies ist der neue Code:
<?php
$i=1;
$r="Ein Mal ist ausreichend<br>\n";
$s="";
function z(){global $i;$i|=14;return $i;}
function y(){global $i;$i=($i>>5)+14;return $i;}
function x($j){$j++;$j<7?($j<0?$j=y():$j=z()):($j>100?$j-=99:$j=z());return $j;}
$i=x($i);for($t=0;$t<$i;$t++)$s.=$r;
echo "<html><body>$s</html></body>";
?>
Er unterscheidet sich nur an folgender Stelle (fett markiert):
function z(){global $i;$i|=14;return $i;}
Also |= statt ^=
Ich hab in der Eile OR und XOR verwechselt...
-
Sagt man dann... ;)
Und dabei hatte ich schon eine L?sung...
Dann dieses Mal eine Frage:
Wird es wieder eine kleinere Zahl sein, also so 1 - 100 oder mehr ?ber 1000 liegen?
H2O -
h2o schrieb:
Wird es wieder eine kleinere Zahl sein, also so 1 - 100 oder mehr ?ber 1000 liegen?
Ist das nicht egal? Hier soll nichts ausprobiert werden, es geht um Reverse Engineering *gg*
Wenn das nicht hilft, dann probierts halt mit Permutationen. -
Oweia...
Die Zahl liegt ?ber 12.000...
Habe mir gerade ein Script geschrieben, was alle Zahlen bis 12.000 ?berpr?ft hat.
Langsam macht mein Apache nicht mehr mit...
Gib mir wenigstens mal einen Tipp, scheinbar bin ich ja der einzige mitmacht...
So einen Bereich von 1.000 Zahlen (z.B. 30.000 - 31.000)
Ansonsten kommen wir (ich??) ja nie drauf...
H2O
0-checka:Nee, ich gebe dir keinen Tip. Wird doch nur spannender f?r die Zuschauer, wenn du dich so abrackerst *l?l*
Das war ?brigens genau das, was ich mit Permutation meinte, aber das ist ja nun keine sinnvolle Vorgehensweise, vor allem nicht bei dem m?glichen Zahlenbereich. Da kannst du ja einen ganzen Apachenstamm zum Rechnen dran setzen *gg*
H2O:
Naja, mittlerweile habe ich raus, dass die Zahl gr??er als 22000 ist.
Naja, wenn du sagst, dass es einen gro?en Zahlenbereich gibt, dann gehe ich lieber anderer Arbeit nach und nicht deinem Quiz
Ich bezweifle, dass es noch jemand l?sen wird 
0-checka:Ist doch toll. Damit habe ich mal wieder bewiesen, wie doof alle sind bzw. wie krass schlau ich bin *g*
Ich werde einfach noch bisschen abwarten und dann anfangen, einen L?sungsansatz nach dem anderen zu pr?sentieren
H2O::
Naja, da sieht man doch eigentlich nur, dass sich hier im Forum wenige zu einer solchen Aufgabe einlassen... Und auch ich habe eigentlich wenig Lust mich zur Zeit damit zu besch?ftigen.
Solltest du mit deinen L?sungsans?tzen fertig sein, werde ich mir mal eine solche Aufgabe ausdenken, die DU l?sen kannst Warte aber noch was mit den L?sungss?tzen, ich versuche es doch nochmal... 8)
-
Ich hab relativ viele L?sungen gefunden. Es gibt aber sicher noch mehr (z.B. -385,5).
L={-385, -386, -387, ..., -416} -
Wollte gerade anfangen, mein Script ?ber den Minus-Bereich laufen zu lassen *gg*
Nachdem ich das hier gefunden habe "$j<0?" ist mir dann eingefallen, dass die Zahl auch kleiner sein kann...
@ Vorposter: Respekt, echt klasse...
Ich glaube jetzt guckt 0-checka dumm aus der W?sche, schlie?lich meint er, es gibt nur eine L?sung...
H2O -
Naja, eigentlich gibt es ja unendlich viele L?sungen, weil zw. zwei Zahlen immer unendlich viele rationale Zahlen liegen. Aber auf die "zahlreichen" L?sungsans?tze von 0-checka bin ich trotzdem mal gespannt.
-
Durch das >>5 ist doch wohl klar, wie viele L?sungsm?glichkeiten es gibt, oder? Und das mit den Fliesskommazahlen... na ja, ich vergesse in PHP immer, das ein Typ kein Typ ist... fuckmist etc.. Und ich guck gar nicht dumm aus der W?sche... *g*
Nachtrag:
Und unendlich viele L?sungen gibt es eh nicht, wegen begrenztem Speicher bei Variablen.
Nachtrag 2:
Und ?berhaupt... ihr Ausprobierer
-
Durch das >>5 ist doch wohl klar, wie viele L?sungsm?glichkeiten es gibt, oder? Und das mit den Fliesskommazahlen... na ja, ich vergesse in PHP immer, das ein Typ kein Typ ist... fuckmist etc.. Und ich guck gar nicht dumm aus der W?sche... *g*
lol, aber immerhin war es mehr als nur eine L?sung!
Nachtrag:
Und unendlich viele L?sungen gibt es eh nicht, wegen begrenztem Speicher bei Variablen.
Theoretisch schon
Nachtrag 2:
Und ?berhaupt... ihr Ausprobierer
100% ausprobiert habe ich gar nicht und phattek scheinbar gar nicht(??)...
H2O -
h2o schrieb:
lol, aber immerhin war es mehr als nur eine L?sung!
Ich wollte euch nicht verwirren!!! Und diese Scheisskommazahlen. Da braucht man nur an eine Stelle ein (int) zu schreiben, dann hat sich das erledigt. Ich habe nur nicht daran gedacht.
h2o schrieb:
100% ausprobiert habe ich gar nicht und phattek scheinbar gar nicht(??)...
Ihr solltet doch gar nicht ausprobieren
Nachdenken ist die Devise. Mit Nachdenken h?tte man es innerhalb von 5 Minuten geschafft...
-
Ihr solltet doch gar nicht ausprobieren
Nachdenken ist die Devise. Mit Nachdenken h?tte man es innerhalb von 5 Minuten geschafft...
Das kann man hinterher immer sagen
Tsss... Aber warte nur, bis du mal l?sen musst. ;)
H2O -
Wann wird nur einmal was ausgegeben?
$i=x($i);for($t=0;$t<$i;$t++)$s.=$r;
echo '<html><body>$s</html></body>';
Beschr?nken wir uns mal nur auf $i==1
Was ist x($i)?
function x($j){$j++;$j<7?($j<0?$j=y():$j=z()):($j>100?$j-=99:$j=z());return $j;}
x($i)=y() oder z()
Wann ist z()=1?
function z(){global $i;$i|=14;return $i;}
z() ist eien Oder-Bit-Operatoren wobei $i mit 14 geodert wird.
14==0...01110
Durch das oder sind also alle Zahlen der Form x...x111x m?glich (mit x als 0 oder 1). Aber es gilt 1==0...01. Somit kann z() nicht 1 werden.
Wann ist y()=1?
function y(){global $i;$i=($i>>5)+14;return $i;}
y() ist eine Shift-Funktion. Somit muss man sich nur ?berlegen welche Zahlen -13 ergibt, wenn sie um 5 Stellen verschoben wird.
phattek schrieb:
L={-385, -386, -387, ..., -416}
Und das sind die Zahlen, welche um 5 Stellen verschoben -13 ergeben.
Jetzt muss man nur noch schauen, bei welchen dieser Werte die Fallunterscheidungen in x($j) y() ausgibt.
Jens -
Ich schildere mal den eigentlich simplen Gedankengang:
Hier noch mal das Script:
<?php
$i=1;
$r="Ein Mal ist ausreichend<br>\n";
$s="";
function z(){global $i;$i|=14;return $i;}
function y(){global $i;$i=($i>>5)+14;return $i;}
function x($j){$j++;$j<7?($j<0?$j=y():$j=z()):($j>100?$j-=99:$j=z());return $j;}
$i=x($i);for($t=0;$t<$i;$t++)$s.=$r;
echo "<html><body>$s</html></body>";
?>
Wir sehen, dass $i am Ende 1 sein muss, um das gew?nschte Ergebnis zu liefern. (10 Sekunden)
Wir stellen fest, dass nirgendwo Rekursionen zu finden sind (10 Sekunden)
Funktion x() ist der Einstiegspunkt f?r das ganze Verfahren. (10 Sekunden)
Wir stellen fest, dass wir verschachtelte Bedingungen in x() haben und fangen an, sie auseinander zu pfl?cken (10 Sekunden)
Wir stellen fest, dass wir eine erste Bedingung mit zwei Varianten haben und jede Variante ebenfalls eine Bedingung mit zwei Varianten. Macht also 2 hoch 2 = 4 vollst?ndige Bedingungen. (10 Sekunden)
Wir haben die erste vollst?ndige Bedingung: (j <=> i + 1) < 7 && (j <=> i + 1) < 0
(10 Sekunden)
Da dies die Bedingung ist, die uns zur L?sung f?hren wird, lassen wir sie erstmal weg.
Zweite vollst?ndige Bedingung:
(j <=> i + 1) < 7 && (j <=> i + 1) > 0 (10 Sekunden)
i m?sste in diesem Falle also -1...5 sein (10 Sekunden)
Durch die zweite Bedingung wird z() aufgerufen. (10 Sekunden)
z() greift auf i (-1 >= i <= 5) zur?ck und gibt ein Ergebnis zur?ck, das an den Hauptteil des Skriptes weitergegeben wird. (10 Sekunden)
z() muss also 1 zur?ckliefern. (10 Sekunden)
Kann irgendeine Zahl zwischen -1 und 5 bitweise mit einer OR-Verkn?pfung mit 14 als Ergebnis 1 haben? Nein (10 Sekunden)
Die zweite vollst?ndige Bedingung wird verworfen (10 Sekunden)
Wir ermitteln die dritte vollst?ndige Bedingung als (j <=> i + 1) >= 7 &&
(j <=> i + 1) > 100. (10 sekunden)
Wir erkennen, das der zweite Teil der Bedingung als alleinige Beschreibung der Bedingung ausreicht und notieren (j <=> i + 1) > 100. (10 Sekunden)
Wir extrahieren die Aktion f?r die 3. vollst?ndige Bedingung:
j -= 99 (10 Sekunden)
Wir erkennen, das j aufgrund der 3. vollst?ndigen Bedingung mindestens 101 sein muss, dass aber bei der kleinsten m?glichen Zahl in diesem Fall bei der Substraktion immer mindestens 2 ?brig bleibt. (10 Sekunden).
Wir stellen fest, dass das Ergebnis an den Hauptteil, in dem der Wert von i 1 betragen muss, zur?ckgegeben wird und somit die dritte vollst?ndige Bedingung niemals das gew?nschte Ergebnis liefern wird. (10 Sekunden)
ups, das fenster ist schon voll lange ge?ffnet. war mit anderen dingen besch?ftigt. muss mal reichen an dieser stelle. den rest kriegt ihr auch selber hin und wenn ihr zum schluss dann zusammenrechnet, dann werden so um die 5 minuten rauskommen. cu -
So gro?er Meister!
Schon anderhalb Tage sind vergangen, und wir harren deiner L?sung des Problems. Mein Apache-PHP-Gespann hat nach 14816.518981934 Sekunden keine L?sung im (Integer-)Bereich zwischen -1_000_000_000 und +1_000_000_000 gefunden. Auf die 32-Bit-Integergrenze (gibts die bei PHP ?berhaupt?) zu testen, hatte ich keine Lust, denn der Notebookl?fter hat zu viel L?rm gemacht.
Ja, du hast richtig erkannt: Ich war auch zu faul, mein Gehirn zu benutzen. Ich habe einfach den Algorithmus leicht erweitert und in eine for()-Schleife gepackt:
<?php
require('../hted/essentials.php');
$i=1;
$test = $i;
$r="Ein Mal ist ausreichend<br>\n";
$s="";
function z(){global $i;$i|=14;return $i;}
function y(){global $i;$i=($i>>5)+14;return $i;}
function x($j){$j++;$j<7?($j<0?$j=y():$j=z()):($j>100?$j-=99:$j=z());return $j;}
echo "<html><body>";
warn("Starte Script ...");
$runtime = calculate_runtime();
for($ct = 1000000000; $ct > -1000000000; $ct--) {
$i=x($i);
if($i == 1) {
warn( sprintf("%s[%s]<br />\n", $test, $i) );
printf("%s[%s]<br />\n", $test, $i);
break;
}
}
$runtime = calculate_runtime($runtime);
printf("==(%ss)==<br />\n", $runtime);
//for($t=0; $t<$i; $t++) $s.=$r;
//echo "$s";
echo "</html></body>";
?>
Wer auch seinen Prozessor foltern will: Das Script essentials.php sorgt nur daf?r, dass die Laufzeit berechnet wird, und mit warn() Texte in ein Logfile geschrieben werden k?nnen. Man kann warn() auch durch echo() oder print() ersetzen, aber dann muss der Browser wahrscheinlich einige Stunden warten, bis eine Ausgabe erfolgt.
Download von essentials.php:
http://alopex.pyrokar.lima-city.de/index.php/PHP/essentials.html
Ach ja, noch was: Wer das nachmachen will, muss in der (richtigen) "php.ini" den Wert "max_execution_time" suchen und auf einen gr??eren Wert einstellen. Ich habe f?r den Test 40000 (Sekunden) genommen, das m?sste theoretisch f?r -2^32 bis +2^32 gen?gen, zumindest auf meinem (uralten) Notebook (Athlon XP 2000 Mobile 1,66 GHz, dank SpeedSwitch aber meistens nur mit 666 MHz laufend).
MfG
alopex
P.S.: Ich wei?, ich bin unw?rdig, ich bin unw?rdig ...
-
Ihr habt die L?sung doch schon. Und den "richtigen" L?sungsweg habe ich im Ansatz ja schon beschrieben, einfach von da aus weitergehen
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
