Fechadura de bicicleta combinada

46

O cenário

Depois de um longo dia de trabalho andando no escritório e navegando pelo stackexchange.com , finalmente saio pela porta às 16:58, já cansada com o dia. Como ainda sou apenas estagiário, meu modo de transporte atual é de bicicleta. Dirijo-me ao meu fiel Peugeot Reynolds 501 , mas antes que possa navegar nele, preciso desbloqueá-lo. A trava é uma trava combinada padrão de quatro dígitos (0-9), através do quadro e da roda dianteira. Enquanto tento ficar acordada, levanto minha mão para entrar na combinação. Fechadura de bicicleta combinada

O desafio

Como meus dedos estão cansados, quero girar a trava para a combinação correta com o menor número de movimentos. Um movimento é definido como uma rotação em uma posição (36 graus); por exemplo, há um movimento de 5737para 5738. No entanto, sou capaz de pegar até três toques consecutivos ao mesmo tempo e girá-los como um , o que conta apenas como um único movimento. Por exemplo, há também apenas um movimento de 5737para 6837ou para 5626. Mover de 5737para 6838não é um movimento, pois os dígitos 1,2 e 4 se moveram na mesma direção, mas independentemente do número 3.

Portanto, para uma determinada combinação que posso ver no bloqueio da bicicleta (qualquer número inteiro de 4 dígitos), qual é o menor número de movimentos que posso fazer para desbloqueá-lo e, sim, posso girar em qualquer direção a qualquer momento. Com isso, quero dizer que posso girar alguns dígitos em uma direção e outros dígitos na outra direção: nem todos os meus movimentos serão no sentido anti-horário ou horário para cada desbloqueio.

Por ser preguiçoso, meu código de desbloqueio é 0000.

Este é um código de golfe. Não posso me incomodar em escrever muito código; portanto, o programa mais curto em número de bytes vence.

A entrada é de stdin, e seu código deve gerar as combinações que posso ver em cada etapa após cada movimento, incluindo o 0000 no final. Cada uma das combinações de saída deve ser separada por um espaço / nova linha / vírgula / ponto / e comercial.

Exemplos

Input: 1210
0100
0000

Input: 9871
9870
0980
0090
0000

Input: 5555
4445&3335&2225&1115&0005&0006&0007&0008&0009&0000

Input: 1234
0124 0013 0002 0001 0000

Tentei postar isso em http://bicycles.stackexchange.com , mas eles não gostaram ...

Isenção de responsabilidade: primeiro golfe, então qualquer coisa que esteja quebrada / qualquer informação faltante me avise! Também fiz todos os exemplos à mão, para que haja soluções que envolvam menos movimentos!

EDIT: Para respostas que possuem vários caminhos de solução com número igual de movimentos (praticamente todos), não há solução preferida.

Lui
fonte
18
Bem-vindo ao PPCG; muito bom primeiro desafio!
Maçaneta
4
Isso parece sólido para mim! Bem-vindo ao PPCG!
Mego
1
Bom desafio. Posso perguntar qual deve ser a saída para os casos: 7478 e 3737?
precisa saber é o seguinte
1
@ noisyass2 Obrigado; A resposta de flawr fornece o seguinte: 7478 8588 9698 0708 0808 0908 0008 0009 0000 e 3737 2627 1517 0407 0307 0207 0107 0007 0008 0009 0000 Basta olhar para o 3737, isso faz sentido: Examinar apenas os 3 primeiros dígitos: se eu mover todos os os três primeiros ao mesmo tempo, são necessários 3 movimentos para os dígitos 1 e 3 e, em seguida, outros 4 movimentos para o dígito 2, totalizando sete. Considerando que se eu mover cada um individualmente, cada um faz 3 movimentos, assim 9 movimentos.
Lui
1
Gostaria de saber se o título "Combination Lock" (ou "Bike Lock") pode atrair mais espectadores.
DavidC

Respostas:

10

Matlab, 412 327 bytes

Golfe (Graças a @AndrasDeak por jogar golfe s!):

s=dec2bin('iecbmgdoh'.'-97)-48;s=[s;-s];T=1e4;D=Inf(1,T);P=D;I=NaN(T,4);for i=1:T;I(i,:)=sprintf('%04d',i-1)-'0';end;G=input('');D(G+1)=0;for k=0:12;for n=find(D==k);for i=1:18;m=1+mod(I(n,:)+s(i,:),10)*10.^(3:-1:0)';if D(m)==Inf;D(m)=k+1;P(m)=n-1;end;end;end;end;n=0;X='0000';while n-G;n=P(n+1);X=[I(n+1,:)+48;X];end;disp(X)

Este código usa alguma programação dinâmica para encontrar o 'caminho' mais curto do número fornecido e 0000usar apenas as etapas possíveis. O desafio é basicamente o prioblem de caminho mais curto (como alternativa, você pode considerar as etapas como um grupo de comutadores.), Mas a dificuldade estava em implantar uma implementação eficiente . As estruturas básicas são duas matrizes de 10000 elementos, uma para armazenar o número de etapas para chegar a esse índice e a outra para armazenar um ponteiro para o 'nó' anterior em nosso gráfico. Ele calcula simultaneamente os 'caminhos' para todos os outros números possíveis.

Exemplos:

9871
0981
0091
0001
0000

1210
0100
0000

Examples by @noisyass:

7478
8578
9678
0788
0899
0900
0000

3737
2627
1517
0407
0307
0207
0107
0007
0008
0009
0000

Own Example (longest sequence, shared with 6284)

4826
3826
2826
1826
0826
0926
0026
0015
0004
0003
0002
0001
0000    

Código completo (incluindo alguns comentários):

%steps
s=[eye(4);1,1,0,0;0,1,1,0;0,0,1,1;1,1,1,0;0,1,1,1];
s=[s;-s];


D=NaN(1,10000);%D(n+1) = number of steps to get to n
P=NaN(1,10000);%P(n+1) was last one before n

I=NaN(10000,4);%integer representation as array
for i=0:9999; 
    I(i+1,:)=sprintf('%04d',i)-'0';
end

G=9871; % define the current number (for the golfed version replaced with input('');
D(G+1)=0;
B=10.^(3:-1:0); %base for each digit

for k=0:100; %upper bound on number of steps;
    L=find(D==k)-1;
    for n=L; %iterate all new steps
        for i=1:18; %search all new steps
            m=sum(mod(I(n+1,:)+s(i,:),10) .* [1000,100,10,1]);
            if isnan(D(m+1))
                D(m+1) = k+1;
                P(m+1)=n;
            end
        end
    end
end
n=0;%we start here
X=[];
while n~=G
    X=[I(n+1,:)+'0';X];
    n=P(n+1);
end
disp([I(G+1,:)+'0';X,''])
flawr
fonte
Agradável! Sendo um usuário principalmente do Matlab, eu estava pensando em como seria o desempenho.
Lui
1
Para entrada, 6444seu código fornece 6444 7554 8664 9774 0884 0994 0004 0003 0002 0001 0000, enquanto eu acho que a resposta é 6444 6333 6222 6111 6000 7000 8000 9000 0000. Minha resposta é 8 etapas, a sua é 10. Não consigo ver o problema, e parece existir tanto na versão com golf quanto na versão sem golf. Isso foi corrigido na sua edição mais recente.
Lui
1
Acabei de corrigir um pequeno erro no código. Na súltima linha deve ser [0,1,1,1]. Então você também tem uma solução de 8 etapas! Sinto muito pela inconveniência =)
flawr
1
@Lui Há uma sala de chat matlab / oitava , entre outras coisas, é algum tipo de base para a linguagem MATLab, derivada do Matlab.
flawr
1
Para 4826, encontrei uma solução de 11 movimentos: 4826 3716 2606 1506 0406 0306 0206 0106 0007 0008 0009 0000
noisyass2
4

Lote - 288 bytes

Mesmo se você disser que eles têm que ser consecutivos (os anéis), eu assumo pela lógica (seguindo o exemplo) que posso pular o do meio, a partir de 1234até 0224.

set / px =
ajuste a =% x: ~ 0,1% & ajuste b =% x: ~ 1,1% & ajuste c =% x: ~ 2,1% & ajuste d =% x: ~ 3,1%
:eu
@echo% x% e se% a% == 0 (se% d% NEQ 0 definido / ad = d-1) outro conjunto / aa = a-1
@if% b% NEQ 0 definido / ab = b-1
@ se% c% NEQ 0 definido / ac = c-1
@if% x% NEQ 0000 defina x =% a %% b %% c %% d% e vá para l

Esta é a minha solução de lote: 236 bytes.


Edit: solução corrigida

set / px =
ajuste a =% x: ~ 0,1% & ajuste b =% x: ~ 1,1% & ajuste c =% x: ~ 2,1% & ajuste d =% x: ~ 3,1%
:eu
@echo% x% e defina k = 1 e se% a% == 0 (se% d% NEQ 0 defina / ad = d-1 e defina k = 0) ou defina / aa = a-1 e defina k = 1
@ se% b% NEQ 0 se% k% == 1 conjunto / ab = b-1 e conjunto k = 0
@ se% c% NEQ 0 se% k% == 0 definido / ac = c-1
@if% x% NEQ 0000 defina x =% a %% b %% c %% d% e vá para l

A nova solução (corrigida de acordo com os comentários subjacentes) tem 288 bytes pesados.

barulho
fonte
Não analisei sua resposta em profundidade, mas estou lutando para seguir sua lógica no primeiro parágrafo. A qual exemplo você está se referindo especificamente? E seu exemplo de passar de 1234para não0224 é um movimento. A idéia é que, usando apenas dois dedos, eu possa agarrar até três anéis consecutivos com um único aperto.
Lui
Eu quis dizer, se você pode mover três toques consecutivos, é razoável pensar que você também pode mover o primeiro e o terceiro, evitando o segundo. Ou devo mudar meu código?
No13
Sua suposição está errada; você deve alterar seu código. Você vê a lógica conforme explicado no comentário acima?
Lui
Código fixo. Eu verifiquei com vários tipos diferentes de combinações e me parece que sempre leva o caminho mais curto.
noize
Este parece contar apenas para baixo, por isso leva mais tempo do que o necessário para combinações com números elevados (por exemplo, 18 movimentos para 9999)
faubi
2

Haskell - 310 bytes

import Data.Char
import Data.List
r=replicate
h=head
a x=map(:x)[map(`mod`10)$zipWith(+)(h x)((r n 0)++(r(4-j)q)++(r(j-n)0))|j<-[1..3],n<-[0..j],q<-[1,-1]]
x!y=h x==h y
x#[]=(nubBy(!)$x>>=a)#(filter(![(r 4 0)])x)
x#y=unlines.tail.reverse.map(intToDigit<$>)$h y
main=do x<-getLine;putStrLn$[[digitToInt<$>x]]#[]

Isso funciona criando repetidamente uma nova lista de combinações aplicando cada turno possível a cada combinação já alcançada até que uma delas seja a combinação certa. Duplicatas são removidas da lista em cada iteração para impedir que o uso da memória cresça exponencialmente.

Como solução de força bruta, isso é muito ineficiente e pode levar alguns minutos para ser executado.

Eu não tenho muita experiência com Haskell, então algo provavelmente poderia ser feito melhor.

faubi
fonte
Parece uma base sólida para sua abordagem. Eu não tenho experiência com Haskell, nem (que eu conheça) qualquer meio de compilar / executá-lo. Um google rápido também não me dá aonde eu possa experimentá-lo. Você pode fornecer um link que permita que eu tente? Obrigado.
Lui
@Lui Ele pode ser compilado com o Glasgow Haskell Compiler , mas, além do download e uso, não conheço nenhuma maneira de executá-lo.
faubi