#!/root/clam/clam
#include "stdlib.h"

/* const int X=123, Y=49; */
const int X=75, Y=23;

list b = dim(1, Y, X);
list rs;
list dx = {1, 0, -1, 0};
list dy = {0, -1, 0, 1};

int rooms = (X/2) * (Y/2);
int nsets = rooms;

main()
{
  list w;

  random(time()+getpid());
  makeboard();
  makeset();

  l = 0;
  while (nsets > 1) {
    l++;
    [wx,wy] = pickwall();
    [r1,r2] = joins(wx,wy);
    s1 = findset(r1);
    s2 = findset(r2);
    if (s1 == s2) continue;
    union(s1,s2);

    b[wy][wx] = 0;
  }
  printboard();
  print(l, "\n");
}

dim(int v, int x, int y)
{
  int r, c;

  l = {v};
  for(r = 0; r < x; r++) {
    l[r] = {v};
    for (c = 0; c < y; c++)
      l[r][c] = v;
  }
  return l;
}

makeboard()
{
  int r, c;

  for(r = 1; r < Y; r+=2)
    for(c = 1; c < X; c+=2)
      b[r][c] = 0;
}

makeset()
{
  int i;

  rs = {};
  for (i = 0; i < rooms; i++) {
    rs[i] = { i };
  }
}

printsets()
{
  int i;

  for (i = 0; i < sizeof(rs); i++)
    print(sizeof(rs[i]), ":", rs[i], "\n");
}

clearboard()
{
  int r, c;

  for(r = 0; r < Y; r++)
    for (c = 0; c < X; c++)
      b[r][c] = 0;
}

printboard()
{
  int x, y;

/*  print(" ");
  for (x = 0; x < X; x++) print(x%10);
  print();
*/
  for (y = 0; y < Y; y++) {
/*    print(y%10); */
    for (x = 0; x < X; x++)
      print(b[y][x] ? "X" : " ");
    print();
  }
}

roomnum(int x, int y)
{
  return ((x-1)/2) + ((X/2) * (y-1)/2);
}

pickwall()
{
  int x, y;

  y = (random() % (Y-2)) + 1;
  if (y % 2 == 0)
    x = (random() % ((X-1)/2))*2 + 1;
  else
    x = (random() % ((X-2)/2))*2 + 2;

  return {x,y};
}

joins(int x, int y)
{
  if (y % 2 == 0)
    return {roomnum(x,y-1), roomnum(x,y+1)};
  else
    return {roomnum(x-1,y), roomnum(x+1, y)};
}

findset(int s)
{
  int i, j;

  for(i=0;i < sizeof(rs); i++)
    for(j=0; j < sizeof(rs[i]); j++)
      if (rs[i][j] == s) return i;
  return 0;
}

union(int sa, int sb)
{
  if (sa < sb) {
    rs[sa] |= rs[sb];
    rs[sb] = {};
  } else {
    rs[sb] |= rs[sa];
    rs[sa] = {};
  }
  nsets--;
}
