October 2018

[mtve]

Originally Posted by Batalov

I am not afraid to post mine. It's ugly (random shaking)

same here, not really readable, https://gist.github.com/mtve/2604be8...561e77343dd89b

random at first N1 levels and full search after.

[EdH]

If anyone would like to criticize my amateur attempt, I'll try to post it below. The first ten points were random with a full search for an eleventh. I got thousands of supposed ten point successes, but never got an eleventh. It's quite possible my method had no chance of success, but all the 10 point successes gave me hope. I started and stopped some of the threads at least daily to help the randomness. I also tried x values as low as 8. Here's what I saw a lot of:

$ ./p2018Oct4 23
x size: 23
y size: 26
(8,25)
(1,16)
(19,17)
(21,6)
(21,25)
(16,2)
(10,1)
(2,12)
(18,0)
(5,5)
10 points success!
(8,25)
(1,16)
(19,17)
(4,24)
(13,25)
(20,6)
(20,22)
(10,0)
(0,5)
(18,9)
10 points success!

The code:

#include <iostream>
#include <time.h>

using namespace std;

int main(int argc, char **argv)
{
    float x[11],y[11],area[700]={0};
    int failed, i, m, n, p, points, temp, test, r=0, runs, xsize=24, ysize, endsize, maxxy=600;

    if(argv[1]){
        xsize=atoi(argv[1]);
    }

    cout << "x size: " << xsize << endl;
    ysize=maxxy/xsize;
    cout << "y size: " << ysize << endl;
    endsize=ysize*xsize;

    srand (time(NULL));

    temp=rand()%endsize+1;
    y[0]=temp/xsize;
    x[0]=temp%xsize;
    temp=rand()%endsize+1;
    y[1]=temp/xsize;
    x[1]=temp%xsize;
    temp=rand()%endsize+1;
    y[2]=temp/xsize;
    x[2]=temp%xsize;

  do{
    failed=0;
    points=3;

    runs=0;
    do{
        points=4;
        runs++;
        test=0;
        temp=rand()%endsize+1;
        y[points-1]=temp/xsize;
        x[points-1]=temp%xsize;
        r=0;
        for(m=0;m<points-2;m++){
            for(n=m+1;n<points-1;n++){
                for(p=n+1;p<points;p++){
                    area[r]=abs(x[m]*y[n]+x[n]*y[p]+x[p]*y[m]-x[m]*y[p]-x[n]*y[m]-x[p]*y[n]);
                    r++;
                }
            }
        }
        for(m=0;m<r;m++){
            for(n=m+1;n<r;n++){
                if(area[m]==area[n] || area[n]==0){
                    test++;
                }
            }
        }
    }while(test>0 && runs<10 && failed==0);
    if(runs>=endsize)
        failed=1;

    runs=0;
    do{
        points=5;
        runs++;
        test=0;
        temp=rand()%endsize+1;
        y[points-1]=temp/xsize;
        x[points-1]=temp%xsize;
        r=0;
        for(m=0;m<points-2;m++){
            for(n=m+1;n<points-1;n++){
                for(p=n+1;p<points;p++){
                    area[r]=abs(x[m]*y[n]+x[n]*y[p]+x[p]*y[m]-x[m]*y[p]-x[n]*y[m]-x[p]*y[n]);
                    r++;
                }
            }
        }
        for(m=0;m<r;m++){
            for(n=m+1;n<r;n++){
                if(area[m]==area[n] || area[n]==0){
                    test++;
                }
            }
        }
    }while(test>0 && runs<endsize && failed==0);
    if(runs>=endsize)
        failed=1;

    runs=0;
    do{
        points=6;
        runs++;
        test=0;
        temp=rand()%endsize+1;
        y[points-1]=temp/xsize;
        x[points-1]=temp%xsize;
        r=0;
        for(m=0;m<points-2;m++){
            for(n=m+1;n<points-1;n++){
                for(p=n+1;p<points;p++){
                    area[r]=abs(x[m]*y[n]+x[n]*y[p]+x[p]*y[m]-x[m]*y[p]-x[n]*y[m]-x[p]*y[n]);
                    r++;
                }
            }
        }
        for(m=0;m<r;m++){
            for(n=m+1;n<r;n++){
                if(area[m]==area[n] || area[n]==0){
                    test++;
                }
            }
        }
    }while(test>0 && runs<endsize && failed==0);
    if(runs>=endsize)
        failed=1;

    runs=0;
    do{
        points=7;
        runs++;
        test=0;
        temp=rand()%endsize+1;
        y[points-1]=temp/xsize;
        x[points-1]=temp%xsize;
        r=0;
        for(m=0;m<points-2;m++){
            for(n=m+1;n<points-1;n++){
                for(p=n+1;p<points;p++){
                    area[r]=abs(x[m]*y[n]+x[n]*y[p]+x[p]*y[m]-x[m]*y[p]-x[n]*y[m]-x[p]*y[n]);
                    r++;
                }
            }
        }
        for(m=0;m<r;m++){
            for(n=m+1;n<r;n++){
                if(area[m]==area[n] || area[n]==0){
                    test++;
                }
            }
        }
    }while(test>0 && runs<endsize && failed==0);
    if(runs>=endsize)
        failed=1;

    runs=0;
    do{
        points=8;
        runs++;
        test=0;
        temp=rand()%endsize+1;
        y[points-1]=temp/xsize;
        x[points-1]=temp%xsize;
        r=0;
        for(m=0;m<points-2;m++){
            for(n=m+1;n<points-1;n++){
                for(p=n+1;p<points;p++){
                    area[r]=abs(x[m]*y[n]+x[n]*y[p]+x[p]*y[m]-x[m]*y[p]-x[n]*y[m]-x[p]*y[n]);
                    r++;
                }
            }
        }
        for(m=0;m<r;m++){
            for(n=m+1;n<r;n++){
                if(area[m]==area[n] || area[n]==0){
                    test++;
                }
            }
        }
    }while(test>0 && runs<endsize && failed==0);
    if(runs>=endsize)
        failed=1;

    runs=0;
    do{
        points=9;
        runs++;
        test=0;
        temp=rand()%endsize+1;
        y[points-1]=temp/xsize;
        x[points-1]=temp%xsize;
        r=0;
        for(m=0;m<points-2;m++){
            for(n=m+1;n<points-1;n++){
                for(p=n+1;p<points;p++){
                    area[r]=abs(x[m]*y[n]+x[n]*y[p]+x[p]*y[m]-x[m]*y[p]-x[n]*y[m]-x[p]*y[n]);
                    r++;
                }
            }
        }
        for(m=0;m<r;m++){
            for(n=m+1;n<r;n++){
                if(area[m]==area[n] || area[n]==0){
                    test++;
                }
            }
        }
    }while(test>0 && runs<endsize && failed==0);
    if(runs>=endsize)
        failed=1;

    runs=0;
    do{
        points=10;
        runs++;
        test=0;
        temp=rand()%endsize+1;
        y[points-1]=temp/xsize;
        x[points-1]=temp%xsize;
        r=0;
        for(m=0;m<points-2;m++){
            for(n=m+1;n<points-1;n++){
                for(p=n+1;p<points;p++){
                    area[r]=abs(x[m]*y[n]+x[n]*y[p]+x[p]*y[m]-x[m]*y[p]-x[n]*y[m]-x[p]*y[n]);
                    r++;
                }
            }
        }
        for(m=0;m<r;m++){
            for(n=m+1;n<r;n++){
                if(area[m]==area[n] || area[n]==0){
                    test++;
                }
            }
        }
    }while(test>0 && runs<endsize*5 && failed==0);
    if(runs>=endsize*5)
        failed=1;

    runs=0;
    if(failed==0){
        for(i=0;i<points;i++)
            cout << "(" << x[i] << "," << y[i] << ")" << endl;
        cout << points << " points success!" << endl;
    }
        points=11;

    for(temp=0;temp<endsize;temp++){
        test=0;
        y[points-1]=temp/xsize;
        x[points-1]=temp%xsize;
        r=0;
        for(m=0;m<points-2;m++){
            for(n=m+1;n<points-1;n++){
                for(p=n+1;p<points;p++){
                    area[r]=abs(x[m]*y[n]+x[n]*y[p]+x[p]*y[m]-x[m]*y[p]-x[n]*y[m]-x[p]*y[n]);
                    r++;
                }
            }
        }
        for(m=0;m<r;m++){
            for(n=m+1;n<r;n++){
                if(area[m]==area[n] || area[n]==0){
                    test++;
                }
            }
        }
        if(test==0){
            cout << "Eleventh point: (" << x[points-1] << "," << y[points-1] << ")" << endl;
        }
        else
            failed=1;
    }
  }while(failed==1);
    cout << endl;
    for(i=0;i<points;i++)
        cout << "(" << x[i] << "," << y[i] << ")" << endl;

    return 0;
}

[dg211]

Hi EdH,

I haven't read your code in detail, but based on your description I think your approach could work, but you would probably see a lot more 10 solutions before an 11 (you mentioned thousands but I think it could be more like hundreds of thousands or millions).

I tried a whole bunch of methods, but the one that finally got me a solution was somewhat similar to yours. I placed 6 points using a random method, then tried to pick the most promising 6 point solutions (based on how many valid points could be added) and perform an exhaustive search from there. I don't think this was an especially strong approach, but it did find a 600 and a 594. I did see a couple of million 10 point solutions though, so it may be that 11s were just a bit too rare compared to 10s for your method.

Best wishes,

Dave

[EdH]

Thanks Dave,


I expected 11 points to be rare, but thought 80+ i7 threads would override the rarity. Apparently not!


Ed