#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

static char *points =
   "6m2o1v7{;~E|DvCq:k6m'bhbkcqhsmurnnhkdbdbh'L/U/T)a+n-q7sFtM{NtVga;M8A55@/L/'DM>H:A?>D;LCRJWPWU`X`Y`[_]h`bj^mSuFt>j3ZDPDM':r;s<t>t?q@oEoFnElDk>k<n:r'bmdmelfkgkiminhpdrbraqanbm'bmcncqbr]r[oYlZj[i]i^k_mbm''",
   *p, *image, *w, *cave, *space = "\n ";
static int width, height,
           *range,
           x, y, t, count, dx, dy;
static double ft, scale;

/* Return a random number in the range of [0,1]. */
static double R()
{
   return (double)rand() / RAND_MAX;
}

/* Return scaled value. */
static double P(int index)
{
   return scale * (p[index] - 39);
}

/* Interpolate between two points. */
static double Interpolate(double a, double b)
{
   return a + (b - a) * ft;
}

/* Interpolate a single component
   https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm */
static int InterpolateComponent()
{
   return (int)Interpolate(
                  Interpolate(
                     Interpolate(P(0), P(2)),
                     Interpolate(P(2), P(4))),
                  Interpolate(
                     Interpolate(P(2), P(4)),
                     Interpolate(P(4), P(6))));
}

/* Skip forward to the next wall character, returns 0 on success. */
static int SkipToNextWall()
{
   /* Skip forward without checking bounds.  This is guaranteed to
      terminate because we added a terminating NUL character before
      doing the floodfill passes.                                   */
   w += strspn(w, space);

   /* Check the wall character is within bounds. */
   return w - cave >= (width + 1) * height - 3;
}

/* Generate mushroom to a particular size, returns 0 on success. */
static int GenerateMushroom()
{
   /* Allocate buffers on first call.  Subsequent calls will work with
      smaller output sizes, so the buffers allocated on the first call
      will be large enough.                                            */
   if( image == NULL )
   {
      /* Record the maximum buffer size. */
      image = malloc(count = dx * dx);
      range = malloc(dx * 2 * sizeof(int));
      if( image == NULL || range == NULL )
      {
         puts("Out of memory");
         exit(EXIT_FAILURE);
      }
   }

   /* Fill background with black pixels.  Here we always fill the
      full buffer, and not just the part that will be drawn.  This is
      because we reduce the image size in single pixel increments, but
      image is encoded in 6 pixel rows, so there might be some leftover
      pixels from the previous iteration.                               */
   memset(image, 0, count);

   scale = dx / 90.0;
   p = points;
   dy = 0;
   while( P(0) > 0 )
   {
      /* Collect horizontal ranges for each scanline.

         This allows us to draw filled shapes one scanline at a time,
         and the shapes can be both convex and concave as long as each
         scanline is continuous.  We can enforce the continuous requirement
         by tweaking our shapes, saving us the complexity of having to
         write a more featureful rasterizer.                                */
      memset(range, 0, dx * 2 * sizeof(int));
      for(; P(2) > 0; p += 6)
      {
         for(t = 0; t < dx * 4; t++)
         {
            ft = (double)t / (dx * 4.0);

            x = InterpolateComponent();
            p++;
            y = InterpolateComponent();
            p--;

            if( x > 0 && x < dx && y >= 0 && y < dx )
            {
               if( range[y * 2] == 0 )
               {
                  range[y * 2] = range[y * 2 + 1] = x;

                  /* Keep track of last scanline.  We will draw only
                     up to the bottomost scanline, and drop all pixels
                     beyond this last scanline.  This saves a bit of
                     space at the end.                                 */
                  dy = dy > y ? dy : y;
               }
               else
               {
                  range[y * 2] = range[y * 2] < x ? range[y * 2] : x;
                  range[y * 2 + 1] = range[y * 2 + 1] > x ? range[y * 2 + 1] : x;
               }
            }
         }
      }

      /* Draw scanlines. */
      for(y = 0; y < dx; y++)
      {
         if( range[y * 2] != 0 )
         {
            for(x = range[y * 2]; x <= range[y * 2 + 1]; x++)
               image[y * dx + x] = p < points + 73 ? (x + y) & 1 : 1;
         }
      }

      /* p[0],p[1] is the last pair of coordinates.  p[2] is a trailing zero.
         Thus, to get to the start of the next shape, we need to skip 3.     */
      p += 3;
   }

   /* Convert to bitmap data to sixel. */
   w = image;
   for(y = 0; y <= dy; y += 6)
   {
      for(x = 0; x < dx; x++)
      {
         *w++ = 0x3f +
                image[y * dx + x] +
                (image[(y + 1) * dx + x] << 1) +
                (image[(y + 2) * dx + x] << 2) +
                (image[(y + 3) * dx + x] << 3) +
                (image[(y + 4) * dx + x] << 4) +
                (image[(y + 5) * dx + x] << 5);
      }
      *w++ = '-';
   }
   *w = '\0';

   /* Replace wall characters with sixel data.

      We will start with the header, which is fixed size.  We are
      guaranteed to have enough contiguous bytes for the header since
      we enforced a minimum output width, and generated borders on
      all four sides.                                                 */
   memcpy(cave, "\x1bPq#0;2;0;0;0#1;2;100;100;100#1", 31);

   w = cave + 31;
   for(p = image; *p;)
   {
      if( SkipToNextWall() )
         return 1;

      /* Check for repeated pixels, up to 99. */
      for(dy = 0; p[dy] == *p && dy < 99; dy++) {}
      if( dy > 3 )
      {
         /* Got a long enough run of repeated pixels. */
         x = strcspn(w, space);
         if( x > 3 && dy > 9 )
         {
            /* Got enough wall characters to use 4 byte sequences. */
            *w++ = '!';
            *w++ = '0' + (dy / 10);
            *w++ = '0' + (dy % 10);
            p += dy - 1;
         }
         else if( x > 2 )
         {
            /* Got enough wall characters to use 3 byte sequences. */
            if( dy > 9 )
               dy = 9;
            *w++ = '!';
            *w++ = '0' + dy;
            p += dy - 1;
         }
      }

      /* Copy byte. */
      *w++ = *p++;
   }

   /* Add padding. */
   while( w - cave < (width + 1) * height - 3 )
   {
      if( SkipToNextWall() )
         return 1;
      *w++ = '$';
   }

   /* Add footer. */
   strcpy(w, "\x1b\\");

   /* Success. */
   return 0;
}

/* Read a single cell with offset. */
static int ReadCell()
{
   return cave[(y + dy) * (width + 1) + x + dx] & 1;
}

/* Floodfill an open region.

   Cave cells are encoded in three states:
   0 = open, unfilled.
   1 = wall.
   2 = open, filled.                       */
static void FloodFill(int offset)
{
   if( cave[offset] != '\0' )
      return;
   cave[offset] = '\2';
   FloodFill(offset + 1);
   FloodFill(offset + width + 1);
   FloodFill(offset - 1);
   FloodFill(offset - width - 1);
}

int main(int argc, char **argv)
{
   if( argc != 3 ||
       (width = atoi(argv[1])) < 32 || (height = atoi(argv[2])) < 16 )
   {
      return printf("%s {width} {height}\n", *argv);
   }

   /* Allocate output buffer, with each row padded 1 to account for
      newline characters.

      Here we allocate a buffer that's twice the requested height.
      We will generate a cave with this double height, and then
      shrink it by half later.  This is to account for the taller
      character cells in terminals.  If we don't do this, we end up
      with caves that are more elongated vertically.  With this change,
      we will end up with more horizontally orientated caves (because
      terminal character aspect ratios tend to be just short of double
      height), but it looks generally nicer that way.                   */
   cave = malloc((width + 1) * height * 2);
   if( cave == NULL )
   {
      puts("Out of memory");
      return 1;
   }
   srand(time(NULL));
   srand(3);

   /* Fill cave with random bits. */
   p = cave;
   for(y = 0; y < height * 2; y++)
   {
      for(x = 0; x < width + 1; x++)
      {
         /* We use 1 to indicate walls and 0 to indicate spaces.
            Only the lowest bit is used in the final output, but
            we fill 4 bits for the edge cells since the smoothing
            function will shift all cells right 3 bits.

            Note that the right wall is 2 cells thick.  The extra
            cell is to account for the newline characters.        */
         *p++ = (y == 0 || y == height * 2 - 1 || x == 0 || x >= width - 1)
            ? 15
            : R() <= 0.47 ? 1 : 0;
      }
   }

   /* Apply smoothing function. */
   for(t = 0; t < 3; t++)
   {
      for(y = 1; y < height * 2 - 1; y++)
      {
         for(x = 1; x < width - 1; x++)
         {
            /* Sum the cave cell values from bit 0, then apply the sum
               to bit 1.

               We could also apply the sum directly to bit 0, which will
               result in an overly smoothed cave that is biased toward
               upper left.                                               */
            count = 0;
            for(dy = -1; dy <= 1; dy++)
            {
               for(dx = -1; dx <= 1; dx++)
                  count += ReadCell();
            }
            cave[y * (width + 1) + x] |= count >= 5 ? 2 : 0;
         }
      }

      /* Shift all cells right. */
      p = cave;
      for(x = 0; x < (width + 1) * height * 2; x++)
         *p++ >>= 1;
   }

   /* Shrink cave to the requested size. */
   p = cave;
   for(y = 0; y < height * 2; y += 2)
   {
      for(x = 0; x <= width; x++)
         *p++ = cave[y * (width + 1) + x] | cave[(y + 1) * (width + 1) + x];
   }

   /* Add terminating NUL character.  This is needed to make strlen work. */
   *p = '\0';

   /* Connect disjoint regions. */
   for(t = 0; t < 4; t++)
   {
      /* Find a random starting point. */
      x = R() * (height * (width + 1));
      x += strlen(cave + x);
      if( x >= height * (width + 1) )
         x = strlen(cave);
      if( x >= height * (width + 1) )
      {
         /* Couldn't find a random starting point, which means all
            disjoint regions have been filled.                     */
         break;
      }
      if( t > 0 )
      {
         /* If we managed to find a new starting point after the first
            pass, it means we found a new disjoint region.  Connect it
            to the previously filled region by digging a path to the
            previous starting point.

            We will stop as soon as we reach a previously filled region.
            We could remove that check and save a few bytes, and the
            end result will be some excessively long tunnels that cross
            multiple regions.                                            */
         dy = dx % (width + 1);
         for(; x % (width + 1) != dy && cave[x] != '\2'; x += x % (width + 1) > dy ? -1 : 1)
            cave[x] = '\0';
         for(; x != dx && cave[x] != '\2'; x += x > dx ? -(width + 1) : width + 1)
            cave[x] = '\0';
         cave[x] = '\0';
      }

      /* Floodfill this open region. */
      FloodFill(x);

      /* Record previous starting point. */
      dx = x;
   }

   /* Convert cave data to printable characters, and count number of wall
      characters.

      Any space not covered by a floodfill pass will be converted to walls,
      since they are disconnected from other spaces.                        */
   count = 0;
   p = cave;
   for(y = 0; y < height; y++)
   {
      for(x = 0; x < width; x++)
      {
         if( *p != '\2' )
         {
            *p++ = '#';
            count++;
         }
         else
         {
            *p++ = ' ';
         }
      }
      *p++ = '\n';
   }

   /* Each wall character encodes 6 pixels without compression.  If we
      use up to 4 byte repeat sequences ("!99{pixel}"), we can get a max
      compression ration of 1:24, so maximum number of output pixels is
      count*6*24.  We will set the output dimension to be a square that
      exceeds this pixel count, and gradually reduce it until compression
      succeeds.

      24x compression ratio is obviously optimistic.  In practice, we get
      about 1:2, or 1:1.6 if we limit ourselves to using only 3 byte
      sequences.  So the ratio is not great, but we do it anyways because
      we do get more pixels, and the output is more interesting than lots
      of repeated characters.

      Alternatively, we can give up compression, which would allow us to
      encode the mushroom in one go, but it will be smaller.             */
   for(dx = 9; dx * dx < count * 6 * 24; dx++) {}

   /* Generate mushroom to fit cave walls, reducing image size until
      we succeed.  This loop is guaranteed to terminate because we
      enforced a minimum size at the start of the program, so we will
      always have enough walls for at least a small mushroom.         */
   while( GenerateMushroom() )
      dx--;

   puts(cave);
   return 0;
}