Damas mais longa jogada chinesa

12

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ão 01vem a seguir. A terceira linha está toda ocupada, então 111. A quarta linha tem dois espaços vazios e dois ocupados (indo da esquerda para a direita) 0011. Depois vem cinco 0, a 1e sete 0para 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)

Ypnypn
fonte
Eu brinco com minha tia-avó; nós dois somos razoavelmente bons. Este é um desafio interessante.
Cjfaure
1
Talvez você deva especificar mais sobre como a entrada é armazenada / quais bits vão para onde.
TheDoctor
Quais peças você pode "pular"? Do jeito que minha mãe e eu costumávamos tocar, você pode pular sobre qualquer peça em uma das 6 direções a qualquer distância (até o ponto oposto da peça em que você pulou), desde que não haja peça no caminho. caminho para esse salto. Outros jogam que você só pode pular sobre peças adjacentes.
Joe Z.
1
@ TheDoctor Adicionei uma explicação mais detalhada.
Ypnypn
Você pode esclarecer um detalhe: posso ocupar a mesma posição duas vezes? Suponho que não posso fazer um loop infinito, mas se eu puder atingir um local movendo-se para a esquerda-direita e depois pressioná-lo novamente, movendo-se da esquerda para a direita para baixo e para a direita, isso abrirá possibilidades.
Devon Parsons

Respostas:

1

Perl, 345 322

Edit: 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:

$_=<>;
$s=2x185;
substr$s,(4,22,unpack'C5(A3)*','(:H[n129148166184202220243262281300')[$i++],0,$_ 
    for unpack A.join A,1..4,13,12,11,10,9..13,4,3,2,1;
$_=$s;
sub f{
    my(@a,%h)=@_;
    $h{$_}++&&return for@a;
    $-+=$#a>$-;
    $s=~/^.{$a[0]}$_/&&f($+[1],@a)
        for map{("(?=.{$_}1.{$_}(0))","(?<=(0).{$_}1.{$_}.)")}0,17,18
}
f$+[0]while/1/g;
print$-
user2846289
fonte
Eu adicionei alguns casos de teste.
Ypnypn
Eles funcionam bem, mas são fáceis demais :-).
User2846289
2

C, 262 260

Có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 forloops para economizar dois pontos e vírgulas.

t[420],j,l,x,y;f(p,d){int z,q,k;for(k=6;k--;t[q]&!t[p+z]?t[q]=0,f(q,d+1),t[q]=1:0)z="AST?-,"[k]-64,q=p+z*2;l=d>l?d:l;}main(int i,char**s){for(i=840;i--;x>3&y>5&x+y<23|x<13&y<15&x+y>13?i>420?t[i-420]=49-s[1][j++]:t[i]||f(i,0):0)x=i%20,y=i/20%21;printf("%d",l);}

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 iloop conta para baixo, o zero fica no canto inferior direito):

....................
....................
...............#....
..............##....
.............###....
............####....
.......#############
.......############.
.......###########..
.......##########...
.......#########....
......##########....
.....###########....
....############....
...#############....
.......####.........
.......###..........
.......##...........
.......#............
....................
....................

O loop ipercorre 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).

0Nesse caso, na primeira vez em que preenche os quadrados, coloca um (falso) para um 1(ocupado) e um 1(verdade) para um 0(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 fque procura os movimentos.

fpesquisa 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

char s[999];                           //input string.
t[420],i,j,l,x,y;                      //t=board. i=board counter, j=input counter. l=length of longest hop found so far.

f(p,d){                                //p=position, d= recursion depth.
  //printf("%d,%d ",p,d);              //debug code: uncomment to show the nodes visited.
  int k,z,q;                           //k=counter,z=displacement,q=destination
  for(k=6;k--;)                        //for each direction
    z="AST?-,"[k]-64,                  //z=direction
    q=p+z*2,                           //q=destination cell
    t[q]&!t[p+z]?                      //if destination cell is empty (and not out of bounds) and intervening cell is full
      t[q]=0,f(q,d+1),t[q]=1           //mark destination cell as full, recurse, then mark it as empty again.
      :0;
  l=d>l?d:l;                           //if d exceeds the max recorded recursion depth, update l
}

main(){
  gets(s);                             //get input
  for(i=840;i--;)                      //cycle twice through t
    x=i%20,                            //get x
    y=i/20%21,                         //and y coordinates
    x>3&y>5&x+y<23|x<13&y<15&x+y>13?   //if they are in the bounds of the board
      i>420?
        t[i-420]=49-s[j++]             //first time through the array put 0 for a 1 and a 1 for a 0 ('1'=ASCII49)
        :t[i]||f(i,0)                  //second time, if t[i]=0,call f(). 
       //,puts("")                     //puts() formats debug output to 1 line per in-bounds cell of the board
      :0;
  printf("%d",l);                      //print output
}
Level River St
fonte