Skip to content

UKSPC Practice Problems » Phone Numbers

Source
driver.c, driver.cpp, or driver.java
Input
standard input
Output
standard output

Your significant other has just moved to Mars and you lost his or her phone number. Desperate to contact them since it's your anniversary, you start guessing numbers. Did I mention that on Mars phone numbers are strings of characters? The keypad looks like this:

A B C D
E F G H
I J K L
M N O P

You can remember one silly fact about the number: it's created by a series of “knight-moves.” A knight-move, like in chess, is two steps in any direction followed by one step in a direction perpendicular to the first direction (the moves make an 'L' shape). For example, from K you can move to E, M, B, and D. So an example phone number of length 5 starting with G would be GNEKB.

Your task is to generate all possible phone number strings of a given length N such that 10 ≥ N ≥ 1. Input will be a single number N. You should output all phone numbers in lexicographical order, separated by a new line with no other spacing between strings—no empty lines, no spaces between letters, and no spaces between strings. After all strings have been output, you will output the total number of strings.

Sample Input

4

Abbreviated Sample Output

AGAG
AGAJ
AGIB
AGIG
AGIO
(...)
PJHB
PJHJ
PJHO
PJPG
PJPJ
464