Beginner Programming Challenge 14

[dv3500ea]

Beginner Programming Challenge # 14

As the winner of Beginner Programming Challenge 13,
it is my turn to propose a challenge.

It will be quite mathematical but very useful for those wanting
to get into graphics/game programming but also requires some simple
text parsing.

Consider a graph on conventional Cartesian axes.
You will be given a set of transformations to perform from a file
of 'commands'. These will be fed into stdin. When your program reaches a
line begginning 'end', it should read one line of coordinates and transform
each pair of coordinates, printing the transformed coordinates.

I will demonstrate the commands. The parts of the commands that should be taken as
variables will be enclosed in 2 $ signs like $this$. Note that in the real commands
these $ signs will no appear - they are used for clarity.

• transform $a$ $b$ $c$ $d$

  -> transform coordinates by matrix
  |a b|
  |c d| which is a linear transformation.

• translate $x$ $y$

  -> translate coordinates by vector
  |x|
  |y|

• enlarge $scale_factor$

  -> enlarge by scale factor scale_factor about the origin

• rotate $angle_in_rads$ clockwise

  -> rotate angle_in_rads radians clockwise about the origin

• rotate $angle_in_rads$ anticlockwise

  ->rotate angle_in_rads radians anticlockwise about the origin

• rotate deg $angle_in_degs$ clockwise

  -> rotate angle_in_degs degrees clockwise about the origin

• rotate deg $angle_in_degs$ anticlockwise

  -> rotate angle_in_degs degrees anticlockwise about the origin

• reflect y = $m$x

  -> reflect through straight line y=mx

• end

  -> read coordinates from next line

The coordinates line, and the printed output should be in the following format

$x1$,$y1$ $x2$,$y2$, ... $xn$,$yn$

EXAMPLE:
input:

transform 1 0 0 1
translate 1 2
translate -1 -2
enlarge 2
enlarge 0.5
enlarge -1
enlarge -1
rotate 3.141592653589 clockwise
rotate 3.141592653589 anticlockwise
rotate deg 180 clockwise
rotate deg 180 anticlockwise
reflect y = 0x
reflect y = 0x
end
0,0 1,1 2,2 -1,-1, 0.5,0.5

output:

0,0 1,1 2,2 -1,-1, 0.5,0.5

I know this may seem a bit daunting but the input is easy enough to parse.
It would be a very good idea to research 'matrix transformations', 'matrix multiplication'
and 'inverse of a 2x2 matrix'. It is likely you have not come across this area of
maths before but there are plenty of places online to look it up and the actual
algorithms are relatively simple.

Rules:

• You may use any language AS LONG AS IT IS AVAILABLE IN THE UBUNTU REPOSITORIES
  
• You may use any standard libraries available with your language
  unless they have specific matrix or vector functionality
• You may not use any non-standard libraries
• You should provide details of how to compile/run your program
• You may ask for helps or hints if you get stuck
• Any obfusgated code or precompiled programs will not be marked

You will be marked out of 100. There will be 10 marks each available for
correctly implementing translate, enlarge, rotate, reflect and 20 marks
for correctly implementing transform. There will be 10 marks for correctly
parsing/formatting the input/output. More subjectively, there will
be up to 10 marks for each of:

• layout and commenting (use whitespace and descriptive comments)
• elegance of design (use object oriented or functional techniques)
• speed of execution (to be tested with the time command)

There may be chance for extra credit later on.

Good luck, and have fun coding!

EXTENSION TASKS:
These are worth 5 marks each, but you can't get over 100 marks.

1. allow a '-c' flag to be passed that causes your calculated coordinates to be converted to the 'computer' coordinate system (by which I mean origin at the top-left hand corner and positive direction down and right). The argument after the -c flag should be the x and y coordinates of the Cartesian origin on this coordinate system, separated by a ','. eg.
   

   ./program -c '100,200'

   puts the origin 100px right and 200px down from 0,0.
2. Accept an '-i' flag that prints the translation vector and transformation matrix that reverse completely all of the transformations performed from the input.

[DanielWaterworth]

This seems a little easy even for a beginner. What's the extra credit options? How about n-dimensional space?

[dv3500ea]

This seems a little easy even for a beginner.

Do you think?

In the UK, you need to be doing AS level further maths to even cover what a matrix is.

What's the extra credit options?

I will come up with these in due course. I'm considering:

• The representation of the cartesian coordinates on a computer screen.
• Asking for 1 matrix and 1 vector that reverse all of the transformations
• Some sort of function plotting ability (as in getting a list of coordinates and transforming them from a mathematical function)

How about n-dimensional space?

3D space, perhaps, although I'd have to teach myself 3D geometry first. I'm not even considering hyperspace geometry!!!

[DanielWaterworth]

In the UK, you need to be doing AS level further maths to even cover what a matrix is.

I know, in fact I'll have finished A2 on Tuesday, which is my last exam. It used to be part of the GSCE syllabus. I suppose the main reason it's simple is because there's no variable sized... anything [=, (except the input).

[lostinxlation]

I think you should drop the speed requirement from the judging criteria. Having speed in mind, the scripting languages are all out.

[dv3500ea]

I think you should drop the speed requirement from the judging criteria. Having speed in mind, the scripting languages are all out.

Don't be put off using scripting languages. In my mind speed is the least important criterion. If your program uses a scripting language this will cause it to be a bit slower, so you will lose some of the speed marks but it is more than likely that you will gain marks for elegance and find it easier to implement.

My main intention for the speed category is to make people think about how they implement the program. For example, it is possible to represent any number of the listed transformations in 6 numbers. You could alternatively store each transformation and apply them all separately. One of these is clearly going to be better performing.

[DaGarver]

Are we allowed to assume that the last line of the text file used for input is reserved for coordinates only? As in, the second to last line is always "end" and the following line is the set of points to perform operations on?

[burton247]

I finished my current project:

a matrix calculator for nxn matrices.

Does all the ERO, addition, multiplication and calculates det, inverse etc.

The inverse bit was good cause of reusing code, use of recursion and stuff

[dv3500ea]

Are we allowed to assume that the last line of the text file used for input is reserved for coordinates only? As in, the second to last line is always "end" and the following line is the set of points to perform operations on?

The line after the 'end' line will only have coordinates on it but don't assume this is at the last line in the file. You can ignore lines after the coordinate line though.

I finished my current project:

a matrix calculator for nxn matrices.

Does all the ERO, addition, multiplication and calculates det, inverse etc.

The inverse bit was good cause of reusing code, use of recursion and stuff

That would be very useful for this challenge. Feel free to use this if you are doing the challenge. Note that this challenge only requires operations on 2x2 and 2x1 matrices. I'd be interested to know how det/inverse is found from nxn matrices (I've only covered these operations on 2x2 matrices in my maths class).

[DaGarver]

I'd be interested to know how det/inverse is found from nxn matrices (I've only covered these operations on 2x2 matrices in my maths class).

Determinant of an NxN matrix is found by using a technique called cofactor expansion. The inverse of a matrix is actually equivalent to the reciprocal of the determinant times a matrix of its cofactors (http://mathworld.wolfram.com/MatrixInverse.html).

Linear Algebra is quite an interesting subject. You get to see how a lot of things relate to each other, a lot of the stuff you take for granted when doing basic algebra. And, in all honesty, it seems like having a background in it is a major help for this challenge.