[Guest]

Got this idea from riddles in other threads:

You have N number of metallic spikes planted into the ground and all arrange in a circle with equal distances between each neighboring spikes (in other words a perfect polygon) You have a string with you that you need to pass around all the spikes creating a net that has every spike connected to every other spike with minimum number of repeated connections...

In other words: connect all dots without going over the line...

Write an algorithm to do it (you can write it in normal speech, not necessarily a comp language)

(Note: actually the dots don't have to be in a circle, they can be scattered anywhere you want so long as no 3 dots are in a straight line)

[Guest]

well this was easy.

assuming the spikes are in a circle,

connect each spike to the one next to it. then connect each spike to every 2nd spike.

then connect each spike to every 3rd spike, and so on.

[Guest]

could it be

((n-1)^2 + (n-1)) / 2

not sure

[Guest]

well this was easy.

assuming the spikes are in a circle,

connect each spike to the one next to it. then connect each spike to every 2nd spike.

then connect each spike to every 3rd spike, and so on.

That wouldn't work in 9 spikes...

[Guest]

okay, okay, fine...

connect one spike to the next spike, then connect that spike to the next next spike (i.e. skip one.)

then skip 2, skip 3, etc. up to number of spikes/2. then go back to connecting 1.

Edited September 2, 2010 by rookie1ja

[Guest]

lets say N=number of spikes set up in said fashion

if Nmod2=1 (meaning we have an odd number) then 0 lines must be re-drawn in order to connect all spikes

if Nmod2=0 (we have an even number) then N/2-1 lines must be re-drawn.

i remember something from high school stating that 'if your want to connect all points, or islands, with one pass, it is possible if and only if the number of points, islands, with an odd number of connections, bridges, is equal to or less than two.

therefore connecting n points is possible if all points have an even number of connections to make which means we have an odd number of points, because we wont connect points to themselves. and if we have an even number of points we will have to redraw at least one line because all points have an odd number of connections, the only exception being a two point arrangement for obvious reasons.

disclaimer: I've never taken an algorithm class so if i don't describe something or word something right please ask me, but i do know essentially what an algorithm is.

i'm going to b using jargon i created because i don't know any other way to do it. when I say level or lv and then a # i'm refering to how many dots ahead to which i'm making a connection from my current dot in a direction i'm moving either forward or backward going left or right doesn't matter as long as you can keep up on your paper.

now i've worked all the to 9 points and found the rules described in the math part.

So lets begin the process of connecting all the points in the in a 5, 6 and 9 point array.

when drawing it I always arrange them in a polygonal fashion and turn the points so that one dot is above all the others. this is my starting point. I like to get rid of the lv1 and lv2 connections at the same time. so I move,draw,connect, forward lv1 and backward lv2 and repeat until i come back to my starting point. this part works for both odd and even number arrays. this will complete 5 point array If all the points aren't connected then move forward lv3 and continue until you reach the starting point. If you cant reach the starting point without re-drawing a line you do one of two things.

1.) if you are drawing on a even number array then now is the time to start redrawing lines. move forward lv1, redraw it, and move to the point directly across from this one and repeat until remaining connections are made.

2.) if you are drawing on a odd number array then If Nmod3=\= 0 then move forward lv3 until all lv3 connections are made. If Nmod3==0 then when you return to your starting point make a forward lv4 connection and then do lv3 connections until you return the the point with which you made the lv4 connection. repeat until remaining lv3 connections are made. then move forward lv4 until all lv4 connections are made.

this is where my current algorithm ends because I've only work array with up to 10 points, but i'm sure you can see that being able to make a higher connection to complete lower connection rings will allow you to solve all odd number arrays without having to redraw any lines and all even number arrays while only haveing to redraw N/2-1 lines. I dont know if this is the easiest algorithm to understand and I'll bet there is an easier one. plz ask questions if there is a misunderstandings or nonunderstandings.

[Guest]

as an interesting side note, you can turn my algorithm into a factor algorithm.

here's how.

def factor(x):

	value = 0

	for i in range(1,int(x/2)):

		value += i

		if value >= x:

			value -= x

		if value == 0:

			return gcd(i,x)

	return 0

def gcd(a,b):

	while a != b:

		if a> b:

			a -= b

		else:

			b -= a

	return a

print(factor(37*43))