mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2005-05-28, 12:42   #1
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default Generating 2005

The folks at mathzone.net.tc posted a (set of) challenge(s) to generate the numeric value 2005 using a single digit and various operators.

As an example of what they had in mind, we could generate the number 12 as (44+4)/4

Their metric for the quality of the solution was the number of times the required digit occurred.

Paul (Xilman on this forum) presented a solution that used a long chain of square root functions to generate any arbitrary integer. Since each sqrt function did not require any digits, his answer has a very low count.

I wish to propose a similar challenge that does not rule out Paul's approach but makes it less desirable because I am specifying a different metric.

Your goal for each of the ten challenges is to write the shortest C++ code fragment to be inserted in the program specified below.
The code must meet the following criteria:

The submitted code fragment will be compressed as follows:
All comments will be removed
All literal strings will be replaced with the null string ""
All whitespace, including new-lines, will be removed

The resulting entry must include at least one instance of the digit for which it is entered.
When inserted in place of the line "2005" in the code below, the program must compile and execute properly to produce (just) the answer "ACCEPTABLE".

Entries will be ranked on two levels
First, the use of Distinct Digits. We count the number of distinct elements of the set { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' } that are used.
In case of a tie, we count Total Characters. Remember that only non-blank characters will be counted. Feel free to use multiple lines, spaces, and comments to make the method more readable. These are all stripped before evaluation and therefore do not penalize you.

In both cases, an entry using fewer will be ranked higher.

My example entry qualifies in the "0", "2", and "5" categories.
In each case, it is ranked on the basis of (3,4)

Let the Challenge Begin!

Code:
#include <iostream>

int main (int argc, char * const argv[]) {
   int answer =
   // BEGIN inserted code on the next line
   2005
   // END inserted code on the above line
   ;
   if (answer != 2005) {
	std::cout << "REJECTED";
   } else {
	std::cout << "ACCEPTABLE";
   }
   std::cout << std::endl;
   return 0;
}

Last fiddled with by Wacky on 2005-05-28 at 13:47 Reason: Typo
Wacky is offline   Reply With Quote
Old 2005-05-28, 13:37   #2
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default Scoreboard

Code:
Digit  Rank   Date     By           Fragment
  0    1,10   Jun 05   Ken_g6       0xFAA>>-~0
  1    1,16   Jun 01   Ken_g6       1-~1111-111<<1|1    // min is probably > 13 chars
  2    1,13   Jun 01   Ken_g6       2222-222|2-~2       // minimal
  3    1,14   Jun 01   Ken_g6       3333+~3*333-~3      // By computer, probably minimal
  4    1,12   Jun 01   Ken_g6       ~4*(44+~444)        // By computer, minimal
  5    1,12   Jun 01   Ken_g6       5*5*5<<~-5|5        // By computer, minimal - sorry, Richard. :(
  6    1,12   Jun 01   Ken_g6       ~6*666-~6666        // By computer, minimal
  7    1,13   Jun 01   Ken_g6       77-~7|7-~7<<7       // By computer, minimal
  8    1,15   Jun 02   Ken_g6       8888/8^-~8-~888     // By computer, minimal
  9    1,11   May 31   Ken_g6       999+(9^999)         // By computer, minimal
Note: The comments have been provided by Ken

Also note: He also has provided (1,9) solutions for each of the digits using 2-character literals,
Since I haven't found any way to get the compiler to reject them, they are the actual "winners".
But I'm leaving the other solutions on the scoreboard because they are, at least to me, more interesting.

Congratulations, Ken, on a good job.

(But the contest remains open as long as there is a moderator who will accept shorter answers)

Wacky

Last fiddled with by Wacky on 2005-06-05 at 22:03
Wacky is offline   Reply With Quote
Old 2005-05-28, 22:27   #3
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

5×79 Posts
Default

I get it. The idea is the shortest expression (in terms of numerals) for 2005 containing digit x.

Well, for x=4, "5*401" (or 401*5) seems minimal in total size.

For x=1,6 try "2006-1".
For x=7 try "2007-2".
For x=3,8 try "2008-3".
For x=9 try "2009-4".
Ken_g6 is offline   Reply With Quote
Old 2005-05-28, 23:07   #4
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

Quote:
Originally Posted by Ken_g6
I get it. The idea is the shortest expression (in terms of numerals) for 2005 containing digit x.
Not quite, it is better to use fewer different digits than it is to have a short expression.

As another example,

you offered "5*401" for the digit 4. It has 4 distinct digits, '0', '1', '4' and '5'
with a total of 5 characters and is scored as (4,5)

I will beat that with "5*400+5" which scores (3,7) because I used only three distinct digits even though I used 2 additional characters.
Wacky is offline   Reply With Quote
Old 2005-05-29, 04:31   #5
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

5×79 Posts
Default

Okay, I get it now. First off, I got a solution for x=1 using only addition (and subtraction):
x=1: 1111+1111-111-111+1+1+1+1+1
That means for any 0<x<10 you can take this, multiply it by x (which changes all the 1's to x's) and divide by x again to get a solution for x.

But then I found better solutions for all of them! :D
I think x=0 requires at least one other digit. Can someone prove me wrong?
x=0: 2002+2+2/2
"<<" is the left-shift operator. Too bad it needs parentheses. :( But it's still sometimes better than anything else I could find.
x=1: (1<<11)-11-11-11-11+1
x=2: 2222-222+2+2+2/2
x=3: 3*333+3*333+3+3+3/3
x=4: 44*44+4*4*4+4+4/4
x=5: 555*5-555-55*5+55+5
x=7: (7<<7)+777+7*7*7-77/7
x=6: 666+666+666+6+6/6
x=8: 888+888+88+88+8*8-88/8
x=9: 999+999+9-(9+9)/9
Ken_g6 is offline   Reply With Quote
Old 2005-05-29, 05:22   #6
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

5×79 Posts
Default

Well, I proved myself wrong! There is a way to do x=0 with no digit but 0. But it's not easy or short:
Code:
0;	// What other number could I use here?
// One of the few functions that get something out of 0 is exp.
int a = exp(exp(0));
// Now a=2 (rounded down from e).
// This line is 2^11 - 2^5 - 8 - 2 - 1
answer = (a<<a*a*a+a)-(a<<a*a) - a*a*a - a - exp(0)
Ken_g6 is offline   Reply With Quote
Old 2005-05-29, 09:16   #7
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

Quote:
Originally Posted by Ken_g6
x=1: 1111+1111-111-111+1+1+1+1+1
Accepted
Quote:
x=0: 2002+2+2/2
Accepted
Quote:
x=1: (1<<11)-11-11-11-11+1
x=2: 2222-222+2+2+2/2
x=3: 3*333+3*333+3+3+3/3
x=4: 44*44+4*4*4+4+4/4
x=5: 555*5-555-55*5+55+5
x=7: (7<<7)+777+7*7*7-77/7
x=6: 666+666+666+6+6/6
x=8: 888+888+88+88+8*8-88/8
x=9: 999+999+9-(9+9)/9
All accepted
Wacky is offline   Reply With Quote
Old 2005-05-29, 09:31   #8
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

Quote:
Originally Posted by Ken_g6
Code:
0;	// What other number could I use here?
// One of the few functions that get something out of 0 is exp.
int a = exp(exp(0));
// Now a=2 (rounded down from e).
// This line is 2^11 - 2^5 - 8 - 2 - 1
answer = (a<<a*a*a+a)-(a<<a*a) - a*a*a - a - exp(0)
A nice try. But the compiler rejected it.

BTW, thanks for the comments to explain your work. They were not what the compiler disliked.
Wacky is offline   Reply With Quote
Old 2005-05-29, 10:32   #9
Richard Cameron
 
Richard Cameron's Avatar
 
Mar 2005

17010 Posts
Default

I think there is a better solution for 5:

(55+5*5)*5*5+5

Richard Cameron
Richard Cameron is offline   Reply With Quote
Old 2005-05-29, 11:53   #10
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

Quote:
Originally Posted by Richard Cameron
(55+5*5)*5*5+5
Accepted
Wacky is offline   Reply With Quote
Old 2005-05-29, 12:17   #11
dave_dm
 
May 2004

8010 Posts
Default

How about this for a digit-free solution?

Code:
'.'*'-'-'A'
Since the rules require us to use at least one of the relevant digit, this can easily be modified to

Code:
x=0: '.'*'-'-'A'+0
x=1: '.'*'-'-'B'+1
...
x=9: '.'*'-'-'J'+9
This solution doesn't get decimated by the "All literal strings will be replaced with the null string" rule as '-' is strictly speaking a char, not a string.

Dave

Last fiddled with by dave_dm on 2005-05-29 at 12:18
dave_dm is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
k*2^n-1 primes in 2005 Kosmaj Riesel Prime Search 2 2006-01-01 11:49
Mathematical Highlights of 2005 rogue Lounge 17 2006-01-01 02:16
Hurricane Season 2005 clowns789 Lounge 22 2005-11-01 12:02
MPrime 2005 BBCD HiddenWarrior Software 4 2005-10-11 10:47
2005 - year of the supercomputer? ixfd64 Lounge 3 2004-11-09 08:46

All times are UTC. The time now is 02:43.


Thu Oct 21 02:43:49 UTC 2021 up 89 days, 21:12, 1 user, load averages: 0.78, 1.03, 1.11

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.