12
\$\begingroup\$

This question already has an answer here:

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
\$\endgroup\$

marked as duplicate by Sriotchilism O'Zaic code-golf Jun 22 '18 at 1:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

11 Answers 11

6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I knew that my first try-and-post solution wouldn't last very long. \$\endgroup\$ – Howard Jan 13 '14 at 10:42
  • \$\begingroup\$ Runs out of memory on the last test case, otherwise seems to be working :) \$\endgroup\$ – Joachim Isaksson Jan 13 '14 at 10:56
12
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ (this is not a function, but a snippet evaluating to the answer. Invalid according to newer consensus, can somebody fix it? ...) \$\endgroup\$ – user202729 Jun 21 '18 at 8:09
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You may save a single char if you take the reverse list, i.e. i*i>=n and then the first element [0]. \$\endgroup\$ – Howard Jan 13 '14 at 8:46
  • \$\begingroup\$ Is it just me or does it blow up on the last test case? :) \$\endgroup\$ – Joachim Isaksson Jan 13 '14 at 9:35
  • \$\begingroup\$ @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... \$\endgroup\$ – Levin Fritz Jan 13 '14 at 13:25
  • \$\begingroup\$ 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 \$\endgroup\$ – user14670 Jan 14 '14 at 1:18
2
\$\begingroup\$

GolfScript, 30 characters

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

Does a test on all numbers as many other solutions.

\$\endgroup\$
  • \$\begingroup\$ @JoachimIsaksson For me it works fine, have a look here. \$\endgroup\$ – Howard Jan 13 '14 at 10:37
  • \$\begingroup\$ 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) \$\endgroup\$ – Joachim Isaksson Jan 13 '14 at 10:44
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You may replace {X}{}if with {X}* in this case. \$\endgroup\$ – Howard Jan 13 '14 at 10:12
  • \$\begingroup\$ @Howard Thanks, updated, although I see you soundly beat me with your solution :) \$\endgroup\$ – Joachim Isaksson Jan 13 '14 at 10:32
1
\$\begingroup\$

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 };
}
\$\endgroup\$
1
\$\begingroup\$

C, 54 bytes

f(x,y){for(y=sqrt(x);x%y;y--);printf("%d, %d",y,x/y);}

Just some general silliness.

Test if you like:

int main() {
    printf("Enter a number\n");
    int a;
    scanf("%d", &a);
    f(a);
    printf("\n");
    return 0;
}
\$\endgroup\$
1
\$\begingroup\$

Java 8, 73 72 bytes

Saved one byte due to @ThomasKwa!

n->{for(int i=(int)Math.sqrt(n);;i--)if(n%i<1)return new int[]{n/i,i};};

Lambda function, test with:

public class Rectangle {
    interface Test {
        int[] run(int v);
    }
    public static void main (String[] args){
        Test test = n->{for(int i=(int)Math.sqrt(n);;i--)if(n%i<1)return new int[]{n/i,i};};

        int[] testCases = {1, 4, 8, 15, 47, 5040, 40320, 25, 53};
        for (int i : testCases) {
            int[] result = test.run(i);
            System.out.println(i + ": " + result[0] + ", " + result[1]);
        }
    }
}

Finds the greatest divisor less than or equal to the square root of the area. Returns an int[].

\$\endgroup\$
  • \$\begingroup\$ @ThomasKwa I knew there was a way to do it with < or >, I just couldn't figure it out. Thanks! \$\endgroup\$ – GamrCorps Dec 13 '15 at 19:40
0
\$\begingroup\$

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 };
}
\$\endgroup\$
0
\$\begingroup\$

C, 71 bytes

Nothing fancy, find the pair of integers (a, b) closest to sqrt(n) such that a*b==n:

f;x;L(n,a,b)int*a,*b;{for(f=0,x=sqrt(n);x;--x)n%x||f++?:(*a=x,*b=n/x);}

If the function is allowed to work only on first invocation, then we can shrink it to 67 bytes:

f;x;L(n,a,b)int*a,*b;{for(x=sqrt(n);x;--x)n%x||f++?:(*a=x,*b=n/x);}

Test main:

#include <stdio.h>

int main() {
  int testdata[] = {1, 4, 8, 15, 47, 5040, 40320};
  int x,y;
  for (int i = 0; i < 7; ++i) {
     L(testdata[i], &x, &y);
     printf("%5d >  %dx%d\n", testdata[i], x, y);
  }
}

The code was originally written for another golf, which is a duplicate of this.

\$\endgroup\$
0
\$\begingroup\$

Jelly, 8 bytes

÷Ɱ½ĖḞƑƇṪ

Try it online!

Use a bunch of new quicks. (ƇⱮƑ)


Jelly, 9 bytes

ọⱮ½TṪð,÷@

Try it online!

A port of my other answer.

\$\endgroup\$

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