Courses/CS 460/Fall 2005/Homework/Brian Smith/Oct 29
From CSWiki
< Courses | CS 460 | Fall 2005 | Homework | Brian Smith
Contents |
[edit] The Second Method
[edit] Four Trees
Each of four men who live in Willowbrook Estates on the city’s north side, planted a different type of tree in their front yard on Arbor Day. From The clues, determine the first and last name of each man and the type of tree each planted.
local
%----- Problem-specific setup -----
LastNames = [becker clary delgado erichsen]
Trees = [ash cedar maple sycamore]
FieldNames = [lastName tree]
proc {IsALastName ?L} {IsIn L LastNames} end
proc {IsATree ?T} {IsIn T Trees} end
fun {MakePerson} {Record.make person FieldNames} end
%----- General Utilities -----
proc {Append ?Xs ?Ys ?Zs}
choice
Xs = nil
Ys = Zs
[] Xr X in
Xs = X | Xr
Zs = X | {Append Xr Ys}
end
end
proc {IsIn ?X Xs} {Append _ X|_ Xs} end
proc {IsInRecord ?X Rec} {IsIn X {Record.toList Rec}} end
proc {NotInRecord ?X Rec}
thread if {Member X {Record.toList Rec}} then fail end end
end
proc {NotEqual X Y} thread X == Y = false end end
fun {GetVarsForField Field Elts}
{Map Elts fun {$ Elt} Elt.Field end}
end
% Different way to test if a list of values is pairwise distinct.
% MakeRecord expects the given list to have distinct values.
% If it doesn't, it throws an exception which is ignored and
% that computational space fails. If Distinct is called before
% the values are determined it simply waits until they have
% all been determined and executes the test.
proc {Distinct Fields}
thread
try {MakeRecord test Fields _}
catch _ then fail end
end
end
%----- Clues -----
% 1. George, Mr.Clary, and Mr. Becker (who got his tree from
% HomeTown Garden Center) all live within three blocks of one
% another.
proc {Clue1 Results}
{NotEqual Results.george.lastName becker}
{NotEqual Results.george.lastName clary}
end
% 2. Mr. Clary planted neither the cedar tree or the maple tree.
proc {Clue2 Results}
{NotInRecord person(lastName:clary tree:cedar) Results}
{NotInRecord person(lastName:clary tree:maple) Results}
end
% 3. Harvey and Mr. Clary live next door to one another.
proc {Clue3 Results}
{NotEqual Results.harvey.lastName clary}
end
% 4. The ash tree was not planted by neither John nor Ivan.
proc {Clue4 Results}
{NotEqual Results.john.tree ash}
{NotEqual Results.ivan.tree ash}
end
% 5. The maple tree was not the tree planted by George (who is
% not surnamed Delgado).
proc {Clue5 Results}
{NotEqual Results.george.tree maple}
{NotEqual Results.george.lastName delgado}
end
% 6. Mr. Erichsen isn't the man who planted the ash tree.
proc {Clue6 Results}
{NotInRecord person(lastName:erichsen tree:ash) Results}
end
% 7. John, who purchased his tree at the Green Thumb Greenhouse,
% isn't the man who planted the sycamore.
proc {Clue7 Results}
{NotEqual Results.john.lastName becker}
{NotEqual Results.john.tree sycamore}
end
%----- Execution -----
fun {FourTrees}
Results = {MakeRecord people [george harvey ivan john]}
People = {Record.toList Results}
Ls Ts
in
% create a 'person' record for each element in 'Results'
{Record.forAll Results fun {$} {MakePerson} end}
% get all the values for a given property of each 'person' record
Ls = {GetVarsForField lastName People}
Ts = {GetVarsForField tree People}
% ensure that these values are pairwise distinct
% (if this is done before populating the fields, the test simply
% waits until all the fields have been determined and executes)
{Distinct Ls}
{Distinct Ts}
% run the clues
{Clue1 Results}
{Clue2 Results}
{Clue3 Results}
{Clue4 Results}
{Clue5 Results}
{Clue6 Results}
{Clue7 Results}
% ensure that all fields have a value
{ForAll Ls fun {$} {IsALastName} end}
{ForAll Ts fun {$} {IsATree} end}
Results
end
RL
in
RL = {SearchAll FourTrees}
{Browse {Length RL}}
{Browse RL}
end
[edit] Flower Boxes
Mary and three other women had flower boxes in windows on either side of their front doors and each woman planted a different type of flower in her window flower boxes (one woman planted petunias). From the clues, can you determine the first name and last name (one is Gumble) of each woman and the type of flower each woman planted?
local
%----- Problem-specific setup -----
LastNames = [drake evans florez gumble]
Flowers = [daisies marigolds petunias violets]
FieldNames = [lastName flower]
fun {MakePerson} {Record.make person FieldNames} end
proc {IsALastName ?L} {IsIn L LastNames} end
proc {IsAFlower ?F} {IsIn F Flowers} end
%----- General Utilities -----
proc {Append ?Xs ?Ys ?Zs}
choice
Xs = nil
Ys = Zs
[] Xr X in
Xs = X | Xr
Zs = X | {Append Xr Ys}
end
end
proc {IsIn ?X Xs} {Append _ X|_ Xs} end
proc {IsInRecord ?X Rec} {IsIn X {Record.toList Rec}} end
proc {NotInRecord ?X Rec}
thread if {Member X {Record.toList Rec}} then fail end end
end
proc {NotEqual X Y} thread X == Y = false end end
fun {GetVarsForField Field Elts}
{Map Elts fun {$ Elt} Elt.Field end}
end
% Different way to test if a list of values is pairwise distinct.
% MakeRecord expects the given list to have distinct values.
% If it doesn't, it throws an exception which I ignore and
% that computational space fails. If Distinct is called before
% the values are determined it simply waits until they have
% all been determined and executes the test.
proc {Distinct Fields}
thread
try {MakeRecord test Fields _}
catch _ then fail end
end
end
%----- Clues -----
% 1. The four women - Julie, Ms. Drake, Ms. Evans, and the woman who
% planted daisies, all belong to the same gardening club.
proc {Clue1 Results}
{NotEqual Results.julie.lastName drake}
{NotEqual Results.julie.lastName evans}
{NotEqual Results.julie.flower daisies}
{NotInRecord person(lastName:drake flower:daisies) Results}
{NotInRecord person(lastName:evans flower:daisies) Results}
end
% 2. The woman who planted violets in her flower boxes isn't Kate.
proc {Clue2 Results}
{NotEqual Results.kate.flower violets}
end
% 3. Ms. Drake isn't the woman who planted marigolds.
proc {Clue3 Results}
{NotInRecord person(lastName:drake flower:marigolds) Results}
end
% 4. Ms. Florez, who didn't plant violets, is married to Lola's brother.
proc {Clue4 Results}
{NotEqual Results.lola.lastName florez}
{NotInRecord person(lastName:florez flower:violets) Results}
end
% 5. Marigolds were not the flower of choice for Julie.
proc {Clue5 Results}
{NotEqual Results.julie.flower marigolds}
end
% 6. Kate, whose lastName isn't Evans, didn't plant daisies in her
% window flower boxes.
proc {Clue6 Results}
{NotEqual Results.kate.lastName evans}
{NotEqual Results.kate.flower daisies}
end
%----- Execution -----
fun {FlowerBoxes}
Results = {MakeRecord people [julie kate lola mary]}
People = {Record.toList Results}
Ls Fs
in
% create a 'person' record for each element in 'Results'
{Record.forAll Results fun {$} {MakePerson} end}
% get all the values for a given property of each 'person' record
Ls = {GetVarsForField lastName People}
Fs = {GetVarsForField flower People}
% ensure that these values are pairwise distinct
% (if this is done before populating the fields, the test simply
% waits until all the fields have been determined and executes)
{Distinct Ls}
{Distinct Fs}
% run the clues
{Clue1 Results}
{Clue2 Results}
{Clue3 Results}
{Clue4 Results}
{Clue5 Results}
{Clue6 Results}
% ensure that all fields have a value
{ForAll Ls fun {$} {IsALastName} end}
{ForAll Fs fun {$} {IsAFlower} end}
Results
end
RL
in
RL = {SearchAll FlowerBoxes}
{Browse {Length RL}}
{Browse RL}
end
[edit] A Day at the Zoo
One day, five mothers each brought their only child to the zoo. The children had a glorious time together watching the different animals and eating their favorite snacks. The kids were so good, at the end of the day each mother let her child get one item from the souvenir shop as they were leaving the zoo. Can you determine the full name of each child, each child's favorite snack and animal, and the souvenir each brought home?
local
%----- Problem-specific setup -----
LastNames = [brown cook macGregor proctor small]
Food = [caramelApple cottonCandy friedDough nachos popcorn]
Animals = [elephants giraffes lions monkeys seals]
Souvenirs = [activitySet coloringBook poster stuffedAnimal toyGun]
FieldNames = [lastName food animal souvenir]
proc {IsALastName ?L} {IsIn L LastNames} end
proc {IsAFood ?F} {IsIn F Food} end
proc {IsAnAnimal ?A} {IsIn A Animals} end
proc {IsASouvenir ?S} {IsIn S Souvenirs} end
fun {MakePerson} {Record.make person FieldNames} end
%----- General Utilities -----
proc {Append ?Xs ?Ys ?Zs}
choice
Xs = nil
Ys = Zs
[] Xr X in
Xs = X | Xr
Zs = X | {Append Xr Ys}
end
end
proc {IsIn ?X Xs} {Append _ X|_ Xs} end
proc {IsInRecord ?X Rec} {IsIn X {Record.toList Rec}} end
proc {NotInRecord ?X Rec}
thread if {Member X {Record.toList Rec}} then fail end end
end
proc {NotEqual X Y} thread X == Y = false end end
fun {GetVarsForField Field Elts}
{Map Elts fun {$ Elt} Elt.Field end}
end
% Different way to test if a list of values is pairwise distinct.
% MakeRecord expects the given list to have distinct values.
% If it doesn't, it throws an exception which I ignore and
% that computational space fails. If Distinct is called before
% the values are determined it simply waits until they have
% all been determined and executes the test.
proc {Distinct Fields}
thread
try {MakeRecord test Fields _}
catch _ then fail end
end
end
%----- Clues -----
% 1. Julia, who loves cotton candy, didn't like the elephants.
% Mary didn't get a caramel apple. The child who got the stuffed
% animal liked the giraffes best.
proc {Clue1 Results}
Results.julia.food = cottonCandy
{NotEqual Results.julia.animal elephants}
{NotEqual Results.mary.food caramelApple}
{IsInRecord person(lastName:_
food:_
souvenir:stuffedAnimal
animal:giraffes)
Results}
end
% 2. Alan Small, the girl who liked the lions, and the child who
% got the activity set didn't want to leave the zoo.
proc {Clue2 Results}
Results.alan.lastName = small
{NotEqual Results.alan.animal lions}
{NotEqual Results.alan.souvenir activitySet}
choice
Results.beth.animal = lions
{NotEqual Results.beth.souvenir activitySet}
[]
Results.julia.animal = lions
{NotEqual Results.julia.souvenir activitySet}
[]
Results.mary.animal = lions
{NotEqual Results.mary.souvenir activitySet}
end
end
% 3. Neither of the boys got fried dough, but one got nachos and
% the other one liked the monkeys best. Tom didn't get a poster.
proc {Clue3 Results}
{NotEqual Results.alan.food friedDough}
{NotEqual Results.tom.food friedDough}
choice
Results.alan.food = nachos
Results.tom.animal = monkeys
[]
Results.tom.food = nachos
Results.alan.animal = monkeys
end
{NotEqual Results.tom.souvenir poster}
end
% 4. The Brown child almost got a coloring book with Mary but
% finally decided on a poster.
proc {Clue4 Results}
{NotEqual Results.mary.lastName brown}
Results.mary.souvenir = coloringBook
{IsInRecord person(lastName:brown
food:_
animal:_
souvenir:poster)
Results}
end
% 5. Tom, whose last name isn't Proctor, got a toy gun but didn't
% get a caramel apple. The MacGregor child had fried dough.
proc {Clue5 Results}
{NotEqual Results.tom.lastName proctor}
Results.tom.souvenir = toyGun
{NotEqual Results.tom.food caramelApple}
{IsInRecord person(lastName:macGregor
food:friedDough
animal:_
souvenir:_)
Results}
end
% 6. Beth, who didn't like the giraffes or the elephants best,
% got an activity set.
proc {Clue6 Results}
{NotEqual Results.beth.animal giraffes}
{NotEqual Results.beth.animal elephants}
Results.beth.souvenir = activitySet
end
%----- Execution -----
fun {DayAtZoo}
Results = {MakeRecord people [alan beth julia mary tom]}
People = {Record.toList Results}
Ls Fs As Ss
in
% create a 'person' record for each element in 'Results'
{Record.forAll Results fun {$} {MakePerson} end}
% get all the values for a given property of each 'person' record
Ls = {GetVarsForField lastName People}
Fs = {GetVarsForField food People}
As = {GetVarsForField animal People}
Ss = {GetVarsForField souvenir People}
% ensure that these values are pairwise distinct
% (if this is done before populating the fields, the test simply
% waits until all the fields have been determined and executes)
{Distinct Ls}
{Distinct Fs}
{Distinct As}
{Distinct Ss}
% run the clues
{Clue1 Results}
{Clue2 Results}
{Clue3 Results}
{Clue4 Results}
{Clue5 Results}
{Clue6 Results}
% ensure that all fields have a value
{ForAll Ls fun {$} {IsALastName} end}
{ForAll Fs fun {$} {IsAFood} end}
{ForAll As fun {$} {IsAnAnimal} end}
{ForAll Ss fun {$} {IsASouvenir} end}
Results
end
RL
in
RL = {SearchAll DayAtZoo}
{Browse {Length RL}}
{Browse RL}
end
[edit] A Day at the Zoo (with in-class additions)
During class we looked at clue 2 and asked what would happen if we said 'child' instead of 'girl'. We developed the NotInRecord procedure to accomplish a negation when we don't know a specific person record.
local
%----- Problem-specific setup -----
LastNames = [brown cook macGregor proctor small]
Food = [caramelApple cottonCandy friedDough nachos popcorn]
Animals = [elephants giraffes lions monkeys seals]
Souvenirs = [activitySet coloringBook poster stuffedAnimal toyGun]
FieldNames = [lastName food animal souvenir]
proc {IsALastName ?L} {IsIn L LastNames} end
proc {IsAFood ?F} {IsIn F Food} end
proc {IsAnAnimal ?A} {IsIn A Animals} end
proc {IsASouvenir ?S} {IsIn S Souvenirs} end
fun {MakePerson} {Record.make person FieldNames} end
%----- General Utilities -----
proc {Append ?Xs ?Ys ?Zs}
choice
Xs = nil
Ys = Zs
[] Xr X in
Xs = X | Xr
Zs = X | {Append Xr Ys}
end
end
proc {IsIn ?X Xs} {Append _ X|_ Xs} end
proc {IsInRecord ?X Rec} {IsIn X {Record.toList Rec}} end
% We created this prcedure in class to provide a negation
% version if IsInRecord. We only care about a subset of the
% fields of each record, so we used Record.zip because it
% silently drops any fields that appear in only one record.
proc {NotInRecord X Rec}
thread
{Record.forAll Rec
proc {$ Z}
if X == {Record.zip X Z fun {$ XF ZF} ZF end}
then fail end
end}
end
end
proc {NotEqual X Y} thread X == Y = false end end
fun {GetVarsForField Field Elts}
{Map Elts fun {$ Elt} Elt.Field end}
end
% Different way to test if a list of values is pairwise distinct.
% MakeRecord expects the given list to have distinct values.
% If it doesn't, it throws an exception which I ignore and
% that computational space fails. If Distinct is called before
% the values are determined it simply waits until they have
% all been determined and executes the test.
proc {Distinct Fields}
thread
try {MakeRecord test Fields _}
catch _ then fail end
end
end
%----- Clues -----
% 1. Julia, who loves cotton candy, didn't like the elephants.
% Mary didn't get a caramel apple. The child who got the stuffed
% animal liked the giraffes best.
proc {Clue1 Results}
Results.julia.food = cottonCandy
{NotEqual Results.julia.animal elephants}
{NotEqual Results.mary.food caramelApple}
{IsInRecord person(lastName:_
food:_
souvenir:stuffedAnimal
animal:giraffes)
Results}
end
% 2. Alan Small, the girl who liked the lions, and the child who
% got the activity set didn't want to leave the zoo.
proc {Clue2 Results}
Results.alan.lastName = small
{NotEqual Results.alan.animal lions}
{NotEqual Results.alan.souvenir activitySet}
{NotInRecord person(souvenir:activitySet
animal:lions)
Results}
% We created NotInRecord in class to replace this (using 'child'
% instead of 'girl')
% choice
% Results.beth.animal = lions
% {NotEqual Results.beth.souvenir activitySet}
% []
% Results.julia.animal = lions
% {NotEqual Results.julia.souvenir activitySet}
% []
% Results.mary.animal = lions
% {NotEqual Results.mary.souvenir activitySet}
% end
end
% 3. Neither of the boys got fried dough, but one got nachos and
% the other one liked the monkeys best. Tom didn't get a poster.
proc {Clue3 Results}
{NotEqual Results.alan.food friedDough}
{NotEqual Results.tom.food friedDough}
choice
Results.alan.food = nachos
Results.tom.animal = monkeys
[]
Results.tom.food = nachos
Results.alan.animal = monkeys
end
{NotEqual Results.tom.souvenir poster}
end
% 4. The Brown child almost got a coloring book with Mary but
% finally decided on a poster.
proc {Clue4 Results}
{NotEqual Results.mary.lastName brown}
Results.mary.souvenir = coloringBook
{IsInRecord person(lastName:brown
food:_
animal:_
souvenir:poster)
Results}
end
% 5. Tom, whose last name isn't Proctor, got a toy gun but didn't
% get a caramel apple. The MacGregor child had fried dough.
proc {Clue5 Results}
{NotEqual Results.tom.lastName proctor}
Results.tom.souvenir = toyGun
{NotEqual Results.tom.food caramelApple}
{IsInRecord person(lastName:macGregor
food:friedDough
animal:_
souvenir:_)
Results}
end
% 6. Beth, who didn't like the giraffes or the elephants best,
% got an activity set.
proc {Clue6 Results}
{NotEqual Results.beth.animal giraffes}
{NotEqual Results.beth.animal elephants}
Results.beth.souvenir = activitySet
end
%----- Execution -----
fun {DayAtZoo}
Results = {MakeRecord people [alan beth julia mary tom]}
People = {Record.toList Results}
Ls Fs As Ss
in
% create a 'person' record for each element in 'Results'
{Record.forAll Results fun {$} {MakePerson} end}
% get all the values for a given property of each 'person' record
Ls = {GetVarsForField lastName People}
Fs = {GetVarsForField food People}
As = {GetVarsForField animal People}
Ss = {GetVarsForField souvenir People}
% ensure that these values are pairwise distinct
% (if this is done before populating the fields, the test simply
% waits until all the fields have been determined and executes)
{Distinct Ls}
{Distinct Fs}
{Distinct As}
{Distinct Ss}
% run the clues
{Clue1 Results}
{Clue2 Results}
{Clue3 Results}
{Clue4 Results}
{Clue5 Results}
{Clue6 Results}
% ensure that all fields have a value
{ForAll Ls proc {$ L} {IsALastName L} end}
{ForAll Fs proc {$ F} {IsAFood F} end}
{ForAll As proc {$ A} {IsAnAnimal A} end}
{ForAll Ss proc {$ S} {IsASouvenir S} end}
Results
end
RL
in
RL = {SearchAll DayAtZoo}
{Browse {Length RL}}
{Browse RL}
end
