Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Just a simple code golf function for fun, intentionally left open with few rules to see what creativity comes up.

Input: An integer representing the area of a rectangle.

Output: Two integers representing the side lengths of the rectangle that have the least perimeter for the area. (In any order.)

Test cases:

25 => 5, 5
53 => 53, 1
4294967295 => 65537, 65535
share|improve this question

7 Answers 7

up vote 4 down vote accepted

GolfScript (21 chars)

:^,{)^\%!},.,2/=)^1$/

This takes the input as a number on the stack and leaves the result as two numbers on the stack.

For fair comparison with Howard's solution, taking input on stdin and giving output on stdout separated by newline is 23 chars:

~:^,{)^\%!},.,2/=)n^2$/

It works because this problem is trivial: it's just looking for the pair of factors closest to sqrt(area).

Online demo for a square; online demo for a non-square.

share|improve this answer
    
I knew that my first try-and-post solution wouldn't last very long. –  Howard Jan 13 at 10:42
    
Runs out of memory on the last test case, otherwise seems to be working :) –  Joachim Isaksson Jan 13 at 10:56

Mathematica 34 26

Besides the explicit search there is a nice convergent series:

enter image description here

n = 27

{i=√n//.i_:>n/⌈n/⌊i⌋⌉,n/i}

{3, 9}

Three previous approaches with 34 characters:

{#,n/#}&@FixedPoint[n/⌈n/⌊#⌋⌉&,√n]

For[i=√n,i>(i=n/⌈n/⌊i⌋⌉),];{i,n/i}

f@i_:=f[f@i=n/⌈n/⌊i⌋⌉]
{i=f@√n,n/i}

ClearAll[f]

Visualization:

p = FixedPointList[n/⌈n/⌊#⌋⌉ &, Sqrt[n]];

Plot[n/x, {x, 0, 11}, GridLines -> {Range@n, Range@n}, 
 AspectRatio -> Automatic, PlotRange -> {{0, 10.2}, {0, 7.2}}, 
 Epilog -> {Red, Thickness[0.005], 
   Arrow[Transpose[{{n/p, ⌈p⌉}, {n/p, ⌊p⌋}, {⌈n/⌊p⌋⌉, ⌊p⌋}}, {2, 3, 1}]], 
  PointSize[0.02], Black, Point[{n/p[[-1]], p[[-1]]}]}]

enter image description here

share|improve this answer

Python 2 (63 62)

n=input()
print[(i,n/i)for i in range(1,n)if i*i>=n/i*i==n][0]

This produces all pairs of integers (i, n/i) that could be the sides of the rectangle, starting from the first one greater or equal to the square root of n. It prints the first one.

share|improve this answer
    
You may save a single char if you take the reverse list, i.e. i*i>=n and then the first element [0]. –  Howard Jan 13 at 8:46
    
Is it just me or does it blow up on the last test case? :) –  Joachim Isaksson Jan 13 at 9:35
    
@Howard thanks, updated. –  Levin Fritz Jan 13 at 13:23
    
@JoachimIsaksson Yes, because it goes through all the numbers from 1 to n, it scales very poorly. I actually had a much more elegant solution first that used a generator instead of a list comprehension, so it didn't generate unused elements, but it needed a few extra characters... –  Levin Fritz Jan 13 at 13:25
    
Follow-up on Levin's answer. It fails on areas that are prime. I.e. > python peri.py 401 Traceback (most recent call last): File "peri.py", line 2, in ? print[(i,n/i)for i in range(1,n)if ii>=n/ii==n][0] IndexError: list index out of range Fix it by using n+1 inside the range. n=input() print[(i,n/i)for i in range(1,n+1)if ii>=n/ii==n][0] > python peri.py 401 (401, 1) Cheers, Gert –  user14670 Jan 14 at 1:18

GolfScript, 30 characters

~:t,{[.t\/].~*t=1$~>!&\@if}*n*

Does a test on all numbers as many other solutions.

share|improve this answer
    
@JoachimIsaksson For me it works fine, have a look here. –  Howard Jan 13 at 10:37
    
Hm, I think my ruby install was severely broken, 32 bit ruby gets it right (but fails with out of memory on the last test case) –  Joachim Isaksson Jan 13 at 10:44

Golfscript (46 43 40)

~1{..*2$>!}{1$1$%!{.@@}*)}while;1$/p p];

No way to beat the math oriented languages at this challenge I suspect :)

Somewhat "long winded", it would be shorter to work with arrays, sadly they get a bit large with the last test case.

Basically what it does is similar to the Python solution, it loops from 1..sqrt(n), testing for an even multiplier, then just displaying the last value found.

share|improve this answer
1  
You may replace {X}{}if with {X}* in this case. –  Howard Jan 13 at 10:12
    
@Howard Thanks, updated, although I see you soundly beat me with your solution :) –  Joachim Isaksson Jan 13 at 10:32

C# (178)

int[] R(int n){var a=Enumerable.Range(1,n);var b=a.SelectMany(x=>a.SelectMany(y=>a.Select(_=>new{x,y}))).Where(f=>f.x*f.y== n).OrderBy(f=>f.x+f.y).First();return new[]{b.x,b.y};}

Pretty

int[] R(int n)
{
    var a = Enumerable.Range(1, n);
    var b = a.SelectMany(x => a.SelectMany(y => a.Select(_ => new { x, y }))).Where(f => f.x * f.y == n).OrderBy(f => f.x + f.y).First();
    return new[] { b.x, b.y };
}
share|improve this answer

C# 4.0: 79 characters

long[] P(long a){long r=0,s=0;while(++s<a/s)if(a%s==0)r=s;return new[]{r,a/r};}

If it weren't for the last test case, I could save 3 characters naming long to int.

In pretty format:

long[] Perimeter(long area)
{
    long result = 0;
    long side = 0;
    while (++side < area / side)
    {
        if (area % side == 0)
            result = side;
    }
    return new long[] { result, area / result };
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.