RPL Micro-Challenge: Christmas in July
07-17-2017, 02:26 PM
Post: #1
 Joe Horn Senior Member Posts: 1,841 Joined: Dec 2013
RPL Micro-Challenge: Christmas in July
Everybody knows the "12 Days of Christmas" Song (Partridge in a Pear Tree etc). How many gifts has my true love given to me altogether by the end of Day 3? Well, the sum of today's 6 gifts (3+2+1) plus yesterday's 3 gifts (2+1) plus the first day's 1 gift comes to 10 gifts in all. So the Total Gifts through Day 3 = TG(3) = 10.

What is the smallest possible (byte-count) User RPL program that calculates TG(x)?

To check your program, here are a few sample inputs and outputs:

TG(3)=10
TG(5)=35
TG(12)=364
TG(365)=8171255

N.B. This is called a micro-challenge instead of a mini-challenge because a REALLY SMALL solution exists. If it's obvious to you, please don't post it right away; let others try to find it first. "We only appreciate the answer if we struggle with the question." -- Ignatius O'Brien, O.P.

<0|ɸ|0>
-Joe-
07-17-2017, 02:53 PM (This post was last modified: 07-17-2017 05:00 PM by Werner.)
Post: #2
 Werner Senior Member Posts: 695 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
I still know the formula by heart, and its shorter form.
4 commands, 2 of which are single digit numbers ;-)
That would then be 20 bytes including the Rpl markers << >>
Cheers, Werner
07-17-2017, 03:45 PM
Post: #3
 Gilles59 Member Posts: 136 Joined: Jan 2017
RE: RPL Micro-Challenge: Christmas in July
(07-17-2017 02:53 PM)Werner Wrote:  I still know the formula by heart, and its shorter form.
4 commands, 2 of which are single digit numbers ;-)
Cheers, Werner

I think I got the idea, but more than 4 commands ....
07-17-2017, 04:09 PM
Post: #4
 Gerson W. Barbosa Senior Member Posts: 1,454 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
32.5 bytes. Only first attempt, though.
07-17-2017, 04:32 PM (This post was last modified: 07-17-2017 04:57 PM by Gerson W. Barbosa.)
Post: #5
 Gerson W. Barbosa Senior Member Posts: 1,454 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
More like it: 27.5 bytes.

PS: Even more like it: 20 bytes.
07-17-2017, 04:54 PM
Post: #6
 Jim Horn Member Posts: 203 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
Great question, Joe! Finite differences quickly gave me the formula; factoring it gave a simplified form (also 4 operations and two single digit constants). Several attempts keep giving me 9 step solutions. Do you have a shorter one? (RPN form used; LBL and RTN not counted)
07-17-2017, 05:58 PM
Post: #7
 Gilles59 Member Posts: 136 Joined: Jan 2017
RE: RPL Micro-Challenge: Christmas in July
(07-17-2017 04:32 PM)Gerson W. Barbosa Wrote:  More like it: 27.5 bytes.

PS: Even more like it: 20 bytes.

I was happy with my 38 bytes solution but i have to search another way
07-17-2017, 06:52 PM
Post: #8
 Gerald H Senior Member Posts: 1,461 Joined: May 2014
RE: RPL Micro-Challenge: Christmas in July
32.5 & stuck.
07-17-2017, 08:17 PM
Post: #9
 Gerson W. Barbosa Senior Member Posts: 1,454 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
(07-17-2017 06:52 PM)Gerald H Wrote:  32.5 & stuck.

Just factor the expression you already have. This might give you an insight towards a shorter solution.
07-17-2017, 08:31 PM (This post was last modified: 07-17-2017 08:55 PM by Gilles59.)
Post: #10
 Gilles59 Member Posts: 136 Joined: Jan 2017
RE: RPL Micro-Challenge: Christmas in July
(07-17-2017 08:17 PM)Gerson W. Barbosa Wrote:
(07-17-2017 06:52 PM)Gerald H Wrote:  32.5 & stuck.

Just factor the expression you already have. This might give you an insight towards a shorter solution.

Yes but I cannot imagine how you arrive at 20 bytes ... Did you have a division in your expression ?

[EDIT] Eureka! I get it!
07-17-2017, 09:33 PM
Post: #11
 Gerson W. Barbosa Senior Member Posts: 1,454 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
(07-17-2017 08:31 PM)Gilles59 Wrote:  [EDIT] Eureka! I get it!

Congratulations!

Apparently the 20-byte record cannot be broken.

Gerson.
07-18-2017, 12:04 AM (This post was last modified: 07-18-2017 12:24 AM by Joe Horn.)
Post: #12
 Joe Horn Senior Member Posts: 1,841 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
(07-17-2017 04:54 PM)Jim Horn Wrote:  Great question, Joe! Finite differences quickly gave me the formula; factoring it gave a simplified form (also 4 operations and two single digit constants). Several attempts keep giving me 9 step solutions. Do you have a shorter one? (RPN form used; LBL and RTN not counted)

This is an RPL challenge, but please feel free to implement it for the RPN machine of your choice. I wonder whether the polynomial form or the shorter form would be faster on a machine that doesn't have the secret command that's needed (such as the bare-bones HP-41).

(07-17-2017 09:33 PM)Gerson W. Barbosa Wrote:  Apparently the 20-byte record cannot be broken.

Yes, I'm sure that we're all arriving at the same 20-byte solution.

Final hint to those still hunting: the formula can be expressed this way, which should remind you of a shorter way of expressing it: $$\frac { x(x+1)(x+2) }{ 1\cdot 2\cdot 3 }$$

<0|ɸ|0>
-Joe-
07-18-2017, 02:17 AM
Post: #13
 Dave Britten Senior Member Posts: 2,074 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
7 steps (not including LBL and RTN) is the shortest I can get it so far on the 20S.
07-18-2017, 04:24 AM
Post: #14
 Paul Dale Senior Member Posts: 1,750 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
Four steps on the 34S.

Pauli
07-18-2017, 06:31 PM
Post: #15
 Jim Horn Member Posts: 203 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
Ausgezeichnet! I had "6" in the denominator so didn't recognize the now-obvious simplification as per Paul's note. Many thanks, Joe - a clever insight on your part!
07-18-2017, 09:07 PM (This post was last modified: 07-18-2017 09:33 PM by Gerson W. Barbosa.)
Post: #16
 Gerson W. Barbosa Senior Member Posts: 1,454 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
(07-17-2017 05:58 PM)Gilles59 Wrote:
(07-17-2017 04:32 PM)Gerson W. Barbosa Wrote:  More like it: 27.5 bytes.

PS: Even more like it: 20 bytes.

I was happy with my 38 bytes solution but i have to search another way

Now that you've found it I should tell you my next program yesterday was 38.5 bytes long.

An exotic memory-consuming solution:

« x x x IDN →DIAG x x x x »

I know there's a better equivalent of the two middle commands, but I don't remember which.

Don't anyone be misled by this one. Joe's optimum solution is simply « y y y y » :-)
07-19-2017, 09:41 AM
Post: #17
 Gerald H Senior Member Posts: 1,461 Joined: May 2014
RE: RPL Micro-Challenge: Christmas in July
All well & good saying you have a solution with so many bytes but eventually you lay your cards on the table.

Below a 32.5 Byte solution to the problem:

Code:
 « DUPDUP 3 + * 2 + * 6 / »
07-19-2017, 11:50 AM
Post: #18
 Gilles59 Member Posts: 136 Joined: Jan 2017
RE: RPL Micro-Challenge: Christmas in July
A 38 bytes solution

Code:
<< [ 1 3 2 0 ] SWAP PEVAL 6 / >>
07-19-2017, 12:56 PM (This post was last modified: 07-19-2017 01:47 PM by Joe Horn.)
Post: #19
 Joe Horn Senior Member Posts: 1,841 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
(07-19-2017 09:41 AM)Gerald H Wrote:  All well & good saying you have a solution with so many bytes but eventually you lay your cards on the table.

Ok, we are far enough down the page to reveal the 20-byte solution:

« 2 + 3 COMB »

Why it works: The formula for TG(x) is $$\frac { x(x+1)(x+2) }{ 1\cdot 2\cdot 3 }$$, but that looks very similar to the formula for COMB(x,3) which is $$\frac { x(x-1)(x-2) }{ 1\cdot 2\cdot 3 }$$. All you have to do to turn the latter into the former is add 2 to x, and voila, TG(x) = COMB(x+2,3).

This is an example of program optimization being obtained not by code optimization but by math optimization.

EDIT: I just noticed something cool. If you run the program above on an input of 'X' (undefined), and then EVAL the resulting mess, you get this:

$\frac { { X }^{ 3 }+3{ X }^{ 2 }+2X }{ 6 }$
Now press FACTOR (or COLLECT) and see this:
$\frac { X\cdot (X+1)\cdot (X+2) }{ 3\cdot 2 }$
It almost does all the thinking for you.

<0|ɸ|0>
-Joe-
07-19-2017, 01:42 PM
Post: #20
 Dave Britten Senior Member Posts: 2,074 Joined: Dec 2013
RE: RPL Micro-Challenge: Christmas in July
Oh, duh, I was doing COMB(x+2, x-1), completely forgetting about the symmetric nature of combinations.
 « Next Oldest | Next Newest »

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