Кодовый велосипедный замок

46

Сценарий

После долгого рабочего дня, работающего в офисе и просматривающего stackexchange.com , я наконец вышел в дверь в 16:58, уже уставший от дня. Поскольку я все еще только стажер, мой текущий способ передвижения на велосипеде. Я направляюсь к своему верному Peugeot Reynolds 501 , но прежде чем я смогу отплыть, мне нужно его разблокировать. Замок представляет собой стандартный четырехзначный кодовый замок (0-9) через раму и переднее колесо. Стараясь бодрствовать, я поднимаю руку, чтобы войти в комбинацию. Кодовый велосипедный замок

Соревнование

Поскольку мои пальцы очень устали, я хочу повернуть замок в правильную комбинацию с наименьшим количеством движений. Одно движение определяется как вращение на одну позицию (36 градусов), например, есть одно движение от 5737до 5738. Тем не менее, я могу одновременно захватывать любые три последовательных кольца и вращать их как одно , что считается только одним движением. Например , существует также только одно движение от 5737до 6837или 5626. Перемещение от 5737к 6838не является одним движением, поскольку цифры номер 1,2 и 4 двигались в том же направлении, но независимо от цифры номер 3.

Поэтому для данной комбинации я могу видеть на замке велосипеда (любое 4-значное целое число), какое наименьшее количество движений я могу сделать, чтобы разблокировать его, и да, я могу вращаться в любом направлении в любое время. Под этим я подразумеваю, что могу поворачивать некоторые цифры в одном направлении и другие цифры в другом направлении: не все мои движения будут против часовой стрелки или по часовой стрелке для каждой разблокировки.

Поскольку я ленивый, мой код разблокировки 0000.

Это кодовый гольф, я не могу не писать много кода, поэтому выигрывает самая короткая программа с количеством байтов.

Входные данные взяты из стандартного ввода, и ваш код должен выводить комбинации, которые я вижу на каждом шаге после каждого движения, включая 0000 в конце. Каждая из комбинаций должна быть отделена пробелом / новой строкой / запятой / точкой / амперсандом.

Примеры

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

Я пытался опубликовать это на http://bicycles.stackexchange.com , но им это не понравилось ...

Отказ от ответственности: Первый гольф, так что все, что сломано / любая недостающая информация, дайте мне знать! Также я сделал все примеры вручную, поэтому могут быть решения, которые включают меньше движений!

РЕДАКТИРОВАТЬ: Для ответов, которые имеют несколько путей решения с равным количеством движений (практически все), не существует предпочтительного решения.

Lui
источник
18
Добро пожаловать в PPCG; очень хороший первый вызов!
Дверная ручка
4
Это выглядит солидно для меня! Добро пожаловать в PPCG!
Mego
1
Отличный вызов. Могу ли я спросить, какой должен быть выход для случаев: 7478 и 3737?
noisyass2
1
@ noisyass2 Спасибо; Ответ Flawr дает следующее: 7478 8588 9698 0708 0808 0908 0008 0009 0000 и 3737 2627 1517 0407 0307 0207 0107 0007 0008 0009 0000 Это имеет смысл: смотреть только на первые 3 цифры: если переместить все первые три в то же время, требуется 3 движения для цифр 1 и 3, а затем еще 4 движения для цифры 2, таким образом, в общей сложности семь. Принимая во внимание, что если я двигаюсь каждый в отдельности, каждый берет 3 хода, таким образом 9 движений.
Луи
1
Мне интересно, может ли название «Кодовый замок» (или «Велосипедный замок») привлечь больше зрителей.
DavidC

Ответы:

10

Matlab, 412 327 байт

Игра в гольф (спасибо @AndrasDeak за игру в гольф 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)

Этот код использует некоторое динамическое программирование для нахождения кратчайшего «пути» из заданного числа и 0000использования только возможных шагов. Задача - это, по сути, проблема кратчайшего пути (в качестве альтернативы вы, возможно, могли бы рассматривать этапы как коммутирующую группу), но проблема заключалась в эффективной реализации. Базовые структуры - это два массива по 10000 элементов, один для хранения количества шагов, чтобы добраться до этого индекса, другой для хранения указателя на предыдущий «узел» в нашем графе. Он одновременно вычисляет «пути» ко всем другим возможным числам.

Примеры:

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    

Полный код (включая некоторые комментарии):

%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
источник
Приятно! Будучи в основном пользователем Matlab, я думал о том, как хорошо это будет.
Луи
1
Для ввода 6444ваш код дает 6444 7554 8664 9774 0884 0994 0004 0003 0002 0001 0000, тогда как я нахожу ответ 6444 6333 6222 6111 6000 7000 8000 9000 0000. Мой ответ - 8 шагов, ваш - 10. Я не вижу проблема, и это, кажется, там и в версии для гольфа и в не гольфе. Это исправлено в вашем последнем редактировании.
Луи
1
Я только исправил небольшую ошибку в коде. В sпоследнем ряду должно быть [0,1,1,1]. Тогда вы получите 8-шаговое решение тоже! Я извиняюсь за неудобства =)
flawr
1
@Lui Существует чатлак Matlab / Octave, среди прочего это своего рода база для языка MATLAB, основанного на гольфе.
flawr
1
для 4826 я нашел решение с 11
ходами
4

Пакет - 288 байт

Даже если вы сказали, что они должны быть последовательными (кольца), я предполагаю по логике (следуя примеру), что могу пропустить среднюю, начиная 1234с 0224.

набор / ПВ =
установить a =% x: ~ 0,1% и установить b =% x: ~ 1,1% и установить c =% x: ~ 2,1% и установить d =% x: ~ 3,1%
: л
@echo% x% &, если% a% == 0 (если% d% NEQ 0 установлено / ad = d-1), иначе установлено / aa = a-1
@if% b% NEQ 0 set / ab = b-1
@if% c% NEQ 0 set / ac = c-1
@if% x% NEQ 0000 установлено x =% a %% b %% c %% d% & goto l

Это мое пакетное решение: 236 байт.


Редактировать: исправленное решение

набор / ПВ =
установить a =% x: ~ 0,1% и установить b =% x: ~ 1,1% и установить c =% x: ~ 2,1% и установить d =% x: ~ 3,1%
: л
@echo% x% & установить k = 1 &, если% a% == 0 (если% d% NEQ 0 установить / ad = d-1 и установить k = 0), в противном случае установить / aa = a-1 & установить k = 1
@if% b% NEQ 0, если% k% == 1 установлено / ab = b-1 и установлено k = 0
@if% c% NEQ 0, если% k% == 0 установлено / ac = c-1
@if% x% NEQ 0000 установлено x =% a %% b %% c %% d% & goto l

Новое решение (исправлено в соответствии с нижеследующими комментариями) имеет размер 288 байт.

Noize
источник
Я не очень внимательно изучил ваш ответ, но я стараюсь следовать вашей логике в первом абзаце. На какой конкретно пример вы ссылаетесь? И ваш пример перехода от 1234к 0224является не одним движением. Идея состоит в том, что с помощью только двух пальцев я могу схватить до трех последовательных колец одной ручкой.
Луи
Я имел в виду, что если вы можете перемещать 3 последовательных кольца, разумно подумать, что вы также можете перемещать первое и третье кольца, избегая второго. Или я должен изменить свой код?
Шум
Ваше предположение неверно; Вы должны изменить свой код. Вы видите логику, как объяснено в комментарии выше?
Луи
Код исправлен. Я проверил с несколькими различными типами комбинаций, и мне кажется, что он всегда идет короче.
Шум
Похоже, что это считается только вниз, так что это занимает больше времени, чем необходимо для комбинаций с большими числами (например, 18 ходов для 9999)
faubi
2

Haskell - 310 байт

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]]#[]

Это работает путем многократного построения нового списка комбинаций, применяя каждый возможный ход к каждой комбинации, которая уже достигнута, пока одна из них не станет правильной комбинацией. Дубликаты удаляются из списка на каждой итерации, чтобы не увеличивать объем использования памяти в геометрической прогрессии.

Как грубое решение проблемы, это очень неэффективно и может занять несколько минут.

У меня нет большого опыта работы с Haskell, так что, возможно, кое-что можно сделать лучше.

faubi
источник
Похоже, прочная основа для вашего подхода. У меня нет опыта работы с Haskell и (как я знаю) никаких средств его компиляции / запуска. Быстрый Google не дает мне нигде, я тоже могу попробовать. Можете ли вы дать ссылку, которая позволяет мне попробовать? Благодарю.
Луи
@Lui Его можно скомпилировать с помощью компилятора Glasgow Haskell , но кроме загрузки и использования, я не знаю ни одного способа его запуска.
Faubi