# UTS Programming Competition 2016 Problem 6

This is a part of the UTS Programming Competition 2016 Problem Set.

# Problem 6: Sator Squares

Run time limit: 5 seconds

## Problem Description

Take a look at the following Latin text (the meaning of the words are irrelevant):

```S A T O R
A R E P O
T E N E T
O P E R A
R O T A S
```

You will see that there are five words of five characters each, that may be read in one of four ways:

1. left-to-right, top-to-bottom; 2. right-to-left, bottom-to-top; 3. top-to-bottom, left-to-right, or; 4. bottom-to-top, right-to-left,

and whichever way you read them, you end up with the same five words in the same order.

This is the original Sator Square dating back to Ancient Roman times, so called because of the first word in the square, sator.

Here is another Sator square, of size 3:

```a r e
r 6 r
e r a
```

Your task is to write a program that finds as many Sator squares as you can in a large grid of text.

Trivial Sator squares (i.e. of size 1, or a single character) are not to be considered.

## Data Specification

### Input

A single test case.

The first line denotes the horizontal (H) and vertical (V) dimensions, respectively, of the grid of characters to search, separated by a single space (1 ≤ H ≤ 200, 1 ≤ V ≤ 200, H,V are integers).

V lines of H characters then follow.

### Output

Lines of the form S Y X, where:

S is the size of a found square (S ≥ 2), and;

X,Y are the co-ordinates of the top-leftmost character of the found square, relative to the grid.

Sort all found squares in ascending order, first by size, then by horizontal and vertical co-ordinates.

If no squares have been found, simply print 0 on a single line.

```6 8
AweFAR
vanACA
3naRAF
f6#rtg
67g33%
764ef^
*&#fEH
!!@feG
```

```2 1 1
2 4 0
3 0 3
```

## Solutions

### Tom's Java solution

```import java.io.*;
import java.util.*;

class Sator
{
private static String getRow(char[][] grid, int row, int start, int finish)
{
return new String(Arrays.copyOfRange(grid[row], start, finish));
}

private static String getColumn(char[][] grid, int column, int start, int finish)
{
StringBuilder sb = new StringBuilder();

for (int row = start; row <= finish; row++)
sb.append(grid[row][column]);

return sb.toString();
}

private static char[][] subGrid(char[][] grid, int x1, int y1, int x2, int y2)
{
int i = 0;
int j = 0;
char sub[][] = new char[x2-x1+1][y2-y1+1];

for (i = 0; i <= x2-x1; i++)
for (j = 0; j <= y2-y1; j++)
sub[i][j] = grid[i+x1][j+y1];

return sub;
}

private static boolean verify(char grid[][])
{
int size = new String(grid[0]).trim().length();
if (size == 0) return false;

int diag = (size % 2 == 0) ? ((size / 2) - 1) : (size / 2);
int window = size;

int i = 0;

while (i <= diag)
{
String row = getRow(grid, i, i, i+window);

if (!(row.equals(new StringBuilder(getRow(grid, size-1-i, i, i+window)).reverse().toString()))) return false;
if (!(row.equals(getColumn(grid, i, i, i+window-1)))) return false;
if (!(row.equals(new StringBuilder(getColumn(grid, size-1-i, i, i+window-1)).reverse().toString()))) return false;

window -= 2;
i++;
}

return true;
}

private static void find(char grid[][], int height, int width)
{
boolean found = false;
for (int size = 2; size <= Math.min(height, width); size++)
{
for (int x = 0; x <= (height - size); x++)
{
for (int y = 0; y <= (width - size); y++)
{
if (verify(subGrid(grid, x, y, x+size-1, y+size-1)))
{
found = true;
System.out.println(size + " " + x + " " + y);
}
}
}
}

if (!found)
System.out.println("0");
}

public static void main(String args[])
{
Scanner in = new Scanner(System.in);
int width = in.nextInt();
int height = in.nextInt();

char grid[][] = new char[height][width];

for (int line = 0; line < height; line++)
grid[line] = in.next().toCharArray();

find(grid, height, width);

}
}
```