Waste less time on Facebook — follow Brilliant.
×

Hardest Problem from South African Programming Olympiad 2014 !

The Programming Olympiad is a prestigious event where thousands of programmers from South Africa compete to be placed among the top 15 programming students in the country. The first round was written on 1 August 2014 and the paper consisted of five thought-provoking programming problems.

Unfortunately, I was unable to solve the last question and I need your help.


PROBLEM #5: Transformation

Some doors can be unlocked using a key card - a plastic card with holes in it. A key card may be square like this :(O means a hole, X means no hole); but it may also be a rectangle or triangle.

XXXO
XXOX
XOXX
XXOX

However in order to work, these specific key cards have to be rotated or flipped according to one or more of these transformation instructions:

R = Rotate 90 degrees to the right

T = Top to bottom flip: you see the back - upside down

L = Left to right flip; you see the back - mirrored

Task

Write a program that will take the given key card, rotate, and/or flip it as instructed, and print out the resulting key card. No card will be more than 40 by 40 spaces.

Example:

Input:

XXXO
XXOX
XOXX
XXOX

Transformation: R, L

Output:

XXXX
XXOX
XOXO
OXXX

Explanation:

After rotating by 90 degrees:

XXXX
XOXX
OXOX
XXXO

After a left to right flip:

XXXX
XXOX
XOXO
OXXX

Credit: Allan Smithee

Note by Mark Mottian
2 years, 5 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Test your program with:

a)

XXXO
XXOX
XOXX
XXOX

Transformation: T

b)

XXXO
XXOX
XOXX
XXOX
XXXX

Transformation: T, L, R

c)

   O
  XXO
 OXXXO
XOOOXXX

Transformation: R, T, L Mark Mottian · 2 years, 5 months ago

Log in to reply

@Mark Mottian I think using a two-dimensional array and then creating methods for each transformation works for the first two cases. I'm clueless how to do the triangle case though... Daniel Liu · 2 years, 5 months ago

Log in to reply

@Daniel Liu Hi Daniel. First off, I'm a big fan. Davis Sparinskis suggested that you can use a space 'character' to get the correct shape for the triangle. My initial thought was to also use a two dimensional array, however, I encountered some problems. Please HELP! Mark Mottian · 2 years, 5 months ago

Log in to reply

@Daniel Liu Couldn't it be assumed that in the triangular case there is a third symbol - space? Then the triangular case would be the same as the others since the symbol itself doesn't matter as long as it's there. Unless that's against the rules or I've misunderstood the input. Dāvis Sparinskis · 2 years, 5 months ago

Log in to reply

@Dāvis Sparinskis That is a legitimate approach. Do you know how to implement this in a program? Mark Mottian · 2 years, 5 months ago

Log in to reply

This is my solution using a 2-D array and treating each of the cards as a square, with symbols ' o ' ,' x ' and ' '. The downside with this approach is that all of the symbols have to be entered manually.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
public class control_structures {

    public static void main(String[] args){


        //Initialise input array, the length of the rows and columns and columns must be the same
       //i.e. n {rows} of elements with n 'columns' in each line.

        char inputArray[][] = {{' ',' ',' ',' ',' ',' ',' '},
                               {' ',' ',' ',' ',' ',' ',' '},
                               {' ',' ',' ',' ',' ',' ',' '},
                               {' ',' ',' ','o',' ',' ',' '},
                               {' ',' ','x','x','o',' ',' '},
                               {' ','o','x','x','x','o',' '},
                               {'x','o','o','o','x','x','x'},
        };


        //Initialise i.
        int i;

        i = inputArray.length; 

        //Initialise transferArray, which will be used for the rotation 'R'.
        char[][] transferArray = new char[i][i];

        //Initialise transformationsArray. Input all the transformations required as capital letters.
        char[] transformationsArray = {'R','T','L'};

        int numberOfTransformations;

        numberOfTransformations = transformationsArray.length;

        //Transformations for loops
        for(int counter = 0; counter < numberOfTransformations; counter++){

        //Rotate array 90 degrees
        if (transformationsArray[counter] == 'R' ){
            //Put elements of inputArray into transferArray
            for(int counterRow = 0; counterRow < i; counterRow++){
                for(int counterColumn = 0; counterColumn < i; counterColumn++){
                    transferArray[counterRow][counterColumn] = inputArray[((i) - 1) - counterColumn][counterRow];
                }
            }

            //Put elements of transferArray into inputArray.
            for(int counterRow = 0; counterRow < i; counterRow++){
                for(int counterColumn = 0; counterColumn < i; counterColumn ++){
                    inputArray[counterRow][counterColumn] = transferArray[counterRow][counterColumn];
                }
            }

        }

        //Flip array left/right
        else if(transformationsArray[counter] =='L'){

        char transfer;//This will store the current element temporarily whilst the element it is swapping with is put in it's old array index.

            for (int counterRow = 0;counterRow < i;counterRow ++){
                for (int counterColumn = 0; counterColumn < (i/2);counterColumn ++){

                    transfer = inputArray[counterRow][counterColumn]; //Transfer array holds all the elements in the left row of input array.

                    int counterColumn2 =  ((i - 1) - counterColumn); //Place the right row of input array into the left row of input array.
                    inputArray[counterRow][counterColumn] = inputArray[counterRow] [counterColumn2];

                    inputArray[counterRow][counterColumn2] = transfer; //Place the elements in transfer array into the right row of 
                                                                       //input array.

                }
            }
        }

        //Flip array top/bottom.
        else if(transformationsArray[counter] == 'T'){

        char transfer;

            for (int counterRow = 0;counterRow < (i/2);counterRow ++){
                for (int counterColumn = 0; counterColumn < i;counterColumn ++){

                    transfer = inputArray[counterRow][counterColumn]; //Place current element of the array into transfer.

                    int counterRow2 = ((i - 1) - counterRow); //Place the bottom column of the array into the top column of the array.
                    inputArray[counterRow][counterColumn] = inputArray[counterRow2] [counterColumn];

                    inputArray[counterRow2][counterColumn] = transfer;//Place the elements in transfer array into the bottom line of 
                                                                      //input array.
                }
            }
        }
        }

        //Output result for loop

        String output;

        for(int counterRow = 0; counterRow < (i); counterRow++){
            output = "";
            for(int counterColumn = 0; counterColumn <(i); counterColumn++){
            output = output + String.valueOf(inputArray[counterRow][counterColumn]);    
            }
            System.out.println(output);
        }

    }

    }
William Macdonald · 2 years, 5 months ago

Log in to reply

:/ Rohan Gupta · 2 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...