Star Rotation

Description:

Consider a (2k+1) × (2k+1) square subarray of an integer integers matrix. Let’s call the union of the square’s two longest diagonals, middle column and middle row a star. Given the coordinates of the star’s center in the matrix and its width, rotate it 45 · tdegrees clockwise preserving position of all matrix elements that do not belong to the star.

Example

  • For
    matrix = [[1, 0, 0, 2, 0, 0, 3],
              [0, 1, 0, 2, 0, 3, 0],
              [0, 0, 1, 2, 3, 0, 0],
              [8, 8, 8, 9, 4, 4, 4],
              [0, 0, 7, 6, 5, 0, 0],
              [0, 7, 0, 6, 0, 5, 0],
              [7, 0, 0, 6, 0, 0, 5]]

    width = 7, center = [3, 3] and t = 1, the output should be

    starRotation(matrix, width, center, t) = [[8, 0, 0, 1, 0, 0, 2],
                                              [0, 8, 0, 1, 0, 2, 0],
                                              [0, 0, 8, 1, 2, 0, 0],
                                              [7, 7, 7, 9, 3, 3, 3],
                                              [0, 0, 6, 5, 4, 0, 0],
                                              [0, 6, 0, 5, 0, 4, 0],
                                              [6, 0, 0, 5, 0, 0, 4]]
  • For
    matrix = [[1, 0, 0, 2, 0, 0, 3],
              [0, 1, 0, 2, 0, 3, 0],
              [0, 0, 1, 2, 3, 0, 0],
              [8, 8, 8, 9, 4, 4, 4],
              [0, 0, 7, 6, 5, 0, 0]]

    width = 3, center = [1, 5] and t = 81, the output should be

    starRotation(matrix, width, center, t) = [[1, 0, 0, 2, 0, 0, 0],
                                              [0, 1, 0, 2, 3, 3, 3],
                                              [0, 0, 1, 2, 0, 0, 0],
                                              [8, 8, 8, 9, 4, 4, 4],
                                              [0, 0, 7, 6, 5, 0, 0]]

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.integer matrixA two-dimensional array of integers.

    Constraints:
    3 ≤ matrix.length ≤ 15,
    3 ≤ matrix[i].length ≤ 15,
    matrix[i].length == matrix[j].length,
    0 ≤ matrix[i][j] ≤ 99.

  • [input] integer widthAn odd integer representing the star’s width. It equals the length of the sides of the bounding square for the star.

    Constraints:
    3 ≤ width ≤ min(matrix.length, matrix[i].length).

  • [input] array.integer centerAn array of two integers.

    Constraints:
    center.length = 2,
    (width - 1) / 2 ≤ center[0] < matrix.length - (width - 1) / 2,
    (width - 1) / 2 ≤ center[1] < matrix[i].length - (width - 1) / 2.

  • [input] integer tA non-negative integer denoting how many times the star should be rotated by 45 degrees.

    Constraints:
    0 ≤ t ≤ 109.

  • [output] array.array.integerAn array with specified star rotated by 45 · t degrees.

Tests:
Solution(C#):

int[][] starRotation(int[][] matrix, int width, int[] center, int t) {
    t = t%8;
    int[][] temp = matrix.Select(x => x.ToArray()).ToArray();   
    switch(t) {
        case 0:
            return matrix;
        case 1:
            for(int i=-width/2;i<=width/2;i++) {
                matrix[center[0]+i][center[1]+i] = temp[center[0]][center[1]+i];
                matrix[center[0]+i][center[1]] = temp[center[0]+i][center[1]+i];
                matrix[center[0]-i][center[1]+i] = temp[center[0]-i][center[1]];
                matrix[center[0]][center[1]+i] = temp[center[0]-i][center[1]+i];
            }
            return matrix;
        case 2:
            for(int i=-width/2;i<=width/2;i++) {
                matrix[center[0]+i][center[1]+i] = temp[center[0]-i][center[1]+i];
                matrix[center[0]+i][center[1]] = temp[center[0]][center[1]+i];
                matrix[center[0]-i][center[1]+i] = temp[center[0]-i][center[1]-i];
                matrix[center[0]][center[1]+i]= temp[center[0]-i][center[1]];
            }
            return matrix;
        case 3:
            for(int i=-width/2;i<=width/2;i++) {
                matrix[center[0]+i][center[1]+i] = temp[center[0]-i][center[1]];
                matrix[center[0]+i][center[1]] = temp[center[0]-i][center[1]-i];
                matrix[center[0]-i][center[1]+i] = temp[center[0]][center[1]-i];
                matrix[center[0]][center[1]+i]= temp[center[0]-i][center[1]-i];
            }
            return matrix;
        case 4:
            for(int i=-width/2;i<=width/2;i++) {
                matrix[center[0]+i][center[1]+i] = temp[center[0]-i][center[1]-i];
                matrix[center[0]+i][center[1]] = temp[center[0]-i][center[1]];
                matrix[center[0]-i][center[1]+i] = temp[center[0]+i][center[1]-i];
                matrix[center[0]][center[1]+i]= temp[center[0]][center[1]-i];
            }
            return matrix;
        case 5:
            for(int i=-width/2;i<=width/2;i++) {
                matrix[center[0]+i][center[1]+i] = temp[center[0]][center[1]-i];
                matrix[center[0]+i][center[1]] = temp[center[0]-i][center[1]-i];
                matrix[center[0]-i][center[1]+i] = temp[center[0]+i][center[1]];
                matrix[center[0]][center[1]+i]= temp[center[0]+i][center[1]-i];
            }
            return matrix;
        case 6:
            for(int i=-width/2;i<=width/2;i++) {
                matrix[center[0]+i][center[1]+i] = temp[center[0]+i][center[1]-i];
                matrix[center[0]+i][center[1]] = temp[center[0]][center[1]-i];
                matrix[center[0]-i][center[1]+i] = temp[center[0]+i][center[1]+i];
                matrix[center[0]][center[1]+i] = temp[center[0]+i][center[1]];
            }
            return matrix;
        case 7:
            for(int i=-width/2;i<=width/2;i++) {
                matrix[center[0]+i][center[1]+i] = temp[center[0]+i][center[1]];
                matrix[center[0]+i][center[1]] = temp[center[0]+i][center[1]-i];
                matrix[center[0]-i][center[1]+i] = temp[center[0]][center[1]+i];
                matrix[center[0]][center[1]+i] = temp[center[0]+i][center[1]+i];
            }
            return matrix;
        default:
            return matrix;
    }
}

Advertisements

Volleyball Positions

Description:

You are watching a volleyball tournament, but you missed the beginning of the very first game of your favorite team. Now you’re curious about how the coach arranged the players on the field at the start of the game.

The team you favor plays in the following formation:

0 3 0
4 0 2
0 6 0
5 0 1

where positive numbers represent positions occupied by players. After the team gains the serve, its members rotate one position in a clockwise direction, so the player in position 2 moves to position 1, the player in position 3 moves to position 2, and so on, with the player in position 1 moving to position 6.

Here’s how the players change their positions:

Given the current formation of the team and the number of times k it gained the serve, find the initial position of each player in it.

Example

  • For
    formation = [["empty",   "Player5", "empty"],
                 ["Player4", "empty",   "Player2"],
                 ["empty",   "Player3", "empty"],
                 ["Player6", "empty",   "Player1"]]
    

    and k = 2, the output should be

    volleyballPositions(formation, k) = [
        ["empty",   "Player1", "empty"],
        ["Player2", "empty",   "Player3"],
        ["empty",   "Player4", "empty"],
        ["Player5", "empty",   "Player6"]
    ]
    
  • For
    formation = [["empty", "Alice", "empty"],
                 ["Bob",   "empty", "Charlie"],
                 ["empty", "Dave",  "empty"],
                 ["Eve",   "empty", "Frank"]]
    

    and k = 6, the output should be

    volleyballPositions(formation, k) = [
        ["empty", "Alice", "empty"],
        ["Bob",   "empty", "Charlie"],
        ["empty", "Dave",  "empty"],
        ["Eve",   "empty", "Frank"]
    ]
    

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.string formation

    A 4 × 3 array of strings representing names of the players in the positions corresponding to those in the schema above.
    It is guaranteed that for each empty position the corresponding element of formation is "empty".
    It is also guaranteed that there is no player called "empty" in the team.

  • [input] integer k

    The number of times the team gained the serve.

    Constraints:
    0 ≤ k ≤ 109.

  • [output] array.array.string

    Team arrangement at the start of the game.

Tests:
Solution(C#):

string[][] volleyballPositions(string[][] formation, int k) {
    List<Point> rotates = new List<Point>{
        new Point(3, 2, 1, 2), 
        new Point(1, 2, 0, 1), 
        new Point(0, 1, 1, 0), 
        new Point(1, 0, 3, 0), 
        new Point(3, 0, 2, 1), 
        new Point(2, 1, 3, 2)};
    string[][] pre = formation.Select(a => a.ToArray()).ToArray();
    string[][] result = formation.Select(a => a.ToArray()).ToArray();
    k = k % 6;
    if (k < 1) {
        return formation;
    }
    for (int i = 1;i<=k;i++) {
        foreach(Point rotate in rotates) {
            int x1 = rotate.x1, y1 = rotate.y1, x2 = rotate.x2, y2 = rotate.y2;
            result[x2][y2] = pre[x1][y1];
        }
        pre = result.Select(a => a.ToArray()).ToArray();
    }
    return result;
}
public class Point
{
    public Point(int x1,int y1,int x2, int y2) {
        this.x1=x1;
        this.x2=x2;
        this.y1=y1;
        this.y2=y2;
    }
    public int x1{get;set;}
    public int x2{get;set;}
    public int y1{get;set;}
    public int y2{get;set;}
}

Draw Rectangle

Description:

You are implementing a command-line version of the Paint app. Since the command line doesn’t support colors, you are using different characters to represent pixels. Your current goal is to support rectangle x1 y1 x2 y2 operation, which draws a rectangle that has an upper left corner at (x1, y1) and a lower right corner at (x2, y2). Here the x-axis points from left to right, and the y-axis points from top to bottom.

Given the initial canvas state and the array that represents the coordinates of the two corners, return the canvas state after the operation is applied. For the details about how rectangles are painted, see the example.

Example

For

canvas = [['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'],
          ['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'],
          ['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'],
          ['b', 'b', 'b', 'b', 'b', 'b', 'b', 'b'],
          ['b', 'b', 'b', 'b', 'b', 'b', 'b', 'b']]

and rectangle = [1, 1, 4, 3], the output should be


drawRectangle(canvas, rectangle) = [['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'],
                                    ['a', '*', '-', '-', '*', 'a', 'a', 'a'],
                                    ['a', '|', 'a', 'a', '|', 'a', 'a', 'a'],
                                    ['b', '*', '-', '-', '*', 'b', 'b', 'b'],
                                    ['b', 'b', 'b', 'b', 'b', 'b', 'b', 'b']]

Note that rectangle sides are depicted as -s and |s, asterisks (*) stand for its corners and all of the other “pixels” remain the same. Color in the example is used only for illustration.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.char canvasA non-empty rectangular matrix of characters.

    Constraints:
    2 ≤ canvas.length ≤ 10,
    2 ≤ canvas[0].length ≤ 10.

  • [input] array.integer rectangleArray of four integers – [x1, y1, x2, y2].

    Constraints:
    0 ≤ x1 < x2 < canvas[i].length,
    0 ≤ y1 < y2 < canvas.length.

  • [output] array.array.char

Tests:
Solution(C#):

char[][] drawRectangle(char[][] canvas, int[] rectangle) {
    char[][] result = canvas.Select(a => a.ToArray()).ToArray();
    int y1 = rectangle[0], x1 = rectangle[1], y2 = rectangle[2], x2 = rectangle[3];
    for (int i = x1;i<=x2;i++) {
        result[i][y1] = '|';
        result[i][y2] = '|';
    }
    for (int j = y1;j<=y2;j++) {
        result[x1][j] = '-';
        result[x2][j] = '-';
    }
    result[x1][y1] = '*';
    result[x1][y2] = '*';
    result[x2][y2] = '*';
    result[x2][y1] = '*';
    return result;
}

Crossing Sum

Description:

Given a rectangular matrix and integers a and b, consider the union of the ath row and the bth (both 0-based) column of the matrix. Return sum of all elements of that union.

Example

For

matrix = [[1, 1, 1, 1], 
          [2, 2, 2, 2], 
          [3, 3, 3, 3]]

a = 1 and b = 3, the output should be
crossingSum(matrix, a, b) = 12.

Here (2 + 2 + 2 + 2) + (1 + 3) = 12.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.integer matrix2-dimensional array of integers representing a rectangular matrix.

    Constraints:
    1 ≤ matrix.length ≤ 5,
    1 ≤ matrix[0].length ≤ 5,
    1 ≤ matrix[i][j] ≤ 100.

  • [input] integer aA non-negative integer less than the number of matrix rows.

    Constraints:
    0 ≤ a < matrix.length.

  • [input] integer bA non-negative integer less than the number of matrix columns.

    Constraints:
    0 ≤ b < matrix[i].length.

  • [output] integer

Tests:
Solution(C#):

int crossingSum(int[][] matrix, int a, int b) {
    int result = 0;
    for (int i = 0;i<matrix.Length;i++) {
        result += matrix[i][b];
    }
    for (int j = 0;j<matrix[a].Length;j++) {
        if (j != b) {
            result += matrix[a][j];
        }
    }
    return result;
}

Swap Diagonals

Description:

Given a square matrix, your task is to swap its longest diagonals by exchanging their elements at the corresponding positions.

Example

For

matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]

the output should be

swapDiagonals(matrix) = [[3, 2, 1],
                         [4, 5, 6],
                         [9, 8, 7]]

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.integer matrix

    Constraints:
    1 ≤ matrix.length ≤ 10,
    matrix.length = matrix[i].length,
    1 ≤ matrix[i][j] ≤ 1000.

  • [output] array.array.integer

    Matrix with swapped diagonals.

Tests:
Solution(C#):

int[][] swapDiagonals(int[][] matrix) {
    int[][] result=matrix.Select(a => a.ToArray()).ToArray();
    int n = matrix.Length;
    for (int i = 0;i<n;i++) {
        for (int j = 0;j<n;j++) {
            if (i == j || i + j + 1 == n) {
                result[i][j] = matrix[i][n - 1 - j];
            }
        }
    }
    return result;
}

Reverse On Diagonals

Description:

The longest diagonals of a square matrix are defined as follows:

  • the first longest diagonal goes from the top left corner to the bottom right one;
  • the second longest diagonal goes from the top right corner to the bottom left one.

Given a square matrix, your task is to reverse the order of elements on both of its longest diagonals.

Example

For

matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]

the output should be

reverseOnDiagonals(matrix) = [[9, 2, 7],
                              [4, 5, 6],
                              [3, 8, 1]]

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.integer matrix

    Constraints:
    1 ≤ matrix.length ≤ 10,
    matrix.length = matrix[i].length,
    1 ≤ matrix[i][j] ≤ 1000.

  • [output] array.array.integer

    Matrix with the order of elements on its longest diagonals reversed.

Tests:
Solution(C#):

int[][] reverseOnDiagonals(int[][] matrix) {
    int[][] result=matrix.Select(a => a.ToArray()).ToArray();
    int n = matrix.Length;
    for (int i = 0;i<n;i++) {
        int[] row = new int[n];
        for (int j = 0;j<n;j++) {
            if (i == j || i + j + 1 == n) {
                result[i][j] = matrix[n - 1 - i][n - 1 - j];
            }
        }
    }
    return result;
}

Are Isomorphic?

Description:

Two two-dimensional arrays are isomorphic if they have the same number of rows and each pair of respective rows contains the same number of elements.

Given two two-dimensional arrays, check if they are isomorphic.

Example

  • For
    array1 = [[1, 1, 1],
              [0, 0]]
    

    and

    array2 = [[2, 1, 1],
              [2, 1]]
    

    the output should be
    areIsomorphic(array1, array2) = true;

  • For
    array1 = [[2],
              []]
    

    and

    array2 = [[2]]
    

    the output should be
    areIsomorphic(array1, array2) = false.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.integer array1

    Constraints:
    1 ≤ array1.length ≤ 5,
    0 ≤ array1[i].length ≤ 5,
    0 ≤ array1[i][j] ≤ 50.

  • [input] array.array.integer array2

    Constraints:
    1 ≤ array2.length ≤ 5,
    0 ≤ array2[i].length ≤ 5,
    0 ≤ array2[i][j] ≤ 50.

  • [output] boolean

Tests:
Solution(C#):

bool areIsomorphic(int[][] array1, int[][] array2) {
    if (array1.Length != array2.Length)
        return false;
    for (int i = 0; i < array1.Length; i++) {
        if (array1[i].Length != array2[i].Length)
            return false;
    }
    return true;
}