How to resolve the algorithm Cut a rectangle step by step in the zkl programming language

Published on 12 May 2024 09:40 PM
#Zkl

How to resolve the algorithm Cut a rectangle step by step in the zkl programming language

Table of Contents

Problem Statement

A given rectangle is made from m × n squares. If m and n are not both odd, then it is possible to cut a path through the rectangle along the square edges such that the rectangle splits into two connected pieces with the same shape (after rotating one of the pieces by 180°). All such paths for 2 × 2 and 4 × 3 rectangles are shown below.

Write a program that calculates the number of different ways to cut an m × n rectangle. Optionally, show each of the cuts. Possibly related task: Maze generation for depth-first search.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Cut a rectangle step by step in the zkl programming language

Source code in the zkl programming language

fcn cut_it(h,w){
   if(h.isOdd){
      if(w.isOdd) return(0);
      t,h,w=h,w,t;  // swap w,h: a,b=c,d --> a=c; b=d; so need a tmp
   }
   if(w==1) return(1);
 
   nxt :=T(T(w+1, 1,0), T(-w-1, -1,0), T(-1, 0,-1), T(1, 0,1)); #[next, dy,dx]
   blen:=(h + 1)*(w + 1) - 1;
   grid:=(blen + 1).pump(List(),False); //-->L(False,False...)
 
   walk:='wrap(y,x){ // lambda closure
      if(y==0 or y==h or x==0 or x==w) return(1);
      count,t:=0,y*(w + 1) + x;
      grid[t]=grid[blen - t]=True;
      foreach nt,dy,dx in (nxt){
         if(not grid[t + nt]) count+=self.fcn(y + dy, x + dx,vm.pasteArgs(2));
      }
      grid[t]=grid[blen - t]=False;
      count
   };

   t:=h/2*(w + 1) + w/2;
   if(w.isOdd){
      grid[t]=grid[t + 1]=True;
      count:=walk(h/2, w/2 - 1);
      count + walk(h/2 - 1, w/2)*2;
   }else{
      grid[t]=True;
      count:=walk(h/2, w/2 - 1);
      if(h==w) return(count*2);
      count + walk(h/2 - 1, w/2);
   }
}

foreach w,h in ([1..9],[1..w]){
   if((w*h).isEven) println("%d x %d: %d".fmt(w, h, cut_it(w,h)));
}

You may also check:How to resolve the algorithm Sutherland-Hodgman polygon clipping step by step in the Standard ML programming language
You may also check:How to resolve the algorithm Draw a sphere step by step in the PostScript programming language
You may also check:How to resolve the algorithm Comma quibbling step by step in the Ring programming language
You may also check:How to resolve the algorithm Integer comparison step by step in the Kotlin programming language
You may also check:How to resolve the algorithm First-class functions/Use numbers analogously step by step in the Tcl programming language