Tijolos e estabilidade definidos
Esta pergunta usa a mesma definição de tijolos e estabilidade que a estrutura de tijolos é estável?
Vamos [__]representar um tijolo de alvenaria e
.
.
.
BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK? . . .
BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?
representam um arranjo ou estrutura arbitrária desses tijolos, com todas as outras linhas deslocadas por meio tijolo, como é habitual na construção de tijolos. A estrutura pode se estender para cima e para a direita indefinidamente, mas a representação da string sempre será um bloco de texto perfeitamente retangular (com espaços finais, quando necessário) cuja largura é divisível por 4.
Cada um BRK?na estrutura pode ser um tijolo ( [__]) ou um espaço vazio (4 espaços).
Por exemplo, uma estrutura possível (instável - continue a ler) é
[__] [__] [__]
[__] [__]
[__][__] [__]
A estabilidade de uma estrutura é importante, e uma estrutura só é estável se cada um de seus tijolos for estável.
Existem três maneiras pelas quais um tijolo individual pode ser estável:
- Qualquer tijolo no chão (a linha mais baixa de tijolos) é estável.
Qualquer tijolo que tenha dois tijolos diretamente abaixo é estável:
[__] <- this brick is stable [__][__] <- because these bricks hold it upQualquer tijolo que tenha um tijolo acima e abaixo do mesmo lado é estável:
[__] [__] [__] [__] <- these middle bricks are stable [__] [__] because the upper and lower bricks clamp them in [__] [__] [__] [__] <- these middle bricks are NOT stable [__] [__]
(Sim, eu sei que essas regras não são fisicamente precisas.)
O último desafio foi determinar se uma estrutura era estável. Este é sobre estabilizar aqueles que não são.
Desafio
Escreva um programa que inclua um arranjo potencialmente instável de tijolos e adicione novos tijolos a espaços vazios de tijolos para tornar tudo estável, imprimindo o resultado. Isso deve ser feito sem aumentar as dimensões gerais do bloco de texto de entrada.
O objetivo é criar um algoritmo que torne a estrutura estável, adicionando o mínimo possível de tijolos.
Este JSFiddle ( fonte ) permite gerar arranjos aleatórios de tijolos para uso durante o teste do seu programa. (Gostaria de poder empilhar trechos .) WidthÉ o número de tijolos na camada base, Heighto número de camadas de tijolos e Densitya fração dos espaços de tijolos preenchidos.
Por exemplo, com Width = 5, Height = 3, Density = 0.6uma saída possível é
....[__]....[__]....
..[__]....[__]......
[__]............[__]
Uma maneira de estabilizar isso com 4 novos tijolos é
....[__]....[__]....
..[__][__][__][__]..
[__][__]....[__][__]
Seu programa deve ser capaz de estabilizar qualquer estrutura de blocos que o JSFiddle possa gerar.
- Isso inclui a cadeia vazia (que é considerada estável).
- O tijolo sempre será
[__]. Os pontos (.) são usados apenas para maior clareza. Seu programa pode usar pontos ou espaços para espaço vazio. - A estrutura já pode estar estável, caso em que nada precisa ser feito (além de imprimi-lo).
- O JSFiddle sempre gera estruturas que podem ser estabilizadas (evitando
Width = 1e tijolos nos cantos superiores). Você pode confiar nisso. (Preencher todos, exceto os cantos superiores, certamente estabilizará as coisas, mas isso claramente não é o ideal.) - Suponha que não haja entrada inválida. Tome a entrada como string como quiser. Imprima a estrutura estabilizada em stdout ou similar.
- Lembre-se de que as dimensões do bloco de texto não devem mudar de tamanho.
- Tijolos pré-existentes não podem ser movidos ou removidos. A colocação de novos tijolos deve seguir o padrão de grade de deslocamento em todas as outras linhas. Todos os tijolos devem estar completamente dentro dos limites.
- É recomendável (mas não obrigatório) que você imprima os tijolos preexistentes em
[XX]vez de[__], para que as pessoas possam ver melhor como sua solução funciona.
Pontuação
Na parte inferior do JSFiddle, existem 8 arranjos instáveis pré-definidos de tijolos. (Eles usam [__]e .devem permanecer assim, a menos que você esteja usando [XX]e / ou não.) Alguns são aleatórios e outros que eu mesmo criei. Para calcular sua pontuação, execute o programa em cada uma delas e some o número de novas peças adicionadas a cada uma delas.
Quanto menos novos tijolos você adicionar, melhor. A finalização com a menor pontuação vence. Em caso de empate, a resposta mais antiga vence.
Se as coisas ficarem controversas, posso adicionar mais alguns casos predefinidos e julgar o vencedor com base neles.
Notas adicionais
- Seu programa precisa ser executado na ordem dos minutos em um computador moderno, para largura e altura da grade inferior a 100. (Máximo de 10 minutos em um computador como este .)
- Você não pode codificar sua saída para as 8 estruturas predefinidas. Seu programa deve tratá-los como trataria qualquer outro arranjo.
- Inclua um exemplo de saída ou dois, ou qualquer estrutura interessante que você queira compartilhar. :)
- Esse problema está relacionado à localização de uma árvore de abrangência mínima .
fonte
Respostas:
Java - 5.056 tijolos
O código fonte é visível aqui .
O código é executado em alguns milissegundos para qualquer uma das 8 entradas de pontuação. Existem algumas saídas visivelmente abaixo do ideal, particularmente na torre cruzada e nos casos de 99x99. Tenho várias idéias sobre como melhorar a rotina, mas é bastante volumosa como está e, portanto, deixarei em paz por enquanto.
Os resultados massacram as leis da física em uma extensão cômica. : D
Algumas amostras são mostradas abaixo.
Saída 20x20, 0,03
Saída simples da casa
fonte
Python, 18992
Essa é a solução mais simplista e a pior pontuação possível. É apenas para referência; a coisa a ser batida. Preenche todos os espaços vazios, exceto os dois cantos superiores, com tijolos, garantindo estabilidade.
Para usar, copie a estrutura inicial entre aspas triplas na parte superior do programa.
Aqui é executado na casa, adicionando 609 tijolos:
O número de tijolos adicionados a cada uma das 8 estruturas predefinidas em ordem é
fonte