[QUIZ#7] RedWing (Scheme und Bash)


RedWing

Erfahrenes Mitglied
Hallo,

hier meine Lösung in Scheme:

Bash:
#! /usr/bin/scm

(define living_cell #\o)
(define dead_cell #\+)

; read_line_from_file: port -> string
(define (read_line_from_file inFile)
  (let ((char (read-char inFile)))
    (if (not (eof-object? char))
        (if (char=? #\newline char)
            (string)
            (string-append (string char) (read_line_from_file inFile)))
        char)))

; const_grid_from_file: port x integer x integer -> vector
(define (const_grid_from_file inFile curRow rows)
  (let ((row (read_line_from_file inFile)))
    (if (= rows curRow)
        (make-vector rows)
        (let ((grid (const_grid_from_file inFile (+ curRow 1) rows)))
             (vector-set! grid curRow (list->vector (string->list row))) grid))))

; get_neighbour_count: vector x integer x integer -> integer
(define (get_neighbour_count grid curX curY)
  (do ((y (- curY 1) (+ y 1))
       (neighbours 0))
      ((= y (+ curY 2)) neighbours)
      (do ((x (- curX 1) (+ x 1)))
          ((= x (+ curX 2)))
            (if (and (> y -1) (> x -1) (< y (vector-length grid))
                     (< x (vector-length (vector-ref grid curY)))
                     (or (not (= x curX)) (not (= y curY)))
                     (char=? (vector-ref (vector-ref grid y) x) living_cell))
                (set! neighbours (+ neighbours 1))))))

; compare_neighbours: integer x list -> boolean
(define (compare_neighbours neigbours rule)
  (if (null? rule)
      #f
      (or (= neigbours (car rule)) (compare_neighbours neigbours (cdr rule)))))

; bear_new_cell: integer x integer x vector -> char
(define (bear_new_cell curX curY grid rule)
  (let ((neighbours (get_neighbour_count grid curX curY)))
    (if (and (compare_neighbours neighbours (list-ref rule 1))
	     (char=? (vector-ref (vector-ref grid curY) curX) dead_cell))
        living_cell
        (if (and (compare_neighbours neighbours (list-ref rule 0))
                 (char=? (vector-ref (vector-ref grid curY) curX) living_cell))
            living_cell
            dead_cell))))

; output_grid: vector -> unspecified
(define (output_grid grid)
  (do ((y 0 (+ y 1)))
      ((= y (vector-length grid)))
      (do ((x 0 (+ x 1)))
          ((= x (vector-length (vector-ref grid y))) (newline))
          (display (vector-ref (vector-ref grid y) x)))))


; next_generation: vector -> vector
(define (next_generation grid configs rule)
  (do ((newGrid (make-vector (vector-length grid)))
       (y 0 (+ y 1)))
      ((= y (vector-length grid)) newGrid)
      (vector-set! newGrid y (make-vector (vector-length (vector-ref grid y))))
      (do ((x 0 (+ x 1)))
          ((= x (vector-length (vector-ref grid y))))
          (vector-set!(vector-ref newGrid y) x (bear_new_cell x y grid rule)))))

; compute_final_grid: integer x vector -> vector
(define (compute_final_grid configs grid rule)
    (do ((i 1 (+ i 1)))
        ((= i configs) (next_generation grid configs rule))
	(display (string-append (string-append (string-append (number->string i) "/") (number->string configs)) "\r"))
        (set! grid (next_generation grid configs rule))))


; start_simulation_from_file: port -> port
(define (start_simulation_from_file inFile rule)
  (let ((gridRows (string->number (read_line_from_file inFile)))
        (configs (get_number_configs_from_file inFile)))
    (output_grid (compute_final_grid configs (const_grid_from_file inFile 0
                                              gridRows) rule)) inFile))

; get_number_configs_from_file: port -> integer
(define (get_number_configs_from_file inFile)
  (let ((columns (read_line_from_file inFile)))
       (string->number (read_line_from_file inFile))))

;(let-syntax ((append_element (syntax-rules () (append_element ))))
 ; (append left_rule (list (- (char->integer element) (char->integer #\0)))))

; parse_short_rule: list -> list
(define (parse_short_rule rule)
  (let ((left_rule (list)) (right_rule (list)) (fill_left #t))
	(for-each (lambda (element)
			(if (char=? element #\/)
			    (set! fill_left #f)
			    (if fill_left
				(set! left_rule (append left_rule (list (- (char->integer element)
									   (char->integer #\0)))))
				(set! right_rule (append right_rule (list (- (char->integer element)
									     (char->integer #\0))))))))
		   rule) (append (list left_rule) (list right_rule))))

(define (main args)
  (if (= (length args) 4)
      (let ((inFile (open-input-file (list-ref args 2)))
            (rule (parse_short_rule (string->list (list-ref args 3)))))
           (close-input-port (start_simulation_from_file inFile rule)))
      (begin
        (display "Usage: gol.scm <start_hefe_gitter.txt> <rule_short_syntax>")
        (newline))))

;(main (command-line-arguments))
(main *argv*)
(exit)
Die Lösung ist straight-forward:
Das Universum wird aus der Datei in ein 2 dimensionales Array eingelesen. Dieses Array wird dann von einer Generation in die nächste, mit Hilfe eines Bufferuniversums (da ja der Generationswechsel für alle Zellen simultan erfolgen soll) überführt.
Die Regeln für das Gebären bzw Sterben einer Zelle in der neuen Generation können dem Programm in Kurzschreibweise (bspw. 23/3 für Conways Regel) als Argument übergeben werden.

Man mag sich wundern warum man dem Programm auch die Anzahl der zu berechnenden Konfigurationen übergeben kann, da diese ja aus dem Textfile gelesen werden sollen. Der Grund liegt in folgendem Bashskript was John helfen soll die Entwicklung bis zur Generation X mit zu verfolgen (d.h jede Zwischenkonfiguration wird auf der Konsole mit ausgegeben):

Bash:
#! /bin/bash

script_filename=./hefe.scm
#script_filename=./hefe

config_steps=1
script_option_start_config_file=hefe_kanone.txt
script_option_short_rule=23/3
output_file=hefe_out.txt
sleep_time=0.1

rows=`head -1 $script_option_start_config_file`
columns=`head -2 $script_option_start_config_file | tail -1`
real_configs=`head -3 $script_option_start_config_file | tail -1`

echo $rows > $output_file
echo $columns >> $output_file
echo $config_steps >> $output_file
tail -$rows $script_option_start_config_file >> $output_file

for ((i=0; i < $real_configs; i++));
do
    echo $i

    $script_filename $output_file \
                     $script_option_short_rule > tmp.out
    echo $rows > $output_file
    echo $columns >> $output_file
    echo $config_steps >> $output_file
    cat tmp.out >> $output_file
    clear
    cat tmp.out
    rm tmp.out
    sleep $sleep_time
done
Eine interessante Startkonfiguration ist die Gleiterkanone bestehend aus einer Kanone (im Bild oben) , welche Gleiter erzeugt, und einem Gleiterabsorber (im Bild unten rechts):
Code:
28
59
70
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++o+++++++++++++++++++++++++++++
+++++++++++++++++++++++++++oooo+++++++++++++++++++++++++++++
++++++++++++++++++o+++++++oooo+++++++++oo+++++++++++++++++++
+++++++++++++++++o+o++++++o++o+++++++++oo+++++++++++++++++++
+++++oo+++++++++o+++oo++++oooo+++++o++++++++++++++++++++++++
+++++oo+++++++++o+++oo+++++oooo++++o++++++++++++++++++++++++
++++++++++++++++o+++oo++++++++o+++++++++++++++++++++++++++++
+++++++++++++++++o+o++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++o+++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++o++++o+++++++++++
+++++++++++++++++++++++++++++++++++++++++oo+oooo+oo+++++++++
+++++++++++++++++++++++++++++++++++++++++++o++++o+++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Gruß,
RedWing
 
Zuletzt bearbeitet:
Hallo RedWing,

wäre hätte das gedacht, dass es diesmal gleich zwei Lösungen in Scheme geben wird, die unterschiedlicher nicht sein könnten :D Ich konnte mich mit LISP & Co. leider nie so ganz anfreunden, deshalb verzeihst du mir hoffentlich, dass ich mir den Quelltext jetzt nicht im Detail angeschaut habe ;-]

Die Idee mit dem Bash-Skript, das die Generierung einer Bilderfolge übernimmt, finde ich sehr cool. Aber ich hab noch nicht ganz verstanden, warum man jetzt die zu berechnende Generation sowohl in der Eingabedatei als auch über die Kommandozeilenparameter übergeben muss. Wenn man die Anzahl nur über die Datei übergibt, sollte es doch genauso klappen. Die Schleife würde dann so aussehen:
Bash:
for ((i=0; i < $real_configs; i++));
do
    echo $i
 
    $script_filename $output_file \
                     $script_option_short_rule > tmp.out
    echo $rows > $output_file
    echo $columns >> $output_file
    echo 1 >> $output_file
    cat tmp.out >> $output_file
    clear
    cat tmp.out
    rm tmp.out
    sleep $sleep_time
done
Oder hab ich was übersehen?

Grüße,
Matthias
 

RedWing

Erfahrenes Mitglied
Hallo Matthias,

wäre hätte das gedacht, dass es diesmal gleich zwei Lösungen in Scheme geben wird, die unterschiedlicher nicht sein könnten :D Ich konnte mich mit LISP & Co. leider nie so ganz anfreunden, deshalb verzeihst du mir hoffentlich, dass ich mir den Quelltext jetzt nicht im Detail angeschaut habe ;-]
ja war auch schon verwundert :) Hab mit Scheme auch noch nicht viel gemacht. Hatte das vor Jahren mal in einer Vorlesung bei mir an der FH kennengelernt. Die Aufgabe bot sich an um rauszufinden ob mein Gehirn auch auf funktionaler Ebene eine etwas komplexere Aufgabe bewerkstelligen kann :)
Scheme hat ein paar sehr nette Features (bspw. call/cc), und eine breitere praktische Basis (auch was man so an Bibliotheken und Resourcen im Inet finden kann) als wie ich gedacht hätte.
Was ich allerdings merkwürdig finde ist, dass die Implementierungen die man so von Scheme (wie das bei *Lisp* ausschaut weiß ich nicht) findet (Compiler sowie Interpreter) um einiges langsamer sind als wenn man bspw. ein gleichwertiges Programm in C schreibt. Die beiden Implementierungen von mir sollten eigtl. äquivalent bzw die gleiche Komplexität besitzen und doch ist das Schemeskript ein vielfaches langsamer, wobei sich der Laufzeitzuwachs (bei größeren Gittern) allerdings proportional zwischen beiden Programmen verhält, aber wer weiß...


Die Idee mit dem Bash-Skript, das die Generierung einer Bilderfolge übernimmt, finde ich sehr cool. Aber ich hab noch nicht ganz verstanden, warum man jetzt die zu berechnende Generation sowohl in der Eingabedatei als auch über die Kommandozeilenparameter übergeben muss. Wenn man die Anzahl nur über die Datei übergibt, sollte es doch genauso klappen.
Ja natürlich, hab da irgendwie den Wald vor lauter Bäumen nicht gesehen, danke für den Hinweis. Allerdings muss man ein paar mehr Änderungen vornehmen da ich die Startkonfiguration anfangs einfach in das $output_file kopiere (und das Scheme Skript somit $real_configs in der Ausgabe überspringen würde), das kann man dann so nicht mehr machen. Habs oben mal geändert.

Gruß,
RedWing

P.S. Cool das du dir die Zeit nimmst die Lösungen kritisch-konstruktiv durchzuforsten.