Если вы не знаете, что такое Ханойская башня , я кратко объясню: есть три стержня и несколько дисков, каждый из которых имеет свой размер. В начале все диски находятся на первой башне в отсортированном порядке: самый большой внизу, самый маленький сверху. Цель состоит в том, чтобы перенести все диски на третий стержень. Звучит легко? В этом и заключается подвох: вы не можете поместить диск поверх диска, который меньше другого диска; вы можете держать только один диск в руке за раз, чтобы переместить их на другой стержень, и вы можете поместить диск только на стержни, а не на стол, подлый ублюдок.

Пример решения ascii:

  A      B      C
  |      |      |      
 _|_     |      |      
__|__    |      |


  A      B      C
  |      |      |      
  |      |      |      
__|__   _|_     |


  A      B      C
  |      |      |      
  |      |      |      
  |     _|_   __|__


  A      B      C
  |      |      |      
  |      |     _|_     
  |      |    __|__      

Вызов

Есть три стержня, называемые A, B и C. (Вы можете также назвать их 1,2 и 3 соответственно, если это помогает). В начале все n дисков находятся на стержне A (1).

Ваша задача состоит в том, чтобы проверить решение для Ханойской башни. Вам нужно убедиться, что:

1. В конце концов все n дисков находятся на штоке C (3).
2. Для любого данного диска в любом данном состоянии под ним нет меньшего диска.
3. Нет очевидных ошибок, таких как попытка извлечь диски из пустого стержня или перемещение дисков в несуществующие стержни.

(решение не должно быть оптимальным.)

вход

Ваша программа получит два входа:

1. Количество дисков n (целое число)

2. Выполняемые ходы, которые будут состоять из набора кортежей: (башня, из которой будет взят самый верхний диск в данный момент), (башня, в которую будет доставлен этот диск), где каждый кортеж относится к ходу. Вы можете выбрать, как они представлены. Например, что-то вроде следующих способов представления решения для n = 2, которые я нарисовал в ascii выше. (Я буду использовать первый в тестовых случаях, потому что это легко для глаз):

   "A-> B; A-> C; B-> C"

   [( "А", "В"), ( "А", "С"), ( "В", "С")]

   [(1,2), (1,3), (2,3)]

   "ABACBC"

   [1,2,1,3,2,3]

Выход

• Правда, если условия, которые можно найти под «вызовом», держатся.

• Ложь, если они этого не делают.

Тестовые случаи:

Правда:

n=1, "A->C"

n=1, "A->B ; B->C"

n=2, "A->B ; A->C ; B->C"

n=2, "A->C ; C->B ; A->C ; B->C"

n=2, "A->C ; A->B ; C->B ; B->A ; B->C ; A->C"

n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"

n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C ; B->C"

Ложь:

3-й предложен @MartinEnder, 7-й - @Joffan

n=1, "A->B"

n=1, "C->A"

n=2, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"

n=2, "A->B ; A->C ; C->B"

n=2, "A->C ; A->B ; C->B ; B->A"

n=2, "A->C ; A->C"

n=3, "A->B ; A->D; A->C ; D->C ; A->C"

n=3, "A->C ; A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"

n=3, "A->C ; A->B ; C->B ; A->B ; B->C ; B->A ; B->C ; A->C"

n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; C->B"

n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C"

n=4, "A->B ; A->B ; A->B ; A->C ; B->C ; B->C ; B->C"

Это код-гольф , выигрывает самое короткое решение. Применяются стандартные правила и лазейки. Аккумуляторы не включены.

Сетчатка , 84 80 байт

^{-5 байт благодаря Мартину Эндеру}

~
 ~$'
$
ABC
{`^(.)(.*)( ~+)\1
$3$2$1
}`^(\W+)(\w)(.*)(?<=\1~+|\w)\2
$3$1$2
^AB 

Попробуйте онлайн! (плюс 5 байтов для построчных тестов)

Код имитирует полноценную игру.

• Вход дан как ACABCBACBABCAC~~~.
  ~~~означает три диска.
• Первые четыре строки преобразуют входные данные в формат игры: ACABCBACBABCAC ~~~ ~~ ~ABC.
  Сначала стержень A имеет все 3 диска, а стержни B и C пусты.
• Далее у нас есть цикл из двух шагов:
  • Возьмите первую букву в строке, которая указывает на следующий исходный стержень. Найдите этот стержень и возьмите последний диск. Удалите букву и переместите диск к штарку (поднимите его).
    В нашем примере, после первого шага, текст будет выглядеть следующим образом : ~CABCBACBABCAC ~~~ ~~ABC.
  • На втором этапе мы находим целевой стержень и перемещаем туда диск. Мы проверяем шток пуст, или имеет больший диск в верхней части: ABCBACBABCAC ~~~ ~~AB ~C.
• Наконец, мы подтверждаем, что стержни A и B пусты - это означает, что все диски находятся в C (в последней строке есть дополнительный пробел).

Сетчатка , 167 165 157 150 123 байта

Это полностью похоже на проблему, которая должна быть решена с помощью одного регулярного выражения ... (несмотря на то, что заголовок говорит "Retina", это просто ванильное регулярное выражение .NET, соответствующее допустимым входным данным).

^(?=\D*((?=(?<3>1+))1)+)((?=A(?<1-3>.+)|B(?<1-4>.+)|C(?<1-5>.+)).(?=A.*(?!\3)(\1)|B.*(?!\4)(\1)|C.*(?!\5)(\1)).)+(?!\3|\4)1

Формат ввода - это список инструкций формы AB, за которыми следует nодинарная цифра 1. Там нет разделителей. Выходные данные 1действительны и 0недействительны.

Попробуйте онлайн! (Первые два символа включают набор тестов, разделенных переводом строки.)

Альтернативное решение с тем же количеством байтов:

^(?=\D*((?=(?<3>1+))1)+)((?=A(?<1-3>.+)|B(?<1-4>.+)|C(?<1-5>.+)).(?=A.*(?!\3)(\1)|B.*(?!\4)(\1)|C.*(?!\5)(\1)).)+(?<-5>1)+$

Это может возможно быть сокращено путем использования 1, 11и 111вместо того , чтобы A, Bи , Cно я должен буду смотреть на это позже. Также может быть короче разделить программу на несколько этапов, но где проблема в этом? ;)

объяснение

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

Для перемещения дисков между стержнями мы используем странную причуду (?<A-B>...)синтаксиса. Как правило, это извлекает захват из стека Bи помещает в стек Aстроку между этим извлеченным захватом и началом этой группы. Таким образом, (?<A>a).(?<B-A>c)против abcбудет оставить Aпустым и Bс b(в отличие от c). Тем не менее, из-за взгляда переменной длины .NET возможно захватывать (?<A>...)и (?<B-A>...)перекрывать друг друга. По какой-то причине, если это так, пересечение двух групп выдвигается на B. Я подробно описал это поведение в «расширенном разделе» о балансировке групп в этом ответе .

На регулярное выражение. Стержни A, Bи Cсоответствуют группам 3, 4и 5в регулярном выражении. Начнем с инициализации стержня A:

^                 # Ensure that we start at the beginning of the input.
(?=               # Lookahead so that we don't actually move the cursor.
  \D*             # Skip all the instructions by matching non-digit characters.
  (               # For each 1 at the end of the input...
    (?=(?<3>1+))  # ...push the remainder of the string (including that 1)
                  # onto stack 3.
  1)+
)

Так, например, если ввод заканчивается на 111, группа 3 / rod Aтеперь будет содержать список снимков [111, 11, 1](верхняя часть справа).

Следующий бит кода имеет следующую структуру:

(
  (?=A...|B...|C...).
  (?=A...|B...|C...).
)+

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

Сначала снимем диск со стержня источника:

(?=
  A(?<1-3>.+)
|
  B(?<1-4>.+)
|
  C(?<1-5>.+)
)

Это использует странное поведение пересечения групп, которое я описал выше. Обратите внимание, что группа 3, 4и 5всегда будет содержать подстроки 1s в конце строки, длина которой соответствует размеру диска. Теперь мы используем, (?<1-N>.+)чтобы Nвытолкнуть верхний диск из стека и поместить пересечение этой подстроки с совпадением .+в стек 1. Так как .+всегда обязательно охватывает весь снятый захват N, мы знаем, что это просто перемещает захват.

Затем мы помещаем этот диск из стопки 1в стопку, соответствующую второму стержню:

(?=
  A.*(?!\3)(\1)
|
  B.*(?!\4)(\1)
|
  C.*(?!\5)(\1)
)

Обратите внимание, что нам не нужно очищать стек 1, мы можем просто оставить диск там, так как мы поместим новый поверх, прежде чем снова использовать стек. Это означает, что мы можем избежать (?<A-B>...)синтаксиса и просто скопировать строку с помощью (\1). Чтобы убедиться, что ход действителен, мы используем негативную перспективу (?!\N). Это гарантирует, что с позиции, где мы хотим сопоставить текущий диск, невозможно сопоставить диск уже в стеке N. Это может произойти, только если a) \Nникогда не совпадет, потому что стек полностью пуст или b) the disc on top of stackN is larger than the one we're trying to match with\ 1`.

Наконец, все, что осталось, - это убедиться, что а) мы сопоставили все инструкции и б) стержни Aи Bони пусты, чтобы все диски были перенесены C.

(?!\3|\4)1

Мы просто проверяем, что ни то, ни другое \3не \4может соответствовать (что имеет место только в том случае, если оба являются пустыми, потому что любой фактический диск будет соответствовать), и что мы можем затем сопоставить, 1чтобы мы не пропустили никаких инструкций.

Java "только" 311 272 263 261 260 259 256 байт

Сохранено 39 бесчисленных байтов благодаря @Frozn, который заметил более старую функцию отладки, а также некоторые хитрые уловки игры в гольф.

Гольф версия

int i(int n,int[]m){int j=0,k=0,i=n;Stack<Integer>t,s[]=new Stack[3];for(;j<3;)s[j++]=new Stack();for(;i-->0;)s[0].push(i);for(;k<m.length;k+=2)if((t=s[m[k+1]]).size()>0&&s[m[k]].peek()>t.peek())return 0;else t.push(s[m[k]].pop());return s[2].size()<n?0:1;}

безрассудный с объяснениями и красивыми печатными стопками на каждом шагу

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package codegolf;

/**
 *
 * @author rohan
 */
import java.util.Arrays;
import java.util.Stack;
public class CodeGolf {
    //golfed version
    int i(int n,int[]m){int j=0,k=0,i=n;Stack<Integer>[] s=new Stack[3];for(;j<3;j++)s[j]=new Stack();for(;i-->0;)s[0].push(i);for(;k<m.length;System.out.println(Arrays.toString(s)),k+=2)if(!s[m[k+1]].isEmpty()&&s[m[k]].peek()>s[m[k+1]].peek())return 0;else s[m[k+1]].push(s[m[k]].pop());return s[2].size()==n?1:0;}
    /** Ungolfed
        * 0 as falsy 1 as truthy
        * @param n the number of disks
        * @param m represents the zero indexed stacks in the form of [from,to,from,to]
        * @return 0 or 1 if the puzzle got solved, bad moves result in an exception
        */
    int h(int n, int[] m) {
        //declarations
        int j = 0, k = 0, i = n;
        //create the poles
        Stack<Integer>[] s = new Stack[3];
        for (; j < 3; j++) {
            s[j] = new Stack();
        }
        //set up the first tower using the "downto operator
        for (; i-- > 0;) {
            s[0].push(i);
        }
    //go through and perform all the moves
        for (; k < m.length; System.out.println(Arrays.toString(s)), k += 2) {
            if (!s[m[k + 1]].isEmpty() && s[m[k]].peek() > s[m[k + 1]].peek()) {
                return 0;//bad move
            } else {
                s[m[k + 1]].push(s[m[k]].pop());
            }
        }
        return s[2].size() == n ? 1 : 0;// check if all the disks are done
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
    //test case
        System.out.println( new CodeGolf().h(3,new int[]{0,2,0,1,2,1,0,2,1,0,1,2,0,2})==1?"Good!":"Bad!");
    }

}

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

[[2, 1], [], [0]]
[[2], [1], [0]]
[[2], [1, 0], []]
[[], [1, 0], [2]]
[[0], [1], [2]]
[[0], [], [2, 1]]
[[], [], [2, 1, 0]]
Good!

Python 2, 186 167 158 135 127 115 110 102 байта

n,m=input()
x=[range(n),[],[]]
for a,b in m:p=x[a].pop();e=x[b];e and 1/(p>e[-1]);e+=p,
if x[0]+x[1]:_

Принимает ввод на STDIN в следующем формате:

(1,[(0,1),(1,2)])

То есть кортеж Python из числа дисков и список кортежей Python из (from_rod,to_rod). Как и в Python, окружающие скобки являются необязательными. Стержни с нулевой индексацией.

Например, этот тестовый пример:

n=2; "A->B ; A->C ; B->C"

будет дано как:

(2,[(0,1),(0,2),(1,2)])

Если решение действительно, ничего не выводит и завершает работу с кодом выхода 0. Если оно недопустимо, генерирует исключение и завершается с кодом выхода 1. Бросает, IndexErrorесли переходит на несуществующий стержень или пытается снять диск с диска. стержень, на котором нет дисков, a, ZeroDivisionErrorесли диск помещен поверх меньшего диска, или a, NameErrorесли на конце остались первые или вторые стержни дисков.

Сохранено 13 байт благодаря @KarlKastor!

Сохранено 8 байт благодаря @xnor!

Python 2.7, 173 158 138 130 127 123 байта:

r=range;a,b=input();U=[r(a,0,-1),[],[]]
for K,J in b:U[J]+=[U[K].pop()]if U[J]<[1]or U[K]<U[J]else Y
print U[-1]==r(a,0,-1)

Принимает ввод через стандартный ввод в формате (<Number of Discs>,<Moves>) где <Moves>задан как массив, содержащий кортежи, соответствующие каждому ходу, каждый из которых содержит пару целых чисел, разделенных запятыми. Например, контрольный пример:

n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C" 

данный в посте будет дан как:

(3,[(0,2),(0,1),(2,1),(0,2),(1,0),(1,2),(0,2)]) 

к моей программе. Выводит, IndexErrorесли 3-е условие не выполнено, a, NameErrorесли 2-е условие не выполняется, и Falseесли 1-е условие не выполняется. В противном случае выводит True.

VBA, 234 217 213 196 байт

Function H(N,S)
ReDim A(N)
While P<Len(S)
P=P+2:F=1*Mid(S,P-1,1):T=1*Mid(S,P,1)
E=E+(T>2):L=L+T-F
For i=1 To N
If A(i)=F Then A(i)=T:Exit For
E=E+(A(i)=T)+(i=N)
Next
Wend
H=L+9*E=2*N
End Function

Формат ввода для ходов - строка с четным числом цифр (012). Вызов в электронной таблице, = H ([количество дисков], [переместить строку])

Массив A содержит положение стержня различных дисков. Ход просто обновляет первое вхождение номера стержня «От» в номер стержня «Кому». Если вы столкнулись с первым стержневым диском «To» или без «стержневого диска« From »», это неверный ход. Общее «значение стержня» A содержится в L, которое должно заканчиваться на 2N. Ошибки накапливаются как отрицательный счет в E.

Как и в других решениях, «перемещение» диска из башни в ту же башню не запрещено. Я мог бы запретить это еще на 6 байтов.

Полученные результаты

Результат функции в первом столбце (последний случай n = 3 - это мое добавление с использованием дополнительного стержня).

TRUE    1   02
TRUE    1   0112
TRUE    2   010212
TRUE    2   02210212
TRUE    2   020121101202
TRUE    3   02012102101202
TRUE    4   010212012021010212102012010212

FALSE   1   01
FALSE   1   20
FALSE   2   02012102101202
FALSE   2   010221
FALSE   2   02012110
FALSE   2   0202
FALSE   3   0202012102101202
FALSE   3   0201210112101202
FALSE   3   02012102101221
FALSE   3   0103023212
FALSE   4   0102120120210102121020120102
FALSE   4   01010102121212

php, 141 байт

<?php $a=$argv;for($t=[$f=range($a[++$i],1),[],[]];($r=array_pop($t[$a[++$i]]))&&$r<(end($t[$a[++$i]])?:$r+1);)$t[$a[$i]][]=$r;echo$t[2]==$f;

Скрипт командной строки, принимает входные данные в качестве высоты, а затем ряд индексов массива (0 проиндексированных), например, 1 0 2 или 2 0 1 0 2 1 2 для 1 или 2 кратчайших тестовых примеров высоты.
Отголосок 1 на истинных случаях и ничего на ложных.
Дает 2 уведомления и 1 предупреждение, поэтому необходимо запустить их в среде, которая их заставляет замолчать.

JavaScript (ES6), 108

n=>s=>!s.some(([x,y])=>s[y][s[y].push(v=s[x].pop())-2]<v|!v,s=[[...Array(s=n)].map(_=>s--),[],[]])&s[2][n-1]

Формат ввода: функция с 2 аргументами

• arg 1, число, количество колец
• arg 2, массив строк, каждая строка 2 символа '0', '1', '2'

Вывод: вернуть 1, если все в порядке, 0, если недействительно, исключение, если не существует стержня

Менее гольф и объяснил

n=>a=>(
  // rods status, rod 0 full with an array n..1, rod 1 & 2 empty arrays
  s = [ [...Array(t=n)].map(_=>t--), [], [] ],
  // for each step in solution, evaluate function and stop if returns true
  err = a.some( ([x,y]) => {
    v = s[x].pop(); // pull disc from source rod
    // exception is s[x] is not defined
    if (!v) return 1; // error source rod is empty
    l = s[y].push(v); // push disc on dest rod, get number of discs in l
    // exception is s[y] is not defined
    if(s[y][l-2] < v) return 1; // error if undelying disc is smaller
  }),
  err ? 0 // return 0 if invalid move
  : s[2][n-1]; // il all moves valid, ok if the rod 2 has all the discs
)

Примечание к тесту : первая строка функции «Тест» необходима для преобразования входного формата, заданного в вопросе, во ввод, ожидаемый моей функцией.

F=
n=>s=>!s.some(([x,y])=>s[y][s[y].push(v=s[x].pop())-2]<v|!v,s=[[...Array(s=n)].map(_=>s--),[],[]])&s[2][n-1]

Out=x=>O.textContent+=x+'\n'

Test=s=>s.split`\n`.map(r=>[+(r=r.match(/\d+|.->./g)).shift(),r.map(x=>(parseInt(x[0],36)-10)+''+(parseInt(x[3],36)-10))])
.forEach(([n,s],i)=>{
  var r
  try {
    r = F(+n)(s);
  } 
  catch (e) {
    r = 'Error invalid rod';
  }
  Out(++i+' n:'+n+' '+s+' -> '+r)
})

Out('OK')
Test(`n=1, "A->C"
n=1, "A->B ; B->C"
n=2, "A->B ; A->C ; B->C"
n=2, "A->C ; C->B ; A->C ; B->C"
n=2, "A->C ; A->B ; C->B ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C ; B->C"`)

Out('\nFail')
Test( `n=1, "A->B"
n=1, "C->A"
n=2, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=2, "A->B ; A->C ; C->B"
n=2, "A->C ; A->B ; C->B ; B->A"
n=2, "A->C ; A->C"
n=3, "A->B ; A->D; A->C ; D->C ; A->C"
n=3, "A->C ; A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->B ; B->C ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; C->B"
n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C"
n=4, "A->B ; A->B ; A->B ; A->C ; B->C ; B->C ; B->C"`)

<pre id=O></pre>