All challenges
Medium 0 solved 0% acceptance

Decode the Pattern

Work out the rule behind a family of letter squares from its first members, then build the member for any n.

What you'll learn

  • Describe a picture with a rule in the row and column numbers
  • Measure a ring number as a maximum of two distances
  • Map a number to a letter

Problem

A puzzle book shows the first three members of a pattern family and asks for the rest:

n = 1    n = 2    n = 3

A        BBB      CCCCC
         BAB      CBBBC
         BBB      CBABC
                  CBBBC
                  CCCCC

Study them before reading on and try to name the rule. Here it is, stated exactly: member n is a square of 2n − 1 rows, each 2n − 1 letters long with no spaces. Number rows and columns from 0 and let the centre be position n − 1. The cell in row r and column c shows the letter that comes d places after A in the alphabet, where d = max(|r − (n − 1)|, |c − (n − 1)|) is how many rings the cell lies away from the centre. So the centre is A, the ring around it is B, and the outer edge is the n-th letter.

Implement decode_the_pattern(n).

Input

n: Which member of the family to build (at most 26, so the letters never run past Z).

Output

Return the 2n − 1 rows from top to bottom. When n is 0, return an empty list.

Constraints

0 ≤ n ≤ 26

Examples

Example 1
Input:
n = 2

Expected output:
expected = ["BBB", "BAB", "BBB"]
Input:
long long n = 2;

Expected output:
std::vector<std::string> expected = {"BBB", "BAB", "BBB"};
Input:
long n = 2;

Expected output:
string[] expected = new string[] {"BBB", "BAB", "BBB"};

Explanation

Only the centre (1, 1) is 0 rings away, every other cell is 1 ring away: ["BBB", "BAB", "BBB"].

Example 2
Input:
n = 4

Expected output:
expected = ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"]
Input:
long long n = 4;

Expected output:
std::vector<std::string> expected = {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
Input:
long n = 4;

Expected output:
string[] expected = new string[] {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};

Explanation

The edge cells are 3 rings out (D); row 3 is the middle row: ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"].

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Mark the centre of each sample square and see how the letters change as you move away from it.

Hint 2

Cells on the same ring share a letter; the ring number uses the larger of the row and column distances to the centre.

Hint 3

Check your rule on the n = 3 sample before building any n.

Expected complexity

O(n^2) time, O(n^2) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.