# How should you arrange your chairs?

You teach a class of students with interesting preferences for how their chairs are arranged. There are 3 very specific requirements they have for how the chairs are arranged:

1. They most be arranged in a rectangle, even if it means some chairs go empty.

2. There must be as few empty chairs as possible.

3. They must be as "squarey" as possible. Squarey-ness is determined by the distance between the width and the height of the rectangle, lower is better. For example, a rectangle that is 4x7 has a squarey-ness of 3.

To be more specific, the "score" of an arrangement is the distance between the width and height plus the number of chairs that would go empty.

Let's take an example. Let's say you have 13 students. You could arrange the chairs any of these ways:

1x13
2x7
3x5
4x4


1x13 is not very squarey. In fact, 1 and 13 are 12 apart, so we give this arrangement 12 points. It also has 0 empty chairs, so we add 0 points, giving this arrangement a score of 12. Not that great.

2x7 is certainly better. 2 and 7 are only 5 apart, so we give this arrangement 5 points. However, if you actually arranged 2 rows of seven chairs, that would take 14 chairs, meaning one chair would be empty. So we add one point, giving this arrangement a score of 6.

We could also do 3x5. 3 and 5 are 2 apart, so +2 points. It takes 15 chairs, meaning we'd have two extra chairs, so another +2 points, for a score of 4.

Last option, 4x4. 4 and 4 are 0 apart, so we give this +0 points. 4x4 takes 16 chairs, so 3 chairs go empty, for a total score of 3. This is the optimal solution.

In case of a tie, the optimal solution is the one with less empty chairs.

# The challenge

You must write a program or function that takes an integer and outputs the optimal arrangement of chairs for that number of students. IO can be in any reasonable format. Here is sample output for any number of students from 1 to 100:

1:  (1, 1)
2:  (1, 2)
3:  (2, 2)
4:  (2, 2)
5:  (2, 3)
6:  (2, 3)
7:  (3, 3)
8:  (3, 3)
9:  (3, 3)
10: (2, 5)
11: (3, 4)
12: (3, 4)
13: (4, 4)
14: (4, 4)
15: (4, 4)
16: (4, 4)
17: (3, 6)
18: (3, 6)
19: (4, 5)
20: (4, 5)
21: (3, 7)
22: (5, 5)
23: (5, 5)
24: (5, 5)
25: (5, 5)
26: (4, 7)
27: (4, 7)
28: (4, 7)
29: (5, 6)
30: (5, 6)
31: (4, 8)
32: (4, 8)
33: (6, 6)
34: (6, 6)
35: (6, 6)
36: (6, 6)
37: (5, 8)
38: (5, 8)
39: (5, 8)
40: (5, 8)
41: (6, 7)
42: (6, 7)
43: (5, 9)
44: (5, 9)
45: (5, 9)
46: (7, 7)
47: (7, 7)
48: (7, 7)
49: (7, 7)
50: (5, 10)
51: (6, 9)
52: (6, 9)
53: (6, 9)
54: (6, 9)
55: (7, 8)
56: (7, 8)
57: (6, 10)
58: (6, 10)
59: (6, 10)
60: (6, 10)
61: (8, 8)
62: (8, 8)
63: (8, 8)
64: (8, 8)
65: (6, 11)
66: (6, 11)
67: (7, 10)
68: (7, 10)
69: (7, 10)
70: (7, 10)
71: (8, 9)
72: (8, 9)
73: (7, 11)
74: (7, 11)
75: (7, 11)
76: (7, 11)
77: (7, 11)
78: (9, 9)
79: (9, 9)
80: (9, 9)
81: (9, 9)
82: (7, 12)
83: (7, 12)
84: (7, 12)
85: (8, 11)
86: (8, 11)
87: (8, 11)
88: (8, 11)
89: (9, 10)
90: (9, 10)
91: (7, 13)
92: (8, 12)
93: (8, 12)
94: (8, 12)
95: (8, 12)
96: (8, 12)
97: (10, 10)
98: (10, 10)
99: (10, 10)
100: (10, 10)


As usual, this is code-golf, so standard loopholes apply, and the winner is the shortest answer in bytes.

• Related. May 18, 2016 at 11:43

# Jelly, 1615 14 bytes

÷RĊ,Rµạ/+PỤḢịZ


### How it works

÷RĊ,Rµạ/+PỤḢịZ  Main link. Argument: n

R              Range; yield [1, ..., n].
÷               Divide n by each k in [1, ..., n].
Ċ             Ceil; round the quotients up to the nearest integer.
R           Range; yield [1, ..., n].
,            Pair; yield A := [[ ⌈n ÷ 1⌉, ..., ⌈n ÷ n⌉ ], [ 1, ..., n ]].
µ          Begin a new, monadic chain. Argument: A
ạ/        Reduce A by absolute difference.
This yields [ |⌈n ÷ 1⌉ - 1|, ..., |⌈n ÷ n⌉ - n| ].
P      Product; reduce A by multiplication.
This yields [ ⌈n ÷ 1⌉ × 1, ..., ⌈n ÷ n⌉ × n].
+        Add the results to left and right, element by element. This yields
[ |⌈n ÷ 1⌉ - 1| + ⌈n ÷ 1⌉ × 1, ..., |⌈n ÷ n⌉ - n| + ⌈n ÷ n⌉ × n ].
Ụ     Grade up; sort the indices of the list of sums by their values.
Ḣ    Head; extract the first value, which corresponds to the smallest
sum. Grading up is stable, so this selects the first index of all
with the smallest sum in case of a tie. In this event, the first
index will have the highest absolute difference of all indices
with the smallest sum, meaning that it has the lowest product and,
therefore, the lowest number of empty chairs.
Z  Zip; transpose A's rows and columns.
This yields [[ ⌈n ÷ 1⌉, 1 ], ..., [ ⌈n ÷ n⌉, n ]].
ị   Retrieve the pair at that index.


# Python 2, 68 bytes

lambda n:min((abs(~i-n/~i)+n/~i*~i,i+1,0-n/~i)for i in range(n))[1:]


Equivalent to the more “obvious”:

lambda n:min([(i+1,0-n/~i)for i in range(n)],key=lambda(p,q):abs(p-q)+p*q)

• You can save three bytes by iterating over range(-n,0), like I do in my answer. Test suite. May 19, 2016 at 15:22

f x=snd$minimum[((a*b+a-b,a*b),(b,a))|a<-[1..x],b<-[1..a],a*b>=x]  Usage example: map f [1..5] -> [(1,1),(1,2),(2,2),(2,2),(2,3)]. Goes through an outer loop a from 1 to x (x -> number of students) and an inner loop b from 1 to a. Keeps all (b,a) where a*b>=x and builds pairs of ((arrangement points,seats left), (b,a)) which follow the lexicographical order we need to find the minimum. Note: a is always greater than b, so we don't need abs for squareyness. No need to subtract x from the "seats left" score, because only the relative order matters. Finally we remove the score pair with snd. • Why not just (ab+a-b, (b, a))? If you minimise the score, surely you minimise ab anyway, or am I missing something? May 19, 2016 at 22:13 • @jpcooper: a*b (number of free seats) is the tie breaker if the main score is equal. E.g. n=43: a) a=7, b=7, score: (49,49) b) a=9, b=5, score: (49,45). Main score is equal, tie breaker decides, b) wins. – nimi May 19, 2016 at 22:42 • You're right. I should have read the description better. May 19, 2016 at 22:45 • @jpcooper: wait a minute ... if I remove the tie breaker a*b, the numbers itself (b,a) which I have to carry around anyway act as the tie breaker and give the same results for (at least) n=1..300. A product is small if one of the factors (here b) is small. But as long as I have no formal proof, I don't want to use this fact. Let's see if I find one. – nimi May 19, 2016 at 22:57 • Good point. It seems right, and shouldn't be too hard to come up with a proof. I'm beginning to wonder though whether there might be a linear solution to this problem. May 19, 2016 at 23:03 ## Javascript, 98 bytes My first code golf, so I post anyway! f=n=>{for(o=1/0,i=1;i<=n;i++)for(j=n;i*j>=n;j--)t=i*j-n+Math.abs(i-j),o>t&&(o=t,a=[i,j]);return a}  Initially my o was an empty object and I checked if o.a was empty, so it was a special case at the first round. But I found the 1/0 trick in edc65's answer to initialize the variable to Infinity. • And I'll try the trick to use an object to store the temporary result May 19, 2016 at 21:01 # Ruby, 64 bytes ->n{(1..n).map{|w|h=(n+w-1)/w;[(h-w).abs+h*w,w*h,w,h]}.min[2,3]}  A lambada that takes the number of people as an argument and returns an array with width and height of the optimal solution. • Why do you need w*h as the second element in your array? I don't think it particularly changes anything when you call min because you minimize on the score aka the first element. May 18, 2016 at 21:01 • @KevinLau-notKenny from the question: In case of a tie, the optimal solution is the one with less empty chairs May 18, 2016 at 21:03 # MATL, 18 bytes :Gy/Xkvtd|yp+&X<Z)  Try it online! ### Explanation : % Implicit input number N. Range [1 2 ... N] G % Push N again y % Duplicate second-from-top: push [1 2 ... N] again /Xk % Divide and round up v % Vertically concatenate. Gives 2×N array of rectangle sizes td| % Duplicate. Absolute difference of each column y % Duplicate second-from-top: push 2×N array again p % Product of each column + % Sum absolute differences and products &X< % Arg min Z) % Use as column index into the 2×N array. Implicitly display  # Pyth, 2422 21 bytes Edit: in the sorting key, I realize that there is no need to find the number of empty chairs. It is equivalent to score the total number of chairs. This saved me 2 bytes. h.m_+B*FbaFbm,d.EcQdS  Try it online! # Matlab(174)(146)121  function g(n),f=@(n,i)ceil(n/i);x=[];for i=1:n,x=[sortrows(x); f(n,i)*i-1/(f(n,i)*i)+abs(f(n,i)-i) i f(n,i)];end,x(1,2:3)  • trick 1: i added the amount 1-1/length*width as tie-scoring • trick 2: i calculated number_students/length ceiled for the width of rectangle, upper bound is the square but ceiled too • I'm sure it can be golfed further ... try it Edit : referenced to @StewieGriffin 's remarks . Edit 2 : • 1 and n are constants no need to add 'em to the overall score. • A function is few bytes less than stdin standalone program. • I used ascendent sorting technique it saves too much bytes though. Edit 3: peformance test. • @StewieGriffin that is not big issue, it can be solved using unique May 18, 2016 at 10:01 • i think im halfway to some nice mathematical translation for this problem, but still it remains as conjecture May 18, 2016 at 17:56 • Also thought about this. See julia example. May 18, 2016 at 18:24 # Python 2, 64 bytes lambda n:max((~-i*~min(i,n/i),0-n/i,-i)for i in range(-n,0))[1:]  This is an amalgamation of @Lynn's Python answer (from where I took the max(...)[1:] trick) and the algorithm from my Julia answer (which allows a slightly shorter implementation). Test it on Ideone. # Julia, 61595553 52 bytes / =cld n->[m=indmax([~i*~-max(i,n/i)for i=1:n]),n/m]  Try it online! ### How it works The code is equivalent to the following, ungolfed version, where cld is ceiling division. function chairs(n) m = indmin([(i + 1) * (max(i, cld(n, i)) - 1) for i in 1:n]) return [m, cld(n, m)] end  To find the optimal arrangement, it is clearly sufficient to examine the pairs [i, j], where 1 ≤ i ≤ n and j = ⌈n / i⌉. The score for such an arrangement is |j - i| + (ij - n), where the second summand is the number of empty chairs. Instead of the actual scores, we can compare scores augmented by a constant, such as ij + |j - i| + 1. It is sufficient to consider pairs [i, j] where i ≤ j since the arrangements [i, j] and [j, i] are equally valid. We deal with strictly descending pairs by setting j = max(⌈n / i⌉, i) instead, which makes sure that j ≥ i and will yield a suboptimal score if ⌈n / i⌉ < i. Since j - i ≥ 0, we have ij + |j - i| + 1 = ij + j - i + 1 = (i + 1) × (j - 1), which can be computed in fewer bytes of code. Finally indmin / indmax gives the index m (and thus the value of i) of the optimal arrangement, which is m by ⌈n / m⌉. Ties are broken by first occurrence, which corresponds to the lowest value of i, therefore the highest value of j - i and thus the lowest value of ij - n (empty chairs). # JavaScript (ES6) 74 78 Edit keeping the temp result as an array instead of 2 vars, borrowed from Thiht's answer n=>(z=>{for(x=0;y=-~(~-n/++x),x<=y;)(s=y-x+x*y-n)>=z||(z=s,r=[x,y])})()||r  Less golfed n=>{ z = 1/0 for (x=0; y=(n-1)/++x+1|0, x <= y; ) { s = y-x+x*y-n; if (s<z) z=s, r=[x,y] } return r }  Test f=n=>(z=>{for(x=0;y=-~(~-n/++x),x<=y;)(s=y-x+x*y-n)>=z||(z=s,r=[x,y])})()||r out=x=>O.textContent+=x+'\n' for(i=1;i<=100;i++)out(i+' :( '+f(i)+' )') <pre id=O></pre> ## PHP, 129 bytes function f($i){$s=INF;for($x=1;$x<$i;$x++){if($s>$t=(abs($x-$e=ceil($i/$x))-$i+($e*$x))){$s=$t;$d[0]=$x;$d[1]=$e;}}var_dump($d);}  Ungolfed: function f ($i){
$s=INF; for($x=1; $x<$i; $x++){ // for every number less than the input if($s > $t=( abs($x-$e=ceil($i/$x))-$i+($e*$x) ) ){
// determine the other dimension, the score, and compare to the minimum score
$s=$t;
$d[0]=$x;
$d[1]=$e;
}
}
var_dump($d); }  # PHP, 104 bytes The algorithm that solves this problem is simple and it is probably used by other answers in languages similar to PHP (JavaScript, f.e.): • start with a large value for the initial score; n is large enough (where n is the input value); the score of the arrangement computed on the first iteration (1, n) is (n-1)+0; • iterate for all values of width between 1 and n; compute the minimum height as ceil(n/width), compute the arrangement score using the formula provided in the question (i.e. abs(width - height) + (width * height - n)); if the score is better than the previous best score then remember the width, the height and the new best score; on ties use the value of width * height - n for current arrangement and previous best arrangement to detect the new best arrangement; • that's all. After golfing, this algorithm produces something like this (wrapped here for readability): for($s=$h=$j=$n=$argv[$w=$i=1];$i<=$j;$j=ceil($n/++$i) {$c=$j-$i+$i*$j-$n;if($c<$s||$c==$s&&$i*$j<$w*$h){$w=$i;$h=$j;$s=$c;}} echo"$w,$h";  It uses 137 bytes (when put on a single line) and it is far from the 104 bytes advertised in the title. The code can probably be shortened by another 2-3 bytes but the big source of improvement is somewhere else: in the details of the algorithm. ## The revised algorithm: There are several places where the algorithm can be improved by removing useless code. • there is no need to iterate the width from 1 to $n; for speed, the width ($i) must iterate between 1 and floor(sqrt($n)) but this makes the code even longer instead of shortening it; but if the width doesn't exceed sqrt($n), the minimum height ($j) will always be larger than sqrt($n) (their product must be at least $n);
• the previous statement allows using $i <=$j (width <= height) as the termination condition for loop; this way, the width will iterate from 1 to floor(sqrt($n)) and the height will get values starting with $n and going down to ceil(sqrt($n)) (not necessarily all of them); • knowing that width is always smaller than or equal to the height allow us know that abs(width - height) is always height - width ($j-$i); 5 bytes saved this way; • the input value $n is used in the computation of score (the number of unoccupied seats is width * height - n) but it is not needed; the score does not need to be displayed, it is computed only for comparison of the arrangements; by removing - n from the score formula we save another 3 bytes (the PHP code is -$n) without losing anything; • given the last two statements, the score formula becomes height - width + width * height ($j-$i+$i*$j); • on ties (the score of the current arrangement is the same as the previous best score), the rules say to use the arrangement with less free seats; because width always increases and height always decreases, the height - width part of the score decreases on each step; • if the current score is equal with the previous best score, the previous statements tells us that the number of free seats of the current arrangement is larger than the one of the previous best arrangement; this means the previous best arrangement win the tie; • because the ties are always won by the previous best arrangement, a new arrangement becomes the new best arrangement only when its score is smaller than the previous best; the code that checks for ties is useless and can be removed (||$c==$s&&$i*$j<$w*$h -- a lot of bytes); • because of the removal of -$n from the score's formula, the score for the first arrangement (1x$n) is $n-1+1*$n (i.e. 2*$n-1); the initial value of the best score ($s) can be any value greater than or equal to 2*$n; the first iteration has a better score and it becomes the best arrangement letting the algorithm run without initialization problems.

The new code (104 bytes), after applying the improvements described above is:

for($s=2*$j=$n=$argv[$i=1];$i<=$j;$j=ceil($n/++$i))
if($s>$c=$j-$i+$i*$j){$w=$i;$h=$j;$s=$c;}echo"$w,$h";


It is wrapped here for readability. Prepend the code above with the PHP marker <?php (technically, it is not part of the code), put it into a file (let's say arrange-your-chairs.php) and run it with an integer greater than zero as argument. It will display the width and height of the computed arrangement, separated by comma:

$php arrange-your-chairs.php 1001 28,36  ### Another solution (116 bytes) Another solution that uses a different algorithm: for($n=$argv[1];++$j<=$n;)for($i=0;++$i<=$j;)
if($n<=$k=$i*$j)$a["$i,$j"]=($j-$i+$k-$n)*$n+$k;asort($a);echo key($a);  It puts all the combinations of at least $n seats into an associative list; the key is the text representation of the arrangement, the value is the arrangement's score. It then sorts the list (ascending by value) and gets the key of the first entry.

### One more (115 bytes)

foreach(range(1,$m=$n=$argv[1])as$i)
if(($d=ceil($n/$i))<=$i&&$m>=$s=$i*$d-$n+$i-$d){$m=$s;$w=$d;$h=$i;}echo"$w,$h";  This is the PHP version of @Neil's answer (JavaScript/ES6, 85 bytes). There are some noticeable differences due to the features of each language: • the JS answer generates an array of n (undefined) values then uses its keys to iterate from 0 to n-1; it increments i (d=(n+i++)/i|0) to make it iterate from 1 to n; the PHP solution doesn't need to increment; it uses range() to generate an array then it uses the generated values (1 to n) to iterate; • the JS answer uses (n+i)/i then converts the value to integer using |0 to get the smallest integer larger than n/i; the PHP answer solves this issue easily with the PHP function ceil(); JavaScript also provides Math.ceil() but it uses 5 bytes more than the solution found by Neil; • PHP provides the function array_map() that is somehow similar with JS Array.map() but it doesn't help here; its syntax is verbose, a foreach produces shorter code; it is larger than the JS code, though; • merging the assignments into the conditions using || is not possible in PHP because it lacks the comma operator; I translated a||b||c into if(!a&&!b)c then, because a and b are comparisons, I negated their operators (replaced < with >=); this also produces larger code than the JS version; • another 23 bytes have to be added just because the names of variables in PHP have to be prefixed by $.

The ungolfed versions of all solutions and the test suite can be found on Github.

• This is the most thorough code-golf answer I have ever seen. May 20, 2016 at 19:33

## JavaSCript (ES6), 83 bytes

n=>[...Array(m=n)].map((_,i)=>(d=(n+i++)/i|0)>i||(s=i*d-n+i-d)>m||(m=s,r=[d,i]))&&r

• Maybe you could apply my trick (to save 2 bytes) May 18, 2016 at 9:48
• @KennyLau I don't think it helps; I'd have to increase m to compensate.
– Neil
May 18, 2016 at 11:07

## Julia, 87

I think this is one step in direction towards finding a magic function for the problem:

f(i)=(i+n)÷(i+1)|>j->(j*i<n)+j
_=indmin([sqrt(n)<=i?i-f(i)*(1-i):2n for i=1:n])
_,f(_)


It only looks at pairs (i, j=(i+n)/(i+1)) or (i, j+1)

• please explain further how does this work, you v turned me curious bout your function May 18, 2016 at 19:43
• I'm not sure how this is supposed to work. You don't define n anywhere, and you don't seem to be taking input. May 18, 2016 at 20:44
• Ah, sorry, I just took n as input. One would need to wrap it into n->.... Nice that you could make it work. Aug 30, 2018 at 19:37

# Oracle SQL 11.2, 173 bytes

SELECT MIN(x||','||y)KEEP(DENSE_RANK FIRST ORDER BY y-x+(y*x-:1))FROM(SELECT CEIL(LEVEL/:1)x,CEIL(MOD(LEVEL+.1,:1))y FROM DUAL CONNECT BY LEVEL<=:1*:1)WHERE x<=y AND:1<=x*y;


Un-golfed

SELECT MIN(x||','||y)KEEP(DENSE_RANK FIRST ORDER BY y-x+(y*x-:1))  -- Keeps the minimal score
FROM   (SELECT CEIL(LEVEL/:1)x,CEIL(MOD(LEVEL+.1,:1))y FROM DUAL CONNECT BY LEVEL<=:1*:1) -- Generate x,y combinations
WHERE  x<=y AND :1<=x*y  -- Filters out wrong combinations


## Q 58 Bytes

{c@d?&/d:+/(-/;*/)@\:+c:{((b<a)?1b)#+(b:-_-x%a;a:1+!x)}x}


Lamba that calculates minimal cost for a given value (x) and returns a sequence of two values (width,height)

Adding name to that lambda requires other two char (ex f:{..} instead of {..})

Test

{..}'1+!100


where {..} is the lambda. Read as "applies lambda to each value of 1+first 100 ints" (in other words to each value 1..100)

Generates

1 1
2 1
2 2
2 2
3 2
3 2
3 3
3 3
3 3
5 2
4 3
4 3
4 4
4 4
4 4
4 4
6 3
6 3
5 4
5 4
7 3
5 5
..


Explanation

Nested lamdba {((b<a)?1b)#+(b:-_-x%a;a:1+!x)} generates all candidates (widht,height) pairs for x chairs as two sequences (w1 w2 w3 ..; h1 h2 h3 ..) (widths and heights). Read from left to right, but evaluates from right to left

a:1+!x generates values 1..x and assign that sequence to a

-_- is negate floor negate, and implements ceil (ceil is not a primitive of the language)

b:-_-x%a applies ceil to each value of x divided by any item im a, and assign the resulting sequence to b. In other words, b is ceil each x dividedBy each 1..x

+(b;a) return a secuence composed of seq a and seq b, an then flips it (the result is a sequence of pair where i-pair contains element i of a and element i of b)

b<a compares item by item of b and a, and generates a secuence of logical values (true=1b for each index where b[i]

s?x returns the first position of item x in sequence s. With (b<a)?1b We look for 1b (true value) in sequence resulting of compare b and a, and get first position where b

n#s takes n first n items from seq s. We want to discard duplicate pairs, so we stop when first item of a pair < second item (ex. consider 13,1 but not 1,13).

As a side effect, each pair of the resulting sequence are of decreasing distance between a and b (ex (13 1; 7 2; 5 3; 4 4)

The candidate pair generated by nested lambda are assigned to c. We then flip c (obtains b,a again) and applies two functions to that argument: */ multiplies over, and -/ subtract over. The result of (-/;*/)@\:+c is the difference and product of each pair. +/ is sum over, and calculares final cost. The cost of each patir is assigned to d

&/ is minimum over, so &/d is the minimum cost. With d?&/d we find the first occurrence of minimum cost in d, and with c@.. we retrieve the pair at that position. As each pair is of decreasing distante between a and n, the first minimum found has the maximum distante betwwen other minimum pairs, so we apply tie rule correctly