CSC231 Homework 7 Fall 2017

--D. Thiebaut (talk) 14:24, 9 November 2017 (EST)

---

This assignment is due on 7/20/17 7/27/17 at 11:55 p.m.

Problem 1: Life on a new level

For this problem you have to implement a more interesting game of life. Take a look at a demo of the solution program. You will understand right away what your program will have to do:

cs231a@aurora ~/handout $ ./hw7a
> 0
> @@

cs231a@aurora ~/handout $ ./hw7a
> 1 
> @      @       @
@      @       @

cs231a@aurora ~/handout $ ./hw7a
> 2
> @           @            @
@           @            @
 @         @ @          @ 

cs231a@aurora ~/handout $ ./hw7a
> 10
> @                @                  @
@                @                  @
 @              @ @                @ 
  @            @   @              @  
 @ @          @ @ @ @            @ @ 
    @        @       @          @    
   @ @      @ @     @ @        @ @   
  @   @    @   @   @   @      @   @  
 @ @ @ @  @ @ @ @ @ @ @ @    @ @ @ @ 
        @@               @  @        
       @@@@             @ @@ @

Explanations

• The program prompts for 2 pieces of information: an integer, which can be 0 or positive, and a string of spaces and '@' characters.
• The integer represents the number of generations we want to have our dish of cells go through. 0 means nothing gets printed. 1 means the original generation entered by the user is shown. 2 or more indicates that the program goes through a loop and evolves the cells in the dish.
• The string can be as long as what _getString allows, which is 1000 characters. However, for this assignment, we will assume that the string of live and dead cells entered by the user will never be more than 100 characters. It also means that your program will be tested only with strings of no more than 100 cells.

Requirements

• Your program should NOT use any loop instructions. Use the cmp instruction and conditional jumps to control the different loops.
• Replacing the loop label instruction with dec ecx, jnz label is not an acceptable solution (although it is one that would work).

Additional Information

Example Loops

• Go here to find various snippets of code in assembly, including loops. Could be useful...

Program Developed in Class

     getcopy  GameOfLifeClassV2.asm 

Getting an int from the keyboard

Use _getInput, which is part of the 231Lib.asm library. The integer is returned as a 32-bit int in eax.

        call    _getInput
        mov     dword[numGen], eax

Getting a string from the keyboard

We've used it before: _getString. It returns the address of the string in ecx, and the number of chars entered in edx. _getString has its own buffer of 1000 characters in which is saves the string. It will return the address of this buffer in ecx.

Submission

• Save your program in a file called hw7a.asm and submit it to Moodle.
• Document your code well!

Problem 2: Coding in C

• Write a C program called hw7b.c that uses loops to print the first N lines of the Pascal triangle.
• Examples with the solution program:

for n in 0 1 2 5 10 ; do echo "n =$n" ;  ./hw7b $n; echo ""; done
n =0

n =1
   1 

n =2
   1    0 
   1    1 

n =5
   1    0    0    0    0 
   1    1    0    0    0 
   1    2    1    0    0 
   1    3    3    1    0 
   1    4    6    4    1 

n =10
   1    0    0    0    0    0    0    0    0    0 
   1    1    0    0    0    0    0    0    0    0 
   1    2    1    0    0    0    0    0    0    0 
   1    3    3    1    0    0    0    0    0    0 
   1    4    6    4    1    0    0    0    0    0 
   1    5   10   10    5    1    0    0    0    0 
   1    6   15   20   15    6    1    0    0    0 
   1    7   21   35   35   21    7    1    0    0 
   1    8   28   56   70   56   28    8    1    0 
   1    9   36   84  126  126   84   36    9    1

Algorithm

Your program should use an array and initialize it with 1 in the first cell, and 0 everywhere, else.

Your program can prints this row, and it's the first row of Pascal's triangle:

1 0 0 0 0 0 0 0 0 0

You program can then scan the array starting with the last cell and replace this cell with the sum of itself and its left neighbor:

    1 0 0 0 0 0 0 0 0 0
                      |                    0+0 = 0
    1 0 0 0 0 0 0 0 0 0

The program keeps on going "down" the array by moving the index left by one cell, summing up cells with their left neighbors:

    1 0 0 0 0 0 0 0 0 0
                    |                  0+0 = 0
    1 0 0 0 0 0 0 0 0 0
 
 
    1 0 0 0 0 0 0 0 0 0
                  |                    0+0 = 0
    1 0 0 0 0 0 0 0 0 0
 
 
    1 0 0 0 0 0 0 0 0 0
                |                      0+0 = 0
    1 0 0 0 0 0 0 0 0 0
 
    . . .
 
    1 0 0 0 0 0 0 0 0 0
      |                                1+0 = 1
    1 1 0 0 0 0 0 0 0 0

You end up with the second row of Pascal's triangle:

   1 1 0 0 0 0 0 0 0 0 0

which your program can now print.

Repeat this process until you have printed all the rows of the triangle that needed to be printed. Row 1 only has one 1 and all 0s following.

Skeleton Program

• Play with the following program to see what it does, and then build up from there.

/*                                                                                                                      
  hw7b.c                                                                                                                
  A skeleton program to get you started.                                                                                
*/
#include <stdio.h>
#include <stdlib.h>


int main( int argc, char *argv[] ) {
  if ( argc<= 1 ) {
    printf( "Syntax %s N\n", argv[0] );
    printf( "where N is the number of rows of Pascal triangle to be printed\n" );
    return 0;
  }

  int N = atoi( argv[1] );
  printf( "Command line parameter = %d\n", N );

  return 0;
}

Maximum Number of Lines

You may safely assume that the number of rows requested will never be larger than 15.

Submission

Submit your program on Moodle before 11:55 p.m. on Monday!

<showafterdate after="20171128 00:00" before="20171231 00:00">

Solutions

Poblem 1

;;; hw7a.asm
;;; D. Thiebaut
;;; Implements a 1-Dimensional game of life, where
;;; the user is prompted to enter the number of generations
;;; first, and then the initial cell population using a string
;;; of spaces 

;;; The documentation is given in the form of an original Python
;;; program.
;;; ===============================================================
;;; dish = "                                      ##                                     "
;;; dish = [ 1 if c=='#' else 0 for c in dish ]
;;; N    = len( dish )
;;; newDish = N * [0]
;;; numGen  = 30
	section .data
prompt	db	"> "	
dish	dd	0
N	dd	0
newDish	times 256 db ' '
numGen	dd	30
i	dd	0
j	dd	0	
	
dishString db	' '
	
	section	.text
	global	_start
	extern	_printString
	extern	_printInt
	extern  _getString
	extern	_getInput
	extern	_println
	
_start:
;;; get the number of generations from the user
	
	mov	ecx, prompt
	mov	edx, 2
	call	_printString
	call	_getInput
	mov	dword[numGen], eax

;;; get the address of the string entered by the user and save
;;; it, as well as the number of chars in dish and N.
	
	mov	ecx, prompt
	mov	edx, 2
	call	_printString
	call	_getString
	mov	dword[dish], ecx
	mov	dword[N], edx


;;; if numGen == 0:
;;; 	exit
	cmp	dword[numGen], 0
	je	theEnd

;;; if N == 0:
;;;     exit
	cmp	dword[N], 0
	je	theEnd
	
;;; # iterate for many generations
;;; for i in range( numGen ):
;;;
	
	mov	dword[i], 0
forGen:
	mov	eax, dword[i]
	cmp	eax, dword[numGen]
	jge	theEnd
	
;;;     # print current dish
;;;     dishString = ''.join( [ '#' if c==1 else ' ' for c in dish ] )
;;;	print( dishString )

	mov	ecx, dword[dish]
	mov	edx, dword[N]
	call	_printString
	call	_println
	
;;;     # generate newDish from what's in dish
;;;     newDish = N * [0]
;;; 
;;;     # loop over dish and generate newDish
;;;     for j in range( 1, N-1 ):
;;;         # compute fate of cell by looking at neighbors
;;;         newDish[j] = dish[j-1] ^ dish[j+1]

	mov	dword[j], 1

	mov	esi, dword[dish]
	inc	esi
	mov	edi, newDish+1
	
forFate:mov	eax, dword[j]
	mov	ebx, dword[N]
	sub	ebx, 1
	cmp	eax, ebx
	jge	forFateEnd
	
	mov	al, byte[esi-1]
	cmp	al, byte[esi+1]
	je	dead
alive:	mov	al, '@'
	jmp	setCell
dead:	mov	al, ' '
setCell:
	mov	byte[edi],al
	inc	esi
	inc	edi

	inc	dword[j]
	jmp	forFate
forFateEnd:	
	
;;;     # copy newDish into dish
;;;     dish = newDish
;;; 
	mov	dword[j],0
	mov	esi, newDish
	mov	edi, dword[dish]
forCopy:
	mov	eax, dword[j]
	cmp	eax, dword[N]
	jge	endForCopy
	
	mov	al, byte[esi]
	mov	byte[edi], al
	inc	esi
	inc	edi

	inc	dword[j]
	jmp	forCopy
endForCopy:	

;;; end of forGen loop
	inc	dword[i]
	jmp	forGen
	
;;; 	exit
theEnd:	mov	eax, 1		
	mov	ebx, 0
	int 	0x80

Problem 2

/*
  hw7b.c
  Program gets a number from the command line and 
  displays a Pascal triangle with that number of lines.

  How to compile and run
  gcc -o hw7b hw7b.c
  ./hw7b  10
     1    0    0    0    0    0    0    0    0    0 
     1    1    0    0    0    0    0    0    0    0 
     1    2    1    0    0    0    0    0    0    0 
     1    3    3    1    0    0    0    0    0    0 
     1    4    6    4    1    0    0    0    0    0 
     1    5   10   10    5    1    0    0    0    0 
     1    6   15   20   15    6    1    0    0    0 
     1    7   21   35   35   21    7    1    0    0 
     1    8   28   56   70   56   28    8    1    0 
     1    9   36   84  126  126   84   36    9    1 

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


int main( int argc, char *argv[] ) {
  if ( argc<= 1 ) {
    printf( "Syntax %s N\n", argv[0] );
    printf( "where N is the number of rows of Pascal triangle to be printed\n" );
    return 0;
  }
  int i, j;
  int Pascal[100];

  // get the number of rows
  int N = atoi( argv[1] );
  //printf( "N = %d\n", N );

  if ( N==0 )
    return 0;

  // initialize the first row with 1 and all 0s
  Pascal[0] = 1;
  for ( j=1; j<=N; j++ )
    Pascal[j] = 0;

  // print all the rows
  for ( i=1; i<=N; i++ ) {

    // print current row 
    for ( j=0; j<N; j++ ) {
      printf( "%4d ", Pascal[j] );
    }
    printf( "\n" );

    // compute one row from the end
    for ( j=N; j>0; j-- ) {
      Pascal[j] = Pascal[j] + Pascal[j-1];
    }
    Pascal[0] = 1;
  }
  return 0;
}

</showafterdate>