Difference between revisions of "CSC231 Homework 7 Fall 2017"
(→Requirements) |
|||
| (3 intermediate revisions by the same user not shown) | |||
| Line 3: | Line 3: | ||
<br /> | <br /> | ||
<bluebox> | <bluebox> | ||
| − | This assignment is due on 7/20/17 at 11:55 p.m. | + | This assignment is due on <strike>7/20/17</strike> 7/27/17 at 11:55 p.m. |
</bluebox> | </bluebox> | ||
<br /> | <br /> | ||
| Line 64: | Line 64: | ||
===Example Loops=== | ===Example Loops=== | ||
<br /> | <br /> | ||
| − | * [[CSC231_Code_Snippets | | + | * Go [[CSC231_Code_Snippets | here]] to find various snippets of code in assembly, including loops. Could be useful... |
<br /> | <br /> | ||
| + | |||
===Program Developed in Class=== | ===Program Developed in Class=== | ||
<br /> | <br /> | ||
| Line 212: | Line 213: | ||
</source> | </source> | ||
<br /> | <br /> | ||
| + | ==Maximum Number of Lines== | ||
| + | <br /> | ||
| + | You may safely assume that the number of rows requested will '''never be larger than 15.''' | ||
<br /> | <br /> | ||
==Submission== | ==Submission== | ||
| Line 219: | Line 223: | ||
<br /> | <br /> | ||
<br /> | <br /> | ||
| − | |||
| + | <showafterdate after="20171128 00:00" before="20171231 00:00"> | ||
=Solutions= | =Solutions= | ||
==Poblem 1== | ==Poblem 1== | ||
| Line 446: | Line 450: | ||
</source> | </source> | ||
| − | </ | + | </showafterdate> |
<br /> | <br /> | ||
<br /> | <br /> | ||
Latest revision as of 10:32, 29 November 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>
