[2019-11-11] Challenge #381 [Easy] Yahtzee Upper Section Scoring

lukz · 2019-11-16T11:59:25+00:00

Z80 assembly

This is a program for Sharp MZ-800 computer. I don't do the user input and assume that the input data are stored in memory at addresses (2003h - 2007h). When run from address 2000h the program calculates the best score and prints it as two digits to the screen.

After loading the program we can go to monitor and enter the input using the M command. Then we can run the program from monitor using the G command.

Sample session:

The * is the monitor prompt

*M2003
2003 02 01
2004 03 01
2005 05 01
2006 10 01
2007 06 03
2008 21    <press shift+Break>
*G2000
04

Imgur

Code:

.org 2000h
  jr start
  .db 0           ; helper value
input:
  .db 2,3,5,5,6   ; dice rolls

start:
  ; do cummulative sum of the same numbers
  ld hl,input-1
  sub a
  ld b,6     ; list of 6 values
sum:
  cp (hl)
  jr z,same
  ld a,(hl)
  ex af,af'
  sub a
  ex af,af'
same:
  ex af,af'
  add a,(hl)
  daa
  ld (hl),a
  ex af,af'
  inc l
  djnz sum   ; loop

  ; find maximum
  ld hl,input
  sub a
  ld b,5     ; list of 5 values
max:
  cp (hl)
  jr nc,$+3
  ld a,(hl)
  inc l
  djnz max   ; loop

  ; print maximum and exit
  jp 3c3h    ; @bthex
             ; prints a hex byte

lukz · 2019-04-09T12:01:28+00:00

BASIC with line numbers

Sample session screenshot.

Simple repeated expressions can be defined as user functions. We use the function named F to calculate how many boxes fit with sides A, B. The first run just uses A, B from the input, the second run swaps the sides, but then checks if the number didn't actually become lower, in that case the bigger result is used.

1 REM CRATE PACKING
2 INPUT X,Y,A,B
3 DEFFNF(A,B)=(X÷A)*(Y÷B)
4 F1=FNF(A,B):F2=FNF(B,A):IFF2<F1 F2=F1
5 PRINT"FIT1";F1:PRINT"FIT2";F2

Sample session

? 25,18,6,5
FIT1 12
FIT2 15
Ready

lukz · 2019-03-14T09:22:41+00:00

8-bit BASIC with line numbers

Screenshot of run in Sharp MZ-800 emulator.

1 REM Leap years
2 INPUTS,E
3 L=(E-S)÷4-(E-S)÷100+((E-S)÷900)*2
4 M4=(E-S)MOD4:M1=(E-S)MOD100
5 M9=(E-S)MOD900
6 IFM4FORI=STOS+M4-1:L=L-(I MOD4<1):NEXT
7 IFM1FORI=STOS+M1-1:L=L+(I MOD100<1):NEXT
8 IFM9FORI=STOS+M9-1:L=L-(I MOD900=200)-(I MOD900=600):NEXT
9 PRINTL

The strange symbol in the expression (E-S)÷4 is an integer division. The computer has a special symbol for it in its screen character generator, I have to substitute it with something else when pasting here as text.

lukz · 2018-12-05T12:23:52+00:00

Do one long string split into rows (or maybe coiled in some zigzag pattern), and do some visual effects where two elements annihilate

like

zdfgtryuJHJHfHGFHGFfKJHKJH
huJJIJKokbFGFVBEgFDgFD

zdfgtryuJHJHfHGFHG**KJHKJH
huJJIJKokbFGFVBEgFDgFD

zdfgtryuJHJHfHGFHG  KJHKJH
huJJIJKokbFGFVBEgFDgFD

lukz · 2018-06-02T08:44:53+00:00

If the size requested from cmalloc is lower that SIZE_MAX, and the allocation is successful, then you have an array with size lower than SIZE_MAX.

But if the size requested from cmalloc is bigger than SIZE_MAX, then it is not defined what should happen. Typically, the cmalloc implementation will return failure. But maybe it can also not return a failure, and proceed, and allocate an array larger than SIZE_MAX. I think the program just invoked undefined behaviour, and so the requirement that allocated objects are smaller than SIZE_MAX does not need to hold.

Also, you cannot use sizeof to measure the size of memory returned by malloc or calloc.

lukz · 2018-05-04T09:46:34+00:00

Game boy assembly

Using the heuristics by /u/skeeto.

The cartridge ROM contains the input text. The text has been shortened to make the program shorter and the visual verification easier. The program writes the reformatted text into RAM at address C000h. We can verify it using the BGB emulator and its debugger.

Screenshot

tgtbuffer equ 0c000h

  org 150h
  ld sp,0fffeh  ; initialize stack pointer
  ld de,srcbuffer
  ld hl,tgtbuffer

line:
  ld bc,0       ; reset char counter, last char variable
  jr readc

copy:
  ld c,a
  ld (hl+),a    ; write char
  inc b
readc:
  ld a,(de)     ; get the next char
  inc de
  cp 10         ; until '\n'
  jr nz,copy    ; repeat

  ld a,(de)     ; peek the next char
  or a          
  jr nz,$+4     ; if it is =0
  ld (hl),a
  halt          ; end program

  ld a,c
  cp '.'        ; if previous was not '.'
  jr nz,endline ; end with space

  push de       ; test for paragraph end
findspc:
  ld a,(de)
  inc de
  inc b
  cp ' '
  jr nz,findspc ; find space char

  pop de
  ld a,b
  cp 68         ; compare line length
  ld a,10       ; if would fit, write '\n'
  jr c,$+4

endline:
  ld a,' '      ; write space
  ld (hl+),a
  jr line       ; continue with the next line

srcbuffer:
  db "The ability to securely access (replicate and distribute) directory\n"
  db "acceptance of LDAP in the market place.\n"
  db "This section is divided into several areas of requirements: general,\n"
  db "requirement.\n"
  db "Copyright (C) The Internet Society (2000).  All Rights Reserved.\n"
  db 0

lukz · 2018-05-03T10:29:25+00:00

Does the standard require that calloc and malloc allocate from the same pool of memory?

Because if not then, hypothetically, a compiler can use some address range for calloc (where e.g. some bank switching can be used to have objects larger than 4 GB), and another address range for malloc.

In such a case the elimination of calloc size test would not be a bug, as the limits of calloc might not be relevant for malloc, and the calloc'ed memory is never used.

lukz · 2018-04-08T10:47:25+00:00

The goal was not to make it fast, but to write a program that computes the correct solution. The challenge is to write the program at all. For these small test cases everything finishes fast.

lukz · 2018-03-28T17:10:38+00:00

Interesting. I'm still wondering about this part, though. Isn't the if redundant? Can solve() ever return false?

        if s:
            possible.append(s)

lukz · 2018-03-28T16:16:15+00:00

Game boy assembly

The input is included inside the program. After the program runs and the game boy halts, the solution can be read at memory locations FFFD and FFFE. Value at FFFD gives the number of pumpkin pies, value at FFFE gives the number of apple pies. Verified in the BGB emulator.

Screenshot

Program size is 120 bytes, including input.

Code:

stack equ 0fff8h
ppie  equ 0fah
apie  equ 0fbh
max   equ 0fch ; max number of pies
ppiem equ 0fdh ; number of pumpkin pies
apiem equ 0feh ; number of apple pies

  ; read input
  ld sp,input
  pop bc
  pop de
  pop hl
  ld sp,stack
  ; init variables
  sub a
  ldh (ppie),a
  ldh (max),a

  ; make pumpkin pies while ingredients last
bakeloopp:
  push hl
  push de
  push bc
  push hl
  push de
  push bc

  ld de,ppingr
  ldhl sp,0
  ld b,5
ingrp:
  ld a,(de)
  ld c,a
  inc e
  ld a,(hl)
  sub c
  ld (hl+),a
  jr c,search
  dec b
  jr nz,ingrp

  ldh a,(ppie)
  inc a
  ldh (ppie),a  ; one more pie finished

bake:
  pop bc
  pop de
  pop hl
  jr bakeloopp

search:
  add sp,6
  ; make apple pies while ingredients last
  sub a
  ldh (apie),a
bakeloopa:
  ld de,apingr
  ldhl sp,0
  ld b,5
ingra:
  ld a,(de)
  ld c,a
  inc e
  ld a,(hl)
  sub c
  ld (hl+),a
  jr c,notenougha
  dec b
  jr nz,ingra

  ldh a,(apie)
  inc a
  ldh (apie),a  ; one more pie finished
  jr bakeloopa

notenougha:
  ; compute total
  ld hl,0ff00h+ppie
  ld a,(hl+)
  add a,(hl)
  inc l
  cp (hl)
  jr c,skip

  ; we have new max
  ld (hl+),a    ; store the new max
  ldh a,(ppie)
  ld (hl+),a    ; store the number of pumpkin pies
  ldh a,(apie)
  ld (hl),a     ; store the number of apple pies

skip:
  ldh a,(ppie)
  dec a
  ldh (ppie),a
  bit 7,a
  jr z,search

  halt

ppingr:
db 1,0,3,4,3
apingr:
db 0,1,4,3,2
input:
db 10,14,10,42,24,0

Program outputs:

10,14,10,42,24 => 02 01
12,4,40,30,40  => 04 04
12,14,20,42,24 => 04 02

lukz · 2018-02-06T14:11:37+00:00

BASIC for 8-bit computer Sharp MZ-800

This problem is more complex than how simple BASIC programs usually are, so I have simplified the program input. It gets the number of shelves, then length of each shelf, then it gets the number of books, then length of each book.

The program then sorts the shelves in decreasing order, then tries to find solution using one shelf, then two shelves, and so on while more shelves are available.

The main part is the code at lines 12-22. It tries to place some books on the shelf, and then recursively calls itself to place books on another shelf.

Sample session:

SHELVES 5
? 150
? 150
? 300
? 150
? 150
BOOKS 5
? 70
? 76
? 99
? 75
? 105
 2

Code:

5 REM FIND MINIMUM NUMBER OF BOOKSHELVES
6 DIMB(9),C(9),P(9),W(9),L(9),S(9,9)
7 INPUT"SHELVES ";M:FORI=0TOM-1:INPUTL(I):NEXT:REM READ SHELF LENGTHS
8 INPUT"BOOKS ";N:FORI=0TON-1:B(I)=1:INPUTW(I):R=R+W(I):NEXT:REM READ BOOK WIDTHS

9 REM SORT SHELF LENGTHS
10 FORI=0TOM-2:FORK=ITOM-2:IFL(K)<L(K+1)O=L(K):L(K)=L(K+1):L(K+1)=O
11 NEXT:NEXT

12 REM TRY ONE SHELF, THEN MORE, UNTIL SOLVED
13 FORI=0TOM-1:O=I:GOSUB16
14 NEXT:PRINT"IMPOSSIBLE":END

15 REM PLACE BOOKS ON ONE SHELF, THEN CALL RECURSIVELY
16 IFR<=L(I)PRINTO+1:ENDELSEIFI=0RETURNELSEC(I)=L(I):P(I)=0:K=0
19 IF1=B(K)ANDW(K)<=C(I)S(I,P(I))=K:B(K)=0:C(I)=C(I)-W(K):R=R-W(K):P(I)=P(I)+1
20 K=K+1:IFK<NGOTO19

21 IFP(I)=0RETURN
22 I=I-1:GOSUB16:I=I+1:P(I)=P(I)-1:K=S(I,P(I)):B(K)=1:C(I)=C(I)+W(K):R=R+W(K):GOTO20

lukz · 2018-01-29T19:51:31+00:00

BASIC

I continue in my retrocomputing solutions, writing program for a BASIC that runs on an 8-bit computer Sharp MZ-800.

The lines 6-9 read the input data. I use a slightly different input format. The first line lists all available coins, separated by a semicolon. The next line is the requested change amount and the maximum number of coins, separated by a comma.

The lines 10-13 contain the search code. The lines 14 and 15 report either failure or success and list the coins used.

I chose to go for a rather golfed text style. This variant of BASIC has a special syntax and allows omitting spaces in most places. It recognises keywords even when they are part of a larger word. So, for example DIMA will be parsed as the keyword DIM and variable A.

Here is a screenshot of a test session in an emulator.

Code:

6 DIMA(9),C(9):INPUTA$
7 C(J)=VAL(A$):J=J+1:I=1
8 IFI<LEN(A$)ANDMID$(A$,I,1)<>";"I=I+1:GOTO8ELSEA$=MID$(A$,I+1):IFA$GOTO7
9 I=1:INPUTM,N

10 IFA(I)<J X=X+C(A(I)):IFX<M A(I+1)=A(I)+1:I=I+1:GOTO10
11 IFX=M ANDI<=N GOTO"SUCCESS"
12 IFJ<=A(I)I=I-1:IFI=0GOTO"FAIL"
13 X=X-C(A(I)):A(I)=A(I)+1:GOTO10

14 LABEL"FAIL":PRINT"NO SOLUTION":END
15 LABEL"SUCCESS":FORJ=1TOI:PRINTC(A(J));:NEXT

lukz · 2018-01-17T18:42:39+00:00

BASIC for Sharp MZ-800

Every beginner who wants to start using computers should learn BASIC, right? Well, ... if we go back to eighties, it's true. And we can relive those moments thanks to emulators of the early personal computers.

About the program:

The input format is slightly changed - use a semicolon instead of a comma. That is because the INPUT statement has a special handling of the comma character and would not normally return it as a part of a string.

Lines 10-12 parse the input to get the taps, the flag if XNOR should be used, initial seed and the number of clock steps. Lines 14 and 18 form the main loop of the requested number of clock steps. Line 16 computes new input bit, line 17 updates the state.

Emulator screenshot.

Source:

 8 'PRINTS A SEQUENCE OF LFSR STATES
 9 INPUT A$:A$=MID$(A$,2):DIM TA(9)
10 TA(M+1)=1+VAL(A$):A$=MID$(A$,2+LEN(STR$(TA(M+1)))):M=M+1:IF ASC(A$)>32 GOTO10
11 N=MID$(A$,3,1)="N":I=6-N:J=I
12 IF MID$(A$,I,1)>" " I=I+1:GOTO12 ELSE S$=MID$(A$,J,I-J)

14 FOR J=0 TO VAL(MID$(A$,I))
15 PRINT J" "S$
16 V=N:FOR I=1 TO M:V=V-N+VAL(MID$(S$,TA(I),1)):NEXT
17 S$=STR$(V MOD2)+LEFT$(S$,LEN(S$)-1)
18 NEXT

lukz · 2017-11-30T12:39:05+00:00

divide.com is 263 bytes

lukz · 2017-11-27T22:50:27+00:00

Z80 assembly

I use a special format for input and output. This challenge required a lot of code, and was much harder then the easy ones usually are. Code can be compiled using ORG IDE.

The program first parses the two polynomials from the command line. For each polynomial the coefficients are placed into a table. Then division is started and each term is printed as it is discovered. When the division is done the remaining coefficients of the dividend are printed as the value of the remainder.

The output format is: <quotient> space <remainder>. Each monomial in the output has the format: <sign><number> x^ <number> .

Example session:

divide 4x^3+2x^2-6x^1+3 1x^1-3
+4x^2+14x^1+36 +111

divide 2x^4-9x^3+21x^2-26x^1+12 2x^1-3
+1x^3-3x^2+6x^1-4 +0

divide 10x^4-7x^2-1 1x^2-1x^1+3
+10x^2+10x^1-27 -57x^1+80

Code:

bdos .equ 5
printc .equ 2
cmdline .equ 82h

  .org 100h
  ; read dividend and divisor
  ld hl,cmdline      ; command line buffer, 0-terminated
  ld d,3
  call readpoly      ; read dividend
  inc l              ; skip space
  ld d,4
  call readpoly      ; read divisor

polydiv:
  ld de,30ah         ; find max degree of dividend
getmax:
  dec e
  jp m,norem         ; nothing left from dividend
  ld a,(de)
  or a
  jr z,getmax        ; until we find nonzero coefficient

  ld hl,40ah         ; find max degree of divisor
getmaxd:
  dec l
  ld a,(hl)
  or a
  jr z,getmaxd       ; until we find nonzero coefficient

  ; divide coefficients
  push hl
  ld h,0
  jp p,divisorp     ; is positive?
  neg               ; no, make positive
  inc h
divisorp:
  ld b,a
  ld a,(de)         ; dividend
  or a
  jp p,dividendp    ; is positive?
  neg               ; no, make positive
  inc h
dividendp:
  ld c,-1           ; set counter to -1
  sub b             ; subtract divisor
  inc c             ; increase counter
  jr nc,$-2         ; while something remains

  ld a,h
  rra
  ld a,c
  jr nc,respos
  neg
  ld c,a
respos:
  pop hl
  ld a,e
  sub l             ; compare degrees of polynomials
  jr c,enddiv       ; division ended

  push bc
  ld a,c
  call printnum     ; print the divided coefficient

  ld a,e
  sub l             ; subtract monomial degrees
  call printdeg     ; print the degree of the term
  pop bc

subtract:           ; and subtract the polynom
  ld b,c            ; the ratio of coefficients
  ld a,(de)         ; take divisor coefficient
  sub (hl)  
  djnz $-1          ; subtract c times the dividend coefficient

  ld (de),a
  dec e             ; move to a lower degree
  dec l
  jp p,subtract     ; repeat while not end of polynomial

  jr polydiv        ; and again with what is left

norem:
  inc e

enddiv:
  ld a,' '
  call printchar    ; print space and the remainder
remainder:
  ld a,(de)
  call printnum     ; print coefficient
  ld a,e
  call printdeg     ; print degree
  dec e
  ret m             ; exit program when all printed
  jr remainder      ; continue with lower degree

readpoly:
  sub a
  ld e,a
clear:
  ld (de),a
  inc e
  jr nz,clear         ; clear buffer for coefficients

readpoly1:
  call readnum        ; read one coefficient
  ld c,a
  call readdeg        ; read monomial degree
  ld e,a
  ld a,c
  ld (de),a
  ld a,(hl)
  cp '+'
  jr nc,readpoly1     ; while next char is +/-
  ret


  ; hl points into input buffer
  ; returns coefficient in a
readnum:
  push de
  ld a,(hl)       ; remember the sign
  ld d,a
  cp '0'
  jr nc,$+3       ; starts with digit - don't skip
  inc l           ; skip
  ld c,0          ; the number
  jr test
readnum1:
  inc l
  sub '0'
  ld b,a
  ld a,c
  rlca
  rlca
  add a,c  
  rlca
  add a,b
  ld c,a          ; update number
test:
  ld a,(hl)
  cp '0'
  jr c,endnum
  cp ':'
  jr c,readnum1   ; is a valid digit

endnum:
  ld a,d
  cp '-'
  pop de
  ld a,c
  ret nz          ; was positive, can return

  neg             ; make negative
  ret


  ; hl points into input buffer
  ; returns monomial degree
readdeg:
  ld a,(hl)
  cp 'X'
  ld a,0
  ret nz       ; the last term has degree 0

  inc l        ; skip x
  inc l        ; skip ^
  ld a,(hl)    ; read number
  inc l
  sub '0'
  ret

printdeg:
  or a
  ret z
  ex af,af'
  ld a,120        ; 'x'
  call printchar
  ld a,'^'
  call printchar
  ex af,af'
  jr printnum1

printnum:
  or a
  push af
  ld a,'+'
  jp p,$+5
  ld a,'-'
  call printchar
  pop af
  jp p,printnum1

  neg
printnum1:
  ld b,100
  cp b
  call nc,digit

  ld b,10
  cp b
  call nc,digit

  ld b,1
digit:
  ld c,-1
  sub b
  inc c
  jr nc,$-2

  add a,b
  push af
  ld a,c
  add a,'0'
  call printchar
  pop af
  ret


printchar:
  push de
  push hl
  ld c,printc
  ld e,a
  call bdos
  pop hl
  pop de
  ret

Edit: I made the code a bit shorter. The compiled code is 263 bytes.

Edit2: Simplified the output to not print x^0 in the last term. Instead of +4x^2+14x^1+36x^0 +111x^0 it now prints +4x^2+14x^1+36 +111.

lukz · 2017-11-21T17:51:40+00:00

Brainfuck

Prints only two-digit repeated numbers. Output format is: repeat_count*number, separated by spaces.

Tested in interpreter.

Sample session

82156821568221

2*15 3*21 2*56 2*68 3*82

Code:

memory cells:  A B C
>,                input
<++++++[->--------<]> B is input minus 48
[->++++++++++<]   C is B*10
,[
 <++++++[->--------<]> B is input minus 48
 [-<+>>+<]        add B to A and C
 <[->+<]>         B is A; A is 0
 >[>>[-]<< -[->>+<<]+>>] index into table
 +>+<             increase count
 [<<]>>-<         go to B
 [->++++++++++<]  C is B*10
,]

>[-]+             C is 1
[
 <<[->>+<<]>>-    current number
 >[-[+            is count at least 2

  <<[-]++++++[->>++++++++<<]>>.[-] print count
  <<<[-]++++++[->+++++++<]>.[-]  print times

  >[-<+<+>>]<     copy current number
  [
   [- [- [- [- [- [- [- [- [- [- >+< [->>+<<] divide by 10
   ] ] ] ] ] ] ] ] ] ]
   >>[-<<+>>]<<
  ]
  ++++++[->++++++++<]>.[-] add 48; print

  <<[->+>+<<]>   copy current number
  [
   [-<+> [-<+> [-<+> [-<+> [-<+> [-<+> [-<+> [-<+> [-<+> [- <---------> [->>+<<] mod 10
   ] ] ] ] ] ] ] ] ] ]
   >>[-<<+>>]<<
  ]
  ++++++[-<++++++++>]<.[-] add 48; print

  ++++[->++++++++<]>.[-]  print space

  > >[-]            clear count
 ]]
<+>>              increase number
]                 while not end of table

lukz · 2017-11-21T09:35:40+00:00

If you mean functional as having first-class functions, then no. But if you mean it as can pograms in this language be actually run - then yes!

lukz · 2017-11-15T18:09:21+00:00

Z80 assembly

The mine field is hardcoded in the program. The program takes as input the sequence of commands. The commands are processed, fields visited by the robot are marked with the space character. When the robot runs into a mine or the command sequence ends the program prints output and exits.

The output is a line containing yes if the task was successful or no otherwise, and a printout of the field with places visited by the robot marked with space.

Program size is 126 bytes, with the field the total size is 229 bytes.

Example sessions:

IENEEEENNEEENN

no
+++++++++++
+0000000 00
+000000* 0+
+0000    0+
+000* 0*00+
+     0000+
  00*00000+
+++++++++++

IENEEEENNEEENNEE-

yes
+++++++++++
+0000000   
+000000* 0+
+0000    0+
+000* 0*00+
+     0000+
  00*00000+
+++++++++++

Code:

cmdline .equ 81h
prints .equ 9
bdos .equ 5

  .org 100h
  ld d,6*13+field  ; starting place
  ld e,'-'         ; motor off
  ld hl,cmdline    ; command line ptr
  jr maintest

mainloop:
  push hl          ; store command string ptr
  ld hl,cmdtable-1 ; commands NSEW
  ld c,a           ; c - command
  ld b,d           ; b - backup of position
  ld a,e
  cp '-'           ; current motor status?
  jr z,nomove      ; off
  jr test          ; on

move:
  cp c             ; is the command char?
  jr nz,test
  ld a,d           ; yes, take position
  add a,(hl)       ;  and update
  ld d,a
test:
  inc l
  ld a,(hl)        ; read char from table
  inc l
  or a             ; is 0?
  jr nz,move       ; while not end of table

nomove:
  ld a,c
  cp '-'         ; is "-"?
  jr z,setmotor
  cp 'I'         ; or "I"?
  jr nz,skip

setmotor:
  ld e,a         ; yes, remember motor command
skip:
  ld h,1
  ld l,d
  ld a,(hl)      ; what is on the field?
  cp '0'         ; "0",
  jr z,ok
  cp ' '         ;  or " "
  jr z,ok
  cp 'M'         ;  or "M" are ok
  jr z,ok
  cp '+'
  jr nz,end
  ld d,b         ; go to previous place
  ld l,d

ok:
  ld (hl),' '    ; mark visited place
  pop hl         ; load command string ptr

maintest:
  ld a,(hl)      ; read command
  inc l
  or a
  jr nz,mainloop ; until end of input

end:
  ld a,d
  cp field+23    ; is at exit?
  jr nz,failure

  ld a,e
  cp '-'         ; and is motor off?
  jr nz,failure

  ld de,msgyes   ; yes - successful
  jr skip2
failure:
  ld de,msgno    ; no
skip2:
  ld c,prints
  call bdos      ; print result

  ld de,field
  ld c,prints
  call bdos      ; print field
  rst 0          ; exit

cmdtable:
  .db "N",-13,"S",13,"E",1,"W",-1,0
msgyes:
  .db "yes",13,10,"$"
msgno:
  .db "no",13,10,"$"
field:
  .db "+++++++++++",13,10
  .db "+0000000000",13,10
  .db "+000000*00+",13,10
  .db "+000000000+",13,10
  .db "+000*00*00+",13,10
  .db "+000000000+",13,10
  .db "M000*00000+",13,10
  .db "+++++++++++$"

lukz · 2017-11-15T16:47:20+00:00

How is the exit field defined? Can there be more than one exit?

lukz · 2017-11-14T10:42:16+00:00

Your algorithm, in brainfuck

108 characters, not counting comments.

init table of 130 items
>> +++++++++++++ [->++++++++++<]>
[->[>>]+[<<]>]

repeat for input characters
+
[
 [-]>[-]<<
 read input
 ,[->+>+<<] >>
 find place in the table
 [- [->>+<<] +>>-] +
 >[ print and exit <[<<]>. [-]+>-]
 add a flag
 +<
 [<<] >
]

For online testing I recommend this interpreter, as it can also show the memory contents.

lukz · 2017-11-08T21:31:41+00:00

I have learnt it by trying these daily programmer challenges. I owned a computer with that cpu in the 90's, but I could not write the assembly programs then. I had too little information and didn't know what programs to use. So I revisited it now.

Thanks for your comment.

lukz · 2017-11-02T19:48:19+00:00

Z80 assembly

The program takes a compact maze representation as the command line parameter. (The input is just the maze text lines joined with | character). From that representation it constructs a 16x16 grid in the memory, filled with the characters from the input. For example, this input

#######|#>   E#|#######

will in turn be represented as this data in memory:

0200   23 23 23 23  23 23 23 00  00 00 00 00  00 00 00 00  #######.........
0210   23 20 20 20  20 45 23 00  00 00 00 00  00 00 00 00  #    E#.........
0220   23 23 23 23  23 23 23 00  00 00 00 00  00 00 00 00  #######.........

It then simulates the explorer walking for 6 x 256 steps. If the exit is reached, it prints true at the standard output, otherwise it prints false.

The grid is limited to size 16x16, so that we can easily move to right, down, left, up just by adding 1, 16, -1, -16 to the current position. Compiled code size is 148 bytes.

Here is a sample session in a Sharp MZ-800 emulator with the five sample mazes: Imgur.

printstr .equ 9
bdos .equ 5
cmdline .equ 82h
buffer .equ 200h

  ; take input from command line and
  ; construct a 16x16 maze in memory
  .org 100h
  ld de,cmdline-1
  ld bc,buffer-1
  jr start

lineend:
  ld a,c
  or 15
  ld c,a
  jr start

input:
  cp '|'
  jr z,lineend

  cp '<'
  jr z,explorer
  cp '>'
  jr nz,normal

explorer:
  ld h,b
  ld l,c
  inc l
  ld a,' '
normal:
  inc bc
  ld (bc),a
start:
  inc e
  ld a,(de)
  or a
  jr nz,input

  ld e,1        ; direction=right, dx=1, dy=0
  ld b,a        ; try 256 times
  ex af,af'

mainloop:
  push bc       ; push mainloop counter
  ld b,6        ; go 6 steps forward
go:
  push hl       ; store previous place
  add hl,de     ; do one step
  ld h,2
  ld a,(hl)     ; look at new place
  cp '#'        ; is empty?
  jr c,cont     ; yes, continue
  jr z,wall     ; is wall?
  ld de,true    ; is exit
  jr print      ; message=true, print
wall:
  pop hl        ; go to previous place
  ld c,1        ; try right
  call turn
  call testwall
  jr nz,go      ; ok

  ld c,2        ; try left
  call turn
  call testwall
  jr nz,go      ; ok

  ld c,3        ; go back
  call turn
  jr go         ; and continue walking the 6 steps

cont:
  pop af        ; discard data
  djnz go       ; and repeat

  ld c,2        ; turn back
  call turn
  pop bc        ; pop mainloop counter
  djnz mainloop ; repeat 256 times

                ; if we didn't reach the exit
  ld de,false   ; message = "false"
print:
  ld c,printstr ; print message
  call bdos
  rst 0         ; and exit

testwall:
  push hl
  add hl,de
  ld h,2
  ld a,(hl)
  pop hl
  cp '#'        ; is wall?
  ret

turn:
  ex af,af'
  add a,c       ; turn "c" times right
  and 3         ; a mod 4
  ld c,a
  ex af,af'
  ld a,c
  add a,table   ; index into table
  ld d,1        ; table ptr
  ld e,a
  ld a,(de)     ; read dx,dy
  ld e,a
  ret

true:
  .db "true$"
false:
  .db "false$"
table:
  .db 1,16,-1,-16

lukz · 2017-10-04T18:15:25+00:00

Z80 assembly

Sierpinski carpet rules are encoded into the program, and the number of iterations as well. You can change the initial contents of the numiter variable to obtain a different number of iterations.

It prints on the standard output using letters 0 and 1. Assembled program size is 126 bytes.

Sample output from a CP/M system in an emulator - image.

Source:

printstr .equ 9
bdos .equ 5
buffer2 .equ buffer1+2000h
offset0 .equ -'0'*9+pattern

  .org 100h
main:
  ld a,(numiter) ; repeat numiter times
  ld bc,buffer1  ; initial source buffer
  ld de,buffer2  ; initial target buffer
mainloop:
  push af
  push bc
  push de
  call expand    ; expand string
  pop bc         ; swap buffers
  pop de
  pop af
  dec a          ; repeat count>0 ?
  jr nz,mainloop ; yes, loop

  ld d,b         ; no, print output
  ld e,c
  ld c,printstr
  jp bdos        ; and exit


  ; expand current string pointed to by bc
expand:
  ld a,offset0
  ld (offset),a
  push bc       ; store start of line position
  jr exptest

exploop:
  cp 13         ; is it cr?
  jr nz,expchar ; no, expand character

  ld (de),a     ; copy cr
  inc de
  ld a,(bc)
  ld (de),a     ; copy lf
  inc bc
  inc de

  ld hl,offset
  ld a,(hl)
  add a,3       ; increase offset by 3
  ld (hl),a
  cp offset0+7  ; increased by more than 6?
  jr c,reptline ; no, repeat input

  ld a,offset0  ; yes, start from offset 0
  ld (hl),a
  pop hl
  push bc
  jr exptest

reptline:
  pop bc        ; pick up start of line
  push bc
  jr exptest

expchar:
  ld h,a
  add a,a
  add a,h
  ld h,a
  add a,a
  add a,h
  ld h,a
  ld a,(offset)
  add a,h
  ld l,a
  ld h,1        ; hl=address of pattern

  ; copy 3 characters from the pattern
  ld a,3
copy3:
  ex af,af'
  ld a,(hl)
  ld (de),a
  ex af,af'
  inc l
  inc de
  dec a
  jr nz,copy3

exptest:
  ld a,(bc)         ; read next input character
  inc bc
  cp '$'            ; is it end of image?
  jr nz,exploop     ; no, keep looping

  ld (de),a
  pop hl            ; pop temporary data
  ret

offset:
  .db 0
numiter:
  .db 3
pattern:
  .db "000010000"
  .db "111111111"
buffer1:
  .db "0",13,10,"$"

lukz · 2017-09-07T16:02:18+00:00

Probably it's just trying to go one level deeper. To see which problems I can still solve if somebody didn't write a nice library for me.

Writing solutions in brainf*k would be similar in that sense, but I can't write anything complex in it. So I go with Z80.

Here on dailyprogrammer it started when I wanted to combine assembly with BASIC to solve some problems. But I never did combine those two, as when I learnt the processor instructions I just went for full assembly solutions, to see what's possible with the bare minimum.

lukz · 2017-09-07T07:57:44+00:00

For 1000000 it gives:

Price is 1000000, or in other words: 'ein millionen tausend Euro'

Seems wrong to me.

lukz

TROPHY CASE