Lado a lado da unidade

8

fundo

Ao expandir e cancelar termos, é fácil mostrar a seguinte identidade:

insira a descrição da imagem aqui

No entanto, é um problema em aberto se todos os retângulos 1 / n por 1 / (n + 1) podem agrupar o quadrado da unidade.

A tarefa

Seu programa deve usar um número inteiro positivo N como entrada de qualquer maneira conveniente e agrupar todos os retângulos abertos de 1 / n-por-1 / (n + 1) com n entre 1 e N, inclusive no quadrado da unidade, para que não se sobreponham dois .

Para cada retângulo, você deve gerar os seguintes números inteiros em ordem:

  • 1 se as arestas horizontais forem mais longas que as arestas verticais, caso contrário, 0
  • O numerador e o denominador da coordenada x do canto inferior esquerdo
  • O numerador e o denominador da coordenada y do canto inferior esquerdo

Observe que assumimos o quadrado da unidade como sendo (0, 1) x (0, 1), com valores x executando da esquerda para a direita e valores y executando de baixo para cima.

A saída final esperada é a concatenação desses números inteiros para cada retângulo em ordem crescente de n, em qualquer formato conveniente (por exemplo, impresso em stdout ou como uma lista retornada de uma função).

Exemplo de entrada e saída

Entrada:

3

Resultado:

0 0 1 0 1 1 1 2 0 1 1 1 2 1 3

Isso analisa da seguinte maneira:

0 (0/1, 0/1)  1 (1/2, 0/1)  1 (1/2, 1/3)

Pontuação

Este é um desafio do código-golfe, portanto a resposta com o menor número de bytes vence. No entanto, seu algoritmo também deve ser razoavelmente eficiente; deve ser capaz de executar para todos N<=100em um total de cerca de 10 minutos.

Sua solução deve fornecer soluções válidas para todos N<=100, mas algoritmos comprovadamente completos também são bem-vindos, mesmo que não sejam os mais curtos.

code-golf geometry search packing user1502040
fonte
Como esse é um problema em aberto, existe um limite para o maior valor de $ N $ para o qual nosso algoritmo deve estar garantido para funcionar?
Greg Martin
@ GregMartin, você deve executar com sucesso o seu programa para N de 1 a 20. O Brownie aponta se for possível provar que seu algoritmo teve êxito ou refutou a conjectura.
user1502040
Para N≤20, a saída pode ser apenas codificada ... é sua intenção permitir isso? Não é um simples algoritmo publicado que permite, pelo menos N = 1000000000 ....
Greg Martin
OK, alterei o limite de 20 para 100. #
user1502040
Oh, Deus. Ainda não aprendi soma ao infinito, portanto não compreendo nada disso.
Matthew Roh

Respostas:

2

Haskell, 263 262 bytes

import Data.Ratio;f m=let{(#)n z|n>m=[[]]|True=[a:y|(a,j)<-[((o,x,y),[c|c<-(u&w,h-v,x,g):(w-u,h&v,a,y):z,c/=b])|b@(w,h,x,y)<-z,(o,u,v)<-[(o,1%(n+1-o),1%(n+o))|o<-[0,1]],(a,g)<-[(x+u,y+v)|u<=w,v<=h],let(&)p q|w>h=p|True=q],y<-(n+1)#j]}in(1#[(1%1,1%1,0%1,0%1)])!!0

Isto segue o algoritmo descrito em Paulhus 1997, An Algorithm for Packing Squares , doi: 10.1006 / jcta.1997.2836 . A principal observação no artigo, que é empiricamente, se não teoricamente verificada, é que a região que resta depois de colocar um retângulo em uma caixa pode ser dividida em duas sub-caixas cujo preenchimento pode então ser considerado independente.

Em vez de encontrar a sub-caixa com a menor largura para caber no próximo retângulo, o código realiza uma pesquisa em todas as sub-caixas possíveis; na prática, isso não torna uma desaceleração apreciável para n <100.

A saída está na forma de uma lista de entradas como tuplas com o marcador de fração %ainda incluído. Os números inteiros na saída formatada estão na ordem desejada, mas, estritamente falando, seria necessário algum pós-processamento para produzir apenas a lista de números inteiros.

Exemplo de execução:

*Main> f 5 (0,0 % 1,0 % 1),(0,1 % 2,0 % 1),(0,1 % 2,1 % 2),(0,3 % 4,1 % 2),(1,1 % 2,5 % 6)

Editar: removido um espaço incorreto após a let.

halfflat
fonte