mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2015-05-31, 21:36   #1
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5×23×79 Posts
Default 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
Batalov is offline   Reply With Quote
Old 2015-05-31, 21:45   #2
kladner
 
kladner's Avatar
 
"Kieren"
Jul 2011
In My Own Galaxy!

26D016 Posts
Default

Quote:
Originally Posted by Batalov View Post
Link returns "not found."
kladner is offline   Reply With Quote
Old 2015-06-01, 23:12   #3
aurashift
 
Jan 2015

25310 Posts
Default

Quote:
Originally Posted by kladner View Post
Link returns "not found."
ooh. someone failed this puzzle.
aurashift is offline   Reply With Quote
Old 2015-06-02, 15:00   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101011000112 Posts
Default

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
R. Gerbicz is offline   Reply With Quote
Old 2015-06-15, 22:10   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

7·197 Posts
Default

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."
R. Gerbicz is offline   Reply With Quote
Old 2015-06-20, 06:41   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5×11×157 Posts
Default

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.

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?)
LaurV is offline   Reply With Quote
Old 2015-06-20, 07:47   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

7×197 Posts
Default

Quote:
Originally Posted by LaurV View Post
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 .
R. Gerbicz is offline   Reply With Quote
Old 2015-06-20, 14:12   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5·11·157 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2015-06-25, 09:02   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5×11×157 Posts
Default

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).
LaurV is offline   Reply With Quote
Old 2015-07-02, 13:22   #10
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

23×331 Posts
Default

https://www.research.ibm.com/haifa/p.../June2015.html
Xyzzy is offline   Reply With Quote
Old 2015-07-07, 14:59   #11
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

7·197 Posts
Default

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.
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 00:06.

Thu Aug 13 00:06:07 UTC 2020 up 26 days, 19:52, 0 users, load averages: 1.64, 1.59, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.