Page 1 of 3
Christmas Challenge
Posted: Sun Dec 19, 2021 12:06 pm
by BigEd
via Stardot, a rather nice small-but-not-too-small
programming challenge.
The rules are quite nice: no sharing your code, or even your score, until the contest closes (which is tonight), and you can submit only once.
And you can use Basic or machine code, and even use the platform of your choice.
The challenge, then, is to produce exactly this output:
Re: Christmas Challenge
Posted: Sun Dec 19, 2021 3:16 pm
by drogon
A good simple challenge - I've entered ... in BCPL on my Ruby '816, of-course
-Gordon
Re: Christmas Challenge
Posted: Sun Dec 19, 2021 7:46 pm
by DRG
Me too. Using the Kowalski 6502 Simulator.
Re: Christmas Challenge
Posted: Mon Dec 20, 2021 12:54 am
by okwatts
May not be too late for me?
I sent in my Fig-forth entry using Plasmo's CRC65.
Re: Christmas Challenge
Posted: Mon Dec 20, 2021 2:08 am
by IamRob
I got 75 bytes using RLE compression centered on a 40-col text screen.
De-compressor not included. Must decompress by hand.
76 bytes using Applesoft
I am pretty sure I am not the smallest, or even if I was, I would not be the first to enter the smallest code.
Re: Christmas Challenge
Posted: Mon Dec 20, 2021 2:13 am
by BillG
I entered as well.
He did not say what time the contest closes.
Re: Christmas Challenge
Posted: Mon Dec 20, 2021 5:40 am
by barrym95838
I'm pretty sure I missed the deadline, but I offered an Apple 1 solution in 76 bytes of self-modifying machine code ... just instructions, no tables:
https://retrocomputingforum.com/t/chris ... hael_barry
WozMon doesn't guarantee a clean RTS back from the R command, so I had to spend six extra bytes for that, and at least four bytes to make it re-runnable.
I have a feeling I should have used a small table instead of employing an algorithmic approach, but it is what it is.
Re: Christmas Challenge
Posted: Mon Dec 20, 2021 6:47 am
by laubzega
C64, asm, 46 bytes.
Re: Christmas Challenge
Posted: Mon Dec 20, 2021 7:50 am
by barrym95838
Wow ... beat me like a rented mule!
Re: Christmas Challenge
Posted: Mon Dec 20, 2021 8:14 am
by BigEd
I'm sure it would be interesting and informative for us to share our efforts, no matter if they are as good as the best or far from the best.
Now the deadline for submission has past, I see solutions are beginning to appear over on
the stardot thread. And I see 6502 programs ranging from 54 down to a remarkable 44 bytes.
My own effort comes in at 69 bytes:
Code: Select all
DIM tree 99
FOR i=0 TO 2 STEP 2
P%=tree
[ OPT i
LDA#1:JSRrow4
LDA#3:JSRrow4
LDA#5:JSRrow4
LDA#3:JSRrow
LDA#3:JMProw
.row4 INCbump+1:INCbump+1:JSRrow2
.row2 JSRrow
.row PHA:PHA:LSR A:TAX
.space LDA#32:JSR&FFEE
INX:CPX#20:BNEspace
PLA:TAX
.star LDA#42:JSR&FFEE
DEX:BNEstar
JSR&FFE7
PLA:CLC:.bump ADC#0
RTS
]
NEXT
PRINT P%-tree;" bytes"
CALL tree
Re: Christmas Challenge
Posted: Mon Dec 20, 2021 12:38 pm
by BillG
Wow ... beat me like a rented mule!
Beats my 52 bytes too...like a drum...
Code: Select all
0050 00001 ScreenWidth equ 80
00002
00003 *-----------------------------------------------------------------------------
00004 *
00005 * FLEX entry points
00006 *
00007 * Change OSBase to $C000 for 6809 FLEX
00008 *
00009 * Note: 6809 version is one byte bigger, leax 1,X instead of inx
00010 *
A000 00011 OSBase equ $A000
00012
AD03 00013 WARMS equ OSBase+$D03 ; Return to FLEX
AD18 00014 PUTCHR equ OSBase+$D18 ; Put Character
AD24 00015 PCRLF equ OSBase+$D24 ; Print Carriage Return and Line Feed
00016
00017 *-----------------------------------------------------------------------------
00018 *
00019 * Encoded tree
00020 *
0000 00021 Data
0000 01 00022 fcb 1 * *
0001 03 00023 fcb 3 * ***
0002 05 00024 fcb 5 * *****
0003 07 00025 fcb 7 * *******
0004 03 00026 fcb 3 * ***
0005 07 00027 fcb 7 * *******
0006 0B 00028 fcb 11 * ***********
0007 0F 00029 fcb 15 * ***************
0008 05 00030 fcb 5 * *****
0009 0B 00031 fcb 11 * ***********
000A 11 00032 fcb 17 * *****************
000B 17 00033 fcb 23 * ***********************
000C 03 00034 fcb 3 * ***
000D 03 00035 fcb 3 * ***
000E 00 00036 fcb 0 *
00037
00038 *-----------------------------------------------------------------------------
00039 *
00040 * Draw the tree
00041 *
000F 00042 Tree
000F CE 0000 [3] 00043 ldx #Data ; Address the encoded tree
00044
0012 00045 TreeLoop
0012 BD AD24 [9] 00046 jsr PCRLF ; Print Carriage Return and Line Feed
00047
0015 8D 0A (0021) [8] 00048 bsr EmitSpaces
0017 8D 11 (002A) [8] 00049 bsr EmitStars
00050
0019 08 [4] 00051 inx ; Address the next row
00052
001A 6D 00 [7] 00053 tst ,X ; More rows?
001C 26 F4 (0012) [4] 00054 bne TreeLoop ; Yes
00055
001E 7E AD03 [3] 00056 jmp WARMS ; Return to FLEX
00057
00058 *-----------------------------------------------------------------------------
00059 *
00060 * Emit a run of spaces
00061 *
00062 * X = address of run information
00063 *
0021 00064 EmitSpaces
0021 86 20 [2] 00065 ldaa #' '
0023 C6 50 [2] 00066 ldab #ScreenWidth
0025 E0 00 [5] 00067 subb ,X ; Number of spaces on the line
00068
0027 54 [2] 00069 lsrb ; Put half of them on the left
00070
0028 20 04 (002E) [4] 00071 bra DoRunRun
00072
00073 *-----------------------------------------------------------------------------
00074 *
00075 * Emit a run of stars
00076 *
00077 * X = address of run information
00078 *
002A 00079 EmitStars
002A 86 2A [2] 00080 ldaa #'*'
002C E6 00 [5] 00081 ldab ,X
00082
00083 * Fall through
00084 * bra DoRunRun
00085
00086 *-----------------------------------------------------------------------------
00087 *
00088 * Emit a run of characters
00089 *
00090 * A = the character
00091 * B = length of the run
00092 *
002E 00093 DoRunRun
002E BD AD18 [9] 00094 jsr PUTCHR ; Put Character
00095
0031 5A [2] 00096 decb ; Finished with the run?
0032 26 FA (002E) [4] 00097 bne DoRunRun ; No
00098
0034 39 [5] 00099 rts
00100
000F 00101 end Tree
Re: Christmas Challenge
Posted: Mon Dec 20, 2021 12:46 pm
by DRG
OK, my effort came in at 68 bytes including the data on the stack and a temporary 1-byte variable (53 bytes of instructions if you ignore data/temp variable). Probably a lot could be done to refine/reduce, but I didn't have the time to spend before getting my submission in.
Most system also have different ways of "printing" so I'm not sure how the impact of that on the length of code is taken into account.
BTW - if you like these kinds of programming challenges at Christmas, then head over to the
Advent of Code.
Code: Select all
; Draw A Christmas Tree.
; DRG 19/12/2021.
; Runs on the Kowalski 6502 Simulator in 65C02 mode.
; X = number of spaces to print.
; Y = number of stars to print.
; C = temporary variable.
; Data pre-populated on the stack.
.ORG $01F1
tree
.BYTE $01, $03, $05, $07, $03, $07, $0B
.BYTE $0F, $05, $0B, $11, $17, $03, $03, $00
.ORG $200
start
STZ IO_AREA ; Clear the "screen".
LDX #$F0
TXS ; Set the stack pointer to our data.
loop1
PLA ; Get the number of stars.
BEQ exit ; $00 was the value for no more stars - so exit.
TAY ; Y = A.
AND #$FE ; Same as A -> A - 1 for odd numbers as it clears bit 0.
LSR ; Half it.
STA C ; C = A.
LDA #$0C ; A = 12.
SEC ; Set carry flag.
SBC C ; 12 - C.
TAX ; X = A. This is the number of spaces to print.
loop2
LDA #' ' ; Space character.
STA IO_AREA+1 ; Print it.
DEX ; Decrement space counter.
BNE loop2 ; If not done, do more.
loop3
LDA #'*' ; Star character.
STA IO_AREA+1 ; Print it.
DEY ; Decrement star counter.
BNE loop3 ; If not done, do more.
LDA #$0D ; Carriage return.
STA IO_AREA+1 ; Print it.
LDA #$0A ; Line feed.
STA IO_AREA+1 ; Print it.
JMP loop1 ; Keep going...
exit
BRK
C
.BYTE $00
Re: Christmas Challenge
Posted: Mon Dec 20, 2021 1:56 pm
by John West
Since I've now got my 65020 running on an FPGA, I thought I've have a go. It could definitely be improved. 46 ... somethings. I'm still not sure what counts as a 'byte' on this system.
Code: Select all
0000e99c: 102 tree
0000e99c: 00a2 000f 103 ldr x0, #15
0000e99e: 20a2 0014 104 ldr x1, #20
0000e9a0: 40a2 0020 105 ldr x2, #32
0000e9a2: 60a2 002a 106 ldr x3, #'*
0000e9a4: 20a0 000d 107 ldr y1, #13
0000e9a6: 02a0 4221 0643 108 ldr.l y0, #$06424321
0000e9a9: 90f0 0003 109 bra.l branches
0000e9ab: 02a0 2d48 02a7 110 ldr.l y0, #$022da748
0000e9ae: 111 branches
0000e9ae: d0a8 112 mov a2, y0
0000e9af: 503c 113 and a2, x0
0000e9b0: 00f0 0017 114 beq done
0000e9b2: 248a 115 mov a1, x1
0000e9b3: a8fc 116 sub a1, a2
0000e9b4: 088a 117 mov a0, x2
0000e9b5: 90f0 000d 118 bra.l row
119
0000e9b7: c87c 120 add a2, a2
0000e9b8: 18ca 121 dec a2
0000e9b9: a8a8 122 mov a1, a2
0000e9ba: 0c8a 123 mov a0, x3
0000e9bb: 90f0 0007 124 bra.l row
125
0000e9bd: 94a8 126 mov a0, y1
0000e9be: 90f0 07a9 127 bra.l chrout
0000e9c0: 2242 0004 128 lsr.l y0, #4
0000e9c2: 80f0 00ea 129 bra branches
0000e9c4: 130 row
0000e9c4: 90f0 07a3 131 bra.l chrout
0000e9c6: 14ca 132 dec a1
0000e9c7: 00d0 00fb 133 bne row
0000e9c9: 134 done
0000e9c9: 0060 135 rts
It's a 6502 with 16 bit 'bytes'. If the top half of the opcode is all 0, it behaves like the original 6502 instruction. The extra bits are used to select data size, data register, index register, and alternate operations (for example, turning ADC into ADD without carry). I've renamed many of the instructions, so it looks a lot less 6502ish than it really is (although having lots of registers and register-to-register operations goes the other way, making it feel even less like a 6502).
'LDR' is "Load Register", and includes the old LDA, LDX, and LDY. It can load any of the 12 general purpose registers A0-A3, X0-X3, and Y0-Y3. An optional suffix on the instruction controls the size of the data, with the default being 8 bit. LDR.L is a 32 bit load.
One of the extra bits on the branch instructions is used to select a different set of conditions, and one of those conditions is 'always'. Another bit (signalled by .L on the instruction) makes it push the current PC before branching. That gives an alternative to JSR with short (16 bit) offsets.
As there are lots more registers than the 6502, I've added register-to-register versions of the instructions that could use them. The various TAX, TXS, etc. instructions have all been renamed MOV, and extended to allow any register to be copied to any other.
Re: Christmas Challenge
Posted: Mon Dec 20, 2021 2:13 pm
by drogon
I did it in a high level language; BCPL. Runs on my Ruby '816 board - 65c816 + 512KB of RAM at 16Mhz. Images of Ruby '816 and a screenshot of the code and output below. I wish I'd thought more about seeing if I could do it algorithmically. I also note that my submission was incorrect as I mis-counted one row, however this is correct - not that it matters now!
(edited because I originally uploaded the one with the error in it!)
-Gordon
Re: Christmas Challenge
Posted: Mon Dec 20, 2021 2:37 pm
by BillG
Upon further examination, I was able to get mine down to 47 bytes.
* Inlined one subroutine
* Store the tree table upside down allowing me to get rid of the sentinel and the test for it
Code: Select all
0050 00001 ScreenWidth equ 80
00002
00003 *-----------------------------------------------------------------------------
00004 *
00005 * FLEX entry points
00006 *
00007 * Change OSBase to $C000 for 6809 FLEX
00008 *
00009 * Note: 6809 version is one byte bigger, leax -1,X instead of dex
00010 *
A000 00011 OSBase equ $A000
00012
AD03 00013 WARMS equ OSBase+$D03 ; Return to FLEX
AD18 00014 PUTCHR equ OSBase+$D18 ; Put Character
AD24 00015 PCRLF equ OSBase+$D24 ; Print Carriage Return and Line Feed
00016
0001 00017 org 1 ; 1 so that decrementing X automagically sets the Z flag when done
00018
00019 *-----------------------------------------------------------------------------
00020 *
00021 * Encoded tree
00022 *
0001 03 00023 fcb 3 * ***
0002 03 00024 fcb 3 * ***
0003 17 00025 fcb 23 * ***********************
0004 11 00026 fcb 17 * *****************
0005 0B 00027 fcb 11 * ***********
0006 05 00028 fcb 5 * *****
0007 0F 00029 fcb 15 * ***************
0008 0B 00030 fcb 11 * ***********
0009 07 00031 fcb 7 * *******
000A 03 00032 fcb 3 * ***
000B 07 00033 fcb 7 * *******
000C 05 00034 fcb 5 * *****
000D 03 00035 fcb 3 * ***
000E 01 00036 Data fcb 1 * *
00037
00038 *-----------------------------------------------------------------------------
00039 *
00040 * Draw the tree
00041 *
000F 00042 Tree
000F CE 000E [3] 00043 ldx #Data ; Address the encoded tree
00044
0012 00045 TreeLoop
0012 BD AD24 [9] 00046 jsr PCRLF ; Print Carriage Return and Line Feed
00047
0015 86 20 [2] 00048 ldaa #' '
0017 C6 50 [2] 00049 ldab #ScreenWidth
0019 E0 00 [5] 00050 subb ,X ; Number of spaces on the line
00051
001B 54 [2] 00052 lsrb ; Put half of them on the left
00053
001C 8D 0C (002A) [8] 00054 bsr DoRunRun
00055
001E 8D 06 (0026) [8] 00056 bsr EmitStars
00057
0020 09 [4] 00058 dex ; Address the next row
00059
0021 26 EF (0012) [4] 00060 bne TreeLoop ; More rows?
00061
0023 7E AD03 [3] 00062 jmp WARMS ; Return to FLEX
00063
00064 *-----------------------------------------------------------------------------
00065 *
00066 * Emit a run of stars
00067 *
00068 * X = address of run information
00069 *
0026 00070 EmitStars
0026 86 2A [2] 00071 ldaa #'*'
0028 E6 00 [5] 00072 ldab ,X
00073
00074 * Fall through
00075 * bra DoRunRun
00076
00077 *-----------------------------------------------------------------------------
00078 *
00079 * Emit a run of characters
00080 *
00081 * A = the character
00082 * B = length of the run
00083 *
002A 00084 DoRunRun
002A BD AD18 [9] 00085 jsr PUTCHR ; Put Character
00086
002D 5A [2] 00087 decb ; Finished with the run?
002E 26 FA (002A) [4] 00088 bne DoRunRun ; No
00089
0030 39 [5] 00090 rts
00091
00092 * Total length is one less than this address because $0000 is not used
00093
000F 00094 end Tree
Edit: Make that 48 bytes. In my hurry yesterday, I introduced an off-by-one error in accounting for the length. The length of my entry was actually 53 bytes.