# Thread: Beginner Programming Challenge 14

1. ## Beginner Programming Challenge 14

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.

• Code:
`transform \$a\$ \$b\$ \$c\$ \$d\$`
-> transform coordinates by matrix
|a b|
|c d| which is a linear transformation.
• Code:
`translate \$x\$ \$y\$`
-> translate coordinates by vector
|x|
|y|
• Code:
`enlarge \$scale_factor\$`
-> enlarge by scale factor scale_factor about the origin
• Code:
`rotate \$angle_in_rads\$ clockwise`
• Code:
`rotate \$angle_in_rads\$ anticlockwise`
• Code:
`rotate deg \$angle_in_degs\$ clockwise`
-> rotate angle_in_degs degrees clockwise about the origin
• Code:
`rotate deg \$angle_in_degs\$ anticlockwise`
-> rotate angle_in_degs degrees anticlockwise about the origin
• Code:
`reflect y = \$m\$x`
-> reflect through straight line y=mx
• Code:
`end`
-> read coordinates from next line

The coordinates line, and the printed output should be in the following format
Code:
`\$x1\$,\$y1\$ \$x2\$,\$y2\$, ... \$xn\$,\$yn\$`
EXAMPLE:
input:
Code:
```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:
Code:
`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!

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.
Code:
`./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.
Last edited by dv3500ea; July 17th, 2010 at 11:22 AM. Reason: Added a restriction that languages used should be available in the repos

2. ## Re: Beginner Programming Challenge 14

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

3. ## Re: Beginner Programming Challenge 14

Originally Posted by DanielWaterworth
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.

Originally Posted by DanielWaterworth
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)

Originally Posted by DanielWaterworth
3D space, perhaps, although I'd have to teach myself 3D geometry first. I'm not even considering hyperspace geometry!!!
Last edited by dv3500ea; June 25th, 2010 at 07:46 PM.

4. ## Re: Beginner Programming Challenge 14

Originally Posted by dv3500ea
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).

5. Just Give Me the Beans!
Join Date
Nov 2009
Location
/dev/null
Beans
74

## Re: Beginner Programming Challenge 14

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

6. ## Re: Beginner Programming Challenge 14

Originally Posted by lostinxlation
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.

7. ## Re: Beginner Programming Challenge 14

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?

8. ## Re: Beginner Programming Challenge 14

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

9. ## Re: Beginner Programming Challenge 14

Originally Posted by 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?
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.

Originally Posted by 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
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).
Last edited by dv3500ea; June 29th, 2010 at 06:58 PM.

10. ## Re: Beginner Programming Challenge 14

Originally Posted by dv3500ea
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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•