A small Tetris-like clone using J and ncurses. Part 2

This is part two of our Tetris-like clone in J series. In this part we're going to see how the ncurses interface was created.

Creating the ncurses UI

To create the user interface we used the ncurses UI using the api/ncurses package. Sadly all interactions with this API makes the code look like straightforward imperative code.

Since we represented the game field using a matrix, we need a way to visualize this matrix. The next snippet shows how we used the wattr_on and mvwprintw functions to print each cell of the game field with the given color.

drawGame=: 3 : 0
matrix =. >{.}.y
win =. >{.y
cols =. }. $ matrix
rows =. {. $ matrix
for_row. i.rows do.
  for_col. i.cols do.
     value =. (<row, col) { matrix
     wattr_on_ncurses_ win;(COLOR_PAIR_ncurses_ (value+1));0
     mvwprintw_1_ncurses_ win; row; (2*col); (('  '))
  end.
end.
)

The game loop handles user interactions and game rules . Here's how it looks:

NB. Game loop
while. 1 do.
   c =. wgetch_ncurses_ vin 
   if. c = KEY_UP_ncurses_ do.
      game =: put_in_matrix (current*_1);k;j;game
      current =. rotate current
      needs_refresh =. 1
   elseif. c = KEY_RIGHT_ncurses_ do.
      game_tmp =. put_in_matrix (current*_1);k;j;game
      if. can_put_in_matrix current;k;(j + 1);game_tmp do.
         game =: game_tmp
         j =. j + 1
         needs_refresh =. 1
      end.
   elseif. c = KEY_LEFT_ncurses_ do.
      game_tmp =. put_in_matrix (current*_1);k;j;game
      if. can_put_in_matrix (current);k;(j - 1);game_tmp do.
         game =: game_tmp
         j =. j - 1
         needs_refresh =. 1
      end.
   elseif. 1 do. 
      if. ((seconds_from_start'') - timestamp) < 0.1 do.
         continue.
      else.
         timestamp =. seconds_from_start'' 
      end.
   
      if. automove = 0 do.
         game =: put_in_matrix (current*_1);k;j;game
         if. can_put_in_matrix (current);(k+1);j;game do.
            k =. k + 1
         else.
           game =: put_in_matrix (current);k;j;game
           k =. 0
           j =. 0
           if. can_put_in_matrix current;k;j;game do.
              current =. (?@$ tetriminos) {:: tetriminos
           else.
             mvwprintw_1_ncurses_ vin; 0; 0; ' Game over '
             nodelay_ncurses_ vin ;'0'
             wgetch_ncurses_ vin 
             exit''
          
           end.
         end.
         automove =. 2
         needs_refresh =. 1
      else.
          automove =. automove - 1
      end.
   end.
   unget_wch_ncurses_ c
   if. needs_refresh do.
      game =: put_in_matrix (current);k;j;game
      game =: remove_full_rows game
      drawGame vin; game
      wrefresh_ncurses_  vin
      needs_refresh =. 0
   end.
end.

The rest of the code is pure ncurses initialization which is not that interesting. Code for this post can be found here: : https://github.com/ldfallas/jcurtris .

A small Tetris-like clone using J and ncurses. Part 1

For me, the J programming language it's a very intriguing. It is full of ideas and concepts that I'm not familiar with. Getting to know a programming language it's not only about learning the syntax. It is learning the techniques that people use to take advantage of it what gives you more insight . This is particularly true for J.

For me the best way to learn more about a programming language is to try to solve a small problem with it. In this post I'm going to describe an attempt to write a small and incomplete Tetris-like clone using J and the ncurses library. Here's a preview of how it looks:

Tetriminos

According to the Wikipedia page for Tetris, the pieces are named Tetriminos https://en.wikipedia.org/wiki/Tetris#Gameplay. Each piece is composed of blocks. In J we can represent this pieces as matrices.

To create this matrices we use the Shape verb ($) For example:

• The "L" tetrimino:

   ] l_tetrimino =. 2 3 $ 1 1 1 1 0 0 
1 1 1
1 0 0

• The "O" tetrimino:

   ] b_tetrimino =. 2 2 $ 4 4 4 4 
4 4
4 4

• The "S" tetrimino:

   ] s_tetrimino =. 2 3 $ 0 5 5 5 5 0 
0 5 5
5 5 0

Tetrimino rotation

In Tetris pressing the 'up' arrow is going to rotate the current piece. We can use matrix Transpose (|:) and Reverse (|.) verbs and compose them together using the Atop conjunction (@). Here's the definition:

rotate =: |.@|:

Here we can see how this verb works:

   l_tetrimino
1 1 1
1 0 0
   rotate l_tetrimino
1 0
1 0
1 1
   rotate rotate l_tetrimino
0 0 1
1 1 1
   rotate rotate rotate l_tetrimino
1 1
0 1
0 1
   rotate rotate rotate rotate l_tetrimino
1 1 1
1 0 0

We can apply this transformation to the other tetriminos for example:

   ] s_tetrimino =. 2 3 $ 0 5 5 5 5 0 
0 5 5
5 5 0
   rotate s_tetrimino
5 0
5 5
0 5
   rotate rotate s_tetrimino
0 5 5
5 5 0

We use different numbers for each tetrimino so we can use different colors to paint them.

Tetrimino placement

A natural way to model the game is to use a matrix representing the playing field. We use a 10 columns by 20 rows matrix for this effect. We use the Shape verb ($) to do this:

   ] game =:  20 10 $ 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

A fundamental piece of functionality that we need is a way to put a tetrimino inside this matrix. This proved to be tricky (maybe because of lack of J knowledge). We're going to incrementally create this verb.

Reading the J documentation, it seems that we can use the Amend (m } _ _ _) verb to change just a set of cells of the game matrix. Here's an example on how to use this verb

   ] sample =. 5 5 $ 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

   1 2 3 4 (1 1;2 1;1 2;2 2) } sample
0 0 0 0 0
0 1 3 0 0
0 2 4 0 0
0 0 0 0 0
0 0 0 0 0

What we are saying here is that we can to change the following cells in sample:

• row 1 column 1 with value 1
• row 2 column 1 with value 2
• row 1 column 2 with value 3
• row 2 column 2 with value 4

Now to take advantage of this verb we need to calculate the target coordinates to change the value of a tetrimino. First we start by generating coordinates for each of the cells of the tetrimino.

We're going to use the following predifined values:

   ] l_tetrimino =. 2 3 $ 1 1 1 1 0 0 
1 1 1
1 0 0
   sample
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

We start by determining how many rows and columns. We use the Shape of verb ($) to do this:

   $ l_tetrimino
2 3

Now we want to generate (0, 0);(0, 1);...(1, 2);(2, 2). With the result of Shape of we generate a sequence of numbers for each of the axis. To do this we use the Integers (i.) verbwith the number of rows and the number of columns. For example:

   NB. Get the number of rows:
   (0&{@$) l_tetrimino
2
   NB. Get the number of columns:
   (1&{@$) l_tetrimino
3
   NB. Get an integer sequence from zero to number of rows or columns
   i.(1&{@$) l_tetrimino
0 1 2
   i.(0&{@$) l_tetrimino
0 1

Now this is very cool, we can use the Table verb (/)to pair this two arrays. From the documentation:

In general, each cell of x is applied to the entire of y . Thus x u/ y is equivalent to x u"(lu,_) y where lu is the left rank of u .

This is very important!. To taken advantage of this we need to use the Append verb (,) but changing the rack to operate on each of the elements from the right argument. See this example:

   0 (,"0) 0 1 2
0 0
0 1
0 2

Now we can take advantage of this and write:

   (  (i.@(0&{@$)) (<@,"0)/ (i.@(1&{@$))) l_tetrimino 
+---+---+---+
|0 0|0 1|0 2|
+---+---+---+
|1 0|1 1|1 2|
+---+---+---+

Now this is almost what we need. We can use the Ravel veb (,) to flatten this box:

, (  (i.@(0&{@$)) (<@,"0)/ (i.@(1&{@$))) l_tetrimino
+---+---+---+---+---+---+
|0 0|0 1|0 2|1 0|1 1|1 2|
+---+---+---+---+---+---+

With this positions we can use the Amend verb to change our game matrix:

   (,l_tetrimino) positions } sample
1 1 1 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

We need something else since this technique only allows us to put the tetrimino at the top of the matrix. In order to do this we need to sum the target position to the coordinates that we generated. We can use the powerful Under verb (&.) which allows us to apply an operation to each of the cells of a box.

   (3 2)&+ &.> positions
+---+---+---+---+---+---+
|3 2|3 3|3 4|4 2|4 3|4 4|
+---+---+---+---+---+---+

We construct this operation by:

1. using Bond conjuction (&) to tie together the position (3 2) with the plus operation (+) . That is (3 2)&+ .
2. we apply this operation to each of the elements of the box and then assemble the box again. That is &.>

Now we can put the tetrimino in row 3, column 2.

   target_position =. 3 2
   target_position =. 2 1
   (,l_tetrimino) (target_position&+&.>positions) } sample
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0

We cannot just pust the tetrimino in the target position. It may also "blend" with existing values. For example say the following game field and the following tetrminio:

   ] game
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 1 0
0 0 0 1 1

positions =., (  (i.@(0&{@$)) (<@,"0)/ (i.@(1&{@$))) tetrimino

   (,tetrimino) ((1 2)&+&.> positions) } game
0 0 0 0 0
0 0 1 1 0
0 0 1 0 0
0 0 1 0 0
0 0 0 1 1

Because of this we need to mix the tetrimino with the current values of the target region. We do this by extracting the values of the target position:

   ($tetrimino) $ ((1 2)&+&.> positions) { game
0 0
0 1
0 1

We can combine this array with the tetrimino and we get the desired target value:

   ] target_tetrimino =. +&tetrimino ($tetrimino) $ ((1 2)&+&.> positions) { game
1 1
1 1
1 1

   (,target_tetrimino) ((1 2)&+&.> positions) } game
0 0 0 0 0
0 0 1 1 0
0 0 1 1 0
0 0 1 1 0
0 0 0 1 1

The final verb definition looks like this:

put_in_matrix =: 3 : 0
 NB. unpack argumets
 tetrimino =. > 0 { y
 i =. > 1 { y
 j =. > 2 { y
 game =. > 3 { y

 NB. calculate target positions 
 positions =. , ((i.@(0&{)@$)(<@,"0)/(i.@(1&{)@$)) tetrimino

 NB. combine tetrimino with target section
 tetrimino =. +&tetrimino ($tetrimino) $ ((+&(i,j))&.> positions) { game
  
 NB. change matrix
 (,tetrimino) ((+&(i,j))&.> positions)} game
)

Checking if space is available

The other piece of functionality that we need is a way to verify if we can put the tetrimino in a target position. We need to verify two conditions: 1. We can put the tetrimino inside the game field. 2. There's space available in the target position.

To check the boundaries we use common comparison operators:

 NB. Verify field boundaries
 is_inside =. (xpos >: 0) *. (ypos >: 0) *. ( (xpos+tetrimino_width - 1) < game_width) *. ((ypos+tetrimino_height - 1) < game_height)

The second criteria it's more intersesting. To illustrate how we did the detection we're going to start with a predifined game field:

   game
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
   ] tetrimino =. 2 3 $ 2 0 0 2 2 2
2 0 0
2 2 2

The first step is to reset the values of the tetrimino to be either zero or one:

   ] tetrimino =. 0&< tetrimino
1 0 0
1 1 1

Now we extract the elements of the target position (in this example column 1, row 3)

   ypos =. 3
   xpos =. 1
   positions =. , ((i.@(0&{)@$)(<@,"0)/(i.@(1&{)@$)) tetrimino
   ($tetrimino) $ ((+&(ypos,xpos))&.> positions){ game
   
0 0 1
0 0 0

   xpos =. 1
   ypos =. 2
   positions =. , ((i.@(0&{)@$)(<@,"0)/(i.@(1&{)@$)) tetrimino
   ($tetrimino) $ ((+&(ypos,xpos))&.> positions){ game
0 0 0
0 0 1

Now we can multiply the tetrimino by the target value:

   target_segment =. ($tetrimino) $ ((+&(ypos,xpos))&.> positions){ game
   ] hits =. +/ , *&tetrimino target_segment
1

Now the variable hits contains the number of elements with a target cell value. The final predicate looks like this:

can_put_in_matrix =: 3 : 0
 NB. Unpack the arguments
 tetrimino =. 0&< > 0 { y
 tetrimino_width =. 1 { $ tetrimino
 tetrimino_height =. 0 { $ tetrimino
 ypos =. > 1 { y
 xpos =. > 2 { y
 game =. > 3 { y
 game_width  =. 1 { $ game
 game_height =. 0 { $ game

 NB. Verify field boundaries
 is_inside =. (xpos >: 0) *. (ypos >: 0) *. ( (xpos+tetrimino_width - 1) < game_width) *. ((ypos+tetrimino_height - 1) < game_height)

 NB. Check if we hit an occupied cell
 hits =. 0
 if. is_inside do.
   positions =. , ((i.@(0&{)@$)(<@,"0)/(i.@(1&{)@$)) tetrimino
   hits =. +/ , *&tetrimino ($tetrimino) $ ((+&(ypos,xpos))&.> positions){ game
 end.

 is_inside *. (hits = 0)
)

End words

As it was said in the beginning, J it's very interesting. For me there are many things to learn (you can tell that by looking at all those parenthesis in some expressions). Also there are many strategies in array languages that one needs to understand in other to write idiomatic code.

The ncurses interface will be discussed in part 2. For future posts it will be interesting to talk about concepts like the obverse (http://www.jsoftware.com/help/jforc/u_1_uv_uv_and_u_v.htm#_Toc191734413) and state machines (http://www.jsoftware.com/help/jforc/loopless_code_vii_sequential.htm#_Toc191734470) .

Code for this post can be found here: https://github.com/ldfallas/jcurtris

A quick look at J

In this post I'm going to show a small overview of the J programming language. An example of polynomial multiplication is examined.

J

J is an array programming language derived from APL which means is good for manipulating arrays and matrices. Its syntax and semantics are very different from other languages which makes it an interesting topic for studying.

There's a lot of documentation and examples available from the J software website. Two complete tutorials are "Learning J" by Roger Stokes and "J for C programmers" by Henry Rich.

The J distribution also includes examples and tutorials. The examples will be presented using J's REPL called jconsole.

The example

In order to give an overview of the language I'm going to start from the definition of a function that performs polynomial multiplication and examine how it was constructed.

The function is defined as follows:

polymulti =: dyad : '+/ (((_1 * i. #y) (|. "0 1) ((x (*"_ 0) y) (,"1 1) (((#y) - 1) $ 0))) , 0)'

Writing this example helped me understand some of the J's basic concepts (I'm completely sure there's a better/more efficient way to do this!).

Polynomial multiplication

The basic technique for polynomial multiplication consists on multiplying each term of one of the polynomials by the order and them simply the result. For example:

(4x3 - 23x2 + x + 1)   *   (2x2 - x - 3) 

= ((4x3 - 23x2 + x + 1) * 2x2) + 
  ((4x3 - 23x2 + x + 1) * -x) +
  ((4x3 - 23x2 + x + 1) * -3)

= (8x5 - 46x4 + 2x3 + 2x2) + 
  (-4x4 + 23x3 - x2 - x)  +
  (-12x3 + 69x2 - 3x - 3) 

= (8x5 - 50x4 + 13x3 + 70x2 - 4x - 3)  

Now I'll start creating polymulti from the bottom up to the definition.

1. Defining polynomials

As mentioned above J is a nice language for manipulating arrays. We're going to use J arrays to define polynomials. In fact J supports some operations on arrays as polynomials which will be described bellow.

In order to write a new array literal containing 1,1, -23 and 4 in J we write (here using jconsole):

   1 1 _23 4
1 1 _23 4

As you can see the elements of the array are separated by space. Also negative numbers are prefixed by underscore '_'. This array is going to be used to represent the coefficients of the "(4x³ - 23x² + x + 1)" polynomial.

We're going to define two variables with the polynomials shown above to use them for examples:

   p1 =: 1 1 _23 4
   p2 =: _3 _1 2

Here the '=:' operator is used to bind the specified arrays with p1 and p2.

2. Multiply each element of one of the polynomials

We can proceed to apply the first step in the process which is multiply each element of the second operand by the first operand.

In J we can operate on arrays easily, for example if we want to multiply each element of the above array by a 2 we write:

   1 1 _23 4 * 2
2 2 _46 8

In J the an operation that receives two arguments is called a dyad and a operation that receives only one is called monad. Here we're using the '*' dyad to perform the multiplication.

We cannot directly go and type "p1 * p2" because we will get the following error:

   p1 * p2
|length error
|   p1    *p2

This happens because the length of the two arrays (4 and 3) could not be used to perform the operation. We can apply '*' to a two same size arrays and J will multiply each element. For example:

   p1 * p1
1 1 529 16

Now what I want is to multiply each element of 'p2' by 'p1'. In order to do this we can change the behavior of the '*' dyad by specifying its rank (more details on how to do this can be found in "Verb Execution -- How Rank Is Used (Dyads)") . To change the rank of '*' and say that we want to multiply the complete array on the left for each of the cells of the right array we write (*"_ 0) .For example:

   p1 (*"_ 0) p2
_3 _3  69 _12
_1 _1  23  _4
 2  2 _46   8

By specifying (*"_ 0) we say that the left operand has "infinite rank" (_) which means it will consider the array as single unit.We also say that for the right argument we will consider every cell (by using the 0 rank). Notice that in order to modify the rank we use double quote (") which, in J, doesn't have to paired with another double quote as in most programming languages.

Also you can notice that the result of this operation is an array of arrays, one for each element of the right argument.

2. Sum each element of one of the polynomials

Now that we have an array of polynomials with the result of multiplying the coefficients, we need to change the degree of each of the polynomials. First we need to make more space to increment the degree of the polynomials. We're going to use the ',' dyad which lets you concatenate two arrays. For example:

   p1 , 0 0
1 1 _23 4 0 0

We need to append an array that is the size of the second polynomial minus one. In order to create a new array of this size we use '$' which lets you create an array or matrix by specifying the size and the value of the elements of the new array. For example:

   10 $ 0
0 0 0 0 0 0 0 0 0 0

The size of the array can be obtained with the '#' monad. For example:

   # p1
4

Now we can combine all these elements to resize each array resulting from the multiplication of the coefficients like this:

   (p1 (*"_ 0) p2)
_3 _3  69 _12
_1 _1  23  _4
 2  2 _46   8
    (((#p2) - 1 ) $ 0)
0 0
   (p1 (*"_ 0) p2) (,"1 1) ( ((#p2) - 1 ) $ 0)
_3 _3  69 _12 0 0
_1 _1  23  _4 0 0
 2  2 _46   8 0 0

Here we use (((#p2) - 1 ) $ 0) to generate an array of zeros of the desired size. Then we use (,"1 1) which is the ',' dyad with a modified rank saying that each element of the left matrix (an array) will be concatenated with the second array (since the second argument is a single dimension array we could have said (,"1 _) ).

With the arrays resized we can change the degree of our polynomial array. In order to do this we're going to use the '|.' dyad which let's you rotate an array an specified amount of positions. For example:

 
   1 |.  1 2 3
2 3 1
   _1 |.  1 2 3
3 1 2

As shown in the example, by specifying a positive number the array will be rotated to the left and a negative number to the right.

Now the question is, how to rotate each element of the polynomial array by a different element count? Before showing that we're going to introduce the 'i.' primitive which lets you create an array of with a sequence of numbers for example, to create an array of 10 numbers (starting with 0) we write:

   i. 10
0 1 2 3 4 5 6 7 8 9

We can use this primitive in conjunction with the rotate primitive to say

   m =:    (p1 (*"_ 0) p2) (,"1 1) ( ((#p2) - 1 ) $ 0)
   i. #p2
0 1 2
   _1 * i. #p2
0 _1 _2
   (_1 * i. #p2) (|."0 1) m
_3 _3 69 _12   0 0
 0 _1 _1  23  _4 0
 0  0  2   2 _46 8

As you can see we use the array generated by (_1 * i. #p2) to specify how many positions are we moving. We apply the change the rank of '|.' by saying (|."0 1) which means apply '|.' for each single cell of the left array to each row of the right array.

The previous step generated an array polynomials to be summed. So the only thing left is to generate the final polynomial. In order to do this we use the '+/' dyad which let's use sum the contents of an array. For example:

   +/ 5 3 4 1
13

We can apply +/ to any array and J will do the operation as expected.

   +/ (_1 * i. #p2) (|."0 1) m
_3 _4 70 13 _50 8

As a work around I'm appending a zero row to this matrix, just in case the p2 array is a 0 degree polynomial.

   +/ ((_1 * i. #p2) (|."0 1) m) , 0
_3 _4 70 13 _50 8

And that's it we have the complete process for multiplying the array.

3. Create the function

Now putting all the elements described above we can put together the polynomial multiplication dyad:

polymulti =: dyad : '+/ (((_1 * i. #y) (|. "0 1) ((x (*"_ 0) y) (,"1 1) (((#y) - 1) $ 0))) , 0)'

The 'x' and 'y' names are the implicit names of the left and right operands.

We can use it with any pair of polynomials. For example:

   2 34 3 polymulti 4 3
8 142 114 9
   2 34 3 polymulti 4 0 3
8 136 18 102 9
   2 34 3 polymulti 1
2 34 3

4. Use the polynomials

J already has support for polynomials inside the library. For example by using the 'p.' we can get an evaluation of a given polynomial.

   3 4 5 p. 34
5919
   3 + (4*34) + (5*34*34)
5919
   _2 p. 34
_2
   (5 3 _2 polymulti 3 0 0 _2)
15 9 _6 _10 _6 4
   (5 3 _2 polymulti 3 0 0 _2) p. 3
204

Final words

It was very interesting to read about J. It offers a different perspective on programming which is definitely worth studying. I have to admit it was difficult at the beginning because of the number of concepts to learn ( only a couple are presented in this post) and the syntax . For future posts I'm going to try to explore more J features.