Question
Please provide the solution for this assignment in Lisp code . Do NOT use any AI tools like Chat-GPT to generate codes/answers as that'd a
Please provide the solution for this assignment in Lisp code.
Do NOT use any AI tools like Chat-GPT to generate codes/answers as that'd a violation.
-------------------------------------------------------------------------------------------------------
_____ _________________ | | | (CUBE A) (CUBE B) | D | H | (CUBE C) (CUBE D) |_____|_________________| (BAR G) (BAR H) | | | | (VERTICAL G) | | | C | (HORIZONTAL H) | | |_____| (ON G *TABLE*) | | | | (ON A *TABLE*) | G | | B | (NEAR A G); "A is one unit to the right | | |_____| of G; valid only for blocks on *TABLE* | | | | (ON B A) | | | A | (ON C B), *TABLE*____|_____|_____|_____|_______(ON H C); This is "symmetrical"-ON
Again be sure to use LOCAL variables within functions (e.g., introduced by 'let') except for truly global parameters (such as a hash table) that multiple functions need to access. Use names of form *....* for global parameters. Unless stated otherwise, include input checking in your functions; i.e., if the user gives an argument which is not of the specied form, your function should return **ERROR**, and briefly indicate the kind of error.
Preamble ```````` As before, we assume that we have just 6 unit "cubes", {A, B, C, D, E, F} and 2 "bars" {G, H} of length 3. All our structures will be 2-dimensional (whereas the physical blocks world mentioned above was 3-D).
In Lisp assignment 1, you prepared the way for building block configurations satisfying a given structural description, by writing code that selects blocks for particularizing that description (replacing variables with names of suitable blocks). In this assignment, we'll first find "levels" of blocks. This will lead to a notion of "layers" that overcomes the flaws of the definition in Lisp1 that was abandoned. It turns out to be well- suited to building a block structure and potentially, reasoning about it.
The "level" of a block will be the height of its top surface above the table. In particular, *TABLE* is level 0. A cube placed on *TABLE* is level 1, A vertical bar placed on *TABLE* is level 3 (its top surface is at level 3). A horizontal bar placed on *TABLE* is level 1. A vertical bar placed on a horizontal bar lying on *TABLE* is level 4 (i.e., 1 + 3); etc.
We then define the set of all blocks whose supports are level-i blocks as the level-i layer. (By "supports" of a block we mean all the blocks it is directly resting on, i.e., that are in contact with its lower surface; for a block on the table, its only support is *TABLE*.) So the blocks put on *TABLE* make up the level-0 layer. If a vertical bar on the table has a cube on top of it, that cube will belong to the level-3 layer (because bars are of length 3). Note that not all levels will have corresponding layers. E.g., if a structure consists of just a vertical bar with a cube on top, we just have a level-0 layer and a level-3 layer (& nothing in between).
We will build structures from lower-level layers to higher-level layers, not because it's the only way but because it's systematic, and makes testing program correctness a little easier. (For the example in Lisp 1, this still gives the same sequence of actions specified there.)
By finding the layers of blocks for a given block structure, we'll be able to find a sequence of actions that build the structure.
Available relations and actions ``````````````````````````````` Here are ON-relation examples, using a notation where, e.g., XX stands XX for cube X, XXXXXX stands for bar X, or when it's vertical, it's like this: XX (U, V, Z are extra blocks, helping to support X) XX
| XXXXXX | YY UU XXXXXX | XXXXXX | XXXXXX | XXXXXX | XXXXXX | XXXXXX | YY VV YYYYYY | ZZ YYYYYY | YYYYYY | YY | YY ZZ | ZZ YY | YY ZZ | | | | | | (ON-1 X Y)| (ON-2 X Y) | (ON+1 X Y)|(ON X Y)|(ON+1 X Y)| (ON-1 X Y)| (ON+1 X Y) | (ON+1 X Z) | | |(ON-1 X Z)| (ON+1 X Z)| (ON-1 X U)
(ON-{1,2} X Y) means that the center of gravity (CofG) of X is displaced LEFTward from the CofG of Y by {1,2} units, and (ON+{1,2} X Y) means that the CofG of X is displaced RIGHTward from the CofG of Y by {1,2} units.
As explained in Lisp 1,
- (PUT-NEAR X Y) means "put X on the table, to the right of Y, with a unit space in between". The result will be (NEAR X Y), which means X, Y are on the table with X to the right of Y, with a space of one unit between them. (This enables us to just work with relative locations, instead of coordinate locations.)
- (PUT-NEXT-TO X Y) means "put X on the table, to the immediate right of Y (with no space in between)". The result will be (NEXT-TO X Y), which means X, Y are on the table with X to the right of Y, touching it. - (PUT-ON X Y) can be applied to any blocks (i.e., cubes or bars), and means that their CofG's will be vertically aligned. (The 4th example above would be the result of (PUT-ON X Y).)
- PUT-ON-1, PUT-ON+1, PUT-ON-2, PUT-ON+2 with arguments X, Y refer to placements of a horizontal bar X on some other block (cube or bar) in such a way that the resulting ON-relations are ON-1, ON+1, ON-2, and ON+2 respectively.
- (TURN-VERTICAL X) turns a horizonal bar X to the vertical position. We don't need TURN-HORIZONTAL because all bars are assumed to be initially horizontal (in some supply box separate from the table).
In placing a block, it suffices to specify one of its supports, because we will already have made sure that all supporting blocks are already in place. Here are 2 more examples (besides the one in Lisp1) of block configurations and their layers, and how they could have been built. However, ignore the definition of "layers" from the dropped part 5 of Lisp1 -- "layers" now start at layer 0, meaning blocks SUPPORTED BY *TABLE*, and in general "layer i" means the blocks whose supports are at height i above the *TABLE*. TTTTTTTTT stands for the *TABLE*:
Example 1 (arch) For a block, "level i" means "reaches up to level i" ````````` HHHHHH Layer 0: (G A) Actions: (TURN-VERTICAL G) GG CC Layer 1: (B) (PUT-ON G *TABLE*) GG BB Layer 2: (C) (PUT-NEAR A G); displaced to the right GG AA Layer 3: (H) (PUT-ON B A) TTTTTTTTTT (PUT-ON C B) (PUT-ON-1 H C) {or, (PUT-ON+1 H G)} Example 2 (shoe) ````````` BBCC Layer 0: (G A) Actions: (PUT-ON G *TABLE*) HHHHHH Layer 1: (H) (PUT-NEAR A G) GGGGGG AA Layer 2: (B C) (PUT-ON+2 H G) {or, (PUT-ON-1 H A)} TTTTTTTTTTTT (PUT-ON B H) (PUT-ON+1 C H) Tasks ````` 0. Create a global 1-D array *BLOCKS-AT-LEVEL-I* of length 12, which will be used to store (*TABLE*) at index 0 (since *TABLE* is the only level-0 object); a list of level-1 blocks (if any) at index 1; a list of level-2 blocks (if any) at index 2; and so on. Note that nothing higher than height 12 can be built with the assumed set of blocks. We could have skipped the level-0 entry of (*TABLE*) because *TABLE* always plays the same role, but we store it for completeness),
Initiate a global hash table (with no entries yet) called *SUPPORTS* to be used for storing (a) all the blocks that support a given block, and (b) all the blocks a given block supports, according to a specific structural description. Block names will be used as keys.
1. Write a function (defun find-supports (specific-struc-descr) ...) whose argument is a particularized structural description (i.e., containing no variables -- see previous assignment), and which uses the *SUPPORTS* hash table to record a pair of lists for each block (using the block name a key) appearing in SPECIFIC-STRUC-DESCR: the list of blocks that directly support it (as indicated by the various ON-relations), and the list of blocks it directly supports. For example, the entry corresponding to bar H in example 2 above would be ((G A) (B C)). The entry for G would be ((*TABLE*) (H)). The entry for *TABLE* would be (() (G A)). If a block (other than *TABLE*, which actually isn't a block) is unsupported, the function should report this error.
2. Write a program (defun find-layers (specific-struc-descr) ...) whose argument is a particularized structural description and which returns a list of sublists, where each sublist is a "layer" preceded by an index indicating the level of its supporting blocks, i.e., of form (i B1 B2 ...) where i is an array index and B1, B2, ... are the blocks supported by level-i blocks (or for i = 0, by *TABLE*). The sublists (layers) should be returned in the output list in order of increasing i, starting with i = 0 (i.e., blocks supported by *TABLE*). Note: the blocks B1, B2, ... in (i B1 B2 ...) are NOT level-i blocks, but rather SUPPORTED by level-i blocks.
Start by emptying the *SUPPORTS* hash table (to "clean up" from any prior runs), and then running 'find-supports' on SPECIFIC-STRUC-DESCR to fill the *SUPPORTS* hash table.
'Find-layers' should work by filling in the *BLOCKS-AT-LEVEL-I* array in tandem with building the output list of layers. Specifically, after entering (*TABLE*) at index 0, find the blocks B1, B2, ... that are supported at level 0 (i.e., by the table), and hence form the first layer (0 B1 B2 ...), which you'll use as part of the output. N.B.: Assume that blocks X involved in a (NEAR X Y) or (NEXT-TO X Y) relation also have (ON X *TABLE*) relations in SPECIFIC-STRUC-DESCR (though it would be easy to add them before starting find-supports). Then enter B1, B2, ... in the *BLOCKS-AT-LEVEL-I* array, at indices determined by their height (= 1 for cubes and horizontal bars, and = 3 for vertical bars on the table). Then progress through the array to find the next index i at which there is a nonempty list of blocks. Using the *SUPPORTS* hash table, find all the blocks C1, C2, ... supported by the blocks at index i, and this will provide the next layer (i C1 C2 ...); and so on, till you reach the end of the 12-element array. Return the list of layers, including the indices.
3. Write a program (defun find-steps (specific-struc-descr) ...) whose single argument is again a particularized structural description, and which outputs a list of steps for creating the described structure. You can start by turning any bars vertical that need to be vertical in the given structure. Then you can proceed layer-by layer, and for each block Bj in a layer (i B1 .. Bj ..), find one level-i block that Bj is on, and hence a corresponding PUT-action. (Such a PUT-action is easily determined from the ON-relation involved; you might use a 'case' statement for that -- a very neat device!). To find level-i candidate blocks use the *SUPPORT* hash table created in part 1.
4. Write a program (defun build-goal-structure (nonspecific-struc-descr) ...) that takes as its single argument a structure specification of the type we have described (with variables for blocks), and outputs steps for building an instance of it. It should use 'find-required-blocks' first and output a message to the effect "I will use the following blocks:
5. Creatively design various structural descriptions (give them names, e.g., "pyramid", "staircase", "fence", "robot" or whatever) and run your program on them, showing that it produces correct instances of the descriptions; correctness will presumably be easy to judge by inspection of the steps. It would be nice, but DEFINITELY not required, and definitely not easy, if you could produce corresponding rough "diagrams" -- something like those above -- of block names arranged in the desired way. -----------------------------------------------------------------------------------------------
- Please include Lisp codes for all parts as I cannot ask this question in parts and under separate questions without previous parts.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started