¿Cómo debes organizar tus sillas?

20

Enseñas a una clase de estudiantes con preferencias interesantes sobre cómo están dispuestas sus sillas. Hay 3 requisitos muy específicos que tienen para la disposición de las sillas:

  1. La mayoría de ellos están dispuestos en un rectángulo, incluso si eso significa que algunas sillas se vacían.

  2. Debe haber tan pocas sillas vacías como sea posible.

  3. Deben ser tan "cuadrados" como sea posible. La cuadratura está determinada por la distancia entre el ancho y la altura del rectángulo, más bajo es mejor. Por ejemplo, un rectángulo que 4x7tiene un cuadrado de 3.

Para ser más específicos, el "puntaje" de un arreglo es la distancia entre el ancho y la altura más el número de sillas que quedarían vacías.

Pongamos un ejemplo. Digamos que tienes 13 estudiantes. Puede organizar las sillas de cualquiera de estas formas:

1x13
2x7
3x5
4x4

1x13No es muy cuadrado. De hecho, 1 y 13 están separados por 12, por lo que le damos a este arreglo 12 puntos. También tiene 0 sillas vacías, por lo que agregamos 0 puntos, dando a este arreglo una puntuación de 12. No es tan bueno.

2x7Ciertamente es mejor. 2 y 7 son solo 5, por lo que le damos a este arreglo 5 puntos. Sin embargo, si realmente dispusiera 2 filas de siete sillas, se necesitarían 14 sillas, lo que significa que una silla estaría vacía. Entonces agregamos un punto, dando a este arreglo una puntuación de 6.

También podríamos hacer 3x5. 3 y 5 son 2 separados, entonces +2 puntos. Se necesitan 15 sillas, lo que significa que tendríamos dos sillas adicionales, por lo que otros +2 puntos, para una puntuación de 4.

Última opción, 4x4. 4 y 4 están separados por 0, por lo que le damos +0 puntos. 4x4 tiene 16 sillas, por lo que 3 sillas quedan vacías, para un puntaje total de 3. Esta es la solución óptima.

En caso de empate, la solución óptima es la que tiene menos sillas vacías.

El reto

Debe escribir un programa o función que tome un número entero y genere la disposición óptima de las sillas para ese número de estudiantes. IO puede estar en cualquier formato razonable. Aquí hay una muestra de salida para cualquier número de estudiantes de 1 a 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)

Como de costumbre, este es el código de golf, por lo que se aplican las lagunas estándar, y el ganador es la respuesta más corta en bytes.

DJMcMayhem
fuente
Relacionado.
Martin Ender

Respuestas:

8

Jalea , 16 15 14 bytes

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

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

÷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.
Dennis
fuente
4

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:]

Equivalente a lo más "obvio":

lambda n:min([(i+1,0-n/~i)for i in range(n)],key=lambda(p,q):abs(p-q)+p*q)
Lynn
fuente
Puede guardar tres bytes iterando range(-n,0), como hago en mi respuesta . Banco de pruebas.
Dennis
3

Haskell, 65 bytes

f x=snd$minimum[((a*b+a-b,a*b),(b,a))|a<-[1..x],b<-[1..a],a*b>=x]

Ejemplo de uso: map f [1..5]-> [(1,1),(1,2),(2,2),(2,2),(2,3)].

Pasa por un bucle externo ade 1a x(x -> número de estudiantes) y un bucle interno bde 1a a. Mantiene todos los (b,a)lugares a*b>=xy construye pares de los ((arrangement points,seats left), (b,a))cuales siguen el orden lexicográfico que necesitamos para encontrar el mínimo. Nota: asiempre es mayor que b, por lo que no necesitamos abscuadratura. No es necesario restar xel puntaje de "asientos restantes", porque solo importa el orden relativo. Finalmente eliminamos el par de puntuación con snd.

nimi
fuente
¿Por qué no solo (a b + ab, (b, a))? Si minimizas el puntaje, seguramente minimizas a b de todos modos, ¿o me estoy perdiendo algo?
justinpc
@jpcooper: a*b(número de asientos libres) es el desempate si el puntaje principal es igual. Por ejemplo n=43: a) a=7, b=7, la puntuación: (49,49)b) a=9, b=5, la puntuación: (49,45). La puntuación principal es igual, el desempate decide, b) gana.
nimi
Tienes razón. Debería haber leído mejor la descripción.
justinpc
@jpcooper: espera un minuto ... si quito el desempate a*b, los números (b,a)que tengo que llevar de todos modos actúan como el desempate y dan los mismos resultados (al menos) n=1..300. Un producto es pequeño si uno de los factores (aquí b) es pequeño. Pero mientras no tenga pruebas formales, no quiero usar este hecho. A ver si encuentro uno.
nimi
Buen punto. Parece correcto, y no debería ser demasiado difícil encontrar una prueba. Estoy empezando a preguntarme si podría haber una solución lineal a este problema.
justinpc
2

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]}

Una lambada que toma el número de personas como argumento y devuelve una matriz con ancho y alto de la solución óptima.

MegaTom
fuente
¿Por qué necesita w*hcomo segundo elemento en su matriz? No creo que cambie particularmente nada cuando llamas minporque minimizas la puntuación, también conocido como el primer elemento.
Value Ink
@ KevinLau-notKenny de la pregunta:In case of a tie, the optimal solution is the one with less empty chairs
MegaTom
2

MATL , 18 bytes

:Gy/Xkvtd|yp+&X<Z)

Pruébalo en línea!

Explicación

:      % 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
Luis Mendo
fuente
2

Javascript, 98 bytes

Mi primer código de golf, así que publico de todos modos!

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}

Inicialmente, mi oera un objeto vacío y comprobé si o.aestaba vacío, por lo que fue un caso especial en la primera ronda. Pero encontré el truco 1/0 en la respuesta de edc65 para inicializar la variable a Infinito.

Thiht
fuente
Y probaré el truco para usar un objeto para almacenar el resultado temporal
edc65
1

Pyth, 24 22 21 bytes

Editar : en la clave de clasificación, me doy cuenta de que no hay necesidad de encontrar el número de sillas vacías. Es equivalente a puntuar el número total de sillas. Esto me ahorró 2 bytes.

h.m_+B*FbaFbm,d.EcQdS

Pruébalo en línea!

Monja permeable
fuente
1

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)
  • truco 1: agregué la cantidad 1-1/length*widthcomo empate

  • Truco 2: i calculado number_students/lengthartesonadas para el ancho de rectángulo, el límite superior es el cuadrado pero artesonadas demasiado

  • Estoy seguro de que se puede jugar más golf ...

intentalo


Editar: referenciado a los comentarios de @StewieGriffin.

Edición 2:

  • 1y nson constantes, no es necesario agregarlos a la puntuación general.
  • Una función tiene pocos bytes menos que el programa independiente stdin.
  • Sin embargo, utilicé la técnica de clasificación ascendente, ahorra demasiados bytes.

Edición 3: prueba de rendimiento.

Abr001am
fuente
@StewieGriffin que no es un gran problema, se puede resolver usandounique
Abr001am
1
Creo que a mitad de camino a algún buen im traducción matemática para este problema, pero aún se mantiene como la conjetura
Abr001am
También pensé en esto. Ver ejemplo de julia.
mschauer
1

Julia, 61 59 55 53 52 bytes

/ =cld
n->[m=indmax([~i*~-max(i,n/i)for i=1:n]),n/m]

Pruébalo en línea!

Cómo funciona

El código es equivalente a la siguiente versión sin golf, donde cldestá la división del techo.

function chairs(n)
    m = indmin([(i + 1) * (max(i, cld(n, i)) - 1) for i in 1:n])
    return [m, cld(n, m)]
end

Para encontrar la disposición óptima, es claramente suficiente para examinar los pares [i, j] , donde 1 ≤ i ≤ n y j = ⌈n / i⌉ .

El puntaje para tal arreglo es | j - i | + (ij - n) , donde el segundo sumando es el número de sillas vacías. En lugar de los puntajes reales, podemos comparar puntajes aumentados por una constante, como ij + | j - i | + 1 .

Es suficiente considerar los pares [i, j] donde i ≤ j ya que las disposiciones [i, j] y [j, i] son igualmente válidas. En su lugar, tratamos con pares estrictamente descendentes estableciendo j = max (⌈n / i⌉, i) , lo que garantiza que j ≥ i dará un puntaje subóptimo si ⌈n / i⌉ <i .

Como j - i ≥ 0 , tenemos ij + | j - i | + 1 = ij + j - i + 1 = (i + 1) × (j - 1) , que se puede calcular en menos bytes de código.

Finalmente indmin/ indmaxda el índice m (y por lo tanto el valor de i ) de la disposición óptima, que es m por ⌈n / m⌉ . Los empates se rompen por primera aparición, que corresponde al valor más bajo de i , por lo tanto, el valor más alto de j - i y, por lo tanto, el valor más bajo de ij - n (sillas vacías).

Dennis
fuente
1

JavaScript (ES6) 74 78

Edite manteniendo el resultado temporal como una matriz en lugar de 2 vars, tomado de la respuesta de Thiht

n=>(z=>{for(x=0;y=-~(~-n/++x),x<=y;)(s=y-x+x*y-n)>=z||(z=s,r=[x,y])})()||r

Menos golf

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
}

Prueba

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>

edc65
fuente
1

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);}

Sin golf:

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);
}
Gato de negocios
fuente
1

PHP, 104 bytes

El algoritmo que resuelve este problema es simple y probablemente lo utilicen otras respuestas en lenguajes similares a PHP (JavaScript, fe):

  • comenzar con un valor grande para la puntuación inicial; nes lo suficientemente grande (donde nestá el valor de entrada); la puntuación de la disposición calculada en la primera iteración ( 1, n) es(n-1)+0 ;
  • iterar para todos los valores de ancho entre 1y n; calcule la altura mínima como ceil(n/width), calcule la puntuación de disposición utilizando la fórmula provista en la pregunta (es decir abs(width - height) + (width * height - n)); Si la puntuación es mejor que la mejor puntuación anterior, recuerde el ancho, la altura y la nueva mejor puntuación; En los lazos, utilice el valor de width * height - npara el arreglo actual y el mejor arreglo previo para detectar el nuevo mejor arreglo;
  • eso es todo.

Después del golf, este algoritmo produce algo como esto (envuelto aquí para facilitar la lectura):

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";

Utiliza 137 bytes (cuando se coloca en una sola línea) y está lejos de los 104 bytes anunciados en el título. El código probablemente se puede acortar en otros 2-3 bytes, pero la gran fuente de mejora está en otro lugar: en los detalles del algoritmo.

El algoritmo revisado:

Hay varios lugares donde se puede mejorar el algoritmo eliminando el código inútil.

  • no es necesario iterar el ancho de 1a $n; para la velocidad, el ancho ( $i) debe iterar entre 1y floor(sqrt($n))pero esto hace que el código sea aún más largo en lugar de acortarlo; pero si el ancho no excede sqrt($n), la altura mínima ( $j) siempre será mayor que sqrt($n)(su producto debe ser al menos $n);
  • la declaración anterior permite usar $i <= $j(ancho <= alto) como la condición de terminación para el bucle; de esta manera, el ancho iterará de 1a floor(sqrt($n))y la altura obtendrá valores que comienzan $ny bajan aceil(sqrt($n)) (no necesariamente todos);
  • sabiendo que el ancho siempre es menor o igual que la altura, permítanos saber que abs(width - height)siempre es height - width( $j-$i); 5 bytes guardados de esta manera;
  • el valor de entrada $nse usa en el cálculo de la puntuación (el número de asientos desocupados es width * height - n) pero no es necesario; no es necesario que se muestre el puntaje, se calcula solo para la comparación de los arreglos; Al eliminar - nde la fórmula de puntuación, guardamos otros 3 bytes (el código PHP es -$n) sin perder nada;
  • dadas las dos últimas declaraciones, la fórmula de puntuación se convierte en height - width + width * height( $j-$i+$i*$j);
  • en los empates (el puntaje del acuerdo actual es el mismo que el mejor puntaje anterior), las reglas dicen usar el arreglo con menos asientos libres; porque el ancho siempre aumenta y la altura siempre disminuye, la height - widthparte de la puntuación disminuye en cada paso;
  • si el puntaje actual es igual al mejor puntaje anterior, las declaraciones anteriores nos dicen que el número de asientos libres del arreglo actual es mayor que el del mejor arreglo anterior; esto significa que el mejor arreglo anterior gana el empate;
  • debido a que los empates siempre son ganados por el mejor arreglo anterior, un nuevo arreglo se convierte en el nuevo mejor arreglo solo cuando su puntaje es menor que el mejor anterior; el código que verifica los lazos es inútil y se puede eliminar (||$c==$s&&$i*$j<$w*$h - muchos bytes);
  • debido a la eliminación de -$nla fórmula del puntaje, el puntaje para el primer arreglo ( 1x$n) es $n-1+1*$n( es decir 2*$n-1); el valor inicial de la mejor puntuación ( $s) puede ser cualquier valor mayor o igual que 2*$n; la primera iteración tiene una mejor puntuación y se convierte en la mejor disposición que permite que el algoritmo se ejecute sin problemas de inicialización.

El nuevo código ( 104 bytes ), después de aplicar las mejoras descritas anteriormente es:

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";

Está envuelto aquí para facilitar la lectura. Anteponga el código anterior con el marcador PHP <?php(técnicamente, no es parte del código), colóquelo en un archivo (digamos arrange-your-chairs.php) y ejecútelo con un número entero mayor que cero como argumento. Mostrará el ancho y la altura de la disposición calculada, separados por comas:

$ php arrange-your-chairs.php 1001
28,36

Otra solución (116 bytes)

Otra solución que usa un algoritmo diferente:

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);

Pone todas las combinaciones de al menos $nasientos en una lista asociativa; la clave es la representación de texto del arreglo, el valor es el puntaje del arreglo. Luego ordena la lista (ascendente por valor) y obtiene la clave de la primera entrada.

Uno más (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";

Esta es la versión PHP de la respuesta de @ Neil (JavaScript / ES6, 85 bytes).

Hay algunas diferencias notables debido a las características de cada idioma:

  • la respuesta JS genera una matriz de nvalores (indefinidos) y luego usa sus claves para iterar de 0a n-1; incrementa i( d=(n+i++)/i|0) para hacerlo iterar de 1a n; la solución PHP no necesita incrementarse; utiliza range()para generar una matriz y luego utiliza los valores generados ( 1a n) para iterar;
  • la respuesta JS usa (n+i)/iluego convierte el valor a entero usando |0para obtener el entero más pequeño más grande que n/i; la respuesta PHP resuelve este problema fácilmente con la función PHP ceil(); JavaScript también proporciona Math.ceil()pero usa 5 bytes más que la solución encontrada por Neil;
  • PHP proporciona la función array_map() que de alguna manera es similar con JS Array.map()pero no ayuda aquí; su sintaxis es detallada, a foreachproduce código más corto; sin embargo, es más grande que el código JS;
  • fusionar las asignaciones en las condiciones usando ||no es posible en PHP porque carece del operador de coma; Traduje a||b||ca if(!a&&!b)centonces, porque ayb son comparaciones, negué sus operadores (reemplazados <por >=); esto también produce código más grande que la versión JS;
  • se deben agregar otros 23 bytes solo porque los nombres de las variables en PHP deben tener el prefijo $ .

Las versiones no protegidas de todas las soluciones y el conjunto de pruebas se pueden encontrar en Github .

axiac
fuente
1
Esta es la respuesta de código de golf más completa que he visto.
DJMcMayhem
0

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
Neil
fuente
Tal vez podrías aplicar mi truco (para guardar 2 bytes)
Leaky Nun
@KennyLau No creo que ayude; Tendría que aumentar mpara compensar.
Neil
0

Julia, 87

Creo que este es un paso en la dirección para encontrar una función mágica para el problema:

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(_)

Solo mira pares (i, j=(i+n)/(i+1))o(i, j+1)

mschauer
fuente
favor de explicar con más detalle cómo funciona esto, se volvió mi curiosidad V combate su función
Abr001am
2
No estoy seguro de cómo se supone que esto funcione. No define en nninguna parte, y parece que no está tomando información.
Dennis
Ah, lo siento, solo tomé ncomo entrada. Uno necesitaría envolverlo n->.... Es bueno que puedas hacer que funcione.
mschauer
0

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;

Sin golf

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
Jeto
fuente
0

Q 58 Bytes

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

Lamba que calcula el costo mínimo para un valor dado (x) y devuelve una secuencia de dos valores (ancho, alto)

Agregar nombre a esa lambda requiere otros dos caracteres (por ejemplo, f: {..} en lugar de {..})

Prueba

{..}'1+!100

donde {..} es la lambda. Lea como "aplica lambda a cada valor de 1 + primeros 100 ints" (en otras palabras, a cada valor 1..100)

Genera

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
..

Explicación

Lamdba anidada {((b<a)?1b)#+(b:-_-x%a;a:1+!x)}genera todos los pares de candidatos (ancho, alto) para las sillas x como dos secuencias (w1 w2 w3 ..; h1 h2 h3 ..) (anchos y alturas). Lee de izquierda a derecha, pero evalúa de derecha a izquierda

a:1+!x genera valores 1..x y asigna esa secuencia a un

-_- es negate floor negate e implementa ceil (ceil no es un primitivo del lenguaje)

b:-_-x%aaplica ceil a cada valor de x dividido por cualquier elemento im a, y asigna la secuencia resultante a b. En otras palabras, b es ceil cada x dividido Por cada 1..x

+(b;a) devuelve una secuencia compuesta de seq a y seq b, y luego la voltea (el resultado es una secuencia de par donde i-pair contiene el elemento i de a y el elemento i de b)

b<a compara elemento por elemento de bya, y genera una secuencia de valores lógicos (verdadero = 1b para cada índice donde b [i]

s?xdevuelve la primera posición del elemento x en la secuencia s. Con (b<a)?1bBuscamos 1b (valor verdadero) en secuencia como resultado de comparar by a, y obtenemos la primera posición donde b

n#stoma n primeros n elementos de las secuencias s. Queremos descartar pares duplicados, por lo que nos detenemos cuando el primer elemento de un par <segundo elemento (por ejemplo, considere 13,1 pero no 1,13).

Como efecto secundario, cada par de la secuencia resultante tiene una distancia decreciente entre ayb (ex (13 1; 7 2; 5 3; 4 4)

El par candidato generado por lambda anidado se asigna a c. Luego volteamos c (obtiene b, a de nuevo) y aplica dos funciones a ese argumento: */multiplica y -/resta. El resultado de (-/;*/)@\:+ces la diferencia y el producto de cada par. +/se suma y calcula el costo final. El costo de cada patrón se asigna a d

& / es mínimo, entonces &/d es el costo mínimo. Con d?&/dencontramos la primera aparición del costo mínimo en d, y con c @ .. recuperamos el par en esa posición. Como cada par tiene una distancia decreciente entre ayn, el primer mínimo encontrado tiene la distancia máxima entre otros pares mínimos, por lo que aplicamos la regla de empate correctamente

J. Sendra
fuente