DESAFIO
Dado um conjunto de cartas agrupadas, organize-as no quadro para que cubram totalmente a área.
Representação do Conselho (também conhecido como SHIP DECK)
- O quadro é uma grade 6x6.
- Sempre haverá 36 quadrados no total.
- As colunas estão marcadas com AF.
- As linhas estão marcadas de 1 a 6.
Exemplo:
A B C D E F
+---+---+---+---+---+---+
1 : : : : : : :
+---+---+---+---+---+---+
2 : : : : : : :
+---+---+---+---+---+---+
3 : : : : : : :
+---+---+---+---+---+---+
4 : : : : : : :
+---+---+---+---+---+---+
5 : : : : : : :
+---+---+---+---+---+---+
6 : : : : : : :
+---+---+---+---+---+---+
ENTRADA (também conhecida como CRATES)
- Uma sequência multilinha que contém o conjunto de letras agrupadas.
- Caixas são feitas a partir de grupos de letras idênticas.
- As caixas são imutáveis, o que significa que não podem ser giradas ou invertidas.
- O ponto inicial de cada caixa está no canto superior esquerdo (deve ser levado em consideração ao mover uma caixa para o convés).
- Do ponto superior esquerdo de uma caixa, os seguintes quadrados idênticos só podem estar à direita ou abaixo.
- Qualquer carta pode ser usada para representar uma caixa. As caixas sempre começam na letra
[a]e sobem no alfabeto. - As caixas são rotuladas por sua letra (ou seja, caixa A, caixa B, etc.)
- O número de caixas pode variar (nem sempre é 10, apesar dos exemplos dados).
- Existem 24 caracteres separando cada bloco de caixas por linha. (início de [a] para início de [b] separados por 24 caracteres, etc.)
Exemplo:
[a][a][a] [b] [c][c]
[a] [b][b][b] [c]
[a] [b][b]
[d] [e] [f][f][f][f][f]
[d][d] [e]
[d][d] [e]
[e]
[e][e]
[g] [h] [i]
[g] [i]
[i]
RESULTADO
É necessário que você imprima uma série de comandos que colocam as caixas em posições no convés para que sejam completamente cobertas (sem espaços vazios).
O formato do comando é assim:
HAUL <crate> TO <column> <row>
ou seja, puxe para a 1
Para esclarecimento, sempre haverá uma solução para a entrada fornecida.
CASOS DE TESTE <- Clique para saber mais.
Entrada
[a][a][a] [b] [c][c][c]
[a][a] [b]
[a] [b][b]
[b][b]
[d] [e] [f]
[d] [f]
[d] [f]
[d]
[d]
[g][g] [h] [i]
[i][i]
[i]
[i][i]
[j][j][j]
Resultado
HAUL I TO A 1
HAUL B TO A 3
HAUL A TO B 1
HAUL J TO D 6
HAUL D TO F 1
HAUL F TO E 1
HAUL C TO C 5
HAUL G TO D 4
HAUL E TO D 3
HAUL H TO C 6
Resultado:
A B C D E F
+---+---+---+---+---+---+
1 : i : a : a : a : f : d :
+---+---+---+---+---+---+
2 : i : i : a : a : f : d :
+---+---+---+---+---+---+
3 : b : i : a : e : f : d :
+---+---+---+---+---+---+
4 : b : i : i : g : g : d :
+---+---+---+---+---+---+
5 : b : b : c : c : c : d :
+---+---+---+---+---+---+
6 : b : b : h : j : j : j :
+---+---+---+---+---+---+
PONTUAÇÃO
Isso é código-golfe, então a resposta mais curta em caracteres vence.
code-golf
sequence
decision-problem
parsing
board-game
Jonathan Picazo
fonte
fonte
Respostas:
Python 3.6,
435437385331 bytesLigue
F()com a corda da caixa.Conseguiu jogar muito mais:
- Analise a cadeia de caixa diretamente em vez de usar a
- Utilizou setdefault para salvar a primeira coordenada de um conjunto de caixas, para que a máscara de bits possa ser criada ao analisar a cadeia de caixas. Eliminando um loop for.
Versão anteriorrebiblioteca.Reestruturou o código para remover loops redundantes.
Versão anteriorCódigo anterior construiu uma lista de todas as posições de uma caixa em
F()e, em seguida, reiterou sobre a lista emR(). O novo código cria uma posição de uma caixaF()eR()tenta todas as posições possíveis.No código anterior,
R()coletou uma possível soluçãoaeF()iterou sobre a solução retornada. No novo código,R()imprime os comandos HAUL diretamenteExplicação
A idéia básica é representar o convés do navio e as caixas como mapas de bits. Usando bitmaps, mover uma caixa torna-se uma mudança de seu bitmap e verificar a sobreposição entre caixas torna-se um AND bit a bit e testa zero.
Código não destruído:
F()analisa a cadeia de definição de caixa e cria os mapas de bits. Um regex procura (linhas 9) em cada linha da cadeia de definição de caixas por caixas (uma letra seguida por um ']'). Quando uma correspondência é encontrada, a correspondente (linha, coluna) é adicionada a um dicionário digitado pela letra (linhas 11 a 13). Para o exemplo de cadeia de definição de caixa fornecida no problema:As coordenadas de cada caixa são normalizadas (linha 17), de modo que cada caixa começa em (0,0) e cada bloco tem uma unidade de largura (em vez de 3 a la '[a]').
Um bitmap é criado para cada caixa com base nas coordenadas normalizadas (linha 18).
O baralho é tratado como uma grade 7 x 7. A coluna 'G' e a linha 7 são usadas para detectar quando uma forma se estende para fora do tabuleiro. Um bitmap possui 1 se as caixas ocuparem o quadrado correspondente no baralho. Os bits de 48 a bit a 42 correspondem aos quadrados A1 a A7, os bits de 41 a 35 correspondem aos quadrados B1 a B7 e assim por diante.
R(used, bitmaps)depois, usa os bitmaps para procurar recursivamente canais de caixas que não tentam colocar duas caixas no mesmo quadrado.usedé uma máscara de bit indicando quais quadrados não podem ser usados porque já estão ocupados por uma caixa ou porque estão fora do tabuleiro (por exemplo, coluna G e linha 7).bitmapsé uma lista de caixas que ainda precisam ser colocadas.O caso base para a recursão é quando não há mais caixas para colocar, ou seja,
bitmapsestá vazio (linha 23). Nesse caso, True é retornado para indicar que uma solução foi encontrada.Caso contrário, um nome de caixa e seu bitmap serão removidos da lista de bitmaps (linha 26). Enquanto o bitmap da caixa não estiver vazio (linha 28), verifique se o posicionamento atual da caixa, representado pelo bitmap da caixa, está em conflito com quaisquer caixas colocadas anteriormente. Na linha 29,
not used & crate_bitmapé False seusedecrate_bitmapambos tiverem 1 na mesma posição de bit, indicando um conflito. Se não houver conflito,R()é chamado recursivamente (linha 30) para tentar colocar as caixas restantes.Se a chamada recursiva
R()retornar True, significa que uma solução foi encontrada e que o posicionamento atual das caixas faz parte dessa solução. Portanto, o comando correspondente para mover as caixas é impresso e True é propagado pelas chamadas recursivas (linhas 31 a 32).Quando criados
F(), cada bitmap de caixa representa os quadrados do convés que seriam ocupados pelas caixas se fossem colocados na posição A1. Mudar um bitmap um pouco para a direita corresponde a mover as caixas para a posição A2. Um deslocamento à direita de sete bits corresponde a mover as caixas para B1 etc. Por exemplo, os seguintes bitmaps representam caixas 'a' em várias posições:Se uma possível colocação de caixas não funcionar, porque entra em conflito com uma caixa colocada anteriormente (linha 30) ou porque não há uma colocação válida das caixas restantes (linha 31). As caixas são movidas para uma posição diferente deslocando a máscara de bit um pouco para a direita (linha 35).
Shiftcontrola quantos lugares o mapa de bits foi deslocado, o que corresponde à posição atual das caixas.Se o bitmap estiver vazio (zero), isso indica que todo o posicionamento possível foi tentado. Falso é retornado (linha 37) para indicar falha, para que uma chamada para o
R()início da recursão tente outro posicionamento para suas caixas.Para garantir que as caixas não se estendam para o lado do baralho, os bits correspondentes à coluna G e linha 7 são definidos
usedpara a chamada inicial paraR()(linha 20).4432676798719é o baralho vazio correspondente a0b0000001000000100000010000001000000100000011111111fonte
Python 2 , 864 bytes
Experimente online!
Explicação
Muitos bytes são usados para analisar as caixas bidimensionais inseridas através de uma única sequência. Caixas são representadas como uma lista aninhada de valores booleanos.
Depois que as caixas são analisadas, a função considera todas as posições possíveis de todas as caixas. Para fazer isso, ele se chama iterativamente. Quando encontra uma posição impossível (se a caixa for colocada fora do convés ou em cima de outra caixa), ela mata o galho da árvore de recursão atual para melhorar o desempenho.
Quando vê que uma certa combinação de veiculações resultou em um deck completamente coberto, imprime o histórico de veiculações de caixas gravadas e sai globalmente ao tentar uma divisão sem esperança. As instruções de transporte impressas são classificadas em ordem alfabética.
Python 2 , 812 bytes
Experimente online!
Explicação
A cadeia de caixas é analisada e transformada em um ninho listado de booleanos que representam cada caixa.
Uma função iterativa gera todas as listas possíveis de comprimento igual à quantidade de caixas fornecidas contendo os números inteiros
0 <= x < 36(todas as posições possíveis no convés do navio). Cada lista é interpretada como uma instrução para posicionar todas as caixas e testadas. Se a lista de instruções testada resultar em um deck sem espaços vazios, a lista de instruções deverá ser válida e será impressa.Sendo extremamente ineficiente, não testei no caso de teste fornecido, embora em cenários com menos caixas (consulte o link TIO). Como o algoritmo pesquisa todos os arranjos possíveis, ele tenta examiná-
36**10 = 3.656e15los. No entanto, em teoria , ainda deve funcionar.fonte
H/Mfora da declaração da função, pois tê-los na declaração torna as funções não reutilizáveis. Bom e velho Python.[i]com[b], ele funciona . O algoritmo pode ser aprimorado classificando primeiro as caixas para que as mais volumosas sejam testadas antes das pequenas.JavaScript, 366
Nota: esta função pode analisar uma entrada mais compacta, pois não se preocupa com o espaçamento de 24 caracteres, e buracos em caixas são permitidos.
Eu acho que poderia ser jogado um pouco mais, mas agora é curto e não muito lento, então eu gosto disso
Menos golfe
Casos de teste muitos deles
fonte