• Do not bring in any outside code (no loading/importing); just focus on lists and basic operators always available in Lisp.
  • you may lose up to all points on functions that use such imported code, and/or a flat rate penalty.
• do not use globals (no *defvar* or *defparameter*).
  • If you ignore this rule, you might lose up to ten points. And realistically it may cause issues with consecutive calls (which is what the tester does).
• any function that serves the same, or nearly the same, purpose, may not be used in that implementation. I will try to indicate obvious things to skip, but there are too many for me to catch them all. Ask on piazza, with enough time to get a response, if you feel you've got a too-easy solution. Examples: If the function body is a single function call itself, you've most likely found a too-good-to-be-true solution; alternatively, if you get significant efforts from a built-in, like a built-in sort and then you inspect that sorted output, that's acceptable.

• if you don't use any macros other than defun, if, cond, let/let*, and lambda, you can earn an additional (+5) bonus! Some macros/special forms to avoid (though I'm sure you can wander off and find far more) are: LOOP, do, dotimes, dolist, for, progn, etc. If you're unsure of other exciting features, give us time to respond.
  • Remember, you can search "CLHS <nameOfThing>" and find out if it's a macro or function. Try it out on cond and on floor as examples.

Here are some built-in functions that you may find useful. It's also something of a short-list of what I have in my own solution, so treat it as a suggested maximal set of operations, like guardrails or bowling lane bumpers. As long as you're using functions not macros, and not finding the solution by a different name, you're in the clear.

• approved macros:
  • defun
  • if
  • cond
  • let/let*
  • lambda
  • and, or
• basic math: +, -, *, /, mod, floor
  • floor, ceiling, round
• some list operations:
  • list
  • first, rest
    • last, butlast, nth
    • second, third, etc.
  • cons, car, cdr
    • also cadr, cddr, cdddr, etc.
  • length
  • member, subseq
• T, NIL
• and, or, (technically macros), not (a function)
• equalp
• some predicate functions:
  • null
  • zerop
  • consp
• funcall (used when we receive a function as an argument and want to call it)
• apply (feed a list as positional arguments)
• (don't use the built-in reverse, call your own reversed once it's complete)
• concatenate, append
• mapcar
• filter, count
• a few other approved things:
  • some sequence-modifying things (focus on the non-destructive versions). The destructive versions require better understanding of where data is stored and shared between expressions, which makes them harder to use correctly as a novice.
    • remove/-if/-not (but avoid delete/-if/-not)
    • substitute/-if/-not (but avoid nsubstitute/-if/-not)

• if you find yourself using these things, you're writing further from the functional style. It's possible they may be just the solution you need to complete your algorithm as you're envisioning it, or they may be the reason you pass no extra test cases the rest of the evening… I would suggest avoiding these, as they are not required or anticipated pieces of solutions at all for this homework.
  • setf
  • return, return-from (use these rarely, preferably not at all)

SBCL seems to handle tail-call optimization directly. If you want to enable it in clisp, you need to manually tell it that you'd like it to have a lower level of debugging information than usual, so that it doesn't need to keep around otherwise-useless frames for tracing purposes. You also need to compile the code. (See the proclaim and compile usage below). Here's a sample session. You shouldn't need it for any of the examples on our assignment, as they do not dive so deeply in a recursive fashion. But it's fun to see tail call optimization at work!

> (defun even (x)
 (if (= 0 x) T
 (if (= 1 x) NIL
 (even (- x 2)))))
EVEN
> (even 10)
T
> (even 10000)
*** - Program stack overflow. RESET
> (proclaim '(optimize (debug 1)))
> (compile 'even)
EVEN ;
NIL ;
NIL
> (even 10000000)
T

given a positive integer, return a list of its prime factors, in increasing order. Include the correct number of occurrences, e.g. (prime-factors 24) is (2 2 2 3).

* (load "h5.lisp")     ;; not needed each time, just a reminder.
T
* (prime-factors 5)
(5)
* (prime-factors 50)
(2 5 5)
* (prime-factors 66)
(2 3 11)
* (prime-factors 463)
(463)
* (prime-factors 512)
(2 2 2 2 2 2 2 2 2)
*

Given two positive integers, return whether they are co-prime or not. Coprime numbers don't share any divisors other than 1.

* (coprime 7 11)
T
* (coprime 10 21)
T
* (coprime 50 100)
NIL
* (coprime 367 463)
T
* (coprime 330 463)
T
* (coprime 222 262)
NIL

Given a non-negative integer n, calculate the nth tribonnaci number (where values are the sums of the previous three items in the sequence, or 1 when there aren't enough values ahead of it). For our purposes, the sequence begins as 1,1,1,... (with indexes 0, 1, 2, …).

• You need to implement a fast version (O(n)); if your code takes some exponential amount of time to complete, you will not get credit for this function.

* (trib 0)
1
* (trib 1)
1
* (trib 2)
1
* (trib 3)
3
* (trib 4)
5
* (trib 5)
9
* (trib 6)
17
* (mapcar 'trib '(5 6 7 8 9 10 11 12))
(9 17 31 57 105 193 355 653)

Given a list of integers xs, find the two largest values and return them in a list (largest first). Largest duplicates should be preserved (included) in the output. Do not modify the original list.

• Hint: doing one traversal and no modification is the suggested approach.

(max-two (list 1 2 3 4 5 1 2))
(5 4)
* (max-two (list 3 6 1 2 6 4))
(6 6)
* (max-two (list -3 -4 -5 -2 -10))
(-2 -3)

Given a list of any type of values, create the list whose values are in the opposite order. Do not modify the original list. You can't call the built-in reverse, of course (or any similar direct reversal functionality).

* (reversed (list 1 2 3 4 5))
(5 4 3 2 1)
* (reversed (list 4))
(4)
* (reversed (list T NIL NIL))
(NIL NIL T)

Given a list of lists, assume it is rectangular (all rows have same length), create and return the list of lists that contains the same values, but rotated clockwise. Do not modify the original grid.

* (clockwise (list '(1 2 3) '(4 5 6)))
((4 1) (5 2) (6 3))
* (clockwise (list '(1 2 3 4 5)))
((1) (2) (3) (4) (5))
* (clockwise (list '(1) '(2) '(3) '(4) '(5)))
((5 4 3 2 1))

Given a list of Bool values, return T if any of them are true, and return NIL if every single one of them is not. Do not modify the original list. You may not just do the single call to or with the argument list's items all unpacked into multiple arguments to or - do your own list-walking.

* (any (list NIL NIL NIL))
NIL
* (any (list T NIL T NIL))
T
* (any NIL)
NIL

Given a predicate function p as well as a list of values xs, create a list of all items from the argument list that pass the predicate function. Preserve ordering in your output. Do not modify the original list.

• note: there are built in functions evenp, oddp, which are convenient for manual testing and exploration.
• note: you may not use remove-if or its cousins.

* (select 'evenp (list 1 2 3 4 5))
(2 4)
* (select (lambda (x) (= 1 (mod x 2))) (list 1 2 3 4 5))
(1 3 5)
* (select (lambda (x) (and (< 5 x) (< x 10))) (list 1 2 3 4 5 6 7 8 9 10 11 12))
(6 7 8 9)

Given a two-argument function f and two lists as bs of arguments to supply, create a list of the results of applying the function to each same-indexed pair of arguments from the two lists. (Zip up the two lists with the function). The answer is as long as the shortest of the two input lists. Do not modify the original lists.

* (zip-with '+ '(1 2 3) '(10 20 30))
(11 22 33)
* (zip-with '+ '(1 2 3) '(10 20 30 40 50 60))
(11 22 33)
* (zip-with (lambda (x y) (* x y))   '(1 2 3 4) '(2 4 6 8))
(2 8 18 32)
* (zip-with (lambda (x y) (* x y))   '(1 2 3 4) NIL)
NIL

Given positive ints r and c indicating number of rows and columns, create a 2D list that represents the "augmented identity matrix" with that dimension: It's the r x c matrix of all zeroes, except the main diagonal is all ones.

* (augdentity 3 3)
((1 0 0) (0 1 0) (0 0 1))
* (augdentity 3 5)
((1 0 0 0 0) (0 1 0 0 0) (0 0 1 0 0))
* (augdentity 5 3)
((1 0 0) (0 1 0) (0 0 1) (0 0 0) (0 0 0))
* (augdentity 2 2)
((1 0) (0 1))