### PEG 11/12 Programming Test 1 - October 19

## Problem 5: Cyclopian Puzzle

There are few in the Cyclopian puzzle market now that FurWear has entered it. Discontent with merely selling clothing, FurWear has ~~ripped off~~ invented a puzzle named after a tower in the Chthonic city of Hanoi.

In FurWear's game, there are three pegs in a line. On the leftmost peg is a tower of N discs of unique sizes, sorted with the largest on the bottom and the smallest on the top. The goal is to move the entire tower to the rightmost peg. The challenge lies in that only one disc may be moved at a time, and no disc may be placed atop a smaller disc.

You've bet your colleagues that nobody can solve this puzzle in fewer moves than you. To this end, you've decided to write a program that will show you how to do so and memorise its output.

### Input

The input consists of a single integer *N* (1 ≤ *N* ≤ 20), the number of discs initially on the leftmost peg.

### Output

You are to output the shortest sequence of moves that will move all discs to the rightmost peg. The pegs are labelled A, B, and C, with A being the leftmost peg and C being the rightmost peg. A move is denoted by the string *xy* where *x* is the peg from which a disc is moved, and *y* is the destination peg. (For example, moving a disc from A to C would be denoted by "AC".)

### Sample Input

4

### Sample Output

AB AC BC AB CA CB AB AC BC BA CA BC AB AC BC

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 3.00s

**Memory Limit:** 16M

**Added:** Oct 17, 2011

**Author:** jargon

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...