# 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? – John Dvorak Jul 16 '14 at 21:48
• Oh, yes of course, I have edited the question. – Somnium Jul 16 '14 at 21:49
• The question would be greatly improved by some motivation. Where do those numbers come from? – Peter Taylor Jul 16 '14 at 22:32
• table lookups Interesting phrasing I suppose... – ɐɔıʇǝɥʇuʎs Jul 16 '14 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? – Thomas Weller Jul 17 '14 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 '14 at 0:54
• @xnor Absolutely! Just to to switch from octal to hexadecimal. Just as sec. – isaacg Jul 17 '14 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 '14 at 2:23
• @xnor Another close one is const%n which could satisfy everything except n=1,2 and 3. – isaacg Jul 17 '14 at 2:43
• I was gonna do the same thing, but you beat me to it... – ɐɔıʇǝɥʇuʎs Jul 17 '14 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! – Somnium Jul 17 '14 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!) – Martin Ender Jul 17 '14 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 '14 at 11:19
• For others to learn, could you elaborate on how you did the brute force calculation? – Thomas Weller Jul 17 '14 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. – Arnaud Jul 18 '14 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? – Somnium Jul 17 '14 at 6:45
• How about (0426415305230 >> (i*3)) & 7? You can see the output digits in reverse order. – CJ Dennis Jul 18 '14 at 14:51
• @CJDennis: I think there are no octal numbers in C#. – Thomas Weller Jul 18 '14 at 15:20
• I thought it was just C? I can't see any other reference to C#. – CJ Dennis Jul 19 '14 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? – Thomas Weller Jul 17 '14 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 '14 at 12:40