# 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

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

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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

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

- 6 years, 10 months ago

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...

- 6 years, 10 months ago

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.

- 6 years, 10 months ago

That is a legitimate approach. Do you know how to implement this in a program?

- 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!

- 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); } } } 

- 6 years, 10 months ago

:/

- 6 years, 10 months ago