# 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? – Jan Dvorak Jul 16 '14 at 21:48
Oh, yes of course, I have edited the question. – Somnium Jul 16 '14 at 21:49
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 Ender Jul 16 '14 at 22:10
The question would be greatly improved by some motivation. Where do those numbers come from? – Peter Taylor Jul 16 '14 at 22:32
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. – Super Chafouin 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