64Digits

Algorithms!

Posted by ludamad on Dec. 11, 2008, 8:32 p.m.

Alright 64Digits, show me your stuff. I will describe three programming situations, and you will describe, or write, the most efficient algorithm for each situation. Most efficient answer wins. Anything goes, but no punches below the belt.

You can give me your answer in words, or give it to me in any language if you feel that is easier.

All questions have been devised by me, although they aren't that original.

Situation 1:

You are given a positive integer and must find out if it can be created by the factorial of a positive, integer number.

Details:

A factorial of a positive integer number is the number multiplied by all integers below it.

Situation 2:

You are given a million integers in the range 0 to 100. You must output them numerically sorted, least to greatest.

Details: Assume the integers are coming from some input function, and you are printing your result in some output function.

Situation 3:

You are given the 2D dimensions of a box, and then the dimensions of a smaller box. Taking into account 90 degree rotations (that is, exchanging the width and height of the smaller box), what is the largest amount of smaller boxes that can fit in the area of the bigger box?

Details:

Your algorithm should waste as little space as possible. No two smaller boxes are allowed to touch. No smaller box is allowed to go out of the bounds of the bigger box.

Do any of the situations you please, I will announce winners by situation next blog.

Comments

SteveKB 15 years, 11 months ago

@kenon the first works out with numbers 1+ but not 0 :p but I guess you don't need zero since it's neutral.

EDIT: on #3 do you mean they can't overlap? or can't be right next to each other :p

Kenon 15 years, 11 months ago

0 isn't positive :D

But 0!=1.

For formality sakes.

@Meow: Overlap.

frenchcon1 15 years, 11 months ago

al gore rhythms

Gamer3D 15 years, 11 months ago

Okay, here's the basic factorial algorithm:

Quote: Gamer3D

var result, n;

result = n;

n = // Whatever the input is.

while (n > 2) {

n -= 1;

result *= n;

}

return result;

So, basic factorial checker:

Quote: Gamer3D

var n, int, fact;

int = // Input.

n = 1;

fact = 1;

while (int mod fact = 0) {

if (fact = int)

{

return true;

exit;

}

n += 1;

fact *= n;

}

return false;

Advantages: Stops when it first becomes apparent that it can.

PY 15 years, 11 months ago

._.

Xxypher 15 years, 11 months ago

Brain input failed…

Please stand by.

mesenberg 15 years, 11 months ago

I have a headache now… I think i would need to consult a book for these…

Kenon 15 years, 11 months ago

@Gamer3D: Yours can be very swift indeed, but modulo is slower than division :|

But the main thing is it can identify as soon as it has a term that does not go in side with it. Either way, meow's is technically faster than both.

s 15 years, 11 months ago

Modulo is just as fast as division for integers. Since you're using GM though, I can't promise anything

There is the question of which kind of efficiency though. Processing or memory? 2 could be done with Radix sort, but that might be a bit of memory

@G3D Why are you exiting after return?

SixWinged 15 years, 11 months ago

Quote:

num=X//This is the number

i=2

while(num>1 && floor(num) = num)

{num/=i;

i+=1;}

return (num==1);

A modification to Kenons, although division is apparently slow and I'm not sure how fast the floor function is. I'm kinda half asleep and not sure if this will work but basically I'm assuming that if num is not a full number it would be useless to continue dividing.