Post Reply 
RPL Mini-Challenge: All Odd Digits?
07-04-2017, 03:10 PM
Post: #21
RE: RPL Mini-Challenge: All Odd Digits?
With Gerald H's sample input my UserRPL program takes 0.1426 seconds, resulting in a score of 8.2708. Not exactly good compared to the scores of others, but straightforward code with some lessons taken from the recent list processing discussion Smile - the list of strings is just eating too much memory, ruining my score.

Let's try SysRPL instead - that's still RPL, right?
Code:
::
  DO>STR TRUE
  BINT10 ZERO_DO
    OVERINDEX@ #>$
    PTR 13FD8
    #0= AND
  BINT2 +LOOP
  SWAPDROP COERCEFLAG
;
You'll probably ask what that PTR does ... it's just BINT1 POS$ in a single command; Nosy showed me that one while looking for ... well, exactly that.
Size is 37.5 bytes.
Times were 0.1495 for the worst case scenario, 0.0292 for the best case, and 0.0942 for Gerald H's average case. The corresponding scores are 5.60625, 1.095, and 3.5325.
Since this is fairly simple code, some of the SysRPL veterans probably have some tricks up their sleeves that will smash this score, but for now ... first score below 4!
Find all posts by this user
Quote this message in a reply
07-08-2017, 08:31 AM
Post: #22
RE: RPL Mini-Challenge: All Odd Digits?
(07-02-2017 04:25 AM)Joe Horn Wrote:  speed * bytes

And what about processor speed? Maybe the right calculation is speed [secs] × bytes ÷ clock [MHz] ?!

Because I measured huge differences on 49G and 48Gii and the other results here.

Csaba
Find all posts by this user
Quote this message in a reply
07-08-2017, 09:11 AM
Post: #23
RE: RPL Mini-Challenge: All Odd Digits?
(07-08-2017 08:31 AM)Csaba Tizedes Wrote:  
(07-02-2017 04:25 AM)Joe Horn Wrote:  speed * bytes

And what about processor speed? Maybe the right calculation is speed [secs] × bytes ÷ clock [MHz] ?!

Because I measured huge differences on 49G and 48Gii and the other results here.

Csaba

Good idea, Horn's parameters far too simple.

As an improvement I suggest

speed [secs] × bytes ÷ (clock [MHz]*(Model Number))+Temperature

although you may say this suffers from the defect that other forum members can't check the temperature of my machine.
Find all posts by this user
Quote this message in a reply
07-08-2017, 10:09 AM (This post was last modified: 07-08-2017 11:40 AM by Paul Dale.)
Post: #24
RE: RPL Mini-Challenge: All Odd Digits?
(07-08-2017 09:11 AM)Gerald H Wrote:  speed [secs] × bytes ÷ (clock [MHz]*(Model Number))+Temperature

I'm going to measure temperature in Celsius, everyone else gets to use Rankine.


- Pauli
Find all posts by this user
Quote this message in a reply
07-08-2017, 11:28 AM
Post: #25
RE: RPL Mini-Challenge: All Odd Digits?
Just for fun, your code with a little polishing - without testing, timing, etc...:

Code:

<<
  0 -> len
  <<
    ->STR 1 9 FOR i i ->STR "0" SREPL 'len' STO+ 2 STEP
    SIZE len ==
  >>
>>

Csaba
Find all posts by this user
Quote this message in a reply
07-08-2017, 11:46 AM
Post: #26
RE: RPL Mini-Challenge: All Odd Digits?
(07-08-2017 11:28 AM)Csaba Tizedes Wrote:  Just for fun, your code with a little polishing - without testing, timing, etc...:

Code:

<<
  0 -> len
  <<
    ->STR 1 9 FOR i i ->STR "0" SREPL 'len' STO+ 2 STEP
    SIZE len ==
  >>
>>

Csaba

Horn's evaluation method gives 22.4 as your score.

Programme seems to work correctly.

The ugliness of my programmes shames me - please help by supplying improvements.

By improvements I mean shorter & faster versions.
Find all posts by this user
Quote this message in a reply
07-08-2017, 04:14 PM (This post was last modified: 07-08-2017 10:46 PM by Gilles59.)
Post: #27
RE: RPL Mini-Challenge: All Odd Digits?
Fastest but not smallest

Code:

 \<<
  \->STR
   CASE
     "0" "" SREPL THEN 0. END
     "2" "" SREPL THEN 0. END
     "4" "" SREPL THEN 0. END
     "6" "" SREPL THEN 0. END
     "8" "" SREPL THEN 0. END
     1.
   END
   NIP
\>>
Find all posts by this user
Quote this message in a reply
07-08-2017, 04:35 PM (This post was last modified: 07-09-2017 09:04 AM by Gilles59.)
Post: #28
RE: RPL Mini-Challenge: All Odd Digits?
Smaller but not fastest (but fast enough) :

Code:
 « ->STR 0 8 2 Seq  « ->STR "" SREPL NOT » All NIP »

Use Gofer list...
61.5 Bytes
Find all posts by this user
Quote this message in a reply
07-09-2017, 10:49 AM (This post was last modified: 07-09-2017 04:04 PM by Gilles59.)
Post: #29
RE: RPL Mini-Challenge: All Odd Digits?
(07-03-2017 01:18 AM)DavidM Wrote:  (...)My submission:
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
  ==
\>>

David, I like very much your approach. You can easily save 2.5 Bytes at the end with :
Code:
OVER 
instead of
DUP UNROT

EDIT : Bad idea... This dont work, sorry
Find all posts by this user
Quote this message in a reply
07-09-2017, 02:25 PM (This post was last modified: 07-16-2017 03:58 PM by Gerald H.)
Post: #30
RE: RPL Mini-Challenge: All Odd Digits?
Edited following posting #37:

To summarize my & Gilles59 best effort, programme

Code:

« →STR 0 8
  FOR i i →STR ""
SREPL { DROP 0. 9 }
2 IFTE
  STEP 0. ≠
»

SIZE: 67.

For an average 1000 digit number, ie having 100 digits zero

11111111111111111111111111111111111111111111111111111111111111111111111111111111​11111111111111111111111111111111111111111111111111111111111111111111111111111111​11111111111111111111111111111111111111111111111111111111111111111111111111111111​11111111111111111111111111111111111111111111111111111111111111111111111111111111​11111111111111111111111111111111111111111111111111111111111111111111111111111111​11111111111111111111111111111111111111111111111111111111111111111111111111111111​11111111111111111111111111111111111111111111111111111111111111111111111111111111​11111111111111111111111111111111111111111111111111111111111111111111111111111111​11111111111111111111111111111111111111111111111111111111111111111111111111111111​11111111111111111111111111111111111111111111111111111111111111111111111111111111​11111111111111111111111111111111111111111111111111111111111111111111111111111111​11111111111111111111000000000000000000000000000000000000000000000000000000000000​0000000000000000000000000000000000000000

TIME: .07 sec

giving a score of 4.7
Find all posts by this user
Quote this message in a reply
07-09-2017, 03:33 PM
Post: #31
RE: RPL Mini-Challenge: All Odd Digits?
(07-09-2017 10:49 AM)Gilles59 Wrote:  David, I like very much your approach. You can easily save 2.5 Bytes at the end with :
Code:
OVER 
instead of
DUP UNROT
In this specific case, the result will be the same

Thanks, Gilles. I'm not clear on exactly what you're suggesting, though. If I replace "DUP UNROT" with a single "OVER", the only time it will give a correct answer for all-odd-digit input is if the input only consists of 1s. As an example, 13579 is all-odd, but results in 0 under those conditions. So I must be misunderstanding what you meant.

I did ultimately decide to make a change to those two commands, though, as I think "SWAP OVER" is clearer in hindsight (though it's the same speed/size as before).

The most "expensive" part of my approach (in terms of speed) is in creating the mask. I kept thinking that there must be a better (built-in) way, and there probably is. But I gave up looking and decided to create a command (RPTCHR) that fulfills that purpose. It's similar to this program that Gerald posted, but more generic in that the repeated character is supplied as a parameter.

Though I consider it to be out-of-scope for this challenge, using RPTCHR to generate the mask made my test both smaller and faster, resulting in a score of about 2.2 (RPTCHR is wicked fast).

A quick scan of the submissions here shows that we're all approaching this using algorithms that check each individual digit for odd/even status. I keep thinking, though, that there might be some kind of mathematical approach that could be applied instead. I've looked at congruences, GCD, and a couple other experiments trying to find some combination of steps that might work here, but I'm afraid I lack the mathematical knowledge to find that kind of solution. Has anyone had any success using something other than a check-every-digit type of approach?
Find all posts by this user
Quote this message in a reply
07-09-2017, 03:59 PM (This post was last modified: 07-09-2017 04:12 PM by Gilles59.)
Post: #32
RE: RPL Mini-Challenge: All Odd Digits?
(07-09-2017 03:33 PM)DavidM Wrote:  
(07-09-2017 10:49 AM)Gilles59 Wrote:  David, I like very much your approach. You can easily save 2.5 Bytes at the end with :
Code:
OVER 
instead of
DUP UNROT
In this specific case, the result will be the same

Thanks, Gilles. I'm not clear on exactly what you're suggesting, though.

OUPS... Sorry...Forget my post ;D I was wrong

RPTCHR will be usefull.

Quote:I keep thinking, though, that there might be some kind of mathematical approach that could be applied instead

I'm not optimistic for this.
Find all posts by this user
Quote this message in a reply
07-09-2017, 06:49 PM
Post: #33
RE: RPL Mini-Challenge: All Odd Digits?
(07-09-2017 03:33 PM)DavidM Wrote:  
(07-09-2017 10:49 AM)Gilles59 Wrote:  David, I like very much your approach. You can easily save 2.5 Bytes at the end with :
Code:
OVER 
instead of
DUP UNROT
In this specific case, the result will be the same

Thanks, Gilles. I'm not clear on exactly what you're suggesting, though. If I replace "DUP UNROT" with a single "OVER", the only time it will give a correct answer for all-odd-digit input is if the input only consists of 1s. As an example, 13579 is all-odd, but results in 0 under those conditions. So I must be misunderstanding what you meant.

I did ultimately decide to make a change to those two commands, though, as I think "SWAP OVER" is clearer in hindsight (though it's the same speed/size as before).

The most "expensive" part of my approach (in terms of speed) is in creating the mask. I kept thinking that there must be a better (built-in) way, and there probably is. But I gave up looking and decided to create a command (RPTCHR) that fulfills that purpose. It's similar to this program that Gerald posted, but more generic in that the repeated character is supplied as a parameter.

Though I consider it to be out-of-scope for this challenge, using RPTCHR to generate the mask made my test both smaller and faster, resulting in a score of about 2.2 (RPTCHR is wicked fast).

A quick scan of the submissions here shows that we're all approaching this using algorithms that check each individual digit for odd/even status. I keep thinking, though, that there might be some kind of mathematical approach that could be applied instead. I've looked at congruences, GCD, and a couple other experiments trying to find some combination of steps that might work here, but I'm afraid I lack the mathematical knowledge to find that kind of solution. Has anyone had any success using something other than a check-every-digit type of approach?

I'd love to be corrected, but my limited knowledge of numbers says that the parity of a digit in a number other than the final position contains no particular info concerning the whole number, ie individual digit checking is the only method.
Find all posts by this user
Quote this message in a reply
07-16-2017, 12:43 AM
Post: #34
RE: RPL Mini-Challenge: All Odd Digits?
Any chance we'll get to see your solution, Joe?
Find all posts by this user
Quote this message in a reply
07-16-2017, 04:22 AM (This post was last modified: 07-16-2017 04:25 AM by Joe Horn.)
Post: #35
RE: RPL Mini-Challenge: All Odd Digits?
(07-16-2017 12:43 AM)DavidM Wrote:  Any chance we'll get to see your solution, Joe?

Almost identical to DavidM's entry:

« →STR DUPDUP SIZE R→I ALOG 1 - 9 / →STR OR SAME »

40 bytes, 0.12 seconds on any 1000-digit input on a 50g, for a "score" of 4.8.

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
07-16-2017, 05:01 AM
Post: #36
RE: RPL Mini-Challenge: All Odd Digits?
(07-16-2017 04:22 AM)Joe Horn Wrote:  Almost identical to DavidM's entry:

« →STR DUPDUP SIZE R→I ALOG 1 - 9 / →STR OR SAME »

40 bytes, 0.12 seconds on any 1000-digit input on a 50g, for a "score" of 4.8.

Yes, it looks familiar. Smile But yours is smaller and a hair faster. Seeing your version (and some other recent posts) prompted me to check the performance of "SAME" vs "==". SAME was much faster in my test. Good to know!

Thanks for posting.
Find all posts by this user
Quote this message in a reply
07-16-2017, 02:10 PM
Post: #37
RE: RPL Mini-Challenge: All Odd Digits?
Yes, SAME is about 2 ms faster than ==. In fact, SAME NOT is faster than\/= as well.

Also, in the code summary in post #30, the final bit ...0 < must be a misprint as it causes an error comparing an integer to a string. I assume it is supposed to be ...0 \/= unless I am missing something.

John
Find all posts by this user
Quote this message in a reply
07-16-2017, 02:58 PM
Post: #38
RE: RPL Mini-Challenge: All Odd Digits?
(07-16-2017 02:10 PM)John Keith Wrote:  Yes, SAME is about 2 ms faster than ==. In fact, SAME NOT is faster than\/= as well.

Also, in the code summary in post #30, the final bit ...0 < must be a misprint as it causes an error comparing an integer to a string. I assume it is supposed to be ...0 \/= unless I am missing something.

John

Correct, should be

Find all posts by this user
Quote this message in a reply
07-17-2017, 06:26 AM (This post was last modified: 07-17-2017 06:26 AM by Werner.)
Post: #39
RE: RPL Mini-Challenge: All Odd Digits?
SAME and == are not .. the same.

1 1. SAME returns 0.
1 1. == returns 1

Don't know why one would return an integer and the other a real, though..

Cheers, Werner

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
Find all posts by this user
Quote this message in a reply
07-17-2017, 07:18 AM
Post: #40
RE: RPL Mini-Challenge: All Odd Digits?
New version:

Code:

« →STR DUP 0 8
  FOR i i →STR ""
SREPL 9 2 IFTE
  STEP SAME
»

Size: 57 Bytes

Time for average 1000 digit input: .069 sec

Score: 3.9
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)