Nas damas chinesas , uma peça pode se mover pulando sobre qualquer outra peça ou fazendo uma sequência desses saltos. Sua tarefa é encontrar a maior seqüência possível de saltos.
Entrada
Uma sequência de 121 zeros ou uns, cada um representando um local em um quadro. Um zero significa que o local está vazio; um significa que o lugar está ocupado. As posições são listadas da esquerda para a direita; de cima para baixo. Por exemplo, a entrada dessa configuração seria
1011110011000001000000000000000000000000100000000001000000000000000000000000000001000000000000000000000001000001100111111
Explicação:
O local mais alto é ocupado por uma peça verde, então o primeiro dígito na entrada é
1
. A segunda linha tem uma posição vazia e, em seguida, uma posição ocupada, então01
vem a seguir. A terceira linha está toda ocupada, então111
. A quarta linha tem dois espaços vazios e dois ocupados (indo da esquerda para a direita)0011
. Depois vem cinco0
, a1
e sete0
para a próxima linha e assim por diante.
Como nessa configuração, há um canto apontando para cima. Pode haver qualquer número de peças no quadro (de 1 a 121). Observe que peças de cores diferentes não são representadas de maneira diferente.
Resultado
O comprimento máximo de um salto legal, usando qualquer peça no quadro. Você não pode visitar o mesmo local mais de uma vez (incluindo as posições inicial e final). No entanto, você pode pular a mesma peça mais de uma vez. Se não houver salto legal, produza 0
. Não considere se existe um movimento legal sem salto.
Por exemplo, a saída para a configuração descrita acima é 3
.
A entrada e a saída podem ser feitas por meio de stdin e stdout, por argumentos de linha de comando, por chamadas de função ou por qualquer método semelhante.
Casos de teste
Entrada:
0100000010000000000000000100000000000000000000000000000001010010000000000000000000000101000000000000000000100000000100001
Saída: 0
(não há duas peças uma ao lado da outra)
Entrada:
0000000000111100000000011100000000011000000000100000000000000000000000000000000000000000000000000000000000000000000000000
Saída: 1
(configuração inicial para um jogador no canto superior esquerdo)
fonte
Respostas:
Perl,
345322Edit: jogado, ligeiramente.
Mais casos de teste seriam bons, mas por enquanto parece que funciona. Adicionarei comentários mais tarde, se necessário. Com novas linhas e recuo para facilitar a leitura:
fonte
C,
262260Código de golfe ( código de depuração e espaço em branco desnecessário removido. Alterado de entrada via stdin para entrada via linha de comando e aproveitou a oportunidade para declarar a variável i). Última edição: código movido para colchetes de
for
loops para economizar dois pontos e vírgulas.Explicação
Isso depende de uma placa 20x21 que se parece com isso, inicialmente preenchida com zeros quando o programa é iniciado (essa arte ASCII foi gerada por uma versão modificada do programa e, à medida que o
i
loop conta para baixo, o zero fica no canto inferior direito):O loop
i
percorre esse quadro duas vezes, usando x e y para calcular se um quadrado realmente pertence ao tabuleiro de damas ou não (isso requer 6 desigualdades separadas em x e y).0
Nesse caso, na primeira vez em que preenche os quadrados, coloca um (falso) para um1
(ocupado) e um1
(verdade) para um0
(desocupado). Essa inversão é importante, porque todos os quadrados fora dos limites já contêm um 0, o que significa que eles se assemelham a quadrados ocupados e é claro que eles não podem ser inseridos, sem a necessidade de uma verificação específica.Na segunda vez, se o quadrado estiver ocupado (contém 0), ele chamará a função
f
que procura os movimentos.f
pesquisa recursivamente nas 6 direções possíveis codificadas por +/- 1 (horizontal), +/- 20 (vertical) e +/- 19 (diagonal) codificadas na expressão"AST?-,"[k]-64
. Quando encontra uma ocorrência, ela define a célula como 0 (ocupada) antes de se chamar recursivamente e, em seguida, a define como 1 (vazia) quando a função é retornada. O valor da célula deve ser alterado antes da chamada recursiva para evitar entrar nessa célula mais de uma vez.Código ungolfed
fonte