Forum

Post 28.04.2009   # 1
Subject CodeFu 2009 Round 1 - Shortest 500 Solution
Shortest solution is the one that is correct for all input test cases, but has the smallest number of non blank characters.

For e.g.
public class PowerOfThree {
public int nthElement(int N) {
int power = 1;
int sum = 0;
for (int i = 0; i < 31; ++i) {
if ((N & (1<<i)) == (1<<i)) {
sum += power;
}
power *= 3;
}
return sum;
}
}

has 148 non blank characters.

The winner is the one who has the smallest number of characters and the solution passes on ALL test cases.
In case of two solutions with the same number of characters, the winner is the one who has submitted earlier.

Post your solutions of the problem 500 here.
Be sure to test the solution in the Practice room first.

The contest is active until May 10th 12:00 (noon), and the winner will receive the new CodeFu T-Shirt.
anikov is offline Reply
Post 28.04.2009   # 2
Well, if no one else is going to post something obvious(ly not the winning solution)...

public class PowersOfThree {
int s, i, p = 1;
public int nthElement(int N) {
for (; i < 31; ++i, p *= 3)
if ((N & 1<<i) == 1<<i)
s += p;
return s;
}
}

Goldsmith is offline Reply
Post 28.04.2009   # 3
previouse one is 114 i think...

public class PowersOfThree {
int s, i, p = 1;
public int nthElement(int N) {
for (; i < 31; ++i, p *= 3)
if ((N & 1<<i)!=0)
s += p;
return s;
}
}


111
vasja is offline Reply
Post 28.04.2009   # 4
vasja's solution is 111

Just as info, the lengths of solutions; from the 4 competitors who solved 500 correctly are:
[list]igorkulev 627[/list]
[list]hsilomedus 311[/list]
[list]palikrushev 778[/list]
[list]martinancevski 180[/list]

Of course, they coded the solutions to work correctly and not for the smallest length, but still, they are quite small.

Awaiting for other submissions to the shortest 500 solution.
There are for sure more things that can be done to make it smaller.
Who can do it in less than 100 characters?
anikov is offline Reply
Post 28.04.2009   # 5
109
public class PowersOfThree {
int s, i, p = 1;
public int nthElement(int N) {
for(;i<31;p*=3)
if ((N & 1<<i++)!=0)
s += p;
return s;
}
}
vasja is offline Reply
Post 29.04.2009   # 6
108 hmm less than 100 ... gonna need a new idea
public class PowersOfThree {
int s, i, p = 1;
public int nthElement(int N) {
for(;i<31;p*=3)
if ((N & 1<<i++) > 0)
s += p;
return s;
}
}
vasja is offline Reply
Post 29.04.2009   # 7
105
public class PowersOfThree {
public int nthElement(int N) {
int L=1,p=0;
for(;N>0;L*=3,N/=2)
if(N%2>0)
p+=L;
return p;
}
}
vasja is offline Reply
Post 29.04.2009   # 8
public class PowersOfThree {
int p=1, s;
public int nthElement(int N) {
for(;N>0;p*=3,N/=2) s+=N%2*p;
return s;
}
}


98
hsilomedus is offline Reply
Post 29.04.2009   # 9
And for the record, what is your top score?

Just for motivation++
hsilomedus is offline Reply
Post 29.04.2009   # 10
hsilomedus wrote:
And for the record, what is your top score?

Just for motivation++


For the moment, it is 87.
I am still working on some ideas.
anikov is offline Reply
Post 29.04.2009   # 11
public class PowersOfThree {
public int nthElement(int N) {
return N>0?N%2 + 3*nthElement(N/2):0;
}
}

87

Recursion rules!
hsilomedus is offline Reply
Post 29.04.2009   # 12
Man i tried the ?: operator in java previously and got error so i thought its only for c++
vasja is offline Reply
Post 29.04.2009   # 13
hsilomedus wrote:
public class PowersOfThree {
public int nthElement(int N) {
return N>0?N%2 + 3*nthElement(N/2):0;
}
}

87

Recursion rules!


Cool, very nice.
Now the real challenge begins
Let us see if someone can do it in 86 characters.
Anything is allowed, as long as the solution passes the test cases.
anikov is offline Reply
Post 30.04.2009   # 14
anikov wrote:
Shortest solution is the one that is correct for all input test cases....


Will there be any test cases with N < 0 ?
azder is offline Reply
Post 30.04.2009   # 15
azder wrote:
Will there be any test cases with N < 0 ?


No.
Constraints for N, as defined in the problem statement, are:
N will be between 1 and 1000000 (one million) inclusive.

bilievsk is offline Reply

Please login to post reply.