TopCoder Statistics - Problem Statement

Problem Statement

A Young tableau is a two-dimensional array of integers such that each row and column is sorted in ascending order (rows left-to-right, columns top-to-bottom). Given a int[] table with exactly 16 elements, all of which are distinct, you will return the fewest number of swaps required to turn table into a Young tableau. table should be interpreted as a 4 x 4 array of integers. More visually,

  table = { A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P }

corresponds to the following 4 x 4 array

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

where A through P are integers.

Definition

Class:: QuickTableau
Method:: numSwaps
Parameters:: int[]
Returns:: int
Method signature:: int numSwaps(int[] table)
(be sure your method is public)

Constraints

table will contain exactly 16 elements.
table will contain no repeated elements.
Each element of table will be between 1 and 16, inclusive.

Examples

{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }

Returns: 0

We already have a Young tableau.
{1,5,9,13,2,6,10,14,3,7,11,15,4,8,12,16}

Returns: 0
{1,2,3,4,5,6,7,8,9,11,12,13,10,14,16,15}

Returns: 1
{1,2,3,4,5,6,7,8,9,11,12,13,10,16,15,14}

Returns: 1
{1,2,3,4,5,6,7,8,9,10,11,12,13,16,14,15}

Returns: 2
{12,2,10,6,14,5,11,16,1,7,3,13,9,8,4,15}

Returns: 7
{16,1,3,2,9,11,13,8,12,5,6,14,4,7,15,10}

Returns: 8
{3,6,15,11,4,2,14,13,9,7,12,5,8,1,16,10}

Returns: 7
{15,8,9,3,7,6,10,11,5,13,2,16,1,12,14,4}

Returns: 7
{7,2,12,15,16,9,4,14,5,3,8,11,13,10,1,6}

Returns: 7
{11,10,12,14,6,5,8,1,16,4,15,13,2,9,3,7}

Returns: 8
{9,3,8,13,11,5,14,12,2,7,10,16,1,4,15,6}

Returns: 7
{3,1,16,12,7,6,14,9,11,5,8,13,10,2,15,4}

Returns: 6
{10,1,2,5,16,15,12,4,13,3,9,6,7,8,14,11}

Returns: 9
{14,1,4,13,16,7,11,6,12,8,15,3,9,5,2,10}

Returns: 8
{4,6,5,14,8,2,7,9,10,16,11,1,3,13,15,12}

Returns: 7
{3,9,5,13,11,10,7,8,16,12,1,6,15,2,14,4}

Returns: 8
{13,7,4,9,11,2,10,14,3,12,6,8,16,1,15,5}

Returns: 7
{12,10,16,5,8,7,4,13,15,6,2,1,11,14,9,3}

Returns: 7
{2,10,5,1,14,8,3,13,4,9,15,6,7,12,16,11}

Returns: 6
{5,1,7,15,8,14,10,16,4,2,13,3,12,9,6,11}

Returns: 8
{4,14,13,8,12,6,2,1,9,10,7,11,16,15,5,3}

Returns: 8
{4,16,8,3,10,6,5,7,13,9,14,2,15,11,12,1}

Returns: 8
{13,9,3,1,5,10,11,2,7,16,15,8,14,12,6,4}

Returns: 9
{2,8,6,4,13,9,3,15,7,14,10,5,12,1,16,11}

Returns: 8
{9,15,3,6,13,1,16,12,2,4,5,8,11,14,10,7}

Returns: 8
{10,13,7,11,8,12,2,5,14,4,1,9,3,6,15,16}

Returns: 7
{2,5,1,15,3,11,16,8,9,14,12,7,10,6,13,4}

Returns: 7
{5,7,15,4,8,3,13,12,11,2,9,1,10,14,16,6}

Returns: 8
{10,9,2,11,16,6,7,5,13,14,4,12,8,15,1,3}

Returns: 8
{1,5,9,4,16,7,8,14,3,12,11,6,2,13,15,10}

Returns: 6
{7,4,6,15,13,2,11,12,1,10,9,8,14,16,3,5}

Returns: 8
{12,2,7,8,10,1,14,15,4,9,11,16,6,5,3,13}

Returns: 6
{13,8,15,9,4,2,12,16,6,1,11,14,7,3,5,10}

Returns: 7
{11,8,2,13,1,3,7,14,16,15,9,4,6,5,12,10}

Returns: 8
{2,11,6,1,15,4,9,12,7,5,14,3,8,10,13,16}

Returns: 5
{2,16,13,9,4,3,7,5,14,8,11,15,1,10,6,12}

Returns: 7
{12,3,4,6,15,2,5,16,7,1,9,11,8,10,13,14}

Returns: 6
{2,7,14,1,10,12,16,4,13,8,15,3,9,5,6,11}

Returns: 9
{3,13,4,5,8,16,11,7,12,2,10,14,15,6,1,9}

Returns: 9
{ 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

Returns: 6
{ 2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }

Returns: 1

Here we only need to swap the first 2 values.
{ 4, 3, 2, 1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }

Returns: 2
{ 4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, 16, 15, 14, 13 }

Returns: 8
{16, 15, 14, 13, 12, 11, 10, 6, 8, 7, 9, 5, 4, 3, 2, 1 }

Returns: 7
{10, 15, 4, 3, 7, 9, 2, 1, 16, 13, 5, 12, 6, 8, 14, 11 }

Returns: 9
{3, 6, 5, 13, 7, 9, 10, 14, 16, 1, 15, 12, 4, 2, 8, 11 }

Returns: 8
{4, 3, 2, 1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }

Returns: 2
{16, 15, 14, 13, 12, 11, 1, 9, 8, 7, 6, 5, 4, 3, 2, 10 }

Returns: 7
{15, 8, 3, 9, 2, 13, 16, 1, 6, 7, 5, 12, 4, 14, 11, 10 }

Returns: 7
{1, 4, 3, 7, 5, 6, 2, 8, 9, 10, 11, 15, 12, 13, 14, 16 }

Returns: 2
{15, 9, 6, 3, 12, 5, 13, 4, 16, 8, 1, 10, 11, 7, 14, 2 }

Returns: 7
{1, 2, 3, 5, 4, 6, 7, 9, 8, 10, 11, 13, 12, 14, 15, 16 }

Returns: 0
{13, 3, 11, 10, 12, 8, 7, 5, 15, 14, 4, 1, 6, 2, 16, 9 }

Returns: 8
{7, 16, 1, 11, 13, 4, 2, 5, 3, 10, 14, 6, 9, 15, 12, 8 }

Returns: 8
{11, 15, 10, 16, 9, 3, 8, 5, 2, 1, 7, 14, 13, 4, 12, 6 }

Returns: 9
{1, 2, 5, 6, 3, 4, 9, 10, 7, 8, 11, 12, 13, 14, 15, 16 }

Returns: 0
{16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

Returns: 6
{1, 2, 5, 6, 3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }

Returns: 0
{1, 13, 7, 8, 16, 6, 9, 3, 14, 10, 12, 15, 11, 5, 4, 2 }

Returns: 4
{10, 5, 16, 7, 12, 9, 15, 1, 14, 3, 6, 13, 2, 11, 8, 4 }

Returns: 8
{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1 }

Returns: 6
{15, 14, 16, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 11, 10 }

Returns: 8
{16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 1, 2, 4, 3 }

Returns: 8
{6, 1, 4, 5, 2, 3, 8, 9, 7, 14, 10, 12, 16, 15, 13, 11 }

Returns: 5
{8, 7, 9, 3, 2, 5, 4, 1, 12, 10, 15, 6, 11, 14, 13, 16 }

Returns: 7
{1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16 }

Returns: 0
{16, 11, 14, 13, 12, 15, 1, 9, 8, 7, 6, 3, 4, 5, 2, 10 }

Returns: 9
{4, 3, 7, 6, 1, 8, 9, 10, 2, 5, 14, 16, 13, 12, 15, 11 }

Returns: 7
{10, 9, 8, 7, 1, 2, 3, 4, 11, 12, 13, 14, 15, 16, 5, 6 }

Returns: 9
{13, 12, 15, 14, 8, 4, 5, 6, 7, 9, 11, 16, 10, 3, 2, 1 }

Returns: 8
{10, 16, 3, 1, 2, 4, 11, 8, 12, 5, 7, 15, 13, 14, 9, 6 }

Returns: 7
{2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }

Returns: 1
{16, 1, 2, 3, 8, 5, 6, 7, 12, 9, 10, 11, 4, 13, 14, 15 }

Returns: 7
{14, 16, 5, 3, 1, 10, 9, 11, 12, 7, 2, 6, 13, 4, 15, 8 }

Returns: 7
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 11, 14, 12, 15, 16 }

Returns: 1
{16, 1, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 15 }

Returns: 7

Statistics

Problem Statement for "QuickTableau"

Problem Statement

Definition

Constraints

Examples