🚀 go-pugleaf

I am posting some source code which may help some people determine "good"
step-sizes for bombing.  This is only my second iteration on this program.
I plan to continue to improve its performance and expand its scope so that
it can handle multiple step-size scenarios too.  My first thought is to
improve the search-for-the-appropriate-block-of-free-memory routine.

Until then, I need someone with some "heavy iron" (aka a fast computer) to
run this program with arguments of 8000 and 8000 for me, and then post or
email the results back to me.  Otherwise, it could be 1993 before the
program finishes!

Thanks, and enjoy the program.
Mark A. Durham
MAD

--------------------------------------------------------------------------

/***************************************/
/*                                     */
/*             Modula Bomber           */
/*                                     */
/* Determines the step-size which will */
/* produce the minimum sum maximum     */
/* contiguous bomb-free space.  Helps  */
/* determine optimum bombing strategy. */
/*                                     */
/* Directions for use:                 */
/*    After compiling and linking      */
/*    (ANSI C), enter:                 */
/*                                     */
/*       progname coresize bombs       */
/*                                     */
/*    on the command line.  "progname" */
/*    is the name you give to the      */
/*    executable (example: mb),        */
/*    "coresize" is a number           */
/*    representing the size of the     */
/*    core (example: 8000), and        */
/*    "bombs" is the number of bombs   */
/*    to drop for each step-size       */
/*    (example: 100).                  */
/*                                     */
/* Mark A. Durham                      */
/* October 4, 1992                     */
/***************************************/


/***************************************/
/*                                     */
/*             Include Files           */
/*                                     */
/***************************************/

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


/***************************************/
/*                                     */
/*             Structures              */
/*                                     */
/***************************************/

struct list {                    /* Excuse the mangling of terminology. */
   int   from;                   /* The idea is to keep a table of bomb */
   int   to;                     /* free areas linked together by both  */
   int   size;                   /* starting location and size.  The    */
   int   last;                   /* "next" field doubles as a link for  */
   int   next;                   /* unused elements of the table.       */
   int   lastsize;
   int   nextsize;
};


/***************************************/
/*                                     */
/*          Global Variables           */
/*                                     */
/***************************************/

int   FirstFree;                 /* Largest unbombed block of memory.   */


/***************************************/
/*                                     */
/*             Functions               */
/*                                     */
/***************************************/

void delete(                     /* Deletes an element from the table.  */
   struct list *core,
   int         i
) {
   core[core[i].lastsize].nextsize = core[i].nextsize;
   core[core[i].last].next = core[i].next;
   core[core[i].nextsize].lastsize = core[i].lastsize;
   core[core[i].next].last = core[i].last;
   core[i].next = FirstFree;
   FirstFree = i;
}


void insert(                     /* Inserts a new element into the      */
   struct list *core,            /* table.                              */
   struct list *node
) {
   int   i;
   int   j;

   i = FirstFree;
   FirstFree = core[i].next;
   core[i].from = node->from;
   core[i].to = node->to;
   core[i].size = node->size;
   for (j = 0; core[i].from > core[j].from; j = core[j].next);
   core[i].next = j;
   core[i].last = core[j].last;
   core[j].last = i;
   core[core[i].last].next = i;
   for (j = 2; core[i].size < core[j].size; j = core[j].nextsize);
   core[i].nextsize = j;
   core[i].lastsize = core[j].lastsize;
   core[j].lastsize = i;
   core[core[i].lastsize].nextsize = i;
}


void hit(                     /* Bomb core.                          */
   struct list *core,
   int         bomb
) {
   int         i;
   struct list left;
   struct list right;

   for (i = 0; bomb > core[i].to; i = core[i].next);  /* Find node.  */
   if (bomb >= core[i].from) {
      left.from = core[i].from;                       /* node exists */
      left.to = bomb - 1;
      left.size = bomb - core[i].from;
      right.from = bomb + 1;
      right.to = core[i].to;
      right.size = core[i].to - bomb;
      delete(core,i);
      if (left.size > 0) {
         insert(core,&left);
      };
      if (right.size > 0) {
         insert(core,&right);
      };
   };
}


void InitList(                /* Initialize table for empty core.    */
   struct list *core,
   int         maxsize
) {
   int   i;
   
   core[0].from = -1;         /* core[0] is guaranteed to be smaller */
   core[0].to = -1;           /* than any other element and first in */
   core[0].size = 0;          /* the list.                           */
   core[0].last = -1;
   core[0].next = 1;
   core[0].lastsize = 1;
   core[0].nextsize = -1;
   core[1].from = 0;          /* core[1] is the initially empty core */
   core[1].to = (maxsize-1);
   core[1].size = maxsize;
   core[1].last = 0;
   core[1].next = 2;
   core[1].lastsize = 2;
   core[1].nextsize = 0;
   core[2].from = maxsize;    /* core[2] is guaranteed to be larger  */
   core[2].to = 2*maxsize + 1;/* than any other element and last in  */
   core[2].size = maxsize + 1;/* the list.  core[0] and core[2] both */
   core[2].last = 1;          /* greatly simplify deletion and       */
   core[2].next = -1;         /* insertion by eliminating special    */
   core[2].lastsize = -1;     /* cases.                              */
   core[2].nextsize = 1;
   for (i=3; i<(maxsize+1); i++) {
      core[i].next = i+1;     /* This initializes the free element   */
   };                         /* list.                               */
   core[(maxsize+1)].next = -1;
   FirstFree = 3;             /* FirstFree always indicates the      */
}                             /* largest block of unbombed core.     */


void main(                    /* Main program code.                  */
   int   argc,
   char  *argv[]
) {
   int         bomb;          /* Location to bomb.                   */
   struct list *core;         /* Table of unbombed blocks of core.   */
   int         done;    /* Largest unbombed block of core when done. */
   int         i;             /* Bomb counter.                       */
   int         freespacesum;  /* Sum of largest unbombed core blocks.*/
   int         maxsize;       /* core size.                          */
   int         mindone;       /* "done" for minimum "freespacesum".  */
   int         minfree;       /* minimum "freespacesum".             */
   int         minstep;       /* step-size fo mimimum "freespacesum".*/
   int         stepsize;      /* step-size for bombing counter.      */
   int         totalbombs;    /* total number of bombs for each step.*/

   if (argc > 1) {
      maxsize = atoi(argv[1]);
   } else {
      printf("Enter core size: ");
      scanf("%d",&maxsize);
   };
   if (argc > 2) {
      totalbombs = atoi(argv[2]);
   } else {
      totalbombs = maxsize;
   };
   core = (struct list *)calloc((maxsize+2),sizeof(struct list));
   minfree = maxsize * maxsize;
   minstep = 0;
   for (stepsize = 1; stepsize < (maxsize/2); stepsize++) {
      InitList(core,maxsize);
      bomb = 0;
      freespacesum = 0;
      for (i = 0; i < totalbombs; i++) {
         hit(core,bomb);
         freespacesum += core[core[2].nextsize].size;
         bomb = (bomb + stepsize) % maxsize;
      };
      done = core[core[2].nextsize].size;
      if (freespacesum < minfree) {
         minfree = freespacesum;
         minstep = stepsize;
         mindone = done;
      };
      printf("%d\t%d\t%d\n",stepsize,done,freespacesum);
   };
   printf("\nMinimum free space = %d for step size %d\n",minfree,minstep);
   printf("\tFree space remaining = %d\n\n",mindone);
   free(core);
}