Particionar un n X ncuadrado en múltiples rectángulos enteros no congruentes. a(n)es la menor diferencia posible entre el área más grande y la más pequeña.

 ___________
| |S|_______|
| | |   L   |
| |_|_______|
| |     |   |
| |_____|___|
|_|_________| (fig. I)

El rectángulo más grande ( L) tiene un área de 2 * 4 = 8, y el rectángulo más pequeño ( S) tiene un área de 1 * 3 = 3. Por lo tanto, la diferencia es 8 - 3 = 5.

Dado un número entero n>2, genera la menor diferencia posible.

Todos los valores conocidos de la secuencia en el momento de la publicación:

2, 4, 4, 5, 5, 6, 6, 8, 6, 7, 8, 6, 8, 8, 8, 8, 8, 9, 9, 9, 8, 9, 10, 9, 10, 9, 9, 11, 11, 10, 12, 12, 11, 12, 11, 10, 11, 12, 13, 12, 12, 12

Por lo tanto a(3)=2, a(4)=4...

OEIS A276523

Relacionado : este desafío relacionado permite soluciones no óptimas, tiene limitaciones de tiempo y no es código de golf.

Para más información, mira este video de Numberphile

CJam, 178

ri_1a*a*L{_:+1&{_[3{_\zW%}*]{_z}%:e<_@={:A0=_1#:X0<{;A1>j}{X>0+0#AzX=0+0#,\,m*1ff+{[_$\~1a*0aX*\+a*A\..-_])s'-&{;}&}%{~j\:X;{Xa&!},Xaf+:$~}%_&}?}{j}?}{;La}?}j{,(},{::*$)\0=-}%:e<

Pruébalo en línea . Sin embargo, es muy lento, no recomendaría ir por encima de 6.

Para verificar que realmente está haciendo el trabajo, puede verificar este programa ligeramente modificado que imprime todas las particiones posibles (cada partición se muestra como una matriz de pares de dimensiones rectangulares).

Befunge, 708 bytes

p&>:10p1-:>20p10g:20g\`v`\g02:-1\p00+1g<>g-#v_10g:*30p"~":40p50p060p070p$>^
1#+\#1<\1_^# !`0::-1$  _:00g3p\:00g2p00^^00:>#:


>>:2-#v_$30p50p60p70g1-70p
^<<<<<:#<<<<<<$$$_v#:!g87g78g79$  _v#!\-1:g88$<_ 98p87g97g*00 v:+!\`*84g++7<
^>$1-:77p1g:2g\3g1>78p97p87p10g97g->88p10g87g-0^!\-1:g89_v#-!\_$1-:v>/88g+7^
^|!-3$<   >\87g/88g+77++p:#v_$
^>:5->v   ^+g89%g78:\g77:-1<>98g88g48*577g387g97g98g88v ^>77g87g97v:^g78\+g<
^ v-4:_$77p88p98p:97p\:87p*^^g79g7>#8\#$_40pv5+"A"g77g< ^14g88g89g<>:87g%98^
^v_$88p98p97p87p:77p60g50g-:40g\`#^_$$>>>>>>>
 >#4!_::80p2g\3g*:90p30g`!v>>>#@>#.>#g^#0
^v:g06p03:-g09\2:g03g05g06_^^_7#<0#<g#<3#<1#<<`g04_$00g1->:#-8#10#\g#1`#:_>$
^>90g\-:0`*+:60p50g:90g-:0`*-:50p-80g70g:1+70p1p\!^

Pruébalo en línea!

Obviamente, esto no va a ganar ningún premio por el tamaño, pero en realidad es bastante rápido teniendo en cuenta que es una implementación básica de fuerza bruta en un lenguaje esotérico. En el intérprete de referencia Befunge, puede manejar hasta n = 6 en un par de segundos. Con un compilador puede manejar hasta n = 8 antes de que comience a ser lento; n = 9 toma un par de minutos y n = 10 está cerrado en 2 horas.

En teoría, el límite superior es n = 11 antes de que se nos acabe la memoria (es decir, no queda suficiente espacio en el campo de juego para caber en un cuadrado más grande). Sin embargo, en ese punto, el tiempo necesario para calcular la solución óptima es probablemente más largo de lo que cualquiera estaría dispuesto a esperar, incluso cuando se compila.

La mejor manera de ver cómo funciona el algoritmo es ejecutándolo en uno de los "depuradores visuales" de Befunge. De esa manera, puede ver cómo intenta ajustar los diversos tamaños de rectángulo en el espacio disponible. Si desea "avanzar rápidamente" hasta el punto donde tiene una buena coincidencia, puede poner un punto de interrupción 4en la secuencia$_40p cerca del medio de la décima línea (9 si está basado en cero). El valor en la parte superior de la pila en ese punto es la diferencia de área actual.

A continuación se muestra una animación que muestra los primeros fotogramas de este proceso para n = 5:

Cada rectángulo distinto está representado por una letra diferente del alfabeto. Sin embargo, tenga en cuenta que el rectángulo final nunca se escribe, por lo que esa sección del cuadrado estará en blanco.

También he escrito una versión de depuración del código que genera el diseño actual cada vez que encuentra una nueva mejor coincidencia (¡ Pruébelo en línea! ). Para los tamaños más pequeños, la primera coincidencia suele ser la solución óptima, pero una vez que supere n = 6, es probable que vea varios diseños válidos pero no óptimos antes de decidirse por la solución final.

El mejor diseño encontrado para n = 10 se ve así:

H F F F A A A C C I
H F F F A A A C C I
H J G G A A A C C I
H J G G A A A C C I
H J D D D D D C C I
H J D D D D D C C I
H J K K K K K K K I
H J B B B E E E E I
H J B B B E E E E I
H J B B B L L L L L

12 - 4 = 8