Resolver o problema numérico de Aristóteles

21

O quebra-cabeça numérico de Aristóteles é o desafio de preencher cada uma das 19 células em uma grade hexagonal com um número inteiro único entre 1 e 19, de modo que o total ao longo de cada eixo seja 38.

Você pode imaginar o tabuleiro do jogo assim:

grade de aristóteles

E o quebra-cabeça, em essência, é a solução para o seguinte conjunto de quinze equações:

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

Onde cada variável é um número único no conjunto {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}.

Existem várias soluções possíveis e 19!combinações possíveis de números inteiros; portanto, a força bruta ingênua será impraticável.

Regras:

  1. Sem codificar a resposta ou procurar a resposta em outro lugar; seu código precisa encontrá-lo por conta própria
  2. A velocidade não importa, mas você precisa mostrar seus resultados, para que o código que leva 1000 anos para ser executado não o ajude
  3. Encontre todas as respostas
  4. Trate respostas idênticas em rotação como idênticas
  5. Deduzir 5% da sua contagem total de bytes, se você produzir os resultados em um atraente favo de mel
  6. Menos bytes ganhos
Michael Stern
fonte
Ótima pergunta, ansioso para encontrar uma solução para isso.
ProgrammerDan
Você considera as respostas rotacionadas como únicas? Por exemplo, vamos supor que a, b, c = 1, 18, 19 indexe uma solução específica, se definirmos c, g, l = 1, 18, 19 e todos os outros valores forem "rotacionados" para corresponder, você considera isso um único solução?
ProgrammerDan
@ProgrammerDan As respostas rotativas são idênticas. Eu vou esclarecer.
Michael Stern
1
Um hexágono tem mais simetrias do que apenas rotações. E as respostas que são idênticas sob uma combinação de rotação e reflexão?
Peter Taylor
Interessado em encontrar uma solução para este usando mapas auto-organizados.
Ant

Respostas:

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

Outra resposta semelhante, usando aritmética para obter os hexágonos intermediários. Diferentemente das outras soluções, não testo se essas somas são> 0, basta testar se os hexágonos classificados são iguais ao intervalo [1 .. 19]. a, c e h são restritos, de modo que somente soluções rotacionadas / espelhadas são permitidas. A solução aparece após alguns segundos e, em seguida, espera um minuto ou mais, enquanto decide que não há mais.

Uso em ghci:

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

Editado para barbear alguns caracteres. 'y 0 t' produz [1 .. 19].

bazzargh
fonte
1
Na verdade, eu estou fazendo a mesma coisa no meu C resposta :) maldita como eu poderia não ver que Haskell é a ferramenta perfeita para o trabalho: P 1
Niklas B.
Perco sua x>0verificação, porque classifico a lista incluindo negativos em vez de incrementar uma matriz? Por outro lado, tenho que restringir os intervalos (meus y a b) para fazer o Haskell executar, o que me custa alguns caracteres. Mas é provável que exista outro idioma que tenha uma classificação interna que me supere trabalhando da mesma maneira (olhando para você, Mathematica).
bazzargh
Sim, classificar em C infelizmente não é tão simples quanto em Haskell. O problema com o Mathematica é que ele não está compilado e, portanto, tão maldito lento :(
Niklas B.
Eu sempre faço isso em Haskell para praticar, mesmo que outro idioma seja melhor.
bazzargh
Na verdade, eu programo Haskell como um trabalho paralelo, por isso estou surpreso com o fato de que nem me ocorreu usá-lo aqui: D É uma linguagem realmente ótima, mesmo no mundo real / impuro
Niklas B.
10

Java (1517 - 75,85) = 1441,15 (1429 - 71,45) = 1357,55 (1325 - 66,25) = 1258,75

Isso foi divertido.

Imprime todas as soluções exclusivas, com espelhamento e rotação, em um favo de mel agradável (redução de 5%)

Tempo de execução: ~ 0.122s (122 milissegundos) no meu laptop de 4 anos.

Código golfado (a edição percebeu que eu estava estupidamente repetindo meus printfs, os reduzi a um único printf para obter o máximo de golfe) ( nova edição Chamadas reduzidas para Definir funções em funções menores inteligentes, algumas outras otimizações):

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

A força bruta é ultrapassada, mas o uso inteligente do fato de existir apenas um conjunto muito pequeno de soluções me levou a uma resposta baseada na iteração, onde em cada loop da iteração eu considero apenas números inteiros que ainda não foram "atribuídos". Faço uso do HashSet do Java para obter O (1) pesquisas de números que foram usados ​​anteriormente. Finalmente, existem exatamente 12 soluções, mas quando você desconta a rotação e o espelhamento, isso reduz a apenas uma solução única; portanto, quando a primeira solução é encontrada, eu a imprimo e termino. Confira meu código de menos golfe no github para ter uma visão mais clara de como estou abordando esta solução.

Apreciar!

ProgrammerDan
fonte
Bem, você mente em seu spoiler, há mais soluções diferentes, então sua resposta é inválida.
ST3 28/03
Reivindicação forte, você pode fazer o backup com uma resposta própria para provar isso? Certamente não estou ciente de nenhuma mentira intencional no meu spoiler.
ProgrammerDan
portanto, quando a primeira solução é encontrada, eu a imprimo e encerro a regra no. 3 diz para encontrar todas as respostas. Há 19 como OP disse, não tenho certeza se é realmente 19, mas eu já tive uma tarefa semelhante antes, então saiba que há mais de uma.
ST3 28/03
Você precisa ler meu spoiler inteiro . Encontrei 12 soluções. Então você precisa ler todos os comentários anexados à pergunta. O OP diz que as respostas que são iguais em rotação são equivalentes e devem ser ignoradas. Outra pessoa perguntou se respostas iguais ao espelhamento errado deveriam ser ignoradas. Embora o OP, até o momento, não tenha respondido a essa consulta, tanto a minha quanto todas as outras soluções até o momento assumem que a resposta é "sim". Portanto, minha solução é totalmente completa, precisa e não há "mentiras" aqui. No entanto, se você quiser ver todas as 12 soluções, remova a return;instrução.
ProgrammerDan
Finalmente, isso é código de golfe. Considerando que adicionar uma return;declaração arbitrária aumente o comprimento do meu código em 7, seria insano adicioná-la se a resposta verdadeira incluísse todas as 12 soluções que são simplesmente versões rotacionadas / espelhadas uma da outra. Embora a loucura não possa ser descartada, neste caso, a adição de return;foi intencional e, como descrevi, com base no diálogo completo de perguntas e comentários , que você deve analisar antes de lançar acusações. Obrigado!
ProgrammerDan
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);}}

Compile com gcc -std=c99 -O3.

Imprime todas as soluções exclusivas de rotação e espelhamento de módulo, no formato a b c d ..., um por linha.

Tempo de execução: 0,8 segundos no meu computador.

Enumeramos as células na ordem h -> c -> s -> a -> l -> q -> e para máxima poda. De fato, a versão acima tenta apenas a cada 20 ^ 7 atribuições para essas variáveis. Então podemos calcular todas as outras células. Existe apenas uma solução única de rotação / espelhamento de módulo. Uma versão C ++ mais antiga, com menos golfe e ~ 20 vezes mais rápida (devido à poda) pode ser encontrada no Github

Niklas B.
fonte
Eu amo a abordagem amplamente aritmética aqui. Bravo! 1
ProgrammerDan
1

Matlab: 333 320 caracteres

Essa é uma abordagem bastante estúpida da força bruta que não usa recursão. Ele cria soluções parciais z, impressas no final. Cada coluna é uma solução; os elementos são listados az de cima para baixo. O tempo de execução é 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

Executando no 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
fonte