Seu carro só vira à direita!

49

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:

  1. Dirija um quadrado para frente ou
  2. 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 a Truesaí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 Crashse um acidente for inevitável ou Stuckse o carro ficar preso na pista de obstáculos para sempre. Essas saídas substituiriam a Falsesaí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:

insira a descrição da imagem aqui

E uma solução possível pode ser:

insira a descrição da imagem aqui

Como existe uma solução, o programa deve retornar / imprimir Truepara este mapa. A sequência de movimentos mostrada aqui é SSSSRSRRRSRSSRRRSSRSSS.

fosgênio
fonte
2
Eu escrevi alguns casos de teste incrivelmente simples para Crashe Stuck. 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
undergroundmonorail
3
Estou confuso sobre pontos percentuais (ao contrário de porcentagens). Obter um bônus multiplica sua pontuação por 0,9. Obter os dois multiplica por 0,8 ou 0,9 ^ 2?
Undergroundmonorail
3
Claro, S e C estão bem. Minhas saídas eram apenas sugestões.
fosgênio
13
"Dois erros não fazem um acerto, mas três esquerdas fazem." - Papai.
precisa saber é o seguinte
2
"Seu carro pode fazer apenas zero ou três esquerdas!"
feersum

Respostas:

17

JavaScript (ES6) - 122 124 148 162 172 178 187 190 193 208 bytes

Muito obrigado ao Optimizer e DocMax por sugestões úteis sobre como melhorar este código:

F=a=>(D=(x,y,d)=>!D[i=[x,y,d]]&&(D[i]=1,x-=~d%2,y-=~-~d%2,x*y==49||!((x|y)&8||a[y][x])&&(D(x,y,d)||D(x,y,~-d%4))),D(-1,0))

Devoluções true(verdadeiras) para solucionáveis ​​e false(falsas) para insolúveis.

Funciona apenas no Firefox a partir de hoje, devido aos recursos do JavaScript 1.7.

Placa de teste

eu e meu gato
fonte
11
Este é 193 bytes: 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).
Optimizer
11
172: 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.
Optimizer
11
@Optimizer Ainda estou me tornando verdadeiro para o segundo caso de teste [[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.
eu e meu gato
2
Isso é porque uma vez xe ysão ambos globals, você não pode executar dois casos de teste antes de recarregar a página ...
Optimizer
11
Você pode economizar mais 9, substituindo x+=d?d^2?0:-1:1por x+=d&1?0:1-de y+=d^1?d^3?0:-1:1por y+=d&1&&2-d.
DocMax
10

Python 2 - 123 125 133 146 148 150 154 160

Trueno sucesso, Falseno fracasso.

def f(h=1,v=0,b=0,x=0,y=0,c=[]):s=x,y,h,v;a=b,x+h,y+v,c+[s];return(s in c)==(x|y)&8==b[y][x]<(x&y>6or f(h,v,*a)|f(-v,h,*a))

Você deve fornecer entrada como f(b=var_containing_board).

Versão Lambda - 154

Retorna 0(falsy) por falha, Truepor sucesso.

F=lambda b,x=0,y=0,h=1,v=0,c=[]:0if[x,y,h,v]in c or x|y>7or x|y<0 or b[y][x]else x&y==7or F(b,x+h,y+v,h,v,c+[[x,y,h,v]])or F(b,x+h,y+v,-v,h,c+[[x,y,h,v]])

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órico s in cserá False. Então a verificação do limite (x|y)&8será 8. Então, o python nem verifica o último valor de ==porque os dois primeiros já são diferentes.

FryAmTheEggman
fonte
11
A versão funcional pode combinar os dois ifs que ambos retornam; como retorno sozinho retorna Nenhum que seja falso, você também não precisa retornar 0..; apenas retornando o favor;)
Será
Se você virar as verificações que você pode combinar os dois ifs também
Will
Você pode combinar as duas declarações de retorno?
Brandon
11
@ Will Obrigado, eu sabia que havia uma maneira melhor de fazer isso: D Hum, não consegui encontrar espaços para remover que não me causem erro de sintaxe. Eu realmente não entendo por que x|y>7orfunciona, mas x|y<0ornão ...
FryAmTheEggman
11
Você pode fazer um literal octal começando com 0o.
precisa saber é
9

C (GNU-C), 163 bytes * 0,9 = 146,7

#C (GNU-C), 186 bytes * 0,9 = 167,4

Minha 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.

g(long long o) {
    typeof(o) a=0,i=255,r=1,u=0,l=0,d=0,M=~0LLU/i,D;
    for( ;i--;d = D<<8&~o)
        a |= D = d|r,
        r = (r|u)*2&~M&~o,
        u = (u|l)>>8&~o,
        l = ((l|d)&~M)/2&~o;
    return a<0?:-!(d|r|u|l);
}

Programa de teste

f(long long o){typeof(o)a=0,i=255,r=1,u=0,l=0,d=0,M=~0LLU/i,D;for(;i--;d=D<<8&~o)a|=D=d|r,r=(r|u)*2&~M&~o,u=(u|l)>>8&~o,l=((l|d)&~M)/2&~o;return a<0?:-!(d|r|u|l);}
{
    char* s[] = {"Crash", "Stuck", "Escape"};
    #define P(x) puts(s[f(x)+1])
    L ex = 0x4640500C0A034020;
    P(ex);
    L blocked = 0x4040404040404040;
    P(blocked);

    L dead = 0x10002;
    P(dead);

    return 0;
}

Resultado

Escape
Stuck
Crash

Conversor de matriz para hexadecimal Python:

a2b=lambda(A):"0x%X"%sum(A[i/8][i%8]<<i for i in range(64))
feersum
fonte
11
Substitua memset(&M,~1,8)(15 caracteres) por M=~(-1ULL/255)(14 caracteres).
R ..
@R .. Nice! -4 bytes disso.
feersum
2
Eu gosto do formato de entrada - muito legal!
fosgênio
Estou recebendo 'crash' para P(0x00fefefefefefefe);= (deve ser acertado em linha reta para o canto superior direito, uma curva, direto para a esquina. O mesmo para P(0x00eeeeeeeeeeeeee);(beco sem saída na 4ª col.) Eu não acho que você precise atribuir ainicialmente.
@tolos Você transpôs a ordem principal da linha / coluna. Para ter a linha superior e a coluna direita abertas, deve ser 0x7f7f7f7f7f7f7f00. Além disso, é necessário inicializar aporque, posteriormente, ele é modificado apenas por ORing em bits adicionais, portanto, não posso permitir que um bit indesejado seja definido inicialmente.
feersum
6

Python, 187 213

207 caracteres, bônus de 10% para o caminho de impressão

b=map(ord," "*9+" ".join("".join("o "[i]for i in j)for j in input())+" "*9)
def r(p,d,s):
 p+=(1,9,-1,-9)[d]
 if b[p]&1<<d:b[p]^=1<<d;return(s+"S")*(p==79)or r(p,d,s+"S")or r(p,(d+1)%4,s+"R")
print r(8,0,"")

Na entrada de teste, ele encontra um caminho ligeiramente diferente: SSSSRSRSRRSSRSSRRSRSSRSSSSS

A abordagem geral é primeiro transformar a entrada em espaços e os. Os espaços têm um hexadecimal 20, portanto, todos os quatro bits inferiores estão desmarcados. otem um hexadecimal de 6F, então os quatro bits baixos estão todos definidos.

Uma borda de os é 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.

Vai
fonte
3
"Seu carro começa no canto superior esquerdo de um mapa 8x8" - você não pode codificar 9no lugar de w=len(b[0])+1etc?
FryAmTheEggman
@FryAmTheEggman obrigado, como eu poderia ignorar isso? : D
Será
Você pode reverter sua declaração ternária e substituir p==79por p-79. Eu recebi um erro de sintaxe ao fazer isso nos dois sentidos sem um espaço antes do else. Eu acho que esse truque só funciona if.
FryAmTheEggman
@FryAmTheEggman Acho que o teste de profundidade precisa antes da recursão? Eu tenho jogado com uma multiplicação por booleano.
Will
7
Acabei de encontrar um truque muito legal. Você provavelmente sabe que -~x== x+1mas os dois operadores unários têm maior precedência que multiplicação, divisão e módulo! Então (d+1)%4poderia ser -~d%4! Isso também funcionaria, x-1mas apenas use ~-x.
FryAmTheEggman # 4/14
6

Javascript - 270 - 20% = 216 262 - 20% = 210 bytes

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

V=I=>{n=[N=[0,0,0]];v={};v[N]='';O='C';for(S='';n[0];){m=[];n.map(h=>{[x,y,d]=h;D=i=>[1,0,-1,0][d+i&3];p=v[h];for(j=2;j--;){O=v[c=[X=x+D(j),Y=y+D(3-3*j)),d+j&3]]?'K':O;J=X|Y;J<0||J>7||I[Y][X]||v[c]?O:(m.push(c),v[c]=p+'SR'[j])}S=(x&y)>6?p:S});n=m;}return S||O;};

Expandido:

V = I => {
    n = [N=[0,0,0]];
    v = {};
    v[N] = '';
    O = 'C';

    for( S = ''; n[0]; ) {
        m = [];
        n.map( h => {
            [x,y,d] = h;
            D = i => [1,0,-1,0][d+i&3];
            p = v[h];
            for( j = 2; j--; ) {
                O = v[c = [X = x+D(j),Y = y+D(3-3*j),d+j&3]] ? 'K' : O;
                J = X|Y;
                J<0 || J>7 || I[Y][X] || v[c] ? O : (
                    m.push( c ),
                    v[c] = p + 'SR'[j]
                );
            }

            S = (x&y) > 6 ? p : S;
        } );
        n = m;
    }
    return S || O;
};

vé uma hashtable com chaves que são triplos de estado (x,y,d)correspondentes à coordenada (x, y) e à direção da entrada d. Cada chave possui um valor associado, que é a sequência de movimentos S(retos) e R(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 externo for( S = ... ), a rotina verifica se existem triplos não processados. Nesse caso, ele executa cada triplo não processado pelo loop interno n.map( ...,.

O loop interno faz cinco coisas:

  1. calcula os dois movimentos possíveis (dirigindo em linha reta, virando à direita) fora do estado atual
  2. se um desses movimentos levar a um estado já registrado na hashtable, ele será ignorado para processamento adicional. No Kentanto, 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.
  3. se um estado é legal e novo, é adicionado à hashtable ( v) e à pilha de triplos não processados ​​( m) para a próxima passagem do loop externo
  4. quando o novo estado é registrado v, seu valor é definido como o valor do estado de origem (a sequência de movimentos) mais Rou com Sbase no movimento atual
  5. se xe yfor 7, o valor do estado de origem (a sequência de movimentos executados para atingir o estado de origem) é copiado S, pois essa sequência de movimento é uma solução para o problema

Após o loop interno terminar, n(a pilha) é substituída por m(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, Sela conterá uma sequência de movimentos que levam a essa célula, e isso é gerado. Se a célula não foi atingida, Sserá a string vazia e a rotina Opassará para a saída , que conterá K(travada) se e somente se um loop for encontrado ou C(acidente) se o carro inevitavelmente falhar.

COTO
fonte
11
Obteve a confirmação do OP, você pode renomear 'Crash' e 'Stuck' para 'C' e 'S'.
FryAmTheEggman
Ah Isso economiza um pouco, então. Obrigado. ;)
COTO
Você pode explicar o que seu código está fazendo? Eu não posso fazer cara ou coroa disso.
fosgênio
@phosgene: incluí uma explicação detalhada em linha.
COTO
Esse é um procedimento inteligente. Nada é desperdiçado.
fosgênio
4

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 de 00001010101010101010101110100111001000, 0para reto, 1para 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.

b=input()
D=[(-1,0),(0,-1),(1,0),(0,1)]
def a(l):
 x,y=0,0
 v=2
 for d in l:
  if d=='1':v=(v+1) % 4
  x+=D[v][0]
  y+=D[v][1]
  if x<0 or x>7 or y<0 or y>7:return 0,x,y
  if b[y][x]:return -1,x,y
 return 1,x,y
def c(l):
 if len(l) < 39:
  t,x,y=a(l)
  if t==1:
   if (x,y)==(7,7):
    print l;exit(0)
   c(l+"0")
   c(l+"1")
c("")
print 0
stokastic
fonte
3
Uma vez que este é Python 2, você pode misturar tabulações e espaços para recuos, como em a's forloop. 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 existe ifou for, etc na linha, por exemplo c(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 :)
FryAmTheEggman