Introdução
Você tem a infelicidade de ficar preso em um carro em fuga em uma pista de obstáculos. Todos os recursos do carro não respondem, exceto o sistema de direção, que está danificado. Pode dirigir em linha reta ou virar à direita. O carro pode ser guiado para a segurança?
Mecânica
Seu carro começa no canto superior esquerdo de um mapa 8x8 e está tentando obter segurança no canto inferior direito. O carro tem uma orientação (inicialmente à direita), medida em incrementos de 90 graus. O carro pode executar uma das duas ações:
- Dirija um quadrado para frente ou
- Gire 90 graus no sentido horário e, em seguida, dirija um quadrado à frente
Observe que o carro não consegue girar bruscamente o suficiente para executar uma curva de 180 graus em um único quadrado.
Algumas das praças são obstáculos. Se o carro entrar em uma praça de obstáculos, ele trava. Presume-se que tudo fora do percurso 8x8 seja um obstáculo; portanto, sair do percurso equivale a bater.
O quadrado inferior direito é o quadrado seguro, que permite que o carro escape da pista de obstáculos. Presume-se que o quadrado inicial e o quadrado seguro não sejam obstáculos.
Tarefa
Você deve escrever um programa ou função que tenha como entrada uma matriz 8x8 (matriz, lista de listas etc.), representando a pista de obstáculos. O programa retorna ou imprime um booleano, ou algo semelhante de verdade. Se é possível que o carro chegue ao quadrado seguro sem bater (ou seja, se o mapa for solucionável), a saída é True
, caso contrário, é False
.
Pontuação
Regras padrão de código de golfe - o vencedor é o código com o menor número de bytes.
Bônus:
Se, para um mapa solucionável, o seu código gerar uma série válida de entradas do motorista que guiam o carro até o quadrado seguro, deduza 10 pontos percentuais da sua pontuação. Um exemplo de formato de saída pode ser
SRSSR
(indicando Reta, Direita, Reta, Reta, Direita). Esta saída substituiria aTrue
saída padrão .Se, para um mapa insolúvel, a saída do seu código distingue entre situações em que uma falha é inevitável e situações em que é possível percorrer a pista de obstáculos para sempre, deduza 10 pontos percentuais da sua pontuação. Um exemplo de saída pode ser
Crash
se um acidente for inevitável ouStuck
se o carro ficar preso na pista de obstáculos para sempre. Essas saídas substituiriam aFalse
saída padrão por um mapa insolúvel.
Exemplo
Se o programa receber uma matriz 8x8 como esta:
[[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[1, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 0, 0, 1, 0]]
Seria interpretado como um mapa como este, com quadrados pretos indicando obstáculos:
E uma solução possível pode ser:
Como existe uma solução, o programa deve retornar / imprimir True
para este mapa. A sequência de movimentos mostrada aqui é SSSSRSRRRSRSSRRRSSRSSS
.
Crash
eStuck
. Eles estão aqui por causa de quanto tempo eles são. Linha 2 preenchida, todo o resto vazio ->Crash
. Linha 7 preenchida, todo o resto vazio ->Stuck
Respostas:
JavaScript (ES6) - 122
124148bytes162172178187190193208Muito obrigado ao Optimizer e DocMax por sugestões úteis sobre como melhorar este código:
Devoluções
true
(verdadeiras) para solucionáveis efalse
(falsas) para insolúveis.Funciona apenas no Firefox a partir de hoje, devido aos recursos do JavaScript 1.7.
Placa de teste
fonte
D=(x,y,d,t,a)=>!t[i=x+y*8+d*64]&&(t[i]=1,x+=d==0?1:d==2?-1:0,y+=d==1?1:d==3?-1:0,x==7&&y==7||!((x|y)&~7||a[y][x])&&G(x,y,d,t,a));G=(x,y,d,t,a)=>D(x,y,d,t,a)||D(x,y,d+1&3,t,a);F=a=>G(0,0,0,[],a)
.D=d=>!t[i=x+y*8+d/4]&&(t[i]=1,x+=d?d^2?0:-1:1,y+=d^1?d^3?0:-1:1,x==7&&y==7||!((x|y)&~7||b[y][x])&&G(x,y,d));G=(X,Y,d)=>D(d,x=X,y=Y)||D(d+1&3,x=X,y=Y);F=a=>G(0,0,0,b=a,t={})
- Testado.[[0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
. Isso deve dar falso.x
ey
são ambos globals, você não pode executar dois casos de teste antes de recarregar a página ...x+=d?d^2?0:-1:1
porx+=d&1?0:1-d
ey+=d^1?d^3?0:-1:1
pory+=d&1&&2-d
.Python 2 - 123
125 133 146 148 150 154 160True
no sucesso,False
no fracasso.Você deve fornecer entrada como
f(b=var_containing_board)
.Versão Lambda - 154
Retorna
0
(falsy) por falha,True
por sucesso.Agradecemos a Will e Brandon por tornar a função mais curta que a lambda. Também para adicionar mais rolagem horizontal: D
Agradecimentos ao xnor pela lógica e quebra de bits superiores!
Editar nota: Estou razoavelmente confiante de que
b[y][x]
nunca será executado quando estiver fora do alcance. Como estamos fora do quadro, a verificação do históricos in c
seráFalse
. Então a verificação do limite(x|y)&8
será8
. Então, o python nem verifica o último valor de==
porque os dois primeiros já são diferentes.fonte
x|y>7or
funciona, masx|y<0or
não ...0o
.C (GNU-C), 163 bytes * 0,9 = 146,7
#C (GNU-C), 186 bytes * 0,9 = 167,4Minha nova versão usa um número inteiro assinado em vez de não assinado. Anteriormente, eu tinha medo do turno certo assinado, mas percebi que, como o bit do sinal é o quadrado do gol, não importa o que acontecer depois disso.
A função usa uma matriz de bits (uns representam quadrados bloqueados) na forma de um número inteiro de 64 bits. Os bits são organizados do menos para o mais significativo da mesma maneira que você leria um livro. Ele retorna -1 para um acidente, 0 para dirigir para sempre ou 1 para escapar para o canto inferior direito.
Programa de teste
Resultado
Conversor de matriz para hexadecimal Python:
fonte
memset(&M,~1,8)
(15 caracteres) porM=~(-1ULL/255)
(14 caracteres).P(0x00fefefefefefefe);
= (deve ser acertado em linha reta para o canto superior direito, uma curva, direto para a esquina. O mesmo paraP(0x00eeeeeeeeeeeeee);
(beco sem saída na 4ª col.) Eu não acho que você precise atribuira
inicialmente.0x7f7f7f7f7f7f7f00
. Além disso, é necessário inicializara
porque, posteriormente, ele é modificado apenas por ORing em bits adicionais, portanto, não posso permitir que um bit indesejado seja definido inicialmente.Python, 187
213207 caracteres, bônus de 10% para o caminho de impressão
Na entrada de teste, ele encontra um caminho ligeiramente diferente:
SSSSRSRSRRSSRSSRRSRSSRSSSSS
A abordagem geral é primeiro transformar a entrada em espaços e
o
s. Os espaços têm um hexadecimal20
, portanto, todos os quatro bits inferiores estão desmarcados.o
tem um hexadecimal de6F
, então os quatro bits baixos estão todos definidos.Uma borda de
o
s é colocada ao redor do quadro para que não tenhamos que nos preocupar com índices ruins.Enquanto andamos sobre o tabuleiro, usamos os bits em cada bloco para ver se somos autorizados a passar ao chegar daquele lado. Dessa forma, evitamos loops infinitos. Não basta ter um único booleano por bloco, pois a direção da saída depende da direção da entrada, para que os blocos possam ser visitados duas vezes.
Em seguida, fazemos uma pesquisa recursiva por um caminho seguro.
fonte
9
no lugar dew=len(b[0])+1
etc?p==79
porp-79
. Eu recebi um erro de sintaxe ao fazer isso nos dois sentidos sem um espaço antes doelse
. Eu acho que esse truque só funcionaif
.-~x
==x+1
mas os dois operadores unários têm maior precedência que multiplicação, divisão e módulo! Então(d+1)%4
poderia ser-~d%4
! Isso também funcionaria,x-1
mas apenas use~-x
.Javascript -
270 - 20% = 216262 - 20% = 210 bytesComo deve haver pelo menos uma solução que receba os dois bônus (e não leve a uma profundidade de pilha ridícula;) ...
Minificado:
Expandido:
v
é uma hashtable com chaves que são triplos de estado(x,y,d)
correspondentes à coordenada (x, y) e à direção da entradad
. Cada chave possui um valor associado, que é a sequência de movimentosS
(retos) eR
(vire à direita) necessários para alcançar o estado representado pela chave.O código também mantém uma pilha de triplos (em variável
n
) que ainda não foram processados. A pilha contém inicialmente apenas o triplo (0,0,0), correspondente ao estado em que o carro está voltado para a direita na célula (0,0). No loop externofor( S = ... )
, a rotina verifica se existem triplos não processados. Nesse caso, ele executa cada triplo não processado pelo loop internon.map( ...
,.O loop interno faz cinco coisas:
K
entanto, sinalizamos a saída FALSE como (travada), pois encontramos pelo menos um loop em que o carro pode continuar a circular para sempre sem bater.v
) e à pilha de triplos não processados (m
) para a próxima passagem do loop externov
, seu valor é definido como o valor do estado de origem (a sequência de movimentos) maisR
ou comS
base no movimento atualx
ey
for7
, o valor do estado de origem (a sequência de movimentos executados para atingir o estado de origem) é copiadoS
, pois essa sequência de movimento é uma solução para o problemaApós o loop interno terminar,
n
(a pilha) é substituída porm
(a nova pilha).Depois que o loop externo termina (nenhum novo estado foi alcançado), a função retorna sua saída. Se a célula (7,7) foi atingida,
S
ela conterá uma sequência de movimentos que levam a essa célula, e isso é gerado. Se a célula não foi atingida,S
será a string vazia e a rotinaO
passará para a saída , que conteráK
(travada) se e somente se um loop for encontrado ouC
(acidente) se o carro inevitavelmente falhar.fonte
Python 339 - 10% = 305 bytes
Eu usei uma pesquisa recursiva em profundidade, que é encerrada no início do sucesso via
exit
. Também imprime o caminho com sucesso na forma de00001010101010101010101110100111001000
,0
para reto,1
para direita. A resposta será mais longa que a ideal, pois é a primeira. Tenho certeza de que algumas otimizações no algoritmo podem reduzir bastante a contagem de bytes.fonte
a
'sfor
loop. Você também não precisa de espaços ao redor dos operadores, por exemplo(v+1) % 4
- ->(v+1)%4
. Você também pode participar de várias instruções em uma única linha, utilizando;
, se não existeif
oufor
, etc na linha, por exemploc(l+"0");c(l+"1")
. Alguns outros campos de golfe:x,y,v=0,0,2
,x|y>7 or x|y<0
,x==y==7
. Boa sorte :)