[Quiz#3] kuddeldaddeldu (PHP)

kuddeldaddeldu

Erfahrenes Mitglied
Hi,

habe gerade keine Zeit zum Kommentieren...

PHP:
#/usr/bin/php5
<?php
class BrainScript {
   private $memory;           // Speicherzellen
   private $m_pointer;        // aktuelle Position im Speicher
   private $program;          // komprimiertes Brainf*ck-Programm
   private $pc;               // Programmzähler (aktueller Befehl)
   private $input;            // Eingabearray
   
   public function __construct() {
      $this->memory = array(0);
      $this->input = array();
      $this->m_pointer = 0;
      $this->pc = 0;
      $this->program = array();
   }
   
   public function load($file) {
      // Kommentare entfernen
      $code = preg_replace('/[^\+^\-^<^>^\.^,^\[^\]]/', '', file_get_contents($file));
      // Code aufteilen in zusammenhängende +,-,<,> und einzelne ,,.,[,]
      // Für das Klammern-Matching werden die Offsets mit zurückgegeben
      $pattern = '/[<]+|[>]+|[\.]?|[,]?|[\+]+|[\-]+|[\[]?|[\]]?/';
      $result = preg_match_all($pattern, $code, $matches, PREG_OFFSET_CAPTURE);
      if($result) {
	 $loops = array();
	 // komprimiertes Programm aus den Matches erstellen
	 foreach($matches[0] as $match) {
	    switch(substr($match[0], 0, 1)) {
	       case '+':
		  $this->program[] = array('+', strlen($match[0]));
		  break;
	       case '-':
		  $this->program[] = array('-', strlen($match[0]));
		  break;
	       case '>':
		  $this->program[] = array('>', strlen($match[0]));
		  break;
	       case '<':
		  $this->program[] = array('<', strlen($match[0]));
		  break;
	       case ',':
		  $this->program[] = array(',');
		  break;
	       case '.':
		  $this->program[] = array('.');
		  break;
	       case '[':
		  // zunächst Sprungadresse 0 speichern
		  $this->program[] = array('[', 0);
		  // aktuelle Position (pc) auf den Loop-Stack schreiben
		  $loops[] = count($this->program) - 1; 
		  break;
	       case ']':
		  if(empty($loops)) {
		     throw new Exception("Öffnende Klammer fehlt.");
		  }
		  // Position der öffnenden Klammer vom Loop-Stack holen
		  $open_bracket_at = array_pop($loops);
		  // Rücksprungadresse setzen
		  $this->program[] = array(']', $open_bracket_at - 1);
		  // Sprungadresse der öffnenden Klammer auf aktuelle Position setzen
		  $this->program[$open_bracket_at][1] = count($this->program) - 1;
		  break;
	       default:
		  break;
	    }
	 }
	 if(!empty($loops)) {
	    throw new Exception("Nicht alle Klammern geschlossen.");
	 }
      } else {
	 throw new Exception("Kein BrainScript-Code gegeben.");
      }
      unset($matches);
      unset($code);
   }
      
   public function execute() {
      while($this->pc < count($this->program)) {
	 switch($this->program[$this->pc][0]) {
	    case '+':
	       $this->incrementCell($this->program[$this->pc][1]);
	       break;
	    case '-':
	       $this->decrementCell($this->program[$this->pc][1]);
	       break;
	    case '>':
	       $this->moveRight($this->program[$this->pc][1]);
	       break;
	    case '<':
	       $this->moveLeft($this->program[$this->pc][1]);
	       break;
	    case ',':
	       $this->readChar();
	       break;
	    case '.':
	       echo chr($this->getCellValue());
	       break;
	    case '[':
	       $this->startLoop($this->program[$this->pc][1]);
	       break;
	    case ']':
	       $this->endLoop($this->program[$this->pc][1]);
	       break;
	    default:
	       break;
	 }
	 $this->pc++;
      }
   }
   
   private function readChar() {
      if(empty($this->input)) {
	 $this->input = array_map(create_function('$item', 'return ord($item);'), str_split(fgets(STDIN)));
	 $this->input[] = 0;        // Eingabe terminieren
      }
      $this->memory[$this->m_pointer] = array_shift($this->input);
   }
   
   private function getCellValue() {
      return $this->memory[$this->m_pointer];
   }
   
   private function moveRight($num) {
      // falls erforderlich, den Speicher erweitern
      if(!isset($this->memory[$this->m_pointer + $num])) {
	 $new_cells = $this->m_pointer + $num - count($this->memory) + 1;
	 $this->memory = array_merge($this->memory, array_fill(0, $new_cells, 0));
      }
      $this->m_pointer += $num;
   }
   
   private function moveLeft($num) {
      // falls erforderlich, den Speicher erweitern
      if($this->m_pointer - $num < 0) {
	 $new_cells = $num - $this->m_pointer;
	 $this->memory = array_merge(array_fill(0, $new_cells, 0), $this->memory);
	 $this->m_pointer = 0;
      } else {
	 $this->m_pointer -= $num;
      }
   }  
    
   private function incrementCell($num) {
      if($this->memory[$this->m_pointer] + $num > 255) {
	 $this->memory[$this->m_pointer] = $num - 2;
      } else {
	 $this->memory[$this->m_pointer] += $num;
      }
   }
      
   private function decrementCell($num) {
      if($this->memory[$this->m_pointer] - $num < 0) {
	 $this->memory[$this->m_pointer] = 255 - $num + 2;
      } else {
	 $this->memory[$this->m_pointer] -= $num;
      }
   }
   
   private function startLoop($jumpTo) {
      if($this->getCellValue() == 0) {
	 $this->pc = $jumpTo;
      }
   }
   
   private function endLoop($jumpTo) {
      $this->pc = $jumpTo;
   }
}

// Main
      
ini_set('memory_limit', '256M');
$program = new BrainScript();
try {
   $program->load($argv[1]);
} catch(Exception $e) {
   echo $e->getMessage() . "\n";
   echo $e->getTraceAsString() . "\n";
}
$program->execute();
echo "\n";

?>
 
Hi,

wohl wahr. Die Mandelbrotmenge geht ja gar nicht... :eek:
Na ja, viel Optimierung ist auch gar nicht dabei. Ich fasse eigentlich nur aufeinanderfolgende <,>,+ und - zusammen. Also im Prinzip das, was Du in Deiner bf.c auch machst. Die Funktionalität aus Deiner optimize.c fehlt, und wenn ich mir das Mandelbrotprogramm so anschaue, macht das eine ganze Menge. Vielleicht habe ich diese Woche noch ein bischen Zeit zum "Nachrüsten"...
Leider gibt's keine weiteren PHP-Lösungen zum Vergleichen.

LG
 
Hier mal PHP, wie ich das machen würde. Statt nem Array mit den Instrukionen hab ich eine verkette Liste, wo jede Anweisung auf die ihr folgende zeigt, ich hoffe das spart die Zeit, die sonnst fürs Array beim "nachgucken" verbracht wird.
Wenn ich das interpretiere, ist es ungefär genau so langsam wie deine Version, wenn man den von toString() generierten Code mit eval ausführt, dann "schafft" er es wenigstens... =)

Außerdem ist mir aufgefallen, ass die Verwendung von define-Konstanten in switch/case langsamer ist, als wenn ich direkt Zahlen nehm, seltsam.

Mandelbrot eval( toString() ): 6min, 9sek
Mandelbrot interpretiert von mir (1. Zeile): 21sek
Mandelbrot interpretiert von dir (1.Zeile ): 1min, 56sek

Och doch ein ganz schöner Unterschied. Naja, das kommt vermutlich von den arrayLookups und den Funktionsaufrufen, die ich mir gespart hab.

Gruß, Olli

Hier meine quick&dirty Lösung:
PHP:
<?php
    
    define( "NOP",          0 );
    define( "MODIFY",       1 );
    define( "MOVE",         2 );
    define( "PUTCHAR",      3 );
    define( "GETCHAR",      4 );
    define( "LOOP_START",   5 );
    define( "LOOP_END",     6 );
    
    class Instruction {
        public $type;
        public $next;

        public $jump;
        public $amount;
        
        public function __construct( $type ) {
            $this->type = $type;
        }
    }
    
    class BrainFuck {
        private $first;
        private $memory;
        
        public function __construct( $input ) {
            $last = $first = new Instruction( NOP );
            $loop = array();
            
            $length = strlen( $input );
            for( $position = 0; $position < $length; $position++ ) {
                $c = $input[ $position ];
                
                $next = null;
                switch( $c ) {
                    case '+':
                    case '-':
                        $next = new Instruction( MODIFY );
                        $amount = $this->countSymbol( substr( $input, $position ) );
                        $next->amount = (($c == '+' ? 1 : -1) * $amount );
                        $position += $amount - 1;
                        break;
                        
                    case '>':
                    case '<':
                        $next = new Instruction( MOVE );
                        $amount = $this->countSymbol( substr( $input, $position ) );
                        $next->amount = (($c == '>' ? 1 : -1) * $amount );
                        $position += $amount - 1;
                        break;
                    
                    case '[':
                        $next = new Instruction( LOOP_START );
                        $stack[] = $next;
                        break;
                    
                    case ']':
                        if( count( $stack ) == 0 )
                            throw "Fehler, fehlerhafte Schleife!";
                        
                        $next = new Instruction( LOOP_END );
                        $next->jump = array_pop( $stack );
                        $next->jump->jump = $next;
                        break;
                        
                    case '.':
                        $next = new Instruction( PUTCHAR );
                        break;
                    
                    case ',':
                        $next = new Instruction( GETCHAR );
                        break;
                        
                    default:
                        // ingore
                }
                if( $next ) {
                    $last->next = $next;
                    $last = $next;
                }
            }
            
            if( count( $stack ) != 0 )
                throw "Fehler, fehlerhafte Schleife!";
            
            $this->first = $first;
        }
        
        public function run() {
            $this->memory = array_fill( 0, 30000, 0 );
            $instr = $this->first;
            $pointer = 0;
            
            while( $instr != null ) {
                switch( $instr->type ) {
                    // MODIFY
                    case 1:
                        $this->memory[ $pointer ] =
                            ($this->memory[ $pointer ] + $instr->amount) & 0xff;
                        
                        break;
                    
                    // MOVE
                    case 2:
                        /*
                        $pointer = ($pointer + $instr->amount) % 30000;
                        if( $pointer < 0 )
                            $pointer += 30000;
                            */
                        $pointer += $instr->amount;
                        break;
                    
                    // LOOP_START
                    case 5:
                        if( ! $this->memory[ $pointer ] )
                            $instr = $instr->jump;
                        break;
                    
                    // LOOP_END
                    case 6:
                        if( $this->memory[ $pointer ] )
                            $instr = $instr->jump;
                        break;
                        
                    // PUTCHAR
                    case 3:
                        echo chr( $this->memory[ $pointer] );
                        break;
                    
                    // GETCHAR
                    case 4:
                        $this->memory[ $pointer ] = (int)fgetc( STDIN ) & 0xff;
                        break;
                }
                $instr = $instr->next;
            }
        }
        
        public function toString() {
            $result = array(
                '$mem = array_fill( 0, 30000, 0 );',
                '$p = 0;'
            );
            
            $instr = $this->first;
            while( $instr ) {
                switch( $instr->type ) {
                    case MODIFY:
                        $result[] = sprintf( '$mem[$p] = ($mem[$p] + %d) & 0xff;',
                            $instr->amount );
                        break;
                    
                    case MOVE:
                        $result[] = sprintf( '$p += %d;', $instr->amount );
                        break;
                    
                    case LOOP_START:
                        $result[] = 'while( $mem[$p] ) {';
                        break;
                    
                    // LOOP_END
                    case 6:
                        $result[] = '}';
                        break;
                        
                    // PUTCHAR
                    case 3:
                        $result[] = 'echo chr($mem[$p]);';
                        break;
                    
                    // GETCHAR
                    case 4:
                        $result[] = '$temp = (int)fgetc( STDIN ); $mem[$p] = ($temp < 0 ? 0 : $temp) & 0xff;';
                        break;
                }
                
                $instr = $instr->next;
            }
            return join( $result, "\n" );
        }
        
        private function countSymbol( $input ) {
            $i = 0;
            $length = strlen( $input );
            while( $i < $length && $input[$i] == $input[0] )
                $i++;
            
            return $i;
        }
    }
    
    $fp = join( file( $argv[1] ) );
    $x = new BrainFuck( $fp );
    eval( $x->toString() ); 
    // $x->run();
?>
 
PHP:
      // Kommentare entfernen
      $code = preg_replace('/[^\+^\-^<^>^\.^,^\[^\]]/', '', file_get_contents($file));
Das macht vermutlich nicht das, was du erwartest. Die Negation erstreckt sich immer auf die komplette Zeichenklasse. Wenn du jedem Zeichen ein ^ voranstellst, bewirkst du damit nur, dass ^ auch als Element der Zeichenklasse interpretiert (und damit nicht aus der Eingabe entfernt) wird. Abgesehen davon: wenn man einzelne Zeichen negieren könnte, welche Semantik sollte dies dann besitzen, wenn gleichzeitig auch nicht-negierte Zeichen in der Zeichenklasse auftreten?

Mein Verbesserungsvorschlag an dieser Stelle daher:
PHP:
      // Kommentare entfernen
      $code = preg_replace('/[^+\-<>.,\[\]]+/', '', file_get_contents($file));
Wie man sieht, kann man sich auch gleich noch ein paar Backslashes sparen, da in Zeichenklassen die Sonderfunktionen mancher Metazeichen aufgehoben sind. Der Backslash vor [ wäre eigentlich unnötig, aber aus Symmetriegründen zum ] habe ich den doch mal dringelassen. Das zusätzliche + am Ende könnte zu einer schnelleren Ausführung beitragen, aber das ist nur ein Bauchgefühl von mir und müsste erst noch verifiziert werden.

Ein ganz verwegener Programmierer könnte auch noch auf die Idee kommen, das ganze so abzukürzen:
PHP:
      $code = preg_replace('/[^+-.<>[\]]+/', '', file_get_contents($file));
Aber das ist schon ziemlich grenzwertig ;-)

Grüße,
Matthias
 
Hi Olli,

danke für die Alternativlösung. :)
Ich hätte nicht gedacht, dass die Array-Lookups und Funktionen so viel ausmachen. Mit den Optimierungen aus Deiner optimize.c könnte man wohl noch mal einiges rausholen, wenn ich dem Aufbau der Menge so zusehe.

Allerdings ist dafür das Parsen anscheinend sehr langsam. Ich hab' das mal mit diesem Textadventure probiert, dass jemand verlinkt hatte. Hab's nach ungefähr 10 Minuten abgebrochen. Eine kleine Testausgabe zeigte, dass das Programm bis dahin nicht fertig geparst war.
Deine C/Assembler-Lösung ist dafür in null komma nix durch damit. ;)
Leider hatte ich diese Woche nicht die Zeit, meine Version auf eine verkettete Liste umzustellen.

Matthias Reitinger hat gesagt.:
Das macht vermutlich nicht das, was du erwartest. Die Negation erstreckt sich immer auf die komplette Zeichenklasse. Wenn du jedem Zeichen ein ^ voranstellst, bewirkst du damit nur, dass ^ auch als Element der Zeichenklasse interpretiert (und damit nicht aus der Eingabe entfernt) wird. Abgesehen davon: wenn man einzelne Zeichen negieren könnte, welche Semantik sollte dies dann besitzen, wenn gleichzeitig auch nicht-negierte Zeichen in der Zeichenklasse auftreten?

Ups, klar. Danke. ;)

LG
 
Zurück