Resolver el problema numérico de Aristóteles

21

El acertijo numérico de Aristóteles es el desafío de poblar cada una de las 19 celdas en una cuadrícula hexagonal con un número entero único entre 1 y 19, de modo que el total a lo largo de cada eje sea 38.

Puedes imaginar el tablero de juego de esta manera:

rejilla de aristóteles

Y el rompecabezas, en esencia, es la solución al siguiente conjunto de quince ecuaciones:

((a + b + c) == 38 && (d + e + f + g) == 38 && (h + i + j + k + l) == 
   38 && (m + n + o + p) == 38 && (q + r + s) == 38 && (a + d + h) == 
   38 && (b + e + i + m) == 38 && (c + f + j + n + q) == 
   38 && (g + k + o + r) == 38 && (l + p + s) == 38 && (c + g + l) == 
   38 && (b + f + k + p) == 38 && (a + e + j + o + s) == 
   38 && (d + i + n + r) == 38 && (h + m + q) == 38)

Donde cada variable es un número único en el conjunto {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}.

Existen múltiples soluciones posibles, y son 19!posibles combinaciones de enteros, por lo que la fuerza bruta ingenua no será práctica.

Reglas:

  1. Sin codificar la respuesta o buscar la respuesta en otra parte; su código necesita encontrarlo solo
  2. La velocidad no importa, pero debe mostrar sus resultados, por lo que el código que tarda 1000 años en ejecutarse no lo ayudará
  3. Encuentra todas las respuestas
  4. Trate las respuestas que son idénticas en rotación como idénticas
  5. Deduzca el 5% de su recuento total de bytes si genera los resultados en un atractivo panal
  6. Pocos bytes ganan
Michael Stern
fuente
Gran pregunta, deseando encontrar una solución.
ProgramadorDan
¿Considera que las respuestas rotadas son únicas? Por ejemplo, supongamos que a, b, c = 1, 18, 19 indexa una solución particular, si establecemos c, g, l = 1, 18, 19 y todos los demás valores se "giran" para que coincidan, ¿considera que esto es único? ¿solución?
ProgramadorDan
@ProgrammerDan Las respuestas rotadas son idénticas. Voy a aclarar
Michael Stern
1
Un hexágono tiene más simetrías que solo rotaciones. ¿Qué pasa con las respuestas que son idénticas bajo una combinación de rotación y reflexión?
Peter Taylor
Interesado en ver una solución para esto usando mapas autoorganizados.
Ant P

Respuestas:

3

Haskell 295 289

import Data.List
t=38
y a b=[max(19-b)(a+1)..19]
w=y 0 t
x=filter((==w).sort)$[[a,b,c,d,e,f,g,h,i,t-a-e-o-s,k,l,m,t-d-i-r,o,p,q,r,s]|a<-[1..14],c<-y a a,l<-y a c,s<-y a l,q<-y a s,h<-y c q,e<-w,let{f=t-g-e-d;i=t-b-e-m;o=t-r-k-g;k=t-p-f-b;b=t-a-c;g=t-l-c;p=t-l-s;r=t-q-s;m=t-q-h;d=t-a-h}]

Otra respuesta similar, usando la aritmética para obtener los hexes intermedios. A diferencia de las otras soluciones, no pruebo que esas sumas sean> 0, es suficiente probar que los hexes ordenados son iguales al rango [1..19]. a, c y h están restringidos, de modo que solo se permiten soluciones rotadas / duplicadas de forma única. La solución aparece después de unos segundos, luego hay que esperar un minuto más o menos mientras decide que no hay más.

Uso en ghci:

ghci> x
[[3,19,16,17,7,2,12,18,1,5,4,10,11,6,8,13,9,14,15]]

Editado para afeitarse algunos caracteres. 'y 0 t' produce [1..19].

bazzargh
fuente
1
En realidad estoy haciendo lo mismo en mi respuesta C :) maldita sea, ¿cómo podría no ver que Haskell es la herramienta perfecta para el trabajo: P +1
Niklas B.
¿Puedo perder su x>0cheque, porque clasifico la lista incluyendo negativos en lugar de incrementar una matriz? Por otro lado, tengo que restringir los rangos (my y a b) para que Haskell funcione, lo que me cuesta algunos caracteres. Pero es probable que haya otro idioma que tenga un tipo incorporado que me supere trabajando de la misma manera (mirándote, Mathematica).
bazzargh
Sí, desafortunadamente ordenar en C no es tan simple como en Haskell. El problema con Mathematica es que no está compilado y por lo tanto es muy lento :(
Niklas B.
Siempre hago esto en Haskell para practicar, incluso si otro idioma sería mejor.
bazzargh
De hecho, programo a Haskell como un trabajo secundario, así que estoy perplejo porque ni siquiera se me ocurrió usarlo aquí: D Es un lenguaje realmente genial, incluso en el mundo real / impuro
Niklas B.
10

Java (1517 - 75.85) = 1441.15 (1429 - 71.45) = 1357.55 (1325 - 66.25) = 1258.75

Esto fue divertido.

Imprime todas las soluciones únicas con reflejo y rotación de wrt, en un agradable panal (por lo tanto, reducción del 5%)

Tiempo de ejecución: ~ 0.122s (122 milisegundos) en mi computadora portátil de 4 años.

Código Golfed (la edición se dio cuenta de que estaba repitiendo estúpidamente mis printfs, los reduje a una sola printf para obtener el máximo golf) ( nueva edición Llamadas reducidas para configurar funciones en funciones inteligentes más pequeñas, algunas otras microoptimizaciones):

import java.util.*;class A{boolean c(Set<Integer>u,int z){return!u.contains(z);}Set<Integer>b(Set<Integer>c,int...v){Set<Integer>q=new HashSet<Integer>(c);for(int x:v)q.add(x);return q;}void w(){Set<Integer>U,t,u,v,w,y,z;int a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,X,Z;X=20;Z=38;for(a=1;a<X;a++)for(b=1;b<X;b++)if(b!=a)for(c=1;c<X;c++)if(c!=a&&c!=b&&a+b+c==Z){U=b(new HashSet<Integer>(),a,b,c);for(d=1;d<X;d++)if(c(U,d))for(h=1;h<X;h++)if(h!=d&&c(U,h)&&a+d+h==Z){t=b(U,a,b,c,d,h);for(m=1;m<X;m++)if(c(t,m))for(q=1;q<X;q++)if(q!=m&&c(t,q)&&h+m+q==Z){u=b(t,m,q);for(r=1;r<X;r++)if(c(u,r))for(s=1;s<X;s++)if(s!=r&&c(u,s)&&q+r+s==Z){v=b(u,r,s);for(p=1;p<X;p++)if(c(v,p))for(l=1;l<X;l++)if(l!=p&&c(v,l)&&s+p+l==Z){w=b(v,p,l);for(g=1;g<X;g++)if(c(w,g)&&l+g+c==Z)for(e=1;e<X;e++)if(e!=g&&c(w,e))for(f=1;f<X;f++)if(f!=e&&f!=g&&c(w,f)&&d+e+f+g==Z){y=b(w,g,e,f);for(i=1;i<X;i++)if(c(y,i))for(n=1;n<X;n++)if(n!=i&&c(y,n)&&d+i+n+r==Z&&b+e+i+m==Z){z=b(y,i,n);for(o=1;o<X;o++)if(c(z,o))for(k=1;k<X;k++)if(k!=o&&c(z,k)&&m+n+o+p==Z&&r+o+k+g==Z&&b+f+k+p==Z)for(j=1;j<X;j++)if(c(z,j)&&j!=o&&j!=k&&a+e+j+o+s==Z&&c+f+j+n+q==Z&&h+i+j+k+l==Z){System.out.printf("%6d%4d%4d\n\n%4d%4d%4d%4d\n\n%2d%4d%4d%4d%4d\n\n%4d%4d%4d%4d\n\n%6d%4d%4d\n\n",a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s);return;}}}}}}}}}public static void main(String[]a){(new A()).w();}}

La fuerza bruta es passe, pero el uso inteligente del hecho de que solo existe un conjunto muy pequeño de soluciones me llevó a una respuesta basada en la iteración, donde dentro de cada ciclo de la iteración solo considero enteros que aún no han sido "asignados". Hago uso de HashSet de Java para obtener búsquedas O (1) de números que se han utilizado anteriormente. Finalmente, hay exactamente 12 soluciones, pero cuando descontas tanto la rotación como la duplicación, esto se reduce a solo una solución única, por lo que cuando se encuentra la primera solución, la imprimo y termino. Echa un vistazo a mi código menos golfizado en github para obtener una visión más clara de cómo me estoy acercando a esta solución.

¡Disfrutar!

ProgramadorDan
fuente
Bueno, mientes en tu spoiler, hay más soluciones diferentes, por lo que tu respuesta no es válida.
ST3
Afirmación fuerte, ¿puede respaldarlo con una respuesta propia para probarlo? Ciertamente no estoy al tanto de ninguna mentira intencional en mi spoiler.
ProgramadorDan
así que cuando se encuentra la primera solución, la imprimo y termino la regla no. 3 dice dice para encontrar todas las respuestas. Hay 19 como OP dijo, no estoy seguro si es realmente 19, pero me he encontrado con una tarea similar antes, así que sé que hay más de una.
ST3
Necesitas leer todo mi spoiler. Encontré 12 soluciones. Luego debe leer todos los comentarios adjuntos a la pregunta. El OP dice que las respuestas que son iguales a la rotación de wrt son equivalentes y deben omitirse. Otra persona preguntó si se deberían omitir las respuestas iguales a la duplicación de wrt. Aunque el OP no ha respondido a esta consulta hasta la fecha, tanto mi como todas las otras soluciones hasta la fecha suponen que la respuesta es "sí". Por lo tanto, mi solución es completamente completa, totalmente precisa, y no hay "mentiras" aquí. Sin embargo, si desea ver las 12 soluciones, elimine la return;declaración.
ProgramadorDan
Finalmente, este es el código de golf. Teniendo en cuenta que agregar una return;declaración arbitraria aumenta la longitud de mi código en 7, sería una locura agregarlo si la respuesta verdadera incluyera las 12 soluciones que son simplemente versiones rotadas / duplicadas entre sí. Aunque no se puede descartar la locura, en este caso, la adición de return;fue intencional, y como lo describí, basado en el diálogo completo de preguntas y comentarios , que debe revisar antes de lanzar acusaciones. ¡Gracias!
ProgramadorDan
8

C, 366 bytes ( C ++ 541 450 )

#define R(i)for(int i=19;i;--i)
#define X(x)if(x>0&&!V[x]++)
#define K(X)X(a)X(b)X(c)X(d)X(e)X(f)X(g)X(h)X(i)X(j)X(k)X(l)X(m)X(n)X(o)X(p)X(q)X(r)X(s)
Q(x){printf("%d ",x);}
T=38,V[99];main(){R(h)R(c)R(s)R(a)R(l)R(q)R(e){int d=T-a-h,b=T-a-c,g=T-c-l,p=T-l-s,r=T-q-s,m=T-h-q,f=T-g-e-d,i=T-b-e-m,n=T-d-i-r,o=T-p-n-m,k=T-g-o-r,j=T-h-i-k-l;R(C)V[C]=0;K(X)K(+Q),exit(0);}}

Compilar con gcc -std=c99 -O3.

Imprime todas las soluciones únicas de módulo de rotación y reflejo, en el formato a b c d ..., una por línea.

Tiempo de ejecución: 0.8 segundos en mi computadora.

Enumeramos las celdas en el orden h -> c -> s -> a -> l -> q -> e para una máxima capacidad de eliminación. De hecho, la versión anterior solo intenta cada 20 ^ 7 asignaciones para esas variables. Entonces podemos calcular todas las otras celdas. Solo hay una solución única de módulo de rotación / reflejo. Se puede encontrar una versión C ++ más antigua, menos golfizada y ~ 20 veces más rápida (debido a la poda) en Github

Niklas B.
fuente
Me encanta el enfoque en gran medida aritmético aquí. ¡Bravo! +1
ProgramadorDan
1

Matlab: 333 320 caracteres

Este es un enfoque bastante tonto de fuerza bruta que no utiliza la recursividad. Construye soluciones parciales en z, que se imprime al final. Cada columna es una solución; los elementos se enumeran az de arriba a abajo. El tiempo de ejecución es de 1-2 horas.

z=[];
a='abc adh hmq qrs spl lgc defg beim mnop dinr rokg pkfb hijkl aejos cfjnq';while a[k,a]=strtok(a);n=length(k);x=nchoosek(1:19,n)';s=[];for t=x(:,sum(x)==38)s=[s,perms(t)'];end
m=0.*s;m(19,:)=0;m(k(1:n)-96,:)=s(1:n,:);y=[];for p=m for w=z m=[];l=w.*p~=0;if p(l)==w(l) y(:,end+1)=w+p.*(~l);end
end
end
z=[m,y];end
z

Corriendo desde Matlab:

>> aristotle;
>> z(:,1)

ans =

    9
   11
   18
   14
    6
    1
   17
   15
    8
    5
    7
    3
   13
    4
    2
   19
   10
   12
   16
intx13
fuente