perm filename ZAP[206,LSP] blob sn#485149 filedate 1979-10-25 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00008 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .REQUIRE "206MAC.PUB[206,LSP]" source_file C00003 00003 .if false then begin "zap" C00011 00004 .hd206 FALL 1979 C00012 00005 #.[10] Write a program mapbin that takes three arguments: C00014 00006 #.[10] Suppose we represent two a dimensional, m by n, array as a list C00021 00007 #.[20] Suppose a set of cities, represented by the list CITIES, C00030 00008 #.[5] Give statements expressing the following facts C00031 ENDMK C⊗; .REQUIRE "206MAC.PUB[206,LSP]" source_file; . .odd heading(,,{page}) ; .even heading({page}, , ) ; . .LSPFONT .basicops . .allops .itemmac 1; . .PORTION MAINPORTION .if false then begin "zap" .hd206 FALL 1979 .PAGE ← 1 .skip .cb |Midterm Exam 22nd October 1979| This examination is open book and notes. When you are asked to write LISP programs you may use external or internal form. Read each question carefully and be sure you understand what is wanted before you begin work. You may use any of the programs defined in chapters I and II, in writing the requested programs. There is a total of 50 points possible distributed as indicated at the beginning of each problem. GOOD LUCK!! .begin .indent 0,3 .item ← 0 #.[5] What well known function does the following program compute: .begin nofill indent 8,8 ⊗⊗foo_x ← baz[<x>,qNIL]⊗ ⊗⊗baz[u,v] ← qif qn u qthen v qelse ⊗ ⊗⊗_________qif qat qa u qthen baz[qd u,qa u_._v] qelse ⊗ ⊗⊗_________baz[qda u_._[qaa u_._qd u],v]⊗ .end #.[10] Write a program ⊗mapbin that takes three arguments: a binary operation, ⊗F, a starting value ⊗e, and a list ⊗u and combines the elements of the list together with ⊗e. If the list is is empty, the result is ⊗e, if it has one element ⊗x1 then the result is ⊗⊗F[x1,e]⊗, if it is a two element list ⊗⊗<x1,x2>⊗ the result is ⊗⊗F[x1,F[x2,e]]⊗, etc.. Thus ⊗⊗⊗mapbin[$$PLUS$,$$0$,$$(1 2 3 4)$]=$$12$.⊗ #.[10] Suppose we represent two a dimensional ⊗m by ⊗n array as a list of lists. Each element of the main list corresponds to a row in the array and will have ⊗n elements (one for each column). The main list will have ⊗m elements, one for each row. Thus the element in the ⊗⊗i⊗th row and ⊗⊗j⊗th column of the array is the ⊗⊗j⊗th element of the ⊗⊗i⊗th list. The transpose of a two dimensional ⊗m by ⊗n array is an ⊗n by ⊗m array whose columns are the rows of the original (and whose rows therefore are the columns of the original). Write a program ⊗transpose that takes a list representing an array and returns the list representing its transpose. For example ⊗⊗⊗transpose $$((A B C) (D E F))$=$$((A D) (B E) (C F))$.⊗ Note that the list representing the transpose of an array is the same as the list representing the array by listing the columns instead of the rows. [Turn the page over to find the rest of the exam!] .next page #.[20] Suppose a set of cities, represented by the list ⊗CITIES, are interconnected by railroads. We use the edge representation of graphs from problem 4 of the homework to represent the shipping needs of these cities. Thus the edge $$(A B 6)$ indicates that $6 tons of goods must be shipped from city $A to city $B, i.e. they will be picked up at $A and unloaded at $B. Call this graph ⊗FREIGHT. Someone at the railroad chooses a route for the train to follow. This route is represented by a list of cities in the order they are visited, e.g. $$(A B C)$. No city is visted more than once. While travelling this route, the train will pick up all goods which are to be delivered to any city appearing later in the route. Write a program ⊗pickup which takes the graph ⊗FREIGHT and a route ⊗ROUTE, and a city ⊗CITY, appearing in the route, and returns a list of the form $$((city number) ...)$ which describes how much freight is to be picked up at ⊗CITY and for what destinations. Thus $$(B 4)$ means pick up $4 tons to go to $B. Write similar program, ⊗drop, which returns a list of the same form, describing how many tons are to be dropped at ⊗CITY, and where they came from. The railraod has the problem that the train has a maximum capacity of ⊗FULL tons. Using ⊗pickup and ⊗drop, write a program ⊗loadcheck that returns $OVERLOAD if the train will ever have to carry more than ⊗FULL tons as it goes along ⊗ROUTE and returns $OK otherwise. [Recall that ⊗assoc is useful for manipulating lists of properties such as the results of ⊗pickup and ⊗drop. ] #.[5] Give formal statements expressing the following facts .begin indent 6,6 ##. ⊗⊗revers⊗ing a list does not change its ⊗length. ##. ⊗⊗append⊗ing a single element list onto a second list is the same as ⊗⊗cons⊗ing that element onto the second list. For example the statement ⊗⊗∀u:_u*qNIL=u⊗ expresses the fact that qNIL is the right identity for ⊗append, e.g. the result of ⊗⊗append⊗ing a list onto the empty list is just that list. .end .end .end "zap" .hd206 FALL 1979 .PAGE ← 1 .skip .cb |Midterm Exam: Solutions| .begin .indent 0,3 .item ← 0 #.[5] What well known function does the following program compute: .begin nofill indent 8,8 ⊗⊗foo_x ← baz[<x>,qNIL]⊗ ⊗⊗baz[u,v] ← qif qn u qthen v qelse ⊗ ⊗⊗_________qif qat qa u qthen baz[qd u,qa u_._v] qelse ⊗ ⊗⊗_________baz[qda u_._[qaa u_._qd u],v]⊗ .end Solution: ⊗⊗∀x: foo x = fringe x⊗ #.[10] Write a program ⊗mapbin that takes three arguments: a binary operation, ⊗F, a starting value ⊗e, and a list ⊗u and combines the elements of the list together with ⊗e. If the list is is empty, the result is ⊗e, if it has on element ⊗x1 the the result is ⊗⊗F[x1,e]⊗, if it is a two element list ⊗⊗<x1,x2>⊗ the result is ⊗⊗F[x1,F[x2,e]]⊗, etc.. Thus ⊗⊗⊗mapbin[$$PLUS$,$$0$,$$(1 2 3 4)$]=$$10$.⊗ Solution: ⊗⊗mapbin[F,e,u] ← qif qn u qthen e qelse F[qa u,mapbin[F,e,qd u]]⊗ or in internal form .begin nofill select 6 indent 8,8 (DEFUN MAPBIN (F E U) (COND ((NULL U) E) (T (F (CAR U) (MAPBIN F E (CDR U)))))) .end #.[10] Suppose we represent two a dimensional, ⊗m by ⊗n, array as a list of lists. Each element of the main list corresponds to a row in the array and will have ⊗n elements (one for each column). The main list will have ⊗m elements, one for each row. Thus the element in the ⊗⊗i⊗th row and ⊗⊗j⊗th column of the array is the ⊗⊗j⊗th element of the ⊗⊗i⊗th list. The transpose of a two dimensional ⊗m by ⊗n array is an ⊗n by ⊗m array whose columns are the rows of the original (and whose rows therefore are the columns of the original). Write a program ⊗transpose that takes a list representing an array and returns the list representing its transpose. For example ⊗⊗⊗transpose $$((A B C) (D E F))$=$$((A D) (B E) (C F))$.⊗ Note that the list representing the transpose of an array is the same as the list representing the array by listing the columns instead of the rows. Solution: The program ⊗transpose starts by computing the list of first elements of the rows of the transposed array. These are just the elements of the first row of the original array, and ⊗mapcar does the job. It then calls ⊗transp which goes through the remaining rows of the original array and for each such row adds the elements to the end of the corresponding new row that is being constructed. This is done by calling ⊗enquel[u,vl] where ⊗u is the row of the original array to be processed next and ⊗vl is the new list of rows. .begin nofill select 2 turnon "∂" .group .n←4 ∂(n+8)transpose ul ← qif qn ul qthen qNIL qelse transp[qd ul, mapcar[[λx: <x>], qa ul]] .apart .group ∂(n+8)transp[ul, vl] ← qif qn ul qthen vl qelse transp[qd ul, enquel[qa ul, vl]] .apart .group ∂(n+8)enquel[u, vl] ← qif qn u qthen qNIL qelse [qa vl * <qa u>] . enquel[qd u, qd vl] .end or in internal form .begin nofill select 6 indent 6,6 .group (DEFUN TRANSPOSE (UL) (COND ((NULL UL) NIL) (T (TRANSP (CDR UL) (MAPCAR (FUNCTION (LAMBDA (X) (LIST X))) (CAR UL)))))) .apart .group (DEFUN TRANSP (UL VL) (COND ((NULL UL) VL) (T (TRANSP (CDR UL) (ENQUEL (CAR UL) VL))))) .apart .group (DEFUN ENQUEL (U VL) (COND ((NULL U) NIL) (T (CONS (APPEND (CAR VL) (LIST (CAR U))) (ENQUEL (CDR U) (CDR VL)))))) .end A somewhat more efficient solution is given by ⊗transpos,trans,stackl. They work in essentially the same way, but start by reversing the the list of rows so that the new list of rows can be built by adding to the fronts of the old rows rather that to the end, thus avoiding excessive use of ⊗append. .begin nofill select 2 turnon "∂" .group .n←4 ∂(n+8)transpos ul ← qif qn ul qthen qNIL qelse [λvl:trans[qd vl,mapcar[[λx:<x>],qa vl]]][reverse ul] .apart .group ∂(n+8)trans[ul, vl] ← qif qn ul qthen vl qelse trans[qd ul, stackl[qa ul, vl]] .apart .group ∂(n+8)stackl[u, vl] ← qif qn u qthen qNIL qelse [qa u . qa vl] . stackl[qd u, qd vl] .end The internal forms of these programs are: .begin nofill select 6 indent 6,6 .group (DEFUN TRANSPOS (UL) (COND ((NULL UL) NIL) (T ((LAMBDA (VL) (TRANS (CDR VL) (MAPCAR (FUNCTION (LAMBDA (X) (LIST X))) (CAR VL)))) (REVERSE UL)) ))) .apart .group (DEFUN TRANS (UL VL) (COND ((NULL UL) VL) (T (TRANS (CDR UL) (STACKL (CAR UL) VL))))) .apart .group (DEFUN STACKL (U VL) (COND ((NULL U) NIL) (T (CONS (CONS (CAR U) (CAR VL)) (STACKL (CDR U) (CDR VL)))))) .end A third solution given by many students is: ⊗⊗⊗transpose u←qif [qn u qor qn qa u] qthen qNIL qelse mapcar[qqa, u]_._transpose mapcar[qqd,u]⊗ which has the internal form .begin nofill select 6 indent 6,6 .group (DEFUN TRANSPOSE (U) (COND ((OR (NULL U) (NULL (CAR U))) NIL) (T (CONS (MAPCAR (FUNCTION CAR) U) (TRANSPOSE (MAPCAR (FUNCTION CDR) U)))))) .end #.[20] Suppose a set of cities, represented by the list ⊗CITIES, are interconnected by railroads. We use the edge representation of graphs from problem 4 of the homework to represent the shipping needs of these cities. Thus the edge $$(A B 6)$ indicates that $6 tons of goods must be shipped from city $A to city $B, i.e. they will be picked up at $A and unloaded at $B. Call this graph ⊗FREIGHT. Someone at the railroad chooses a route for the train to follow. This route is represented by a list of cities in the order they are visited, e.g. $$(A B C)$. No city is visted more than once. While travelling this route, the train will pick up all goods which are to be delivered to any city appearing later in the route. Write a program ⊗pickup which takes the graph ⊗FREIGHT and a route ⊗ROUTE, and a city ⊗CITY, appearing in the route, and returns a list of the form $$((city number) ...)$ which describes how much freight is to be picked up at ⊗CITY and for what destinations. Thus $$(B 4)$ means pick up $4 tons to go to $B. Write similar program, ⊗drop, which returns a list of the same form, describing how many tons are to be dropped at ⊗CITY, and where they came from. The railraod has the problem that the train has a maximum capacity of ⊗FULL tons. Using ⊗pickup and ⊗drop, write a program ⊗loadcheck that returns $OVERLOAD if the train will ever have to carry more than ⊗FULL tons as it goes along ⊗ROUTE and returns $OK otherwise. Solution: First of all, it is important to determine which cities precede of follow CITY in ROUTE. FIND-GOOD-CITIES finds the cities following CITY in ROUTE. By reversing ROUTE we use it to find the cities preceding to CITY in ROUTE. We use the cities following CITY in PICKUP, and the cities preceding in DROP. Having got these cities, calling the list of them GOOD-CITIES, we now map through FREIGHT, looking for edges of the correct form, i.e., one city is CITY, the other is in GOOD-CITIES. (The desired order is opposite in PICKUP and DROP.) We use MAP-APPEND, which was defined in the solutions of the first homework; there are a variety of ways to achieve the same effect. To do LOADCHECK we need to keep track of the load being carried as the train goes from city to city along route. We use the program LC, which has a variable for this, initialized to 0. At each city we compute the change in the load by totalling up what is picked up and dropped. We check the new total against FULL. .begin nofill select 2 turnoff "{" .group .n←8 ⊗⊗ pickup[city, route, freight] ← ⊗ ⊗⊗ {find-good-cities[city, route]}[λgood-cities: ⊗ ⊗⊗ map-append[⊗ ⊗⊗ [λx: qif qa x = city ∧ qad x ε good-cities qthen <qd x>], ⊗ ⊗⊗ freight]]⊗ .apart .group ⊗⊗ drop[city, route, freight] ← ⊗ ⊗⊗ {find-good-cities[city, reverse route]}[λgood-cities: ⊗ ⊗⊗ map-append[⊗ ⊗⊗ [λx: qif qad x = city ∧ qa x ε good-cities qthen ⊗ ⊗⊗ <<qa x, qadd x>>], ⊗ ⊗⊗ freight]]⊗ .apart .group ⊗⊗ find-good-cities[city, route] ← ⊗ ⊗⊗ qif qn route qthen $$ERROR-I-THOUGHT-YOU-SAID-CITY-WAS-IN-ROUTE!$⊗ ⊗⊗ qelse qif qa route = city qthen qd route⊗ ⊗⊗ qelse find-good-cities[city, qd route]⊗ .apart .group ⊗⊗ loadcheck[route, freight] ← lc[route, freight, 0]⊗ ⊗⊗ lc[route, freight, load] ← ⊗ ⊗⊗ qif qn route qthen $$OK$⊗ ⊗⊗ qelse apply [⊗ ⊗⊗ [λp, d: qif load + p + -d > full qthen $$OVERLOAD$⊗ ⊗⊗ qelse lc[qd route, freight, load + p + -d]], ⊗ ⊗⊗ total pickup[qa route, route, freight], ⊗ ⊗⊗ total drop[qa route, route, freight]]⊗ ⊗⊗ total info ← apply[$$PLUS$, mapcar[$$CADR$, info]]⊗ .END .fill or in internal form .begin select 6 nofill indent 2,2 .group (DEFUN PICKUP (CITY ROUTE FREIGHT) ((LAMBDA (GOOD-CITIES) (MAP-APPEND (FUNCTION (LAMBDA (X) (COND ((AND (EQ (CAR X) CITY) (MEMBER (CADR X) GOOD-CITIES)) (LIST (CDR X)))))) FREIGHT)) (FIND-GOOD-CITIES CITY ROUTE))) .apart .group (DEFUN DROP (CITY ROUTE FREIGHT) ((LAMBDA (GOOD-CITIES) (MAP-APPEND (FUNCTION (LAMBDA (X) (COND ((AND (EQ (CADR X) CITY) (MEMBER (CAR X) GOOD-CITIES)) (LIST (LIST (CAR X) (CADDR X))))))) FREIGHT)) (FIND-GOOD-CITIES CITY (REVERSE ROUTE)))) .apart .group (DEFUN FIND-GOOD-CITIES (CITY ROUTE) (COND ((NULL ROUTE) 'ERROR-I-THOUGHT-YOU-SAID-CITY-WAS-IN-ROUTE!) ((EQ (CAR ROUTE) CITY) (CDR ROUTE)) (T (FIND-GOOD-CITIES CITY (CDR ROUTE))))) .apart .group (DEFUN LOADCHECK (ROUTE FREIGHT) (LC ROUTE FREIGHT 0)) .apart .group (DEFUN LC (ROUTE FREIGHT LOAD) (COND ((NULL ROUTE) 'OK) (T ((FUNCTION (LAMBDA (P D) (COND ((GREATERP (PLUS LOAD P (MINUS D)) FULL) 'OVERLOAD) (T (LC (CDR ROUTE) FREIGHT (PLUS LOAD P (MINUS D))))))) (TOTAL (PICKUP (CAR ROUTE) ROUTE FREIGHT)) (TOTAL (DROP (CAR ROUTE) ROUTE FREIGHT)))))) .apart .group (DEFUN TOTAL (INFO) (APPLY 'PLUS (MAPCAR 'CADR INFO))) .end #.[5] Give statements expressing the following facts .begin indent 4,4 ##. ⊗⊗revers⊗ing a list does not change its ⊗length. Solution: ⊗⊗∀u:length reverse u=length u.⊗ ##. ⊗⊗append⊗ing a single element list onto a second list is the same as ⊗⊗cons⊗ing that element onto the second list. Solution: ⊗⊗∀x v: <x>*v = [x_._v]⊗ Alternate solution: ⊗⊗∀u v: [length u = 1 ⊃ u*v = [qa u_._v] ]⊗ .end .end