# Shortest expression for {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}

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

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.

• I guess array dereferencing (and the kin) isn't allowed either? Jul 16, 2014 at 21:48
• Oh, yes of course, I have edited the question. Jul 16, 2014 at 21:49
• The question would be greatly improved by some motivation. Where do those numbers come from? Jul 16, 2014 at 22:32
• table lookups Interesting phrasing I suppose... Jul 16, 2014 at 23:15
• Why not count the %7 in the score? Maybe there's another solution not using %. Is zero positive, negative, both or nothing? Jul 17, 2014 at 6:16

# 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]

• 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, 2014 at 0:54
• @xnor Absolutely! Just to to switch from octal to hexadecimal. Just as sec. Jul 17, 2014 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, 2014 at 2:23
• @xnor Another close one is const%n which could satisfy everything except n=1,2 and 3. Jul 17, 2014 at 2:43
• I was gonna do the same thing, but you beat me to it... Jul 17, 2014 at 5:41

## 2.0

(127004 >> i) ^ 60233


or (score 2.2) :

(i * 3246) ^ 130159


All found with brute force :-)

• 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! Jul 17, 2014 at 10:23
• @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!) Jul 17, 2014 at 10:50
• @m.buettner I have to agree with you. Next time, I will be more careful with description and answer selection. Jul 17, 2014 at 11:19
• For others to learn, could you elaborate on how you did the brute force calculation? Jul 17, 2014 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. Jul 18, 2014 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.

## 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.

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

• How does your solver consider the cost of operands? Jul 17, 2014 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 &. Jul 18, 2014 at 12:40