Assignment #1 Due: 2/10 Monday Noon
Note: You can upload the file(s) as many times as you need by the due.
Do not make any of these problems or your answers posted or available in Internet or do not share with any others. All of the assignment should be done by yourself.
Demo & DocumentationPart1 30%
Lisp#1 #2#3#4#5Part2 30%
ttt#1#2#3
Deduction – Documentation (this .doc file) and upload.
Max -10% if documentation is not done or poorly prepared
Deduction – Demo (Demo time-slots may be scheduled by TA later, for you to do the demo).
Max -10% if demo is not done in the week of the due date or as scheduled/arranged with TA.
Note1. TA will schedule a demo later, for you to sign up and do your demo for the assignment.
Note2. During the demo, TA may select a random portion of your submission (including the code segment that you wrote) and ask you to explain it. If you cannot explain your own code, your assignment total assignment grade is set to 0/100.
Note. Any “poor” documentation (that is, this document with your answers etc.) may result in a penalty (up to -10%).
Upload two files: (1) this document file (this file with your answers) and (2) a zip file (containing all the codes [source and binary etc.] and its run log or results. (All the codes if applicable should run in csgrads.utdallas.edu without any change.)
** A demo (of your assignment) will be announced and scheduled by TA. Your demo should be done within the week of the due date. For any scheduling conflict, please contact or consult with TA (or the instructor) for your situation, and/or for alternate time or discretion as soon as possible, before the due.
Attach your answers for all parts in this document (to make this document self-explanatory). Organize and present your documentation here professionally (to assist the grader/TA to save his or her time in grading, without searching your files and running codes beyond and above what is expected and reasonable).
Warning. Please have a proper heading for each part (of code, run/execution result, and your explanation, etc). Any poor documentation may result in 0 for each part and/or the whole assignment.
Note. We plan to have quiz (in-class and closed-book) for some of these lisp programs. Please make sure that you can do the code by yourself out of memory.
Note1. If a program run gets too long (e.g., running over 5 or 10 min) or out of memory/stack memory, then your test/run is done. Please state the case (with screenshot).
Note2. If the program output or log gets too long (more than 1 page, then copy and paste only the first 10 lines and the last 10 lines here (in max 1/2 page) in this document. Also submit all of the program file (e.g., flatten.lisp) and its complete run-log or output of the program run in a log file (e.g., flatten-log.txt) in a zip file to elearning.
Part 1. Lisp [Place your answer here in this document for each question.]
Note. We plan to have a few in-class quiz (closed-book and surprise) for some of these problems.
Design and implement a Lisp function to be run it. Place (copy and paste) your code here and its execution & result. Also provide a performance measure with time (e.g., “(time (factorial1 10))”) to compare one function with the other. All of the codes and run-logs of this assignment should be also uploaded in a zip file.
(time (+ 1 10))
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 0 Bytes
11
A Hint for coding with a list. For example, consider a variable named fibo for a list.
(setq fibo ‘(1 1)) ;;; to define a variable named fibo for a list, initially containing fibo(0) and fibo(1).
(nth 0 fibo) ;;; this will return 0th element of the list fibo. That is, fibo(0) => 1.
(push 2 (cdr (last fibo)) ;;; this will insert 2 to the end of the list fibo.
(+ (nth 0 (reverse fibo)) (nth 1 (reverse fibo))) ;;; to add the last two elements of the list of fibo
For Lisp or Aima program, use dribble to start a log and to end it. Submit the log file in a zip file.
(dribble “a1part1.log.txt”) ;;; to start log.txt
(dribble) ;;; to end log
Note. Also consider to compile your program for speed-up and/or stack overflow problems, using (compile #’function-name) or (compile ‘function-name), or to compile all the programs in a file with (compile-file “file-name.lisp”) and load the compiled file (load “file-name”). It may depend on your installation but more likely to run (factorial 1000) for interpreted mode and (factorial 10000) for compiled version. Your program may get into a shortage of stack memory or similar. Please increase the memory to run the case.
For further information, please check: https://clisp.sourceforge.io/impnotes/faq.html
#1. Factorial functions. Save the codes for this problem in a file named factorial.lisp to be submitted.
For your test run, try the following cases: factorial of 0, 10, 1000, 10000, 100000.
Note. Compile your program for stack overflow problems, using (compile #’function-name) or (compile ‘function-name), or to compile all the programs in a file with (compile-file “file-name.lisp”) and load the compiled file (load “file-name”). It may depend on your installation but more likely to run (factorial 1000) for interpreted mode and (factorial 10000) for compiled version. Your program may get into a shortage of stack memory or similar. Please increase the memory to run the case.
For further information, please check: https://clisp.sourceforge.io/impnotes/faq.html
(1) Write a simple Lisp function factorial1 to compute factorial number of n recursively (where n is an integer >= 0).
Program function to run: factorial1
Program file: factorial1.lisp
Program run-log: factorial1-log.txt
Listing of the code
(defun (factorial1(N)
Execution (output) of the code loaded and run with time
(2) Write a Lisp function factorial3 to compute factorial of n (where n is an integer >= 0) with a loop (iteratively) with a global variable (e.g., a list, an array, or a hash table, etc.) to save the previous results to be used later. You may use a global variable or a hash table or an array to save the results to be used later (memorization) to compute next factorial number.
For your test run, try the following cases: factorial of 0, 1, 10, 100, 1000, 10000, 100000.
Program function to run: factorial3
Program file: factorial3.lisp
Program run-log: factorial3-log.txt
Listing of the code
Execution (output) of the code loaded and run.
(3) Write a Lisp function fibonacci3 to compute Fibonacci number of n (where n is an integer >= 1) with a loop (iteratively) with a global variable (e.g., a list, an array, or a hash table, etc.) to save the previous results to be used later. You may use a global variable or a hash table or an array to save the results to be used later (memorization) to compute next factorial number.
For your test run, try the following cases: factorial of 0, 1, 10, 100, 1000, 10000, 100000.
Program function to run: fibonacci3
Program file: fibonacci3.lisp
Program run-log: fibonacci3-log.txt
Listing of the code
Execution (output) of the code loaded and run.
(4) Write FLATTEN, a function that returns all the elements of an arbitrarily nested list in a single-level list.
A few test cases for your trial.
(FLATTEN ‘( ) )
(FLATTEN ‘(A) )
(FLATTEN ‘((A)) )
(FLATTEN ‘(A (B)) )
(FLATTEN ‘(A (B) ((C))) )
(FLATTEN ’((A B (R)) A C (A D ((A (B)) R) A))) should return (A B R A C A D A B R A).
Function: flatten
Program file: flatten.lisp
Program run-log: flatten-log.txt
Listing of the code
Execution (output) of the code loaded and run.
(5) Write a Lisp function EXP-EVAL, a function which evaluates an arithmetic expression. You may assume that the binary operators used for an arithmetic expression are: +, -, *, and /, and each (nested) expression is well-formed (parenthesized) binary expression recursively in infix-notation).
For example, (EXP-EVAL ‘(2 + (3 * 5))) should return 17.
Try with the following sample test cases.
(EXP-EVAL ‘(3 + 5))
(EXP-EVAL ‘(2 * ( 3 + 5)))
(EXP-EVAL ‘((4 / 2) + (3 * 5)))
(EXP-EVAL ‘(2+ (3 * 5) – 4))
Listing of the code
Execution (output) of the code loaded and run.
Part 2.
#1. Design and implement a function (ttt3x3n.lisp) to set the game to be run the game (computer versus computer) n times, to collect the statistics of run-times to be displayed. The program will have one argument n to run the function ttt3x3 n times (where n could be any positive integer).
To run ttt3x3n program n=4 times for test case:
(ttt3x3n 4)
Program function to run: ttt3x3n
Program file: ttt3x3n.lisp
Program run-log: ttt3x3n-log.txt
You should modify the program to set the first player X and the second player to be O and to run the program (so that the program will not ask the user to set who is X or O).
Program Listing (ttt3x3n.lisp)
Program run: try with n=4. Also submit the program-run (log) in a text file (e.g., ttt3x3n-log.txt)
If the run-result is too long (more than 1 page, then copy and paste only the first 10 lines and the last 10 lines here (in max 1/2 page). Please submit the complete output (run-log) of the program run in a log file (e.g., ttt3x3n-log.txt).
#2. Design and implement ttt4x4n.lisp from ttt3x3n.lisp program.
Modify the program (ttt3x3.lisp as your base) to implement ttt4x4.lisp to handle the tic-tac-toe game in 4×4 board. To run the game tic-tac-toe in 4×4 for computer vs computer ttt game. To run: (ttt4x4n)
Program function to run: ttt4x4n
Program file: ttt4x4n.lisp
Program run-log: ttt4x4n-log.txt
Warning: You should use the sample code provided (ttt.lisp) as your base code for this part. Otherwise, not only this part but also this assignment will be set to 0. Do your own work individually.
** State (Yes or No) for each function to be modified or not
Modified? Yes/No
Function
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
(defun generate-board ()(loop repeat 9 collect nil))
(defparameter *straights* …)
(defparameter *current-player* ‘x)
(defun get-board-elt (n board)(nth (1- n) board))
(defun legal-p (n board)(null (get-board-elt n board)))
(defun set-board-elt (n board symbol) …)
(defun list-legal-moves (board) …)
(defun get-random-element (lst)(nth (random (length lst)) lst))
(defun multi-non-nil-eq (lst) …)
(defun elements-of-straights (board) … )
(defun find-winner (board) … )
(defun set-player (mark) … )
(defun player-move (board symbol) …)
(defun computer-move (board symbol) … )
(defun computer-move-p (current-player autoplay-x-p autoplay-o-p) …)
(defun perform-turn (current-player board autoplay-x-p autoplay-o-p) …)
(defun switch-player () …)
(defun display-board (board) … )
(defun tic-tac-toe () …)
Program Listing (ttt4x4.lisp)
Program run (ttt4x4-log.txt)
#3. A Heuristic for ttt3x3nh
The ttt3x3n.lisp program (in #1) uses a random move to select next move of each player. Your task here is to provide a better heuristic (than a random move).
(defun computer-move (board symbol)
(let ((move (get-random-element (list-legal-moves board))))
(set-board-elt move board symbol)
(format t “~%computer selects ~a~%~%” move)))
Design and implement computer-move2 (to replace computer-move) for one player (e.g., X) to provide an admissible heuristic. The other player will use the random move (computer-move). Your program should output the performance of each player (e.g., how many moves for one player to win or not for each ttt 3×3 and a summary of the n runs).
Program function to run: ttt3x3nh.lisp
Program file: ttt3x3nh.lisp
Program run-log: ttt3x3nh-log.txt
You should provide a rationale for your heuristic with an informal proof to show that it is: (a) better than random move, (b) admissible, or (c) consistent. Note that (a) is a minimal requirement for this part whereas (b) or (c) is optional and for bonus points.
Heuristic function and your rationale with informal proof
Program Listing (ttt3x3nh.lisp)
Program run ttt3x3nh-log.txt
PAGE \* MERGEFORMAT 5