API tools faq
paste
Advertisement
Guest User

cutting and fitting pieces with backtracking

a guest
Jul 9th, 2021
84
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.80 KB | None | 0 0
raw download clone embed print report
  1. /*
  2.   hxGroesseXyGroesse,xPosition,yPosition
  3.   für ein zu definierendes Hindernis
  4.  
  5.   *xMindestgroeseXYMindestgroesse
  6.   direkt hintendran fuer einen durchzuprobierenden Block,
  7.   der noch in den Bereich mit dem Hindernis paßt.
  8.  
  9.   Die festen Bloecke definiert man lieber zuerst.
  10.   Danach direkt Semikolon und fertig.
  11.  
  12.   Es sollen aus einem anderen Ding Formen rausgeschnitten werden
  13.   und anschließend versucht das Programm mit Backtracking, die
  14.   Form so einzufügen, damit möglichst wenig Einzelteile gebraucht
  15.   werden und es den Restbereich möglichst gut abdeckt.
  16.  
  17.   Nachdem man die rausgeschnittenen Formen definiert hat,
  18.   kann man immer noch danach auch mit Backtracking andere Positionen
  19.   zum Herausschneiden suchen und spart möglichst viel von dem
  20.   laufenden Material.
  21.   Sowas in der Art soll es werden.
  22.  
  23.   */
  24.  
  25. #include <stdio.h>
  26. #include <fcntl.h>
  27. #include <stdlib.h>
  28.  
  29. #define XSIZE 10
  30. #define YSIZE 10
  31.  
  32. int charseqc,
  33.       charseqlen=0;
  34.    
  35.  
  36. unsigned char command[2048];
  37.  
  38. int nquickest=0;
  39.  
  40. unsigned char sequencefeed[2048];
  41.  
  42. unsigned char input[2048];
  43.  
  44. unsigned int feedx, feedy, feedj,feedk;
  45.  
  46. unsigned char screen[XSIZE][YSIZE];
  47.  
  48.  
  49.  
  50. unsigned char backtrackfeed()
  51. {
  52.  
  53.   /*if ( charseqc!=simbreak)printf("%d %c",maskc, sequencefeed[charseqc]),getchar();
  54.    else printf("q");*/
  55.    
  56.  if ( feedx > 0){ feedx--; return 'x'; }
  57.  if ( feedy > 0){ feedy--; return 'y'; }
  58.  if ( feedj > 0){ feedj--; return 'j'; }
  59.  if ( feedk > 0){ feedk--; return 'k'; }
  60.  
  61.  unsigned char c=sequencefeed[charseqc];
  62.  charseqc++;
  63.  return c;
  64.    
  65. }
  66.  
  67. int remains=1000;
  68.  
  69. int remainlen(int size)
  70. {
  71.  if ( remains-size>0) return 1;
  72.  else return 0;
  73.  
  74. }
  75.  
  76. void remainsub(int size)
  77. {
  78.  remains-=size;
  79. }
  80.  
  81.  
  82. struct
  83. {
  84.  int x,y,xdim,ydim;
  85. }boxes[100],boxbak[100];
  86.  
  87.  unsigned char htmltext[200*100];
  88.  
  89.  
  90.  
  91.  
  92. unsigned char cutarray[XSIZE][YSIZE],cutarraybak[XSIZE][YSIZE];
  93.  
  94. int roomcovered=0,bestoldeval=0;
  95.  
  96. int cutout(int n)
  97. {
  98.  int x=0,y=0;
  99.  int failed=0;
  100.  failed=0;
  101.  
  102.  int x_start=0,y_start=0;
  103.   int x_iter,y_iter;
  104.    
  105.     y_start=0;
  106.     while ( y_start+boxes[n].ydim<YSIZE)
  107.     {
  108.        
  109.      x_start=0;
  110.      while ( x_start+boxes[n].xdim<XSIZE)
  111.       {
  112.      failed=0;
  113.     y_iter=0;
  114.    while ( y_iter <boxes[n].ydim)
  115.    {
  116.    x_iter=0;
  117.    while ( x_iter < boxes[n].xdim)
  118.    {
  119.       if (cutarray[x_start+x_iter][y_start+y_iter]!=0) failed=1;
  120.    
  121.      if ( failed==0&& x_iter==boxes[n].xdim-1&&y_iter==boxes[n].ydim-1) goto matched;
  122.      x_iter++;
  123.        }   
  124.    
  125.      y_iter++;
  126.      } 
  127.      
  128.      x_start++;
  129.    }
  130.    
  131.    y_start++;
  132.    
  133.   }
  134.  
  135.   return 1;
  136.  
  137.  
  138.   matched:
  139.    
  140.     y_iter=0;
  141.     while ( y_iter<boxes[n].ydim)
  142.     {
  143.       x_iter=0;
  144.       while ( x_iter<boxes[n].xdim)
  145.       {
  146.         cutarray[x_start+x_iter][y_start+y_iter]=n+1,roomcovered++;
  147.         x_iter++;
  148.         }
  149.         y_iter++;
  150.       }
  151.      
  152.     return 0;
  153.    
  154. }
  155.  
  156. void cutreset(int n)
  157. {
  158.  int x=0,y=0;
  159.  y=0;
  160.  
  161.  
  162.  if ( n==-2)
  163.  {
  164.    
  165.       y=0;
  166.  while ( y< YSIZE)
  167.  {
  168.   x=0;
  169.   while ( x < XSIZE)
  170.   {
  171.     cutarraybak[x][y]=cutarray[x][y];
  172.     x++;
  173.  } 
  174.  printf("\n");
  175.  y++;
  176.  }
  177.  return 0;
  178. }
  179.  
  180.  if ( n==-1)
  181.  {
  182.    
  183.     printf("\n-----\nSo schneiden:\n");
  184.  y=0;
  185.  while ( y< YSIZE)
  186.  {
  187.   x=0;
  188.   while ( x < XSIZE)
  189.   {
  190.     printf("%c",cutarraybak[x][y]==0? 177 :cutarraybak[x][y]+0x31);
  191.     x++;
  192.  } 
  193.  printf("\n");
  194.  y++;
  195.  }
  196.  return 0;
  197. }
  198.  
  199.  while ( y< YSIZE)
  200.  {
  201.   x=0;
  202.   while ( x < XSIZE)
  203.   {
  204.     if ( cutarray[x][y]==n+1||n==0)
  205.       {
  206.        cutarray[x][y]=0;
  207.          if ( n!=0)roomcovered--;
  208.       }
  209.        x++;
  210.       }
  211.     y++;
  212.  } 
  213.    
  214. }
  215.  
  216.  
  217.  
  218.  
  219.  
  220. int generate(int n)
  221. {
  222.   unsigned char generatestring[200];
  223.   //if ( boxes[n].xdim==0||boxes[n].ydim==0) return 0;
  224.   unsigned char x[5],y[5];
  225.   int n2=0,n3=0;
  226.  
  227.  
  228.   //printf("Text(T) oder Bild(B)");
  229.   unsigned char test;
  230.   switch((test=toupper(backtrackfeed())))
  231.   {
  232.     case 'T':
  233.                if ( cutout(n)==0)
  234.                 {
  235.                    
  236.                     //printf("%d %d %d %d\n",boxes[n].x,boxes[n].y,boxes[n].xdim,boxes[n].ydim),getch();
  237.                  return 1;
  238.                 }
  239.    
  240.             return 0;
  241.    
  242.   case 'B': cutout(n);
  243.            
  244.             return 1;
  245.    
  246.     default: return 0;
  247.    
  248.    }
  249.    
  250.    
  251. }
  252.  
  253. signed int boxptr=0;
  254.  
  255. int backtracksteps(int rec_depth, int cmdpos)
  256. {
  257.    
  258.   int allteststeps=1;
  259.    charseqc=0;
  260.    
  261.    //if ( rec_depth>5) return 0;
  262.         if ( command[cmdpos]==';')
  263.         {
  264.             charseqc=0;
  265.             /*sequencefeed[0]='d',*/sequencefeed[1]='q';
  266.             teststep();
  267.             /*
  268.             sequencefeed[0]='r',
  269.              charseqc=0;
  270.              teststep();
  271.             */
  272.         }
  273.         else
  274.           if ( command[cmdpos]=='h')
  275.           {
  276.           sequencefeed[0]='n',sequencefeed[1]='b';
  277.               charseqc=0;
  278.              
  279.                 feedk=0,feedx=0,feedy=0;
  280.                 feedj=command[cmdpos+4];
  281.               while ( feedj > 0)teststep();
  282.              
  283.              feedj=0,feedx=0,feedy=0;
  284.              feedk=command[cmdpos+3];
  285.              while ( feedk > 0)teststep();
  286.  
  287.              
  288.                feedy=0,feedj=0,feedk=0;
  289.                feedx=command[cmdpos+1];
  290.                while ( feedx>0 )teststep();
  291.               /*
  292.                printf("TEST%d",feedx),getch();
  293.                unsigned char teststring[100];
  294.                scanf("%s",teststring);
  295.                */
  296.                feedx=0,feedj=0,feedk=0;
  297.                feedy=command[cmdpos+2];
  298.                while ( feedy>0)teststep();
  299.  
  300.  
  301.               if (teststep()==0)
  302.               printf("Hindernis eingefuegt...");
  303.              
  304.               //printf("gehe rein..."),getchar();
  305.               backtracksteps(rec_depth+1,cmdpos+5);
  306.              
  307.              }
  308.              else if (command[cmdpos]=='*')
  309.              {
  310.               //printf("binda"),getch();
  311.              
  312.                     int xbuf2,ybuf2,kbuf2,jbuf2;
  313.                
  314.              jbuf2=0;
  315.              while ( jbuf2 < YSIZE)
  316.              {
  317.               kbuf2=0;
  318.               while ( kbuf2 < XSIZE)
  319.               {
  320.                xbuf2=XSIZE/2;
  321.                 if(xbuf2+command[cmdpos+1]+kbuf2>=XSIZE) xbuf2=0;
  322.                while ( xbuf2>0)
  323.                {
  324.                 ybuf2=YSIZE/2;
  325.                 if(ybuf2+command[cmdpos+2]+jbuf2>=YSIZE) ybuf2=0;
  326.                 while ( ybuf2>0)
  327.                 {
  328.                     boxes[boxptr].x=kbuf2,boxes[boxptr].y=jbuf2,
  329.                     boxes[boxptr].xdim=command[cmdpos+1]+xbuf2,boxes[boxptr].ydim=command[cmdpos+2]+ybuf2;
  330.                    
  331.                      feedx=0,feedy=0,feedk=0,feedj=0;
  332.                       charseqc=0;
  333.                       sequencefeed[0]='c';
  334.                       if ( teststep()==0)
  335.                       {
  336.                          //printf("Probe..."),getch();
  337.                        charseqc=0;
  338.                     sequencefeed[0]='n',sequencefeed[1]='t';
  339.                             if (teststep()==0 )
  340.                         {
  341.                             //printf("Kam tiefer..."),getch();
  342.                              charseqc=0;
  343.                              sequencefeed[0]='q';
  344.                              teststep();
  345.                              //printf("%d",boxptr),getch();
  346.                              backtracksteps(rec_depth+1,cmdpos+5) ;
  347.                             sequencefeed[0]='r',
  348.                                  charseqc=0;
  349.                                 teststep();
  350.                           }
  351.                       }
  352.                
  353.                     ybuf2--;
  354.                    }
  355.                
  356.                
  357.                   xbuf2--;
  358.                 }  
  359.                
  360.                 kbuf2++;
  361.                
  362.               }
  363.               jbuf2++;
  364.              }
  365.            
  366.             return 1;
  367.            }
  368.          
  369.        
  370.        
  371.  return allteststeps;
  372. }
  373.  
  374. int draw=0;
  375.  
  376. int main(void)
  377. {
  378.  printf("Hindernis oder * fuer Positionierungserproben,(Mindest-)BreiteXLaenge,Start,Ende; :\n");
  379.  gets(input);
  380.  int n=0,n2=0,n3=0;
  381.  
  382. int number;
  383.  
  384. n=0;
  385. while ( input[n]!='\0')
  386. {
  387.  if ( input[n]=='*'||input[n]=='h') command[n3]=input[n],n3++,n++; else return;
  388.  n2=0,number=0;while ( input[n2+n]>=0x30&&input[n2+n]<=0x39)number*=10,number+=input[n2+n]-0x30,n2++;
  389.  command[n3]=number,n3++,n+=n2;
  390.  if ( input[n]=='X')n++; else return;
  391. n2=0,number=0;while ( input[n2+n]>=0x30&&input[n2+n]<=0x39)number*=10,number+=input[n2+n]-0x30,n2++;
  392.  command[n3]=number,n3++,n+=n2;
  393.  if ( input[n]==',')n++; else return;
  394. n2=0,number=0;while ( input[n2+n]>=0x30&&input[n2+n]<=0x39)number*=10,number+=input[n2+n]-0x30,n2++;
  395.  command[n3]=number,n3++,n+=n2;
  396.  if ( input[n]==',')n++; else return;
  397. n2=0,number=0;while ( input[n2+n]>=0x30&&input[n2+n]<=0x39)number*=10,number+=input[n2+n]-0x30,n2++;
  398.  command[n3]=number,n3++,n+=n2;
  399.  if ( input[n]==';') command[n3]=';',n3++,n++; else if ( input[n]=='*'||input[n]=='h');else return;
  400.  if ( input[n]=='\0') break;
  401.  
  402. }
  403. command[n3]='\0';
  404.  
  405. cutreset(0);
  406.  
  407. printf("binda");
  408. sequencefeed[0]='i',teststep();
  409. int succeeded;
  410.  
  411.      charseqc=0;
  412.      feedx=0,feedy=0,feedj=0,feedk=0;
  413.    
  414.       succeeded=backtracksteps(0,0);
  415.  
  416.  int x=0,y=0;
  417.     memcpy(boxes,boxbak,sizeof(boxes));
  418.     boxptr=nquickest;
  419.     printf("%d",boxptr),getch();
  420.       draw=1;
  421.       charseqc=0,sequencefeed[0]='i';
  422.      teststep();
  423.      cutreset(-1);
  424.    
  425. }
  426.  
  427. int teststep(void)
  428. {
  429.   int stepfailed=0;
  430.    
  431.     static
  432.   enum
  433.   {
  434.    up,down,left,right,grewx,grewy,test
  435.   }LASTSTEP;
  436.    
  437.    static
  438.  unsigned char collide[XSIZE][YSIZE];
  439.   int x,y;
  440.    static int n=0;
  441.    
  442.      static int initbuffer=0;
  443.     if ( initbuffer==0)
  444.     {
  445.      y=0;
  446.      while ( y<YSIZE )
  447.      {
  448.       x=0;
  449.       while ( x<XSIZE ) screen[x][y]=collide[x][y]=0,x++;     y++;
  450.      }
  451.      boxes[n].x=boxes[n].y=boxes[n].xdim=boxes[n].ydim=0;  
  452.    
  453.    }
  454.    n=boxptr;
  455.   unsigned char c;
  456.  
  457.    //while(1)
  458.    {
  459.     if ( 1)
  460.     {
  461.      switch(c=backtrackfeed())
  462.      {
  463.       case 'x': if ( boxes[boxptr].xdim<XSIZE/2&&boxes[boxptr].x+boxes[boxptr].xdim<XSIZE-1)
  464.         boxes[boxptr].xdim++; LASTSTEP=grewx; break;
  465.       case 'y':if ( boxes[boxptr].ydim<YSIZE/2&&boxes[boxptr].y+boxes[boxptr].ydim<YSIZE-1)
  466.         boxes[boxptr].ydim++;  LASTSTEP=grewy;break;
  467.       case 's': if ( boxes[boxptr].xdim>0)
  468.         boxes[boxptr].xdim--;  break;
  469.    case 'a': if ( boxes[boxptr].ydim>0)
  470.         boxes[boxptr].ydim--;  break;
  471.    case 'u': if ( boxes[boxptr].y>0)
  472.          boxes[boxptr].y--; LASTSTEP=up;break;
  473.   case 'j': if ( boxes[boxptr].y+boxes[boxptr].ydim<YSIZE-1)
  474.          boxes[boxptr].y++;LASTSTEP=down; break;
  475.   case 'h': if ( boxes[boxptr].x>0)
  476.          boxes[boxptr].x--; LASTSTEP=left;break;
  477.   case 'k': if ( boxes[boxptr].x+boxes[boxptr].xdim<XSIZE-1)
  478.          boxes[boxptr].x++; LASTSTEP=right;break;
  479.   case 'n': if(generate(boxptr)==1) {
  480.            boxptr++;   boxes[boxptr].x=boxes[boxptr].y=boxes    [boxptr].xdim=boxes[boxptr].ydim=0; return 0; }
  481.            else return 1; // paßt nicht
  482.            break;
  483.   case 'r' : n--,boxptr--,cutreset(boxptr); return 0;
  484.   case 'c' : LASTSTEP=test; break;
  485.   case 'd' : memcpy(boxbak,boxes,sizeof(boxes)), nquickest=boxptr; break;
  486.  
  487.   case 'q': goto writeout;
  488.      }
  489.     }
  490.  
  491.     //if(initbuffer==0)
  492.     {
  493.         y=0;
  494.     while ( y<YSIZE )
  495.     {
  496.      x=0;
  497.      while ( x<XSIZE ) screen[x][y]=' ',collide[x][y]=255,x++;
  498.      y++;
  499.     }
  500.     //screen[boxes[boxptr].x][boxes[boxptr].y]='X';
  501.      initbuffer=1;  
  502.     }
  503.    
  504.  
  505.    n=0;
  506.    while ( n < boxptr+1)
  507.    {
  508.     if ( n==boxptr&&boxes[n].xdim==0&&boxes[n].ydim==0)break;
  509.     int dimc_x,dimc_y;
  510.      
  511.      dimc_y=boxes[n].ydim;
  512.  
  513.      while ( dimc_y>=0)
  514.      {      
  515.        dimc_x=boxes[n].xdim;      
  516.  while ( dimc_x >= 0 )
  517.  {
  518.  
  519.     if ( collide[boxes[n].x+dimc_x][boxes[n].y+dimc_y]==255||collide[boxes[n].x+dimc_x][boxes[n].y+dimc_y]==n)
  520.      screen[boxes[n].x+dimc_x][boxes[n].y+dimc_y]=n+0x30,
  521.      collide[boxes[n].x+dimc_x][boxes[n].y+dimc_y]=n;
  522.      else
  523.      {
  524.      //printf("\a");
  525.      stepfailed=1;
  526.      
  527.       int x2,y2;
  528.       int xgoal,ygoal;
  529.      
  530.       ygoal=boxes[n].y+boxes[n].ydim;
  531.       xgoal=boxes[n].x+boxes[n].xdim;
  532.        y2=boxes[n].y;
  533.        
  534.       while ( y2<ygoal)
  535.       {
  536.         x2=boxes[n].x;
  537.         while ( x2<xgoal)
  538.         {
  539.           if ( collide[x2][y2]==n)
  540.             {
  541.                 collide[x2][y2]=255;
  542.                 screen[x2][y2]=' ';
  543.             }
  544.                 x2++;
  545.                 }  
  546.             y2++;
  547.        }
  548.      
  549.       switch(LASTSTEP)
  550.       {
  551.        case up: boxes[n].y++;break;
  552.        case down:boxes[n].y--;break;
  553.        case left:boxes[n].x++;break;
  554.        case right:boxes[n].x--;break;
  555.        case grewx: boxes[n].xdim--; break;
  556.        case grewy: boxes[n].ydim--; break;
  557.        case test: return 1;
  558.       }
  559.       dimc_x=0;
  560.       dimc_y=boxes[n].ydim+1;
  561.       goto repeat;
  562.      }
  563.  
  564.     dimc_x--;
  565.     }
  566.      repeat:
  567.        dimc_y--;
  568.       }    
  569.  
  570.     n++;  
  571.    }
  572.  
  573.    if ( rand()%1000==0||draw==1)
  574.    {
  575.    system("cls");
  576.  
  577.    y=0;
  578.    while ( y < YSIZE)
  579.    {
  580.     x=0;
  581.     while ( x<XSIZE) printf("%c%c%c%c%c",screen[x][y],screen[x+1][y],screen[x+2][y],screen[x+3][y],screen[x+4][y]),x+=5;
  582.      printf("\n");
  583.     y++;
  584.    }
  585.    
  586.    }
  587.  
  588. }
  589.  
  590. //if ( c=='c' )boxptr--,n--;
  591.  
  592. if (1) return  stepfailed;
  593.  
  594.   writeout:
  595.    
  596.     (0);
  597.     if ( stepfailed==0&&roomcovered/boxptr>= bestoldeval)
  598.     {
  599.        
  600.         memcpy(boxbak,boxes,sizeof(boxes));
  601.         cutreset(-2);
  602.         //printf("Schreibe... boxptr ist %d roomcovered ist %d",boxptr,roomcovered),getch();
  603.         nquickest=boxptr;
  604.           bestoldeval=roomcovered/boxptr;
  605.         //printf("%d %d",n,boxptr),getch();
  606.       }
  607.  
  608.       return stepfailed;
  609.     /*
  610.     (0);
  611.     FILE *output=fopen("posdata","wb");
  612.       fwrite(boxes, sizeof(boxes),1,output);
  613.       fwrite(htmltext, sizeof(htmltext),1,output);
  614.        fwrite(&boxptr,sizeof(signed int),1,output);
  615.     fclose(output);
  616.     */
  617.  
  618. }
  619.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!