[QUIZ#9] OnlyFoo (Bash)

OnlyFoo

Erfahrenes Mitglied
Eine Version des Turtles in bash.
Dies ist vermutlich eine der langsamsten und ungenausten Versionen, die abgegeben wurden, da ich auf die Rechnung mit Fließkommazahlen verzichten musste.

Im Anhang ein paar Ausgabegraphiken. Besonders deutlich wird die Ungenauigkeit an dem tutorials1 Beispiel.
Der Baum sieht auch recht seltsam aus, aber ich schiebe das auf die Fixkommarechnung.

Das Script unterstützt jedoch fast alle in der Aufgabe vorgestellten Features.


Bash:
#!/bin/bash

#
# Bash kann nur mit 64bit Ganzzahlen rechnen.
# Ich habe mich entschieden, mit festen 4 Stellen hinter dem Komma zu rechnen.
#
# Dies ist eine lookup-Tabelle für den Cosinus. Die Werte wurden
# so berechnet:
# result = []
# for i in range( 0, 900, 2 ):
#    print str( int( math.cos( math.radians(i * 0.1) ) * 10000 ) )
# 
#
LOOKUP_COSINUS=(
    10000 9999 9999 9999 9999 9998 9997 9997 9996 9995 9993 9992 9991 9989
    9988 9986 9984 9982 9980 9978 9975 9973 9970 9967 9964 9961 9958 9955
    9952 9948 9945 9941 9937 9933 9929 9925 9921 9916 9912 9907 9902 9897
    9892 9887 9882 9876 9871 9865 9859 9854 9848 9841 9835 9829 9822 9816
    9809 9802 9795 9788 9781 9774 9766 9759 9751 9743 9735 9727 9719 9711
    9702 9694 9685 9677 9668 9659 9650 9640 9631 9622 9612 9602 9593 9583
    9573 9563 9552 9542 9531 9521 9510 9499 9488 9477 9466 9455 9443 9432
    9420 9408 9396 9384 9372 9360 9348 9335 9323 9310 9297 9284 9271 9258
    9245 9232 9218 9205 9191 9177 9163 9149 9135 9121 9106 9092 9077 9063
    9048 9033 9018 9003 8987 8972 8957 8941 8925 8910 8894 8878 8862 8845
    8829 8813 8796 8779 8763 8746 8729 8712 8694 8677 8660 8642 8625 8607
    8589 8571 8553 8535 8517 8498 8480 8461 8443 8424 8405 8386 8367 8348
    8329 8309 8290 8270 8251 8231 8211 8191 8171 8151 8131 8110 8090 8069
    8048 8028 8007 7986 7965 7944 7922 7901 7880 7858 7836 7815 7793 7771
    7749 7727 7705 7682 7660 7637 7615 7592 7569 7547 7524 7501 7477 7454
    7431 7408 7384 7360 7337 7313 7289 7265 7241 7217 7193 7169 7144 7120
    7095 7071 7046 7021 6996 6971 6946 6921 6896 6870 6845 6819 6794 6768
    6743 6717 6691 6665 6639 6613 6586 6560 6534 6507 6481 6454 6427 6401
    6374 6347 6320 6293 6266 6238 6211 6184 6156 6129 6101 6073 6045 6018
    5990 5962 5934 5906 5877 5849 5821 5792 5764 5735 5707 5678 5649 5620
    5591 5562 5533 5504 5475 5446 5417 5387 5358 5328 5299 5269 5239 5210
    5180 5150 5120 5090 5060 5030 5000 4969 4939 4909 4878 4848 4817 4786
    4756 4725 4694 4663 4632 4601 4570 4539 4508 4477 4446 4415 4383 4352
    4320 4289 4257 4226 4194 4162 4131 4099 4067 4035 4003 3971 3939 3907
    3875 3842 3810 3778 3746 3713 3681 3648 3616 3583 3551 3518 3485 3452
    3420 3387 3354 3321 3288 3255 3222 3189 3156 3123 3090 3056 3023 2990
    2957 2923 2890 2856 2823 2789 2756 2722 2689 2655 2621 2588 2554 2520
    2486 2453 2419 2385 2351 2317 2283 2249 2215 2181 2147 2113 2079 2044
    2010 1976 1942 1908 1873 1839 1805 1770 1736 1702 1667 1633 1598 1564
    1529 1495 1460 1426 1391 1357 1322 1287 1253 1218 1184 1149 1114 1079
    1045 1010 975 941 906 871 836 801 767 732 697 662 627 593 558 523 488
    453 418 383 348 314 279 244 209 174 139 104 69 34 )


# Teilt die Zahl durch 10000 und gibt das Ergebnis mit
# Kommastellen aus.
function float() {
    echo "$(( $1 / 10000 )).$(( $1 % 10000 ))"
}


#
# Wandelt eine Fließkommazahl in eine Fixkommazahl um
#
function int() {
    PRE=${1%.*}
    SUF=$(printf "%-4s" ${1#*.} | tr ' ' 0)
    
    echo $(( PRE * 10000 + SUF ))
}

#
# Gibt den Cosinus für eine Zahl zurück. Benutzt die Lookup-Tabelle
#
function cos() {
    # Auf 0 bis 2pi bringen
    local PHI=$(( ($1 < 0 ? -$1 : $1) % (31415 * 2) ))
    
    # Auf 0 bis pi bringen
    local PHI=$(( PHI > 31415 ? (2 * 31415) - PHI : PHI ))
    
    # Faktor setzten, wenn > 0.5pi
    local FACTOR=$(( PHI > 15707 ? -1 : 1 ))
    
    # Auf 0 bis 0.5pi bringen
    local PHI=$(( PHI > 15707 ? 31415 - PHI : PHI ))
    
    # Index berechnen + Wert zurückgeben
    local IDX=$(( PHI * 900 / 31415 ))
    echo $(( ${LOOKUP_COSINUS[$IDX]} * FACTOR ))
}


#
# sin(x) = cos( x - pi/2 )
#
function sin() {
    cos $(( $1 - 15707 ))
}


#
# Gibt den Anfang einer SVG Graphik aus.
#
function svg_start() {
    local WIDTH=$1
    local HEIGHT=$2
    
    echo '<?xml version="1.0" ?>'
    echo '<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"'
    echo ' "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">'
    
    echo '<svg xmlns="http://www.w3.org/2000/svg" version="1.1"'
    echo "width='$WIDTH' height='$HEIGHT' stroke=\"black\" fill=\"none\">"
}

#
# Gibt das Ende der SVG Graphik aus.
#
function svg_end() {
    echo '</svg>'
}


#
# Beginnt einen <POLYLINE>-Tag
#
function svg_polyline_start() {
    local X=$(float $1)
    local Y=$(float $2)
    
    echo -n "<polyline points=\"$X $Y"
}

#
# Fügt einen Punkt in die Polyline ein
#
function svg_polyline_point() {
    local X=$(float $1)
    local Y=$(float $2)
    
    echo -n ",$X $Y"
}

#
# Endet einen <POLYLINE>-Tag
#
function svg_polyline_end() {
    echo "\" />"
}


#
# Führt eine Sequenz von + - F [ ] Zeichen aus und gibt das
# Ergebnis als SVG aus.
#
function run_sequence() {
    local ANGLE=0
    local FIX=10000
    
    local SEQUENCE=$1
    local POSITION_X=$( int $2 )
    local POSITION_Y=$( int $3 )
    local STEP_FORWARD=$( int $4 )
    local STEP_ANGLE=$(( $( int $5 ) * 174 / FIX ))
    
    local WIDTH=$6
    local HEIGHT=$7

    # Stack als Memory für [ ... ]
    local MEMORY=( )
    
    # Beginne die Ausgabe
    svg_start $WIDTH $HEIGHT
    svg_polyline_start $POSITION_X $((HEIGHT * FIX - POSITION_Y))
    
    # Gehe jedes Zeichen durch
    local IDX
    for(( IDX=0; IDX <= ${#SEQUENCE}; IDX++ )) ; do
        CHAR=${SEQUENCE:$IDX:1}
        
        
        # Drehe im Uhrzeigersinn
        if [ x$CHAR = x+ ] ; then
            ANGLE=$(( ANGLE + STEP_ANGLE ))
        
        
        # Drehe gegen den Uhrzeigersinn
        elif [ x$CHAR = x- ] ; then
            ANGLE=$(( ANGLE - STEP_ANGLE ))
        
        
        # Bewege Vorwärts
        elif [ x$CHAR = xF ] ; then
            POSITION_X=$(( POSITION_X + ( $(cos $ANGLE) * STEP_FORWARD / FIX) ))
            POSITION_Y=$(( POSITION_Y + ( $(sin $ANGLE) * STEP_FORWARD / FIX) ))
            
            # Zeichne den Punkt
            svg_polyline_point $POSITION_X $((HEIGHT * FIX - POSITION_Y))
        
        
        # Schreibe aktuelle Position + Winkel der Schildkröte
        # auf den Stack
        elif [ x$CHAR = x[ ] ; then
            MEMORY=( "${MEMORY[@]}" $POSITION_X )
            MEMORY=( "${MEMORY[@]}" $POSITION_Y )
            MEMORY=( "${MEMORY[@]}" $ANGLE )
            
        
        # Lese aktuelle Position + Winkel der Schildkröte
        # vom Stack und beginne ein neues Linienstück
        elif [ x$CHAR = x] ] ; then
            ANGLE=${MEMORY[${#MEMORY[@]}-1]}
            POSITION_Y=${MEMORY[${#MEMORY[@]}-2]}
            POSITION_X=${MEMORY[${#MEMORY[@]}-3]}
            
            unset MEMORY[${#MEMORY[@]}-1]
            unset MEMORY[${#MEMORY[@]}-1]
            unset MEMORY[${#MEMORY[@]}-1]
            
            # Neues Linienstück starten
            svg_polyline_end
            svg_polyline_start $POSITION_X $((HEIGHT * FIX - POSITION_Y))
            
        fi
        
        # Alle 500 Anweisungen einen kleinen Fortschrittsbericht ausgeben.
        if [ $(( IDX % 500 )) -eq 0 ] ; then
            echo $(( $IDX * 100 / ${#SEQUENCE} ))"% fertig" >&2
        fi
        
    done
    
    # Polyline und SVG beenden
    svg_polyline_end
    svg_end
    
    #Fertig!
    echo "100% fertig" >&2
}

#
# Gibt nicht den ASCII-Code eines Zeichens zurück, sondern seine
# Position im Alphabet. Gibt für Sonderzeichen oder ähnliches 0 zurück.
# Die Methode heißt ASCII, weil mir nichts besseres einfiel... und
# function nr_of_char_in_alphabet() find ich doof.
# 
function ascii() {
    expr index ABCDEFGHIJKLMNOPQRSTUVWXYZ "$1"
}


#
# Lese die Eingabe-Werte vom User
#
read WIDTH HEIGHT
read POSITION_X POSITION_Y
read STEP_FORWARD
read STEP_ANGLE
read SEQUENCE

# Schaue ob wir das ganze erweitern sollen
read ITERATIONS
if [ -n "$ITERATIONS" -a ${ITERATIONS}0 -gt 0 ] ; then
    read LINE
    
    # Array mit Ersetzungsregeln
    RULES=( )
    
    # Kein Leerzeichen in der Zeile? Dann eine einfache
    # F -> Bla Ersetzungsregel
    if [ $(expr index "$LINE" " ") -ne 2 ] ; then
        RULES=( [$(ascii F)]=$LINE )
        
    else
        # Sonnst lese solange bis wir eine leere Zeile lesen (eof)
        while [ -n "$LINE" ] ; do
            NAME=${LINE% *}
            RULE=${LINE#* }
            RULES[$(ascii $NAME)]=$RULE
            
            read LINE
        done
    fi
    
    
    # Erweiterte die Ausgangszeichenkette
    for (( IT = 0; IT < ITERATIONS; IT++ )) ; do
        echo "Erweitere, Schritt $(($IT+1)) von $ITERATIONS" >&2
        NEW_SEQUENCE=
        
        IDX=0
        for(( IDX=0; IDX <= ${#SEQUENCE}; IDX++ )) ; do
            # Jedes Zeichen C angucken, und schauen ob wir eine Regel
            # C -> Bla
            # haben, wenn ja, Bla an die Ausgabe hängen, sonnst
            # das Zeichen unverändert durchreichen.
            CHAR=${SEQUENCE:$IDX:1}
            
            if [ $(ascii "\\$CHAR") -gt 0 ] && [ -n "${RULES[$(ascii $CHAR)]}" ] ; then
                # Ersetzten
                NEW_SEQUENCE=${NEW_SEQUENCE}${RULES[$(ascii $CHAR)]}
                
            else
                # Durchreichen
                NEW_SEQUENCE=${NEW_SEQUENCE}${CHAR}
                
            fi
        done
        
        # Sequenz mit neuer Sequenz überschreiben
        SEQUENCE=$(echo ${NEW_SEQUENCE[@]} | tr -d ' ')
    done
fi

# Die Schildkröte loslaufen lassen!
run_sequence $SEQUENCE $POSITION_X $POSITION_Y $STEP_FORWARD $STEP_ANGLE $WIDTH $HEIGHT
 

Anhänge

  • hilbert.bash.png
    hilbert.bash.png
    33,1 KB · Aufrufe: 27
  • tutorials1.bash.png
    tutorials1.bash.png
    3,1 KB · Aufrufe: 22
  • tree.bash.png
    tree.bash.png
    114,9 KB · Aufrufe: 17
Zuletzt bearbeitet:

RedWing

Erfahrenes Mitglied
Coole Sache mit dem bash-skript. Jetzt würde mich noch interessieren ob das jemand als Batch-Job hinbekommt :)

Apropos Fließkomma, hast du es denn mal mit "bc" versucht? Wenn man bc mit dem Schalter -l startet kann man auch cos und sin verwenden und mit Fließkommazahlen rechnen.

Gruß,
RedWing
 

OnlyFoo

Erfahrenes Mitglied
Jupp ich kenn bc, hab auch überlegt den zu verwenden, aber dachte mir, das ist mehr Herausforderung wenn ichs selbst mache.