June 2015

Batalov · 2015-05-31, 21:36

Ponder This, June 2015

I have discovered a truly marvelous demonstration of this proposition that this margin is too narrow to contain.
...Too soon? ;-)

kladner · 2015-05-31, 21:45

Quote:

Originally Posted by Batalov

Ponder This, June 2015

Link returns "not found."

aurashift · 2015-06-01, 23:12

Quote:

Originally Posted by kladner

Link returns "not found."

ooh. someone failed this puzzle.

R. Gerbicz · 2015-06-02, 15:00

The problem is out! Not sure why ibm is using lots of different (semi)-working addresses, what is the fun with using multiple links for the same site? Anyway, here is the problem: https://www.research.ibm.com/haifa/p.../June2015.html
(not sure how long it is online), on the other link: http://domino.research.ibm.com/Comm/...s/May2015.html you can't even see a clickable link for the June's problem.

R. Gerbicz · 2015-06-15, 22:10

There was an update:

"Update (14/6):
We'll add a star to the best solver. Currently it is Alex Wagner with a convex hull of 7,719,775."

LaurV · 2015-06-20, 06:41

Now, this is a very interesting problem, and LaurV has nothing to do this weekend...

Is it only me, or the problem is very suitable for a “genetic” approach?

I “feel” it can be solved mathematically (i.e. an equation can be obtained for the spiral that pass through those 9 points, and resolved for a “maximum possible area”) but a genetic approach is much nicer.

So, we have a chromosome which has a “head” formed by the 2 given starting points (4 integer coordinates), it has a “body” containing the other 7 points (14 integers), and a “tail” where we do the calculus (few more integers to retain the partial norms/distances, coordinates of center points at each step, and, at the end of the tip of the tail, the “area” we are interested in. [well, memory can be saved by not storing the head at all, but this is behind the point of the discussion]

One could remark that we don’t need a complicated algorithm to calculate the convex hull, if we always arrange the points in a spiral (no, I don’t have a proof that the area is maximized in this way, it is just “common sense”), then the “convex hull” is in fact the area given by the last 4 points. Yes, because this is what the “intermediary” points do: they “prepare the sling” to shot those 4 points as far away as possible. Shooting stars… or shooting the moon?

So, a chromosome (head, body, tail) will divide itself in other (maximum 56) chromosomes, in the next generation, where at least one of the coordinates in the body varies with +1 or -1 (the head is not changed, and the tail is only calculus depending on the head and body). Of course, we can have +n or -n, for a small n, (and maximum n*56 offsprings in next generation) but this is not really important.

After G generations we have (say) about ~50^G chromosomes (many of them “fall back” into their parents, at the third, forth, etc generation, same coordinates which once increased, can now decrease, but well, this is how the “evolution” works…

). So, we have to “trim” them. For each “child” which we spawn, we calculate the “tail” and we "cut the head of those with blue tail, because we only like green tail"… ok, this sounds more like snake-theory, orange head green tail is good, orange head blue tail is not good

(remember, the tip of the tail contains the area).

So, we arrange the snakes descending, by the color of the tail, keep few millions of the good snakes, trim the bad snakes, rewind the tape, breed a new generation.

From time to time we examine the snakes on the head of the list, to see if we got that one with pure-emerald-green tail...

Still I can't understand why the people who sent answers stopped at 7 millions, because I reached answers into 16M already, and still feel comfortable. You can see here how the first chromosome in the list looks from a generation to the other. The 9 blue dots are the points (I draw the line just to see the order), and the 8 red dots are the centers of the averaged former points. Technically, the distance from a blue point to its corespondent red point must not be more than 3 times the previous point's distance (well, this is heavier to explain than to do!). At the end of the video there are 3 or 4 configurations (snakes) which reach an area over 15M, one close to 17M (there is no comment, but if you watch the coordinates, you will see when they jump from hundreds to thousands). I have to check if I didn't do a stupid mistake in computing those tails, then I will send my answer in.

R. Gerbicz · 2015-06-20, 07:47

Quote:

Originally Posted by LaurV

Still I can't understand why the people who sent answers stopped at 7 millions, because I reached answers into 16M already

That is quite unlikely (currently my best is roughly 7717000).

"Technically, the distance from a blue point to its corespondent red point must not be more than 3 times the previous point's distance"

You need (from ponder this): "Make sure that every measurement is not exceeding 3 standard deviations from the mean of all the previous one." Lookup at https://en.wikipedia.org/?title=Standard_deviation .

LaurV · 2015-06-20, 14:12

If you look to my video you can see that the "standard deviation" is used, even if I call it "distance". When you compute the standard deviation in the complex plane, it is the square root of the sum of the squares of the distances. Which is (from Pythagoras' Theorem) the sum of the squares of the differences of coordinates (grr, it sounds more complicate to explain than to do, again!). Give or take some distributivity rules, this is just a "distance" for me, but be sure the right formulas were used there. The first center is in (0,0) and the first 3SD is 300, so the third point can be anywhere in a circle with a radius of 300, centered in (0,0). Then, depending on this third point, you find the second center, the second circle can have a radius of up to ~500 (the second 3SD), centered in this new center, and the forth point has to be anywhere inside of this second circle. Etc.

However, you are right about the limit value, it is around 7M7 for me too. I found that shortly after I posted. Due to a stupid programmer error, i was doing the "floor" function (to restrict the calculus to gaussian integers) and totally forgot that for negative numbers, this is the integer which is higher in absolute value. You must do "floor(x)" for positives, and "-floor(-x)" for negatives, to round toward zero

Amazing how such small error propagates, the first 3SD is 300, the second goes to 485 or so, but if you put the first only to 300.66, then you can find the next point to get a value for the 3SD over 500,

LaurV · 2015-06-25, 09:02

Ok, I did a very beautiful implementation for my genetic algorithms, with few tricks and optimizations, and with the right rounding to integers (i.e. when modify a point, it is possible that the other points coming after it will get "out of range", so I did a nice trick to avoid this, of which I am very proud). I love how it works. I let it run for a day (a bit more than 13 hours) in one core. The largest score it produced is 7M64. That is far behind the best displayed score

We are still struggling (but refusing stubbornly to write a "full space search", which would be kinda slower, even with some heuristic like moving the points only on the circles' perimeter, and not inside of all the disks).

Xyzzy · 2015-07-02, 13:22

https://www.research.ibm.com/haifa/p.../June2015.html

R. Gerbicz · 2015-07-07, 14:59

My sent solution was (not posting the actual code and I have made no big attack to find much better point set).:

One solution: (-100,0),(100,0),(-80,289),(443,235),(286,-608),(-1000,-196),(-86,1604),(527,-2045),(3120,422) with convex hull's area=7706357, see my attached code that has found this ( random algorithm and depends on the initial seed, that is time(NULL), so it is unlikely that it will rediscover the same polygon for a new run, but finds several good point sets, with area>=7700000 ).

First I have found a good solution (convex hull's area is close to 7700000), then optimized the point set by perturbation.

To find a good solution I have generated some random point sets where in that each point is (very) far from the previous point's average (but still closer than 3*standard dev.), if we choose (u,v) in such a way that
u=x+r*cos(deg)
v=y+r*sin(deg)
where r<=3*sd (here sd is the standard dev.) and (x,y) is the average of the points so far, then the distance of (u,v) from (x,y) is r, round this (u,v) to an integer point (we still need to check that we won't be far from (x,y)). Finally find the convex hull of the polygon with Jarvis march, then the calculation of the polygon's area is easy. (the double of the area is an integer).

One such convex hull had area=7680036.5 . To perturbate this point set I have choosen close degrees to the above original degree selection.

2015-05-31, 21:36	#1
Batalov "Serge" Mar 2008 San Diego, Calif. 24247₈ Posts	June 2015 Ponder This, June 2015 I have discovered a truly marvelous demonstration of this proposition that this margin is too narrow to contain. ...Too soon? ;-) Last fiddled with by Batalov on 2015-06-02 at 15:50 Reason: 1st of June comes earlier in Beer Sheva but not as early as in Lamphun

2015-06-02, 15:00	#4
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 3165₈ Posts	The problem is out! Not sure why ibm is using lots of different (semi)-working addresses, what is the fun with using multiple links for the same site? Anyway, here is the problem: https://www.research.ibm.com/haifa/p.../June2015.html (not sure how long it is online), on the other link: http://domino.research.ibm.com/Comm/...s/May2015.html you can't even see a clickable link for the June's problem. Last fiddled with by R. Gerbicz on 2015-06-02 at 15:01

2015-06-20, 06:41	#6
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2×5,179 Posts	Now, this is a very interesting problem, and LaurV has nothing to do this weekend... Is it only me, or the problem is very suitable for a “genetic” approach? I “feel” it can be solved mathematically (i.e. an equation can be obtained for the spiral that pass through those 9 points, and resolved for a “maximum possible area”) but a genetic approach is much nicer. So, we have a chromosome which has a “head” formed by the 2 given starting points (4 integer coordinates), it has a “body” containing the other 7 points (14 integers), and a “tail” where we do the calculus (few more integers to retain the partial norms/distances, coordinates of center points at each step, and, at the end of the tip of the tail, the “area” we are interested in. [well, memory can be saved by not storing the head at all, but this is behind the point of the discussion] One could remark that we don’t need a complicated algorithm to calculate the convex hull, if we always arrange the points in a spiral (no, I don’t have a proof that the area is maximized in this way, it is just “common sense”), then the “convex hull” is in fact the area given by the last 4 points. Yes, because this is what the “intermediary” points do: they “prepare the sling” to shot those 4 points as far away as possible. Shooting stars… or shooting the moon? So, a chromosome (head, body, tail) will divide itself in other (maximum 56) chromosomes, in the next generation, where at least one of the coordinates in the body varies with +1 or -1 (the head is not changed, and the tail is only calculus depending on the head and body). Of course, we can have +n or -n, for a small n, (and maximum n56 offsprings in next generation) but this is not really important. After G generations we have (say) about ~50^G chromosomes (many of them “fall back” into their parents, at the third, forth, etc generation, same coordinates which once increased, can now decrease, but well, this is how the “evolution” works… ). So, we have to “trim” them. For each “child” which we spawn, we calculate the “tail” and we "cut the head of those with blue tail, because we only like green tail"… ok, this sounds more like snake-theory, orange head green tail is good, orange head blue tail is not good (remember, the tip of the tail contains the area). So, we arrange the snakes descending, by the color of the tail, keep few millions of the good snakes, trim the bad snakes, rewind the tape, breed a new generation. From time to time we examine the snakes on the head of the list, to see if we got that one with pure-emerald-green tail... Still I can't understand why the people who sent answers stopped at 7 millions, because I reached answers into 16M already, and still feel comfortable. You can see here how the first chromosome in the list looks from a generation to the other. The 9 blue dots are the points (I draw the line just to see the order), and the 8 red dots are the centers of the averaged former points. Technically, the distance from a blue point to its corespondent red point must not be more than 3 times the previous point's distance (well, this is heavier to explain than to do!). At the end of the video there are 3 or 4 configurations (snakes) which reach an area over 15M, one close to 17M (there is no comment, but if you watch the coordinates, you will see when they jump from hundreds to thousands). I have to check if I didn't do a stupid mistake in computing those tails, then I will send my answer in. Last fiddled with by LaurV on 2015-06-20 at 06:58 Reason: WTF is with strange formatting? (I copy/pasted some text, is that why?)*

2015-06-20, 14:12	#8
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2×5,179 Posts	If you look to my video you can see that the "standard deviation" is used, even if I call it "distance". When you compute the standard deviation in the complex plane, it is the square root of the sum of the squares of the distances. Which is (from Pythagoras' Theorem) the sum of the squares of the differences of coordinates (grr, it sounds more complicate to explain than to do, again!). Give or take some distributivity rules, this is just a "distance" for me, but be sure the right formulas were used there. The first center is in (0,0) and the first 3SD is 300, so the third point can be anywhere in a circle with a radius of 300, centered in (0,0). Then, depending on this third point, you find the second center, the second circle can have a radius of up to ~500 (the second 3SD), centered in this new center, and the forth point has to be anywhere inside of this second circle. Etc. However, you are right about the limit value, it is around 7M7 for me too. I found that shortly after I posted. Due to a stupid programmer error, i was doing the "floor" function (to restrict the calculus to gaussian integers) and totally forgot that for negative numbers, this is the integer which is higher in absolute value. You must do "floor(x)" for positives, and "-floor(-x)" for negatives, to round toward zero Amazing how such small error propagates, the first 3SD is 300, the second goes to 485 or so, but if you put the first only to 300.66, then you can find the next point to get a value for the 3SD over 500, Last fiddled with by LaurV on 2015-06-20 at 14:20

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
June 2017	R. Gerbicz	Puzzles	14	2017-07-03 20:01
June 2016	Xyzzy	Puzzles	16	2016-07-07 02:51
LLRnet/PRPnet rally June 4th-6th	gd_barnes	No Prime Left Behind	61	2010-07-30 17:28
Max on the move: vacation June 28/30-July 4	mdettweiler	No Prime Left Behind	8	2009-07-05 05:20
LLRnet server rally 400<k<1001 June 20-22	mdettweiler	No Prime Left Behind	67	2008-06-23 15:32

2015-06-15, 22:10	#5
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 3165₈ Posts	There was an update: "Update (14/6): We'll add a star to the best solver. Currently it is Alex Wagner with a convex hull of 7,719,775."

2015-06-25, 09:02	#9
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2×5,179 Posts	Ok, I did a very beautiful implementation for my genetic algorithms, with few tricks and optimizations, and with the right rounding to integers (i.e. when modify a point, it is possible that the other points coming after it will get "out of range", so I did a nice trick to avoid this, of which I am very proud). I love how it works. I let it run for a day (a bit more than 13 hours) in one core. The largest score it produced is 7M64. That is far behind the best displayed score We are still struggling (but refusing stubbornly to write a "full space search", which would be kinda slower, even with some heuristic like moving the points only on the circles' perimeter, and not inside of all the disks).

2015-07-02, 13:22	#10
Xyzzy Aug 2002 10000111111001₂ Posts	https://www.research.ibm.com/haifa/p.../June2015.html

2015-07-07, 14:59	#11
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 3×19×29 Posts	My sent solution was (not posting the actual code and I have made no big attack to find much better point set).: One solution: (-100,0),(100,0),(-80,289),(443,235),(286,-608),(-1000,-196),(-86,1604),(527,-2045),(3120,422) with convex hull's area=7706357, see my attached code that has found this ( random algorithm and depends on the initial seed, that is time(NULL), so it is unlikely that it will rediscover the same polygon for a new run, but finds several good point sets, with area>=7700000 ). First I have found a good solution (convex hull's area is close to 7700000), then optimized the point set by perturbation. To find a good solution I have generated some random point sets where in that each point is (very) far from the previous point's average (but still closer than 3standard dev.), if we choose (u,v) in such a way that u=x+rcos(deg) v=y+rsin(deg) where r<=3sd (here sd is the standard dev.) and (x,y) is the average of the points so far, then the distance of (u,v) from (x,y) is r, round this (u,v) to an integer point (we still need to check that we won't be far from (x,y)). Finally find the convex hull of the polygon with Jarvis march, then the calculation of the polygon's area is easy. (the double of the area is an integer). One such convex hull had area=7680036.5 . To perturbate this point set I have choosen close degrees to the above original degree selection.