Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Given list of integers {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}. For those who interested these numbers are used in weekday calculation.

Weekday = (m[n] + d + y + y>>2 + y/400 - y/100) % 7;, where m[n] - expression I'm searching, d - day of month, y - year - (month <= 2).

Construct expression consisting of arithmetic, logic and bitwise operators, which will output for positive integer n integer m so that m % 7 equals n-th number in the list.

Branches, ternary operators, table lookups and pointers are not allowed.

Score:
1 - for | & ^ ~ >> << operators
1.1 - for + - < > <= >= == != ! && || operators
1.2 - for * operator
1.4 - for / % operators

Answer with lowest score wins.

Personally I have found:

(41*n)>>4+((n+61)>>4)<<2 with score 6.4. I thought this will be hard to find so provided own expression to start with.

share|improve this question
    
I guess array dereferencing (and the kin) isn't allowed either? –  Jan Dvorak Jul 16 at 21:48
    
Oh, yes of course, I have edited the question. –  Somnium Jul 16 at 21:49
11  
I like this until I read "Personall I have found:". Why post a solution yourself? It would have been fun to figure it out from scratch. :-/ (It also would have been fun to see all sorts of approaches, but I think now you won't get any which score less than 6.4) –  Martin Büttner Jul 16 at 22:10
5  
The question would be greatly improved by some motivation. Where do those numbers come from? –  Peter Taylor Jul 16 at 22:32
3  
Why not count the %7 in the score? Maybe there's another solution not using %. Is zero positive, negative, both or nothing? –  Thomas W. Jul 17 at 6:16

5 Answers 5

up vote 27 down vote accepted

2 2.2

I love arbitrary precision arithmetic.

0x4126030156610>>(n<<2)

Or, if you don't like hex,

1146104239711760>>(n<<2)

Test:

print([(0x4126030156610>>(n<<2))%7 for n in range(1,13)])
[0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
share|improve this answer
    
Could you perhaps make a lookup table with 4*n instead, and save 0.2 points by writing it as n<<2? –  xnor Jul 17 at 0:54
    
@xnor Absolutely! Just to to switch from octal to hexadecimal. Just as sec. –  isaacg Jul 17 at 2:04
    
Cool. I'm pretty convinced nothing can do better because it would require using only one operation, and they all seem to have too much structure mod 7. My best candidate of integer floor division const/n runs into a contradiction with n=4 and n=8. –  xnor Jul 17 at 2:23
    
@xnor Another close one is const%n which could satisfy everything except n=1,2 and 3. –  isaacg Jul 17 at 2:43
    
I was gonna do the same thing, but you beat me to it... –  ɐɔıʇǝɥʇuʎs Jul 17 at 5:41

2.0

(127004 >> i) ^ 60233

or (score 2.2) :

(i * 3246) ^ 130159

All found with brute force :-)

share|improve this answer
    
Since this has the same score as isaacg's answer, but doesn't uses 64-bit integers, I'm choosing this as accepted answer. Thank you for answer! –  Somnium Jul 17 at 10:23
7  
@user2992539 While it's nice that this answer uses 32-bit integers, you didn't specify this criterion in your challenge, which makes isaacg's answer perfectly valid. Therefore, the two answers tie and I think it's only fair to accept the first one that got this score. (Kudos to Super Chafouin, though, +1!) –  Martin Büttner Jul 17 at 10:50
    
@m.buettner I have to agree with you. Next time, I will be more careful with description and answer selection. –  Somnium Jul 17 at 11:19
    
For others to learn, could you elaborate on how you did the brute force calculation? –  Thomas W. Jul 17 at 22:07
    
@Thomas I just made a double for loop, testing all the values p, q for the formula (p >> i) ^ q, then went to take a coffee, and 10 mn after came to read the results. –  Super Chafouin Jul 18 at 1:59

35.3

I suspect this may be the least efficient method to create the list:

1.7801122128869781e+003 * n - 
1.7215267321373362e+003 * n ^ 2 + 
8.3107487075415247e+002 * n ^ 3 - 
2.0576746235987866e+002 * n ^ 4 + 
1.7702949291688071e+001 * n ^ 5 + 
3.7551387326116981e+000 * n ^ 6 - 
1.3296432299817251e+000 * n ^ 7 + 
1.8138635864087030e-001 * n ^ 8 - 
1.3366764519057219e-002 * n ^ 9 + 
5.2402527302299116e-004 * n ^ 10 - 
8.5946393615396631e-006 * n ^ 11 -
7.0418841304671321e+002

I just calculated the polynomial regression. I'm tempted to see what other terrible method could be attempted.

Notably, I could save 3.3 points if the result was rounded. At this point, I don't think that matters.

share|improve this answer

3.2

Zero based solution:

7 & (37383146136 >> (i*3))

One based solution:

7 & (299065169088 >> (i*3))

I initially thought that the %7 operation would be counted as well and % being an expensive operation here, I tried to solve it without it.

I came to a result of 3.2 like this:

// Construction of the number
// Use 3 bits per entry and shift to correct place
long c = 0;
int[] nums = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
for (int i = nums.Length - 1; i >= 0; i--)
{
    c <<= 3;
    c += nums[i];
}
// c = 37383146136

// Actual challenge
for (int i = 0; i < 13; i++)
{
    Console.Write("{0} ",7 & 37383146136 >> i*3);
}

I'd be interested in optimizations using this approach (without %). Thanks.

share|improve this answer
    
This is cool, maybe this will help me some day) How do you think, maybe I should create separate question for whole formula minimization? –  Somnium Jul 17 at 6:45
1  
How about (0426415305230 >> (i*3)) & 7? You can see the output digits in reverse order. –  CJ Dennis Jul 18 at 14:51
    
@CJDennis: I think there are no octal numbers in C#. –  Thomas W. Jul 18 at 15:20
    
I thought it was just C? I can't see any other reference to C#. –  CJ Dennis Jul 19 at 1:17

Python (3)

Since there are quite a few of these questions these days, I decided to make a program to automatically solve them in 3 (or 2) tokens. Here's the result for this challenge:

G:\Users\Synthetica\Anaconda\python.exe "C:/Users/Synthetica/PycharmProjects/PCCG/Atomic golfer.py"
Input sequence: 0 3 2 5 0 3 5 1 4 6 2 4
f = lambda n: (72997619651120 >> (n << 2)) & 15
f = lambda n: (0x426415305230L >> (n << 2)) & 15
f = lambda n: (0b10000100110010000010101001100000101001000110000 >> (n << 2)) & 15

Process finished with exit code 0

Proof that this works:

f = lambda n: (72997619651120 >> (n << 2)) & 15

for i in range(12):
   print i, f(i)

0 0
1 3
2 2
3 5
4 0
5 3
6 5
7 1
8 4
9 6
10 2
11 4
share|improve this answer
    
How does your solver consider the cost of operands? –  Thomas W. Jul 17 at 22:12
    
@ThomasW. It doesn't, it'll always use a right shift, possibly a left shift (if the values aren't 1 bit) and an &. –  ɐɔıʇǝɥʇuʎs Jul 18 at 12:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.