Hello There, Guest!
View New Posts  |  View Today's Posts
Code Challenge [Help Needed]

  • 0 Vote(s) - 0 Average


01-05-2016, 11:45 AM #1
Zultralord
Junior Member
**
Posts: 5 Threads:3 Joined: Jan 2016 Reputation: 0

Code Challenge [Help Needed]
Hello Everyone! Thanks for taking the time to view my first forum post! Cool I was on a code challenge site called codeingame.com today and came across a problem that is absolutely eating my brain alive! So I thought I would ask for some help before I hurt myself. I've listed the instructions it gave me below.

Instructions
A console program must be created that will take 4 pairs of random numbers. These pairs represent coordinate points on a graph. The program written must return whether the given pairs make a square. For example, the following ints are passed into the console program ordered in x, y coordinate format (0,0) (0,-2) (-2,-2) (-2,0) The result would be true because they form a square.

http://1drv.ms/1ZM3DYa <- Picture of some wack notes lol

I realize that this is more a math problem given that the only thing to do is parse the input string but for the life of me I can't get it. Maybe it's been too long since that last math class.

Thanks for the help and I hope someone can get a good brain teaser out of this.


--Update--

Ok so after finding the department head for math at the university I work in i.t at I've managed to learn more about how to solve the problem from a math standpoint, unfortunately it get a little more complicated than what I originally anticipated because the first step requires us finding out what plane the square might be on (if the same one). I'll throw some stuff up here once I've had a chance to settle in from work. Cheers!

--Update--

Alright, I've made a GUI with some field inputs now it's time for the math. More soon.
[Image: 4f2505d764c8c94a598664b313f61730.png]
This post was last modified: 01-09-2016, 06:08 PM by Zultralord.
- Neckbeard wannabe

01-08-2016, 04:17 AM #2
Mazzn
ლ(ಠ益ಠლ)
*******
Administrators
Posts: 198 Threads:16 Joined: Sep 2013 Reputation: 19

RE: Code Challenge [Help Needed]
First of all welcome to the forum and sorry for not helping you out earlier!

Oh my... My math skills are very rusty (rarely need it in IT, and if I need to I use Google or Calc.exe) but let me see what I can recall. Here's what I think you should do:

Before you read anything else: we're in 2D space, right? Makes this easier than 3D and you won't have to worry about the plane they're in, since there is only one. (Unless I misunderstood what you meant, English isn't my primary language so I'm not very familiar with math terms.)

I'll call the points p1, p2, p3 and p4.

Before doing anything else, check if:
- more than two points share their x or y
- at least two points share both x and y
If either is true, we're definitely not looking at a square (in 2D space). We can also confirm the second case by checking if the distance between two points is 0 instead of checking x and y.

Now check the distance between the points.
Code:
double distanceTo2 = distance(p1, p2);
double distanceTo3 = distance(p1, p3);
double distanceTo4 = distance(p1, p4);

One of the following must be true, otherwise it's not a square:
Code:
(distanceTo2 == distanceTo3 and distanceTo4 == sqrt(pow(distanceTo2,2) + pow(distanceTo3,2)))
or
(distanceTo2 == distanceTo4 and distanceTo3 == sqrt(pow(distanceTo2,2) + pow(distanceTo4,2)))
or
(distanceTo3 == distanceTo4 and distanceTo2 == sqrt(pow(distanceTo3,2) + pow(distanceTo4,2)))
This tells us that the distance from p1 to the other points qualify (but not confirm) it as square, due to two vectors being the same length and, if it is a square, the diagonal distance to the furthest point would be correct as well.

But as of now, assuming this square (in our example "code" above that is the second case) we have only confirmed that:
- p2 and p4 lie somewhere on the red circle
- p3 lies somewhere on the purple circle



This doesn't tell us anything yet, as the possible constellations are not conclusive.

However by confirming the distance from p1 to p2 and p4 we can triangulate the only possible position of p3 for it to be a square. As seen here, we know that both p1 and p3 must have the same distance to both p2 and p4:




So we have to calculate the distance from p3 to p2 and p4. This way we can assure that (on a 2D plane) the quadrangle is at least a diamond, since we confirmed in the beginning that p1 and p3 are not the same point.

Code:
distance(p1, p2) == distance(p1, p4) == distance(p3, p2) == distance(p3, p4)

Since we also confirmed that
Code:
distance(p1, p3) == sqrt(distance(p1, p2), 2) + distance(p1, p4))
we know for certain that we are looking at a square.

If you want to make really sure, check the distance between p2 and p4:
Code:
distance(p2, p4) == distance(p1, p3)

Here's an illustration of all the things we calculated.

...Well, at least I am certain I am looking at one. Here goes hoping I didn't mess up, that'd be embarrassing :O


----

Edit: I guess an alternative approach would be to check the angles of the vectors in relation to each other.

Careful: I'm not 100% sure if this if correct. Well, that applies to both approaches, but the thought just crossed my mind and I figured I'd write it down for you ;)


You'd start out looking at p1-p2, make that our reference vector. (red)

Check if the other two vectors p1-p3 (blue) and p1-p4 (green) are at a 45° or 90° angle (origin p1). Two should be at a 90° angle to each other and both at a 45° angle to the remaining one.

See here: Green & red -> 90°
Green & blue as well as red & blue -> 45°


If the opposite end (p3 in this example) also has a 90° angle between the vectors (p3-p2 and p3-p4) it guarantees it to be a rectangle, and due to the 45° angle of the diagonal line it's a confirmed square.

Hope that was understandable and correct :P
This post was last modified: 01-08-2016, 08:40 AM by Mazzn.
Visit me at mazzn.net & blog.mazzn.net!
//This is very important :)

Self.KeepImproving(true);


01-09-2016, 12:26 AM #3
Zultralord
Junior Member
**
Posts: 5 Threads:3 Joined: Jan 2016 Reputation: 0

RE: Code Challenge [Help Needed]
Thanks Mazzn!

Some wonderful insight here. Let me look into this in the morning and see if I can put something together based on your advice. Thanks Chief :)
- Neckbeard wannabe

01-09-2016, 03:20 AM #4
AceInfinity
Developer
*******
Administrators
Posts: 9,733 Threads:1,026 Joined: Jun 2011 Reputation: 76

RE: Code Challenge [Help Needed]
Nice to see that there are others using Codingame :) It's a nice programming website for challenges. My profile: https://www.codingame.com/profile/788dc0...24a0381221

The shortest code clashes get to be lots of fun with C:
Code:
main(i,h){scanf("%d",&h);while(++i<5)h+=(h*=2);printf("%d\n",h);}

Haha
This post was last modified: 01-09-2016, 03:40 AM by AceInfinity.


Microsoft MVP .NET Programming - (2012 - Present)
®Crestron DMC-T Certified Automation Programmer

Development Site: aceinfinity.net

 ▲
 ▲ ▲




Forum Jump:


Possibly Related Threads...
Thread Author Replies Views Last Post
   IsPrime Function (Code Golfing Style) AceInfinity 1 823 01-01-2016, 06:52 PM
Last Post: AceInfinity
  C++ Pirate Challenge - The Survivor AceInfinity 8 3,703 01-06-2014, 10:33 PM
Last Post: AceInfinity
  Quick Challenge: Explain the output AceInfinity 2 1,499 11-30-2013, 06:21 PM
Last Post: AceInfinity
  Hola coding challenge ... Get money easy! Florin 4 4,284 09-14-2013, 02:10 PM
Last Post: AceInfinity
  [C/C++] Programming Challenge AceInfinity 10 5,394 06-25-2013, 09:44 PM
Last Post: KoBE


Users browsing this thread: 1 Guest(s)