O quebra - cabeça das quinze é peculiar, pois apenas metade dos possíveis estados de arranjo são solucionáveis. Se você virar as peças 14 e 15, não há como deslizar os blocos para que eles sejam virados para trás.
Sua tarefa é criar um programa que aceite uma lista de números inteiros no formato de sua escolha (contendo exatamente uma instância de cada um dos números de 0 a 15, com 0 sendo o espaço em branco) representando o estado de um arranjo de blocos em uma grade 4x4 e gera um único valor booleano determinando se a grade é solucionável ou não.
O código mais curto para fazer isso em qualquer idioma vence.
Respostas:
Geléia , 9 bytes
Um link monádico que aceita uma lista dos números inteiros lidos na ordem das linhas principais alternando entre esquerda-direita e direita-esquerda, o que produz
0
se for solucionável e1
se não for (para inverter isso, adicione¬
à direita do código).Experimente online! (este exemplo é um quadro em que apenas 12 se encaixa)
Quão?
Semelhante à resposta de John Dvorak , calculamos paridades e utilizamos uma ordem de entrada semelhante a cobra para simplificar a paridade do tabuleiro de damas, embora, em vez de verificar a igualdade de paridade, somamos a contagem fora de ordem com índices diferentes de zero e testamos se isso é ímpar:
fonte
J, 28 caracteres
A ordem de entrada é principal com linhas lidas alternadamente da esquerda para a direita e da direita para a esquerda em um único caminho na tabela. Assume que o zero pertence ao canto superior esquerdo.
Uso no Windows:
Explicação:
<nul set /p=
é usado para impedir uma nova linha na entrada, queecho
produz aquilo".
que não gosta. Claro, o Unix suportaecho /n
.v&.".&.stdin''
lê "v em análise em stdin" significa "entrada", analise a entrada e, em seguida, v, desfaça a análise (= formato) e desfaça a entrada (= saída) ".1!:1]3
é um caractere mais curto, mas não possui um inverso definido.C.!.2
significa "paridade de permutação". Retorna1
(paridade par) ou_1
(paridade ímpar). Isso é,_1^inversions
_1^i.&0
significa "-1 à potência do índice de 0".C.!.2=_1^i.&0
significa "a paridade de permutação é igual à paridade de posição do furo?"Isso funciona para uma placa 4x4, mas se a posição final desejada for maior da linha da esquerda para a direita, a permutação para a posição resolvida tem um número ímpar de inversões e, portanto, uma paridade ímpar. Além disso, a paridade é revertida (para qualquer ordem de entrada) quando a posição desejada do furo se move da parte superior esquerda para a parte inferior direita. Nos dois casos, a correção é de um caractere: add
-
after=
para reverter a paridade esperada.Prova de correção:
Após cada movimento, o zero troca uma posição com algum número, invertendo a paridade de permutação. O zero também alterna entre as posições quadriculado em branco e preto, indicadas por posições ímpares e pares na ordem de entrada. Portanto, essa condição é necessária. Também é suficiente pelo argumento da contagem: é do conhecimento geral que exatamente metade das posições é solucionável. Essa condição filtra exatamente metade das posições possíveis.
fonte