O usuário CarpetPython publicou uma nova visão sobre esse problema, que coloca um foco muito maior nas soluções heurísticas, devido ao aumento do espaço de pesquisa. Pessoalmente, acho que esse desafio é muito melhor do que o meu, então considere tentar esse!
Vector racing é um jogo viciante que pode ser jogado com uma caneta e uma folha de papel quadriculado. Você desenha uma pista arbitrária no papel, define um começo e um fim e depois dirige seu carro de tamanho pontual de maneira baseada em turnos. Chegue ao fim o mais rápido possível, mas tome cuidado para não acabar em uma parede!
The Track
- O mapa é uma grade bidimensional, onde cada célula possui coordenadas inteiras.
- Você move nas células da grade.
- Cada célula da grade faz parte da trilha ou é uma parede.
- Exatamente uma célula da trilha é a coordenada inicial.
- Pelo menos uma célula de rastreamento é designada como objetivo. A aterrissagem em qualquer um deles completa a corrida. Várias células de objetivo não estão necessariamente conectadas.
Dirigindo o carro
Seu carro começa em uma determinada coordenada e com vetor de velocidade (0, 0)
. Em cada turno, você pode ajustar cada componente da velocidade ±1
ou deixá-lo como está. Em seguida, o vetor de velocidade resultante é adicionado à posição do seu carro.
Uma imagem pode ajudar! O círculo vermelho era sua posição no último turno. O círculo azul é sua posição atual. Sua velocidade é o vetor do círculo vermelho ao azul. Nesse turno, dependendo de como você ajusta sua velocidade, você pode mover-se para qualquer um dos círculos verdes.
Se você cair em uma parede, você perde imediatamente.
Sua tarefa
Você adivinhou: escreva um programa que, dado uma pista de corrida como entrada, leve o carro a uma das células do gol no menor número de curvas possível. Sua solução deve ser capaz de lidar razoavelmente bem com trilhas arbitrárias e não ser otimizada especificamente para os casos de teste fornecidos.
Entrada
Quando seu programa é chamado, leia a partir de stdin :
target
n m
[ASCII representation of an n x m racetrack]
time
target
é o número máximo de turnos que você pode fazer para concluir a faixa e time
o orçamento total de tempo para a faixa, em segundos (não necessariamente inteiro). Veja abaixo os detalhes sobre o tempo.
Para a faixa delimitada por nova linha, os seguintes caracteres são usados:
#
- paredeS
- o começo*
- um objetivo.
- todas as outras células da via (estrada)
Todas as células fora da n x m
grade são implicadas em paredes.
A origem das coordenadas está no canto superior esquerdo.
Aqui está um exemplo simples:
8
4.0
9 6
###...***
###...***
###...***
......###
S.....###
......###
Usando indexação baseada em 0, a coordenada inicial seria (0,4)
.
Após cada movimento, você receberá mais informações:
x y
u v
time
Onde x
, y
, u
, v
são todos os inteiros baseados em 0. (x,y)
é sua posição atual e (u,v)
sua velocidade atual. Observe que x+u
e / ou y+v
pode estar fora dos limites.
time
é o que resta do seu orçamento de tempo, em segundos. Sinta-se livre para ignorar isso. Isso é apenas para participantes que realmente querem levar sua implementação ao limite de tempo.
Quando o jogo terminar (porque você caiu em uma parede, saiu dos limites, excedeu as target
curvas, ficou sem tempo ou atingiu a meta), você receberá uma linha vazia.
Saída
Para cada turno, escreva para stdout :
Δu Δv
onde Δu
e Δv
são cada uma de -1
, 0
, 1
. Isso será adicionado (u,v)
para determinar sua nova posição. Apenas para esclarecer, as instruções são as seguintes
(-1,-1) ( 0,-1) ( 1,-1)
(-1, 0) ( 0, 0) ( 1, 0)
(-1, 1) ( 0, 1) ( 1, 1)
Uma solução ideal para o exemplo acima seria
1 0
1 -1
1 0
Observe que o controlador não se conecta ao stderr ; portanto, você pode usá-lo para qualquer tipo de saída de depuração necessária ao desenvolver seu bot. Por favor, remova / comente qualquer saída desse tipo no código enviado.
Seu bot pode levar meio segundo para responder a cada turno. Para turnos que demoram mais, você terá um orçamento de tempo (por faixa) de target/2
segundos. Sempre que uma curva demorar mais de meio segundo, o tempo adicional será subtraído do seu orçamento de tempo. Quando seu orçamento de tempo chegar a zero, a corrida atual será abortada.
Novo: Por razões práticas, tenho que definir um limite de memória (já que a memória parece ser mais limitadora do que o tempo para tamanhos razoáveis de faixas). Portanto, terei que abortar qualquer execução de teste em que o piloto use mais de 1 GB de memória, conforme medido pelo Process Explorer como bytes privados .
Pontuação
Há uma referência de 20 faixas. Para cada faixa:
- Se você completar a faixa, sua pontuação é o número de movimentos necessários para alcançar uma célula de objetivo dividida por
target
. - Se você ficar sem tempo / memória ou não atingir a meta antes do
target
término dos turnos ou você cair em uma parede / fora dos limites a qualquer momento, sua pontuação será2
. - Se o seu programa não é determinístico, sua pontuação é a média acima de 10 corridas nessa faixa (por favor, indique isso na sua resposta).
Sua pontuação geral é a soma das pontuações individuais das faixas. Menor pontuação ganha!
Além disso, todo participante pode (e é fortemente encorajado a) fornecer uma faixa de referência adicional , que será adicionada à lista oficial. As respostas anteriores serão reavaliadas, incluindo esta nova faixa. Isso é para garantir que nenhuma solução seja adaptada muito de perto aos casos de teste existentes e para dar conta de casos extremos interessantes que eu poderia ter esquecido (mas que você pode perceber).
Quebra de gravata
Agora que já existe uma solução ideal, esse provavelmente será o principal fator para a pontuação dos participantes.
Se houver um empate (devido a várias respostas resolverem todas as faixas da melhor maneira ou de outra forma), adicionarei casos de teste adicionais (maiores) para romper o empate. Para evitar qualquer viés humano ao criar esses desempatadores, eles serão gerados de maneira fixa:
- Aumentarei o comprimento do lado
n
em10
comparação com a última faixa gerada dessa maneira. (Eu posso pular tamanhos se eles não quebrarem a gravata.) - A base é este gráfico vetorial
- Isso será rasterizado na resolução desejada usando esse trecho do Mathematica .
- O início está no canto superior esquerdo. Em particular, será a célula mais à esquerda da linha superior da extremidade da pista.
- O objetivo está no canto inferior direito. Em particular, será a célula mais à direita da linha mais baixa do final da pista.
- A
target
vontade4*n
.
A trilha final do benchmark inicial já foi gerada assim, com n = 50
.
O controlador
O programa que testa as submissões está escrito em Ruby e pode ser encontrado no GitHub junto com o arquivo de benchmark que utilizarei. Há também um exemplo de bot chamado randomracer.rb
lá, que simplesmente escolhe movimentos aleatórios. Você pode usar sua estrutura básica como ponto de partida para o seu bot ver como a comunicação funciona.
Você pode executar seu próprio bot em um arquivo de trilha de sua escolha da seguinte maneira:
ruby controller.rb track_file_name command to run your racer
por exemplo
ruby controller.rb benchmark.txt ruby randomracer.rb
O repositório também contém duas classes Point2D
e Track
. Se o seu envio estiver escrito em Ruby, fique à vontade para reutilizá-los para sua conveniência.
Opções de linha de comando
Você pode adicionar opções de linha de comando -v
, -s
, -t
antes do nome de arquivo do benchmark. Se você deseja usar vários comutadores, também é possível, por exemplo -vs
,. Isto é o que eles fazem:
-v
(detalhado): use isso para produzir um pouco mais de saída de depuração do controlador.
-s
(silencioso): se você preferir manter o controle de sua posição e velocidade e não se importar com o orçamento de tempo, pode desativar essas três linhas de saída a cada turno (enviadas para sua apresentação) com esta bandeira.
-t
(faixas): permite selecionar faixas individuais a serem testadas. Por exemplo -t "1,2,5..8,15"
, testaria apenas as faixas 1, 2, 5, 6, 7, 8 e 15. Muito obrigado ao Ventero por esse recurso e pelo analisador de opções.
Sua submissão
Em resumo, inclua o seguinte na sua resposta:
- Sua pontuação.
- Se você estiver usando aleatoriedade, indique isso, para que eu possa calcular sua pontuação em várias execuções.
- O código para o seu envio.
- A localização de um compilador ou intérprete gratuito para o seu idioma preferido, executado em uma máquina Windows 8.
- Instruções de compilação, se necessário.
- Uma sequência de linhas de comando do Windows para executar seu envio.
- Se o seu envio exige a
-s
bandeira ou não. - (opcionalmente) Uma nova faixa solucionável que será adicionada ao benchmark. Eu determinarei um razoável
target
para sua faixa manualmente. Quando a faixa for adicionada à referência, eu a editarei com sua resposta. Reservo-me o direito de solicitar uma faixa diferente (caso você adicione uma faixa desproporcionalmente grande, inclua arte ASCII obscena na faixa etc.). Quando adiciono o caso de teste ao conjunto de benchmarks, substituirei a trilha na sua resposta por um link para a trilha no arquivo de benchmark para reduzir a confusão nesta postagem.
Como você pode ver, testarei todos os envios em uma máquina Windows 8. Se não houver absolutamente nenhuma maneira de fazer o seu envio ser executado no Windows, também posso experimentar uma VM do Ubuntu. Isso será consideravelmente mais lento, portanto, se você deseja maximizar o limite de tempo, verifique se o seu programa é executado no Windows.
Que o melhor motorista surja vetorial!
Mas eu quero jogar!
Se você quiser experimentar o jogo para ter uma idéia melhor, existe esta implementação . As regras usadas lá são um pouco mais sofisticadas, mas é semelhante o suficiente para ser útil, eu acho.
Entre os melhores
Última atualização: 01/09/2014, 21:29 UTC
Faixas de referência: 25
Tamanhos de desempatador: 290, 440
- 6.86688 - Kuroi Neko
- 8.73108 - user2357112 - segundo envio
- 9.86627 - nneonneo
- 10.66109 - user2357112 - 1º envio
- 12.49643 - Ray
- 40.0759 - pseudônimo117 (probabilístico)
Resultados detalhados do teste . (As pontuações para envios probabilísticos foram determinadas separadamente.)
fonte
400
, pois está de acordo com a forma como eu determinei todos os outros alvos (exceto o desempate). Atualizarei a postagem principal assim que redirecionar todas as outras submissões.C ++, 5.4 (determinístico, ideal)
Solução de programação dinâmica. Provavelmente ideal. Muito rápido: resolve todos os 20 casos de teste em 0,2s. Deve ser especialmente rápido em máquinas de 64 bits. Supõe que o quadro tenha menos de 32.000 lugares em cada direção (o que deve ser verdade).
Este piloto é um pouco incomum. Ele calcula o caminho ideal na linha de partida e depois executa o caminho calculado instantaneamente. Ele ignora o controle de tempo e assume que pode concluir a etapa de otimização no prazo (o que deve ser verdadeiro para qualquer hardware razoavelmente moderno). Em mapas excessivamente grandes, há uma pequena chance de o piloto falhar. Se você pode convencê-lo a segfault, obtém um ponto de brownie e eu o corrigirei para usar um loop explícito.
Compile com
g++ -O3
. Pode exigir C ++ 11 (para<unordered_map>
). Para executar, basta executar o executável compilado (nenhum sinalizador ou opção é suportado; todas as entradas são obtidas no stdin).Resultados
Novo Testcase
fonte
Python 2 , determinístico, ideal
Aqui está o meu piloto. Eu não o testei no benchmark (ainda questionando qual versão e instalador do Ruby instalar), mas ele deve resolver tudo da melhor maneira possível e dentro do prazo. O comando para executá-lo é
python whateveryoucallthefile.py
. Precisa da-s
bandeira do controlador.Depois de inspecionar o piloto de nneonneo (mas na verdade não testá-lo, já que também não tenho um compilador C ++), descobri que ele parece realizar uma pesquisa quase exaustiva no espaço de estados, não importa o quão próximo o objetivo ou o curto seja um caminho já foi encontrado. Também descobri que as regras de tempo significam a construção de um mapa com uma solução longa e complexa, que exige um prazo longo e chato. Assim, o envio do meu mapa é bem simples:
Novo Testcase
(O GitHub não pode exibir a linha longa. A faixa é
*S.......[and so on].....
)Submissão adicional: Python 2, pesquisa bidirecional
Essa é uma abordagem que escrevi há cerca de dois meses atrás, ao tentar otimizar minha primeira apresentação. Para os casos de teste que existiam na época, ele não ofereceu uma melhoria, então eu não o enviei, mas, para o novo mapa de kuroi, ele parece apenas se espremer sob o limite de memória. Ainda estou esperando que o solucionador de kuroi supere isso, mas estou interessado em como ele se mantém.
fonte
n = 400
.) Entre em contato se aplicar alguma otimização para que eu possa executar novamente os testes.Python 3: 6.49643 (ideal, BFS)
Para o antigo arquivo de referência de 20 casos, obteve uma pontuação de 5,35643. A solução da @nneonneo não é ótima, pois obteve a versão 5.4. Alguns erros talvez.
Esta solução usa o BFS para pesquisar o gráfico, cada estado de pesquisa está na forma de (x, y, dx, dy). Então eu uso um mapa para mapear de estados para distâncias. No pior dos casos, a complexidade do tempo e do espaço é O (n ^ 2 m ^ 2). Isso raramente acontecerá, pois a velocidade não será muito alta ou o piloto cairá. Na verdade, custou 3 segundos na minha máquina para concluir todos os 22 casos de teste.
# Resultados
fonte
O(√n)
que tornaria sua implementaçãoO(n³)
em grades quadradas (o mesmo que os outros, suponho). Vou adicionar um desempate para pontuar sua inscrição contra as de user2357112 mais tarde hoje.n=270
, e é por isso que agora você está atrás dos outros dois envios "ideais". Dito isto, sua submissão também é a mais lenta das três, portanto seria a terceira de qualquer maneira, apenas com um desempate maior.RandomRacer, ~ 40.0 (média de 10 execuções)
Não é que esse bot nunca termine uma faixa, mas definitivamente com muito menos frequência do que uma vez em 10 tentativas. (Eu recebo uma pontuação que não é do pior caso a cada 20 a 30 simulações.)
Isso serve principalmente como um caso de linha de base e para demonstrar uma possível implementação (Ruby) para um piloto:
Execute-o com
fonte
Corredor aleatório 2.0, ~ 31
Bem, isso não vai superar o solucionador ideal publicado, mas é uma ligeira melhora em um piloto aleatório. A principal diferença é que esse corredor apenas considera ir aleatoriamente onde não há um muro, a menos que fique sem lugares válidos para se mover e, se puder passar para um objetivo que vire, ele o fará. Ele também não será movido para permanecer no mesmo local, a menos que não haja outro movimento disponível (improvável, mas possível).
Implementado em Java, compilado com java8, mas Java 6 deve estar bem. Sem parâmetros de linha de comando. Há uma hierarquia muito boa de cluster, então acho que estou fazendo java corretamente.
Os resultados (o melhor caso que já vi)
fonte
.class
arquivo está por algum motivo (em vez do diretório em que o controlador está). Ping-me (com um comentário) se você decidir adicionar um caso de teste, para que eu possa adicioná-lo à referência. Sua pontuação foi de 33 em 10 corridas (consulte a tabela de classificação), mas isso pode mudar a cada nova pista de teste adicionada ao benchmark.java -cp path/to/class/file VectorRacing