Here's a mini-challenge for HP 49 & HP 50 programmers.
Purpose of program: Test whether a number contains only odd digits.
Input: Any positive exact integer (that is, exact-mode integer-type objects only, no reals or negatives allowed). Invalid inputs need not be tested for.
Output: 1 (meaning "true") if the input contains only odd digits. 0 (meaning "false") if the input contains any even digits.
Examples:
1357335 --> 1 (True; all digits are odd)
1357325 --> 0 (False; there's an even digit in there)
1234567 --> 0 (False; not all digits are odd)
0 --> 0 (False; 0 is even)
The winner is determined by speed * bytes (execution in seconds, times size of program without name) on 1000-digit inputs. My current best score is roughly 4.8.
A first suggestion:
Code:
« 1. SWAP →STR 0 8
FOR i i →STR "0" SREPL
IF
THEN NIP 0. SWAP 10
ELSE 2
END
STEP DROP
»
Time in seconds for 1000th repunit (worst case)
.13 sec
byte size of programme
84.5
giving a score of 10.95
Edit: As most 1000 digit numbers contain a zero, average score would be 5.2
This will be easily a new processing list challenge! Thanks for the input.
Slightly shortened version:
Code:
« →STR 0 8
FOR i i →STR "0"
SREPL
IF
THEN DROP 0. 10
ELSE 2
END
STEP 0. ≠
»
Score on average now 5.07
Further slightly shorter version:
Code:
« →STR 0 8
FOR i i →STR ""
SREPL
IF
THEN DROP 0. 10
ELSE 2
END
STEP 0. ≠
»
Average score now 5.07
With the GoferList Library :
Code:
→STR Chars « STR→ 2 MOD » All
Short but slow (24sec) in the worst case (1000 digits all odd). I think SREPL is a (the) key ;D
PS :
Code:
→STR Chars STR→ « 2 MOD » All
is a little slower
(07-02-2017 10:18 AM)Gerald H Wrote: [ -> ]Further slightly shorter version:
Average score now 5.07
Hi Gerald, what do you mean with "average score" ?
Joe, how do you calculate the execution time ? Is it in the worst case?
This code is a variation of Gerald program but shorter and little faster :
Code:
« →STR
0 8 FOR n
n →STR "" SREPL {DROP 0. 9} 2 IFTE
STEP
0. ≠
»
67 bytes
Execution time on 1000-digit inputs :
Best case : 0.0619 s (101...111)
Worst case : 0.1351 s (111...111)
SREPL is very fast. I suspect it is ARM coded.
Another Idea
Code:
«
->STR
{ 1 3 5 7 9 } 1. « ->STR "" SREPL DROP » DOLIST
SIZE NOT
»
Wow so many ideas. Here is mine.
«
STR 1 SWAP
WHILE
DUP HEAD OBJ 2 MOD ROT AND SWAP TAIL DUP2 SIZE AND
REPEAT
END DROP
»
@Joe: Nice mini-challenge! I'm glad to see you are still exercising your RPL skills. And I'm also pleased to see that you've specified a balanced approach for scoring this one. All the work I've been doing with lists lately has really underscored the importance of considering speed and memory issues along with code size.
My submission:
I decided to try a different tactic for this challenge, though it's still not quite as fast as Joe's. This one has a size of 45 bytes, and clocks in on my 50g at 0.1222 seconds. That gives me a score of about 5.5 on the 1000-digit numbers:
Code:
\<<
@ convert integer to string
\->STR
@ obtain number of digits
DUP SIZE
@ create a mask of 1s for the given length
R\->I ALOG 1 - 9 / \->STR
@ save a copy of the mask, then apply it to mark all odd digit positions
DUP UNROT AND
@ if the result is the same as the mask, all digits were odd
==
\>>
*Note that the calculator has to already be in exact mode when you transfer (or edit) the above program, otherwise the 1 and 9 constants will get compiled as reals instead of integers. The program won't work if that happens. I believe this is still in keeping with the specified rules of the challenge, though.
Using Gilles version of my prog at 67 bytes & time for a zero inclusive 1000 digit .065 sec gives a score of 4.3
Taking the product of 900th repunit & 10^100 as the average input, I get using Gilles version a time of .071 sec & size of 67, giving a score of 4.75
(07-03-2017 06:50 AM)Gerald H Wrote: [ -> ]Taking the product of 900th repunit & 10^100 as the average input, I get using Gilles version a time of .071 sec & size of 67, giving a score of 4.75
Excuse me, but what score are you talking about?
Dieter
(07-03-2017 07:33 AM)Dieter Wrote: [ -> ] (07-03-2017 06:50 AM)Gerald H Wrote: [ -> ]Taking the product of 900th repunit & 10^100 as the average input, I get using Gilles version a time of .071 sec & size of 67, giving a score of 4.75
Excuse me, but what score are you talking about?
Dieter
Please see post #1 for method of evaluating score.
(07-03-2017 01:18 AM)DavidM Wrote: [ -> ]I decided to try a different tactic for this challenge, though it's still not quite as fast as Joe's. This one has a size of 45 bytes, and clocks in on my 50g at 0.1222 seconds. That gives me a score of about 5.5 on the 1000-digit numbers:
Code:
\<<
@ convert integer to string
\->STR
@ obtain number of digits
DUP SIZE
@ create a mask of 1s for the given length
R\->I ALOG 1 - 9 / \->STR
@ save a copy of the mask, then apply it to mark all odd digit positions
DUP UNROT AND
@ if the result is the same as the mask, all digits were odd
==
\>>
Very interesting David!
I dont have my 50G here, but I think there is a way to improve speed of the part :
Code:
R\->I ALOG 1 - 9 / \->STR
I think at something like :
Code:
1. - R\->I ALOG \->STR "0" "1" SPREPL DROP
(07-03-2017 07:33 AM)Dieter Wrote: [ -> ]Excuse me, but what score are you talking about?
See the first post.
Quote:The winner is determined by speed * bytes (execution in seconds, times size of program without name) on 1000-digit inputs.
Pauli
(07-03-2017 07:52 AM)Gilles59 Wrote: [ -> ]Very interesting David!
I dont have my 50G here, but I think there is a way to improve speed of the part :
Code:
R\->I ALOG 1 - 9 / \->STR
I think at something like :
Code:
1. - R\->I ALOG \->STR "0" "1" SREPL DROP
I tried some variants of the above, but found that the version I posted ended up being faster, at least on a real 50g vs. Emu48. This is one of those cases where the performance on Emu48 is misleading when compared to a real 50g. When I use your code instead of the first version posted, the overall speed on a real 50g goes from 0.1222 seconds to around 0.167. The SREPL version is faster on Emu48, though, probably because Emu48 doesn't emulate the ARM layer. So I guess it depends on what platform you're targeting.
Unfortunately the SREPL version is also about 15 bytes longer, so it not only slows down but also raises the score on that front as well. I've been assuming that Joe's scoring method is based on the results of size/performance as measured on a real calculator as opposed to an emulated one.
My take:
Code:
\<< \->STR { "0" "2" "4" "6" "8" } POS \GSLIST NOT \>>
58 bytes, worst case time on 1000-digit input (111...111) was 0.1969 seconds, best case would be 86420111...111 so the POS command finds each digit early, which took 0.0767 seconds. Scores would be 11.4202 and 4.4486, respectively.
Now what would constitute "average" input?
For an average number, in this case
1(100*)2(100*)3(100*)4(...............*)9(100*)*10^100
Gilles programme requires .057 sec, giving a score of 3.84
The notation 1(100*) indicates a concatenation of 100 1s.
(07-02-2017 07:53 PM)Gilles59 Wrote: [ -> ]Joe, how do you calculate the execution time?
I put the input number on the stack, then recall the program itself onto the stack, then execute TEVAL (which I keep assigned to a key).
(07-03-2017 10:26 AM)DavidM Wrote: [ -> ]I've been assuming that Joe's scoring method is based on the results of size/performance as measured on a real calculator as opposed to an emulated one.
Correct. Otherwise the "score" would be meaningless, allowing crummy code on a fast computer to beat elegant code on a slower computer.