October 2018

[Batalov]

Originally Posted by bsquared

I finally managed to find a solution (yay!).

Great!

Are you still at Mayo?

I've seen some talks from Mayo today, - this year ASHG is right here in San Diego.
Are you doing to any genetics conferences between some math puzzles?

[bsquared]

Yep, still here! No conference attendance planned as of now. Really I should wait till Jan/Feb to plan any trips to San Diego ;) Heck, Missouri starts looking nice in January.

[Dr Sardonicus]

Originally Posted by Batalov

Of course, maybe they have an elegant solution, instead.

They updated the site on the 17th. It now has this note:

A bonus '*' will be awarded to the solutions with the smallest area.

[Batalov]

And with the 10/24 update, the asterisks moved to other submitters.
So, minimality is an elusive goal.

[EdH]

After much frustration with 88 threads running for a couple of weeks I dialed them back considerably for a few days. But I now have a random program running on several of them again (80 threads). If I can't find a solution through a systematic approach, let's see how lucky I can get.

My random threads are turning up lots and lots of ten point solutions. All I need is one "lucky" eleventh point...

[Xyzzy]

http://www.research.ibm.com/haifa/po...tober2018.html

[Batalov]

It is a little underwhelming - because it shows that there is no elegant solution.
There is apparently no proof that 528 is minimal.
And if 528 is minimal then 23x23 square solution is not easily out of question (24x24 exists).

(and he also slipped into that N-1 x M-1 mode of presenting results, so I will, too)

[Dr Sardonicus]

What they posted are answers, not solutions. No clue on how they arrived at the answers. No indication of how they determined minimality.

Color me disappointed.

[axn]

Originally Posted by Dr Sardonicus

No indication of how they determined minimality.

It doesn't look to me like they're claiming minimality, merely that that is the smallest area that they _received_.

[EdH]

The fact that less than 30 names are listed makes me feel slightly better about not being one of them, but somewhat worse for tasking 8, i7s for the month with nothing to show. Not sure how I'll approach November's challenge...

[Batalov]

Originally Posted by Dr Sardonicus

What they posted are answers, not solutions. No clue on how they arrived at the answers. Color me disappointed.

I am not afraid to post mine. It's ugly (random shaking) but it did find 570 and later 567.
It is shown as hacked - it could have been improved, but it did produce a solution overnight on 20 threads (different L1 and L2=600\(L1-1)+1), so there, after that I had too much work.


I later played with some heuristics... but I am not going to show those variants.

// IBM_Oct2018.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
  char x,y;
  float w;
} _pt;

int xy[24], tr[3*165], ar[165];

int ptcmp(const void* a,const void* b) { float x = ((_pt*)a)->w - ((_pt*)b)->w; return (x > 0) - (x < 0); }

int area(int n) {
  int i, x = xy[2*tr[3*n]], y = xy[2*tr[3*n]+1];
  int a = (xy[2*tr[3*n+1]]-x)*(xy[2*tr[3*n+2]+1]-y) - (xy[2*tr[3*n+2]]-x)*(xy[2*tr[3*n+1]+1]-y);
  if(a<0) a = -a; else if(a==0) return 0;
  for(i=0;i<n;i++) if(ar[i]==a) return 0;
  return (ar[n] = a);
}

main(int argc, char **argv) {
  int i,j,k,l,m,n,x,y,z, F[14], L1, L2, L;
  int of[12]={0,0}, s = argc>3 ? atoi(argv[3]) : 13;
  _pt *pt;

  s = rand(); srand(s+time(0));
  L1 = argc>1 ? atoi(argv[1]) : 20;
  L2 = argc>2 ? atoi(argv[2]) : 30;
  pt = malloc(L1*L2*sizeof(_pt));
top_: s++;
  //srand(s);
  for(n=j=0;j<L1;j++)
  for(k=0;k<L2;k++) {
    pt[n].x = j;
    pt[n].y = k;
    pt[n].w = rand(); n++;
  }
  L=L1*L2;
  qsort(pt,L,sizeof(_pt),ptcmp);
  //printf(" %d %d %f\n",pt[0].x,pt[0].y,pt[0].w); fflush(stdout);

  for(i=n=0;i<11;i++) {
  for(j=0;j<i;j++)
  for(k=0;k<j;k++) {
    tr[3*n]=k;
    tr[3*n+1]=j;
    tr[3*n+2]=i; //printf(" %d %d %d\n",k,j,i);
    n++;
  } of[i+1]=n;
  }
  //printf(" n=%d \n",n);
  for(n=i=0;i<11;i++) {
  retry_: if(n>=L) break;
    xy[2*i]=pt[n].x;
    xy[2*i+1]=pt[n].y; n++;
    for(k=of[i];k<of[i+1];k++) {
      if(!area(k)) goto retry_;
      //printf(" %d",ar[k]);
    }
  }
  if(i==11) {
    int mx=xy[0], my=xy[1], sx=0, sy=0;
    for(i=1;i<11;i++) {if(mx>xy[2*i]) mx=xy[2*i]; if(my>xy[2*i+1]) my=xy[2*i+1];}
    for(i=0;i<11;i++) {
      xy[2*i]-=mx;xy[2*i+1]-=my;
      if(sx<xy[2*i]) sx=xy[2*i]; if(sy<xy[2*i+1]) sy=xy[2*i+1];
      pt[i].w=(pt[i].x=xy[2*i])*1000+(pt[i].y=xy[2*i+1]);
    }
    qsort(pt,11,sizeof(_pt),ptcmp);
    printf("[");
    for(i=0;i<10;i++) printf("[%d,%d], ",pt[i].x,pt[i].y);
    printf("[%d,%d]] L1=%d L2=%d S=%d\n",pt[i].x,pt[i].y,sx,sy,sx*sy);
  } else goto top_;
  exit(0);
 }