Problem bei ersten python versuchen

[BlackJack]

Problem 1 in CoffeeScript:

Code: Alles auswählen

#!/usr/bin/env coffee

Number :: isDivisibleBy7 = -> this % 7 is 0

Number :: containsDigit7 = -> this.toString().indexOf("7") isnt -1

test = (n) -> n.isDivisibleBy7() or n.containsDigit7()

console.log(if test i then "*" else i) for i in [1..100]

Ist der Io-Lösung sehr ähnlich.

Problem 2 zeige ich mal nicht, weil sich daraus eine Python-Lösung ziemlich 1:1 ergibt.

[BlackJack]

Auch eine Haskell-Variante der Lösungen von mir:

Problem 1:

Code: Alles auswählen

isDivisibleBy7 = (==) 0 . mod 7

containsDigit7 = elem '7' . show

convertNumber n = if test n then "*" else show n
    where test n = isDivisibleBy7 n || containsDigit7 n

main = putStr . unlines $ map convertNumber [1..100]

Problem 2:

Code: Alles auswählen

faks = scanl (\a b -> a * succ b) 1

outputPairs r = zip r (faks r)

formatOutputPair (a,b) = show a ++ "! = " ++ show b

main = putStr . unlines $ map formatOutputPair $ outputPairs [0..10]

[BlackJack]

Da Hyperion sich den C64 schon mit BASIC als Zielplattform ausgesucht hat, und mein BASIC-Programm nicht viel anders ausgesehen hätte, habe ich mal Forth auf dem Brotkasten bemüht.

Problem 1:

Code: Alles auswählen

\ Seven-Star                        bj11

: div-by-7? ( n -- ? )
  7 mod 0= ;

: contains-7? ( n -- ? )
  10 /mod 7 =  swap 7 =  or ;

: main ( -- )
  101 1 ?do
    i div-by-7?  i contains-7?  or
    if ." * " else i . then
  loop cr ;

\\ Print all numbers from 1 to 100 but
an asterisk if the number is divisible
by 7 or contains the digit 7.

Problem 2:

Code: Alles auswählen

\ Fac-Table                         bj11

: main ( -- )
  1
  9 0 ?do
    i . del ." ! = " dup u. cr
    i 1+ *
  loop
  drop ;

\\ Print a fac table. Unfortunately only
up to 8! because that is the limit for
the 16 bit integers of VolksFORTH on the
Commodore 64.

Es steht ja schon im Kommentar — mit 16-Bit-Werten kommt man bei der Fakultät nicht all zu weit.

[Hyperion]

Da Hyperion sich den C64 schon mit BASIC als Zielplattform ausgesucht hat, und mein BASIC-Programm nicht viel anders ausgesehen hätte, habe ich mal Forth auf dem Brotkasten bemüht.

Hehe... sorry

Sag mal weißt Du evtl. wie man Modulo auf dem Brotkasten in Assembler ausdrücken kann? Ich war ja fast versucht, meine bescheidenen Assemblerkenntnisse wieder aufzufrischen, aber dafür hatte ich keine Idee.

[lunar]

Da Haskell bereits vergeben ist, bleibt mir noch SWI-Prolog:

Code: Alles auswählen

format_number('*', X) :- 0 is X mod 7, !.
format_number('*', X) :- number_chars(X, L), memberchk('7', L), !.
format_number(S, X) :- swritef(S, "%t", [X]).

write_number(X) :- format_number(S, X), writef("%t\n", [S]).

main :- forall(between(1, 100, X), write_number(X)).

Und Problem 2:

Code: Alles auswählen

factorial(1, 0).
factorial(1, 1).
factorial(F, X) :- P is X - 1, factorial(PF, P), F is PF * X.

format_factorial(S, X) :- factorial(F, X), swritef(S, "%t! = %t", [X, F]).

write_factorial(X) :- format_factorial(S, X), writef("%t\n", [S]).

main :- forall(between(0, 10, X), write_factorial(X)).

[BlackJack]

@Hyperion: Der Prozessor kann ja nur addieren, subtrahieren, und Bits verschieben. Daraus muss man sich das selber basteln. Simpelste, aber vielleicht nicht eleganteste Variante für ``a % b`` ist so lange `b` von `a` abziehen wie ``b > a`` gilt. Das was dann übrig bleibt wäre der Rest der Division. Wenn man mit zählt wie oft man das gemacht hat, bekommt man auch den ganzzahligen Anteil der Division heraus.

Trotz fehlender Eleganz wäre das bei dieser Aufgabe aber IMHO sogar im Bereich des Tolerierbaren. Das wären maximal 14 Schleifendurchläufe für 100 und 7.

Ansonsten muss man sich eine effizientere Division basteln, wo auch der Rest bei heraus fällt. Ist bei Byte/Byte auch nur eine Handvoll Befehle in einer Schleife.

Ich habe sowohl das Modulo-7 als auch das Teilen durch 10 für die Ausgabe umgangen. Ersteres, in dem ich einfach parallel einen Zähler laufen lasse um jeden 7. Durchlauf der Schleife zu erkennen. Und für die Umwandlung in eine Zeichenkette bemühe ich Routinen im BASIC-ROM:

Code: Alles auswählen

        !to "test.prg", cbm
        
        chrout = $ffd2
        strout = $ab1e
        ldf_u8 = $b3a2
        f2str  = $bddd
        
        i = $fa
        j = $fb
        
        * = $c000

        lda #1          ; i = 1
        sta i
        lda #7          ; j = 7
        sta j
loop
        dec j           ; every 7th iteration -> print asterisk
        bne .not_div_7
        lda #7
        sta j
        bne print_asterisk
.not_div_7

        ldy i           ; FAC = i
        jsr ldf_u8
        jsr f2str       ; $0100... = STR(FAC) + 0x00; A/Y = $0100
        
        lda #"7"        ; compare digits with "7"
        cmp $0101
        beq print_asterisk
        cmp $0102
        beq print_asterisk

        tya             ; print number (A/Y = $0101)
        jsr strout
        jmp print_space

print_asterisk
        lda #"*"
        jsr chrout

print_space
        lda #" "
        jsr chrout
        
        inc i           ; i++
        ldy i
        cpy #101        ; already i == 101?
        bne loop
        
        lda #13         ; print newline
        jmp chrout

Und wo ich schon dabei war, hier das Problem 2:

Code: Alles auswählen

        !to "test.prg", cbm
        
        intout = $bdcd
        strout = $ab1e
        ldf    = $bba2
        stf    = $bbd4
        ldf_u8 = $b3a2
        fltmul = $ba28
        fltout = $aabc
        
        i = $fa
        f_one  = $bfe8

        * = $c000

        ldx #4          ; n = 1.0
-       lda f_one,x
        sta n,x
        dex
        bpl -
        
        lda #0          ; i = 0
        sta i
loop
        lda #0          ; print i
        ldx i
        jsr intout
        
        lda #<txt       ; print "! ="
        ldy #>txt
        jsr strout
        
        lda #<n         ; FAC = n
        ldy #>n
        jsr ldf
        
        jsr fltout      ; print FAC + newline
        
        ldy i           ; FAC = i + 1
        iny
        jsr ldf_u8
        
        lda #<n         ; FAC *= n
        ldy #>n
        jsr fltmul
        
        ldx #<n         ; n = FAC
        ldy #>n
        jsr stf
        
        inc i           ; i++
        lda i           ; loop finished?
        cmp #11
        bne loop
        
        rts

txt:    !pet "! =", 0

n:      * = * + 5

Da mache ich auch Gebrauch von den Gleitpunktzahl-Routinen im BASIC-ROM um die Multiplikation und die Umwandlung in Dezimaldarstellung nicht selbst implementieren zu müssen. Da kann man nun natürlich streiten ob das geschummelt ist.

Ach ja: Quelltext ist für den ACME-(Cross-)Assembler.

[Hyperion]

@BlackJack: Danke Gute Erklärung und auch die "Tricks" Deiner Umsetzung habe ich verstanden. Da hätte ich wirklich selber drauf kommen können!

[BlackJack]

Nochmal zu der 6510-Assembler-Lösung von Problem 1: Wenn man die Umwandlung von `i` in Zeichen und die Ausgabe der Zeichenkette nicht mehr über das ROM macht, kommt das Programm mit einer Unterroutine zur Ausgabe eines einzelnen Zeichens als „externe“ Abhängigkeit aus und wird damit portierbarer. Dazu muss man den Code zwischen ``.not_div_7`` und ``print_asterisk`` durch dieses hier ersetzen:

Code: Alles auswählen

        lda i           ; X/Y/A = decimal digits of i
        ldx #"0"-1
        sec
-       inx
        sbc #100
        bcs -
        ldy #"9"+1
-       dey
        adc #10
        bmi -
        adc #"0"-1
        
        cpy #"7"        ; check if there is a "7"
        beq print_asterisk
        cmp #"7"
        beq print_asterisk

        pha             ; print digits in X/Y/A without leading "0"s
        cpx #"0"
        beq +
        txa
        jsr chrout
        jmp ++
+       cpy #"0"
        beq +++
++      tya
        jsr chrout
+++     pla
        jsr chrout
        jmp print_space

Insgesamt wächst dadurch der Code um 38% von 70 auf 97 Bytes. Jetzt muss ich nur noch die zweite Zählvariable durch eine gescheite Division/Modulo ersetzen, dann ist es nicht mehr so „geschummelt“.

[BlackJack]

Okay, ich denke das ist jetzt die finale 6510-Assembler-Version für Problem 1. Keine zweite Zählschleife mehr, sondern eine Modulo-Rechnung, so dass man die Grenzen jetzt im Rahmen von 1 bis 255 ändern kann, in dem man die Konstanten am Anfang setzt:

Code: Alles auswählen

        !to "test.prg", cbm
        
        chrout  = $ffd2
        
        i       = $fa
        tmp     = $fb
        
        * = $c000

        FROM    = 1
        TO      = 100
        
        ldy #FROM       ; i = FROM
        sty i
loop
        sty tmp         ; tmp = (i / 7) / 2; A = i % 7
        lda #0
        ldx #7
        clc
-       rol tmp
        rol
        cmp #7
        bcc +
        sbc #7
+       dex
        bpl -
        
        cmp #0          ; divisible by 7?
        beq print_asterisk

        lda i           ; X/Y/A = decimal digits of i
        ldx #"0"-1
        sec
-       inx
        sbc #100
        bcs -
        ldy #"9"+1
-       dey
        adc #10
        bmi -
        adc #"0"-1
        
        cpy #"7"        ; check if there is a "7"
        beq print_asterisk
        cmp #"7"
        beq print_asterisk

        pha             ; print digits in X/Y/A without leading "0"s
        cpx #"0"
        beq +
        txa
        jsr chrout
        jmp ++
+       cpy #"0"
        beq +++
++      tya
        jsr chrout
+++     pla
        jsr chrout
        jmp print_space

print_asterisk
        lda #"*"
        jsr chrout

print_space
        lda #" "
        jsr chrout
        
        inc i           ; i++
        ldy i           ; already finished?
        cpy #TO+1
        bne loop
        
        lda #13         ; print newline and return to caller
        jmp chrout

Ist jetzt bei 106 Bytes, könnte aber, da keine Abhängigkeit vom BASIC-ROM mehr besteht, 50 KiB RAM am Stück verwenden wenn man das ROM ausblendet.

[Hyperion]

Ist jetzt bei 106 Bytes, könnte aber, da keine Abhängigkeit vom BASIC-ROM mehr besteht, 50 KiB RAM am Stück verwenden wenn man das ROM ausblendet.

Fehlt nur noch die Killerapplikation, die diese 50KiB ausnutzt und diese Routine benötigt

Ob wir den OP irgend wie vergrault haben? :K

[lunar]

@Hyperion: Ich glaube, der OP hat jetzt Angst… hätte ich auch, wenn ich nicht schon länger hier unterwegs wäre

[Masaru]

In jedem Witz steckt ein Fünkchen Wahrheit ... wenn ich über die Jahre hinweg, die ich dieses Forum nun schon lese (und auch lange Zeit meinen Brei dazugegeben habe), betrachte -> wieviele Neulinge verschlissen, verratzt und mundtot gemacht worden sind (direkt, wie indirekt) *lach*und nie wieder einen Fuß in die Foren-Territorialität gesetzt haben ... *TräneAusAugewisch* ... dann hat es fast schon wieder etwas komisches an sich.

Jaja, Wattebäuschen bis ich blute - ich weiss

[Dav1d]

Ich persönlich hab solche Threads gerne . Man lernt was (BlackJacks Assembler) und es macht Spass das Problem auch in anderen Sprachen zu lösen und die Ergebnisse zu vergleichen.

[T64]

Für alle, die die gleiche Aufgabe haben und noch eine Lösung suchen, das hier müsste für 2. funktionieren:

Code: Alles auswählen

def fak(x):
    if x == 0: return 1
    y = 1
    for i in range(1, x +1):
        y = y*i
    return y

for i in range(10):
    print "%s! = %s" % (i, fak(i))

Edit: Bei mir war auch ein kleiner Fehler drin :O ...

[derdon]

Das auch:

Code: Alles auswählen

>>> print '\n'.join("%d! = %d" % (index, value) for index, value in enumerate(imap(math.factorial, xrange(1, 10)), 1))
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880

Edit: Fehler behoben, den hoffentlich noch keiner bemerkt hat

[EyDu]

@derdon: Jetzt musst du uns nur noch erklären, warum du `enumerate` UND `xrange` brauchst

Code: Alles auswählen

print "\n".join("%d! = %d" % (x, math.factorial(x)) for x in range(1, 10))

[lunar]

Ich finde ja einen endlosen Iterator mit allen Paaren viel schöner

Code: Alles auswählen

facs = ((x, math.factorial(x)) for x in count())
print '\n'.join('{0}! = {1}'.format(x, y) for x, y in islice(facs, 10))

Ansonsten fängt die Fakultät ja eigentlich bei 0 an

[derdon]

Ihr habt ja soooo Recht

EyDu: Das kann ich nicht erklären

[BlackJack]

Die eigenständigere 6510-Assembler-Variante ohne Rückgriff auf die Rechenroutinen im BASIC-ROM des C64 ist noch in Arbeit. Aber zwischendurch mal schnell der BASIC-Einzeiler, der das selbe macht (wie die Assembler-Variante, die wohl irgendwo bei ≈200 Zeilen enden wird):

Code: Alles auswählen

1 N=1:FOR I=0 TO 12:PRINT I "!=" N:N=N*(I+1):NEXT

[BlackJack]

Okay, hier ist nun die Assemblervariante für Problem 2 die nicht die Rechenroutinen im BASIC-ROM verwendet: http://pastebin.com/uCCF6UXb

Edit: Noch mal ein Nachtrag zur Forth-Lösung auf dem C64. Jetzt auch hier mit 32-Bit, also bis 12!:

Code: Alles auswählen

\ Fac-Table                           bj


: d*u ( d u -- d*u )
  dup rot * -rot um* rot + ;


: main ( -- )
  page 1.
  13 0 ?do
    i . del ." ! = " 2dup d. cr
    i 1+ d*u
  loop
  2drop ;

\\ Print a fac table from 0! to 12!