title: Optimization of Brute-Force algorithm or Alternative?
body: <p>I have a simple (brute-force) recursive solver algorithm that takes lots of time for bigger values of OpxCnt variable. For small values of OpxCnt, no problem, works like a charm. The algorithm gets very slow as the OpxCnt variable gets bigger. This is to be expected but any optimization or a different algorithm ?</p>
  
  <p>My final goal is that :: I want to read all the True values in the map array by
  executing some number of read operations that have the minimum operation
  cost. This is not the same as minimum number of read operations.
  At function completion, There should be no True value unread.</p>
  
  <p>map array is populated by some external function, any member may be 1 or 0.</p>
  
  <hr>
  
  <p>For example ::</p>
  
  <p>map[4] = 1;
  map[8] = 1;</p>
  
  <p>1 read operation having Adr=4,Cnt=5 has the lowest cost (35)</p>
  
  <p>whereas</p>
  
  <p>2 read operations having Adr=4,Cnt=1 &amp; Adr=8,Cnt=1 costs (27+27=54)</p>
  
  <hr>
  
  <pre><code>#include &lt;string.h&gt;
  
  typedef unsigned int    Ui32;
  
  #define cntof(x)    (sizeof(x) / sizeof((x)[0]))
  
  #define ZERO(x)     do{memset(&amp;(x), 0, sizeof(x));}while(0)
  
  typedef struct _S_MB_oper{
  
      Ui32    Adr;
      Ui32    Cnt;
  
  }S_MB_oper;
  
  typedef struct _S_MB_code{
  
      Ui32        OpxCnt;
      S_MB_oper   OpxLst[20];
      Ui32        OpxPay;
  
  }S_MB_code;
  
  char map[65536] = {0};
  
  static int opx_ListOkey(S_MB_code *px_kod, char *pi_map)
  {
      int  cost = 0;
      char map[65536];
  
      memcpy(map, pi_map, sizeof(map));
  
      for(Ui32 o = 0; o &lt; px_kod-&gt;OpxCnt; o++)
      {
          for(Ui32 i = 0; i &lt; px_kod-&gt;OpxLst[o].Cnt; i++)
          {
              Ui32 adr = px_kod-&gt;OpxLst[o].Adr + i;
              // ...
              if(adr &lt; cntof(map)){map[adr] = 0x0;}
          }
      }
  
      for(Ui32 i = 0; i &lt; cntof(map); i++)
      {
          if(map[i] &gt; 0x0){return -1;}
      }
  
      // calculate COST...
  
      for(Ui32 o = 0; o &lt; px_kod-&gt;OpxCnt; o++)
      {
          cost += 12;
          cost += 13;
          cost += (2 * px_kod-&gt;OpxLst[o].Cnt);
      }
  
      px_kod-&gt;OpxPay = (Ui32)cost; return cost;
  }
  
  static int opx_FindNext(char *map, int pi_idx)
  {
      int i;
  
      if(pi_idx &lt; 0){pi_idx = 0;}
  
      for(i = pi_idx; i &lt; 65536; i++)
      {
          if(map[i] &gt; 0x0){return i;}
      }
  
      return -1;
  }
  
  static int opx_FindZero(char *map, int pi_idx)
  {
      int i;
  
      if(pi_idx &lt; 0){pi_idx = 0;}
  
      for(i = pi_idx; i &lt; 65536; i++)
      {
          if(map[i] &lt; 0x1){return i;}
      }
  
      return -1;
  }
  
  static int opx_Resolver(S_MB_code *po_bst, S_MB_code *px_wrk, char *pi_map, Ui32 *px_idx, int _min, int _max)
  {
      int pay, kmax, kmin = 1;
  
      if(*px_idx &gt;= px_wrk-&gt;OpxCnt)
      {
          return opx_ListOkey(px_wrk, pi_map);
      }
  
      _min = opx_FindNext(pi_map, _min);
      // ...
      if(_min &lt; 0){return -1;}
  
      kmax = (_max - _min) + 1;
      // must be less than 127 !
      if(kmax &gt; 127){kmax = 127;}
  
      // is this recursion the last one ?
      if(*px_idx &gt;= (px_wrk-&gt;OpxCnt - 1))
      {
          kmin = kmax;
      }
      else
      {
          int zero = opx_FindZero(pi_map, _min);
          // ...
          if(zero &gt; 0)
          {
              kmin = zero - _min;
              // enforce kmax limit !?
              if(kmin &gt; kmax){kmin = kmax;}
          }
      }
  
      for(int _cnt = kmin; _cnt &lt;= kmax; _cnt++)
      {
          px_wrk-&gt;OpxLst[*px_idx].Adr = (Ui32)_min;
          px_wrk-&gt;OpxLst[*px_idx].Cnt = (Ui32)_cnt;
  
          (*px_idx)++;
          pay = opx_Resolver(po_bst, px_wrk, pi_map, px_idx, (_min + _cnt), _max);
          (*px_idx)--;
  
          if(pay &gt; 0)
          {
              if((Ui32)pay &lt; po_bst-&gt;OpxPay)
              {
                  memcpy(po_bst, px_wrk, sizeof(*po_bst));
              }
          }
      }
  
      return (int)po_bst-&gt;OpxPay;
  }
  
  int main()
  {
      int _max = -1, _cnt = 0;
  
      S_MB_code best = {0};
      S_MB_code work = {0};
  
      // SOME TEST DATA...
  
      map[ 4] = 1;
      map[ 8] = 1;
      /*
      map[64] = 1;
      map[72] = 1;
      map[80] = 1;
      map[88] = 1;
      map[96] = 1;
      */
  
      // SOME TEST DATA...
  
      for(int i = 0; i &lt; cntof(map); i++)
      {
          if(map[i] &gt; 0)
          {
              _max = i; _cnt++;
          }
      }
  
      // num of Opx can be as much as num of individual bit(s).
      if(_cnt &gt; cntof(work.OpxLst)){_cnt = cntof(work.OpxLst);}
  
      best.OpxPay = 1000000000L; // invalid great number...
  
      for(int opx_cnt = 1; opx_cnt &lt;= _cnt; opx_cnt++)
      {
          int rv;
  
          Ui32 x = 0;
  
          ZERO(work); work.OpxCnt = (Ui32)opx_cnt;
  
          rv = opx_Resolver(&amp;best, &amp;work, map, &amp;x, -42, _max);
      }
  
      return 0;
  }
  </code></pre>