00 C0 20 FD AE 20 6B A9 A2 05 A9 00 85 FB 85 FC 85 FD A0 10 06 FB 06 14 26 15
90 02 E6 FB A5 FB C9 09 90 04 E9 09 85 FB 26 FC 26 FD 88 D0 E5 A5 FB 95 61 CA
A5 FD 85 15 A5 FC 85 14 D0 CC A5 15 D0 C8 E8 86 FE B5 61 D0 1E A9 09 95 61 86
9E CA B4 61 F0 11 D6 61 D0 0D E4 FE D0 04 E6 FE B0 05 95 61 CA 10 EB A6 9E E8
E0 06 D0 D9 18 A6 FE B5 61 69 30 20 D2 FF E8 E0 06 D0 F4 60
Online demo
Usage: sys49152,[n]
, e.g. sys49152,100
. n
is 1-indexed.
Valid values are in the range [1,63999].
Explanation:
The common approach to save bytes is to do it iteratively / recursively checking for decimal 0
digits -- this doesn't save bytes on the C64 because there's not even a division instruction available -- just converting to base 9 and adjusting the digits gives a shorter result (still with the need to hand-code a long binary division). Here's the commented disassembly:
00 C0 .WORD $C000 ; load address
.C:c000 20 FD AE JSR $AEFD ; consume comma
.C:c003 20 6B A9 JSR $A96B ; read 16bit number
.C:c006 A2 05 LDX #$05 ; index of last digit in result
.C:c008 .divide:
.C:c008 A9 00 LDA #$00 ; initialize some variables
.C:c00a 85 FB STA $FB ; to zero ...
.C:c00c 85 FC STA $FC
.C:c00e 85 FD STA $FD
.C:c010 A0 10 LDY #$10 ; repeat 16 times for division
.C:c012 .div_loop:
.C:c012 06 FB ASL $FB ; shift remainder left
.C:c014 06 14 ASL $14 ; shift dividend ...
.C:c016 26 15 ROL $15 ; ... left
.C:c018 90 02 BCC .div_nobit ; highest bit set?
.C:c01a E6 FB INC $FB ; then add one to remainder
.C:c01c .div_nobit:
.C:c01c A5 FB LDA $FB ; compare remainder ...
.C:c01e C9 09 CMP #$09 ; ... to 9 (divisor)
.C:c020 90 04 BCC .div_nosub ; if greater or equal 9 (divisor)
.C:c022 E9 09 SBC #$09 ; subtract 9 from remainder
.C:c024 85 FB STA $FB
.C:c026 .div_nosub:
.C:c026 26 FC ROL $FC ; shift quotient left, shifting in
.C:c028 26 FD ROL $FD ; carry if remainder was >= 9
.C:c02a 88 DEY ; loop counting
.C:c02b D0 E5 BNE .div_loop ; and repeat
.C:c02d A5 FB LDA $FB ; load remainder
.C:c02f 95 61 STA $61,X ; store in current output digit
.C:c031 CA DEX ; decrement digit index
.C:c032 A5 FD LDA $FD ; copy quotient ...
.C:c034 85 15 STA $15
.C:c036 A5 FC LDA $FC ; ... to dividend
.C:c038 85 14 STA $14
.C:c03a D0 CC BNE .divide ; if not zero yet
.C:c03c A5 15 LDA $15
.C:c03e D0 C8 BNE .divide ; repeat division by 9
.C:c040 E8 INX
.C:c041 86 FE STX $FE ; remember index of first digit
.C:c043 .adjust_loop:
.C:c043 B5 61 LDA $61,X ; load digit
.C:c045 D0 1E BNE .nonine ; if it's zero, must be changed to 9
.C:c047 A9 09 LDA #$09
.C:c049 95 61 STA $61,X
.C:c04b 86 9E STX $9E ; save current index and go back
.C:c04d CA DEX
.C:c04e .sub_loop:
.C:c04e B4 61 LDY $61,X ; examine previous digit
.C:c050 F0 11 BEQ .sub_done ; zero? nothing more to subtract
.C:c052 D6 61 DEC $61,X ; decrement previous digit
.C:c054 D0 0D BNE .sub_done ; not zero -> done
.C:c056 E4 FE CPX $FE ; are we at the first digit?
.C:c058 D0 04 BNE .sub_next ; no: go on
.C:c05a E6 FE INC $FE ; first digit now zero, so increment
.C:c05c B0 05 BCS .sub_done ; and done with subtraction
.C:c05e .sub_next:
.C:c05e 95 61 STA $61,X ; store 9 to this digit
.C:c060 CA DEX ; and go to previous
.C:c061 10 EB BPL .sub_loop ; repeat
.C:c063 .sub_done:
.C:c063 A6 9E LDX $9E ; load saved digit index
.C:c065 .nonine:
.C:c065 E8 INX
.C:c066 E0 06 CPX #$06 ; reached last digit?
.C:c068 D0 D9 BNE .adjust_loop ; no -> repeat
.C:c06a 18 CLC
.C:c06b A6 FE LDX $FE ; start output at first digit
.C:c06d .out_loop:
.C:c06d B5 61 LDA $61,X ; load digit
.C:c06f 69 30 ADC #$30 ; add character code `0`
.C:c071 20 D2 FF JSR $FFD2 ; output character
.C:c074 E8 INX ; next
.C:c075 E0 06 CPX #$06 ; last digit done?
.C:c077 D0 F4 BNE .out_loop ; if not, repeat
.C:c079 60 RTS
5Converting
n
to bijective base 10 is fundamentally the same as counting in bijective baseB
, so by the standards of PPCG this is a duplicate. – Peter Taylor – 2017-10-12T20:20:57.3974@PeterTaylor I wouldn't say this is a duplicate, since here much simpler approaches are possible, like counting up and discarding numbers containing a 0 (and seeing different ways to check if a number contains a 0 is interesting by itself) – Leo – 2017-10-12T20:57:08.617
2@Leo, that approach is possible in the other question too. – Peter Taylor – 2017-10-12T21:42:47.640
1@PeterTaylor it may be possible, but it is not competitive there. Of the answers I can understand in the other question, none use this approach. The vast majority of them are based on cartesian product, which could also be applicable here but currently seems inferior to the other approaches. – Leo – 2017-10-12T22:29:21.750
The way I see it is, convert k (zero indexed) into base 9, in the string of digits add 1 to each (and interpret the string as a number in base 10). That seems to be an efficient way time-wise, but won't necessarily make shorter code, depending on the language's features, so brute force may be shorter... – Heimdall – 2017-10-13T13:39:36.180
@Heimdall this doesn't work, e.g.
99
is120
in base 9, so your method would yield231
. what works is converto the 1-indexed k into base 9, and starting from the most significant digit, replace every0
you encounter with a9
and then subtract 1 from the group of digits to the left of your current digit. – Felix Palmen – 2017-10-13T13:52:53.633@FelixPalmen I see the flaw in my method, it doesn't give numbers that begin with 1. I should use a hybrid system where the most significant digit is is base 10 and the rest of the number is in base 9 (but then I wouldn't be able to use a built-in base converter if there is one in whichever language I go for, I would have to write my own). Then leave the most significant digit alone and add 1 to all other digits (if any). Of course, that would need 1-indexed k. – Heimdall – 2017-10-15T04:56:54.583
@FelixPalmen Your method is good though, applied carefully. You could just subtract 1 from the digit to the left rather than the group because it's not going to be 0 since you're parsing from left (from the most significant digit. But sometimes you'll create more zeroes because you'll subtract 1 from 1 (which I guess you'll ignore if that 1 was the most significant digit, like with k=1). So those additional zeroes will have to be dealt with, too, maybe immediately, and continue to parse the number after dealing with the additional zero, or parse the number again. – Heimdall – 2017-10-15T04:59:19.700
For example, k=66348, in base 9 it is 111010. First zero is the fourth digit, so it becomes 110910. Continue parsing the number, the next zero is the sixth (last) digit, we get 110909. Because we created more zeroes, we do another parse (or we have remembered where they were, positions 3 and 5). We get 109909, 109899, next parse, 099899; as it's the most significant number that became 0, we just drop it -> 99899. Or if newly created zeroes are dealt with immediately, it's just one parse: find first zero on position 4, 111010 -> 110910 -> 109910 -> (0)99910, find next zero, -> 99909 -> 99899. – Heimdall – 2017-10-15T05:37:25.350
@Heimdall the latter is the algorithm my submission uses ;) This is effectively "subtracting
1
from the group of digits to the left" with the special rule that for the most significant digit only,0
isn't wrapped to9
but "cut off" instead. Of course, doing multiple adjustment passes would work as well, didn't think of that. I might check whether it buys me bytes :) – Felix Palmen – 2017-10-15T07:39:55.123@WheatWizard This can't be a duplicate. If you solve this with a base conversion, adjusting the resulting digits is quite a bit more complex than in the linked challenge. Also, as already commented, other solutions than a base conversion are possible and, depending on the language, superior here. – Felix Palmen – 2017-10-15T07:43:41.540
2@felixpalmen I disagree. I think this is a duplicate. I'm quite tired of this general attitude that nothing is a duplicate because of minor differences in the approach of language X. Your free top vote to reopen but I'm not changing my vote. – Post Rock Garf Hunter – 2017-10-15T16:08:08.830
2@WheatWizard I'm quite tired of people spoiling challenges because of faint similarities. The differences here are substantial. – Felix Palmen – 2017-10-16T05:09:50.893