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

#ComputerScience

Note by Mark Mottian
6 years, 10 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

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 - 6 years, 10 months ago

Log in to reply

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 - 6 years, 10 months ago

Log in to reply

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 - 6 years, 10 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 - 6 years, 10 months ago

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 - 6 years, 10 months ago

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 - 6 years, 10 months ago

:/

Rohan Gupta - 6 years, 10 months ago
×

Problem Loading...

Note Loading...

Set Loading...