Courses/CS 460/Fall 2005/Homework/Cynthia York/Oct 29

From CSWiki

[edit] The Band

• Presented this in class
• The Band Puzzle creates a bandMate record with an element for each given name of the group. These elements have property/value pairs of instrument make, instrument type, magazine and surname. It then assigns values to each property based on the following clues:

1. Steve wasn't the sound engineer. One of the women enjoyed EQ magazine.
2. Angie and Steve didn't like Recording magazine. The bass player used Ibanez equipment.
3. Mr. Magnus didn't use Mackie equipment. Mark's last name wasn't Hydal and he didn't play keyboard.
4. The sound engineer, whose last name wasn't Engel, enjoyed reading Mix magazine. The person who used Yamaha drums wasn't Robert, but their last name is Hydal.
5. The five band members (in no particular order) were: Mark Scott, the female bass player, the person who read Musician, the one who used Peavey equipment, and Robert.
6. Shelley's last name was not Hydal or McArthur and she didn't use Roland equipment. Mackie only developed equipment for live sound and recording NOT musical instruments.
7. Steve McArthur was the guitarist.

   % TheBand
   
   % UTILITIES
   declare
      % Every member of Xs has a value from Values.
      % Instantiates those that don't.
      proc {AllInstantiated Xs Values}
         {ForAll Xs proc {$ X} {IsIn X Values} end}
      end
      
      proc {IsIn ?X Xs} {Append _ X|_ Xs} end
      
      proc {Append ?Xs ?Ys ?Zs}
         choice
            Xs = nil 
            Ys = Zs
         [] X Xr in
            Xs = X | Xr
            Zs = X | {Append Xr Ys}
         end
      end
      
      % Creates a list of the values for Field in the elements
      % of Elts. Assumes Elts is a homgeneous list whose 
      % members are records with a field named Field.
      fun {GetFields Field Elts}
         {Map Elts fun {$ Elt} Elt.Field end}
      end
      
      % Returns the first index of X in Xs.  X and Xs must be
      % instantiated or will suspend until they are.
      % Fails if X is not in Xs.
      fun {IndexOf X Xs}
         fun {IndexOf3 X Xs N}
            case Xs of
               nil then fail
            [] Y | Rest then
               if X == Y then N else {IndexOf3 X Rest N+1} end
            end
         end
      in
        {IndexOf3 X Xs 1}
      end
      
      proc {IsAnElt ?X Elts} {IsIn X {Record.toList Elts}} end
      
   % CONTRAINTS
      % Generate thread bombs that ensure that all the members
      % of List are distinct.
      proc {AllDistinct List}
         L = {Length List} in
         for I in 1; I =< L-1; I+1 do
            for J in I+1; J =< L; J+1 do
               {NotEqual {Nth List I} {Nth List J}}
            end
         end
      end
     
      % Plant a thread bomb that goes off if X and Y become
      % instantiated to the same value.
      proc {NotEqual X Y} thread X == Y = false end end
      
      % A thread bomb that ensures that X1 precedes X2 in Xs. 
      proc {Precedes ?X1 ?X2 Xs}
         thread {IndexOf X1 Xs} < {IndexOf X2 Xs} = true end
      end
      
   % PROPAGATOR UTILITIES
      % If the fields common to R1 and R2 are all instantiated, returns 
      % true/false depending on whether they are all equal (==).
      % Suspends until fields become instantiated.
      fun {Match R1 R2}
         {Record.all
          {Record.zip R1 R2 fun {$ A B} A == B end}
          fun {$ X} X == true end}
      end
      
      % If {Match Condition R} then {UnifyRecs Result R}.
      % Does this in a thread to avoid blocking the main thread.
      % Also acts as a constraint in case the unification fails.
      proc {Propagate Condition Result R}
         thread if {Match Condition R} then {UnifyRecs Result R} end end    
      end
      
      % Propagates Condition -> Result to all the fields in the record Rec.
      % Each field is done in its own thread.  See Propagate.
      proc {PropagateAll Condition Result Rec}
         {Record.forAll Rec proc {$ R} {Propagate Condition Result R} end}
      end
      
      % Unifies the values of the fields common to R1 and R2
      proc {UnifyRecs R1 R2}
         {Record.zip R1 R2 fun {$ A B} A = B end _}
      end
   
   % PROBLEM SPECIFIC
   local
      Surnames  = ['Engel' 'Hydal' 'Magnus' 'McArthur' 'Scott']
      InstMakes = ['Ibanez' 'Mackie' 'Peavey' 'Roland' 'Yamaha']
      InstTypes = [bass drums guitar keyboard sound]
      Magazines = ['EQ' 'Home Recording' 'Mix' 'Musician' 'Recording']
   
      % Had to add the following property types to negate a property 
      % value when no specific record was known
      
      % Name is a surname
      proc {IsASurname ?Name} {IsIn Name Surnames} end
      
      % Make is an instrument make
      proc {IsAnInstMake ?Make} {IsIn Make InstMakes} end
      
      % Type is an instrument type
      proc {IsAnInstType ?Type} {IsIn Type InstTypes} end
      
      % Mag is a magazine
      proc {IsAMagazine ?Mag} {IsIn Mag Magazines} end
   
      proc {Clue1 Elts}
         % Steve wasn't the sound engineer
         {NotEqual Elts.'Steve'.instType sound}
   
         % One woman enjoyed EQ magazine
         choice Elts.'Angie'.magazine = 'EQ'
         [] Elts.'Shelley'.magazine = 'EQ'
         end
      end
   
      proc {Clue2 Elts}
         % Angie & Steve didn't like Recording magazine
         {NotEqual Elts.'Angie'.magazine 'Recording'}
         {NotEqual Elts.'Steve'.magazine 'Recording'}
         
         % the bass player used Ibanez equipment
         {PropagateAll properties(instMake:'Ibanez') properties(instType:bass)
          Elts}
      end
   
      proc {Clue3 Elts}
         Name
      in
         % Mr. Magnus didn't use Mackie equipment
         {PropagateAll properties(instMake:'Mackie') properties(surname:Name)
          Elts}
         {IsASurname Name}
         Name == 'Magnus' = false
         {NotEqual Elts.'Angie'.surname 'Magnus'}
         {NotEqual Elts.'Shelley'.surname 'Magnus'}
   
         % Mark's last name wasn't Hydal and he didn't play keyboard
         {NotEqual Elts.'Mark'.surname 'Hydal'}
         {NotEqual Elts.'Mark'.instType keyboard}
      end
   
      proc {Clue4 Elts}
         Surname
      in
         % The sound engineer, whose last name wasn't Engel, enjoyed
         % reading Mix magazine
         {PropagateAll properties(instType:sound) properties(magazine:'Mix')
          Elts}
         {PropagateAll properties(instType:sound) properties(surname:Surname)
          Elts}
         {IsASurname Surname}
         Surname == 'Engel' = false
   
         % The person who used Yamaha drums wasn't Robert, but their
         % last name is Hydal
         {PropagateAll properties(surname:'Hydal')
          properties(instMake:'Yamaha') Elts}
         {PropagateAll properties(surname:'Hydal') properties(instType:drums)
          Elts}
         {NotEqual Elts.'Robert'.surname 'Hydal'}
      end
   
      proc {Clue5 Elts}
         % The five band members (in no particular order) were:
         % Mark Scott,
         Elts.'Mark'.surname = 'Scott'
         {NotEqual Elts.'Mark'.instType bass}
         {NotEqual Elts.'Mark'.magazine 'Musician'}
         {NotEqual Elts.'Mark'.instMake 'Peavey'}
         
         %the female bass player,
         %the person who reads Musician,
         %the one who used Peavey equipment
         choice Elts.'Angie'.instType = bass
         [] Elts.'Angie'.magazine = 'Musician'
         [] Elts.'Angie'.instMake = 'Peavey'
         end
   
         choice Elts.'Shelley'.instType = bass
         [] Elts.'Shelley'.magazine = 'Musician'
         [] Elts.'Shelley'.instMake = 'Peavey'
         end
   
         choice Elts.'Steve'.magazine = 'Musician'
         [] Elts.'Steve'.instMake = 'Peavey'
         end 
   
         % and Robert
         {NotEqual Elts.'Robert'.instType bass}
         {NotEqual Elts.'Robert'.magazine 'Musician'}
         {NotEqual Elts.'Robert'.instMake 'Peavey'}
      end
   
      proc {Clue6 Elts}
         % Shelley's last name was not Hydal or McArthur and she didn't
         % use Roland equipment.
         {NotEqual Elts.'Shelley'.surname 'Hydal'}
         {NotEqual Elts.'Shelley'.surname 'McArthur'}
         {NotEqual Elts.'Shelley'.instMake 'Roland'}
   
         % Mackie only developed equipment for live sound and recording
         % NOT musical instruments
         {PropagateAll properties(instType:sound) properties(instMake:'Mackie')
          Elts}
      end
   
      proc {Clue7 Elts}
         % Steve McArthur was the guitarist.
         Elts.'Steve'.surname = 'McArthur'
         Elts.'Steve'.instType = guitar
      end
      
      fun {TheBand}
         Elts = {MakeRecord bandMates ['Angie' 'Mark' 'Robert' 'Shelley' 'Steve']}
         Sn
         IM
         IT
         Mg
         BandMates = {Record.toList Elts}
      in
         % Create property records for each band member
         {Record.forAll
          Elts proc {$ M} M =
   	       {Record.make properties [surname instMake instType magazine]}
   	    end}
         
         % Get the lists of property variables.
         % Constrain them to be distinct.
         Sn = {GetFields surname BandMates}
         {AllDistinct Sn}
         IM = {GetFields instMake BandMates}
         {AllDistinct IM}
         IT = {GetFields instType BandMates}
         {AllDistinct IT}
         Mg = {GetFields magazine BandMates}
         {AllDistinct Mg}
   
         % Run the clues
         {Clue1 Elts}
         {Clue2 Elts}
         {Clue3 Elts}
         {Clue4 Elts}
         {Clue5 Elts}
         {Clue6 Elts}
         {Clue7 Elts}
         
         % Ensure that every property has a value.
         {AllInstantiated IM InstMakes}
         {AllInstantiated IT InstTypes}
         {AllInstantiated Mg Magazines}
         {AllInstantiated Sn Surnames}
   
         % Return Elts as the answer
         Elts
      end
   in
      {Browse {SearchAll TheBand}}
   end

   [edit] Zoo Feeding Time

   • Zookeeper George was in charge of feeding all of the animals in the morning. He had a regular schedule that he followed every day. Can you figure it out from the clues?
   1. Feeding times are 6:30, 6:45, 7:00, 7:15 and 7:30.
   2. The giraffes were fed before the zebras but after the monkeys.
   3. The bears were fed 15 minutes after the monkeys.
   4. The lions were fed after the zebras.

      %ZooFeedingTime
      
      % UTILITIES
      declare
         % Every member of Xs has a value from Values.
         % Instantiates those that don't.
         proc {AllInstantiated Xs Values}
            {ForAll Xs proc {$ X} {IsIn X Values} end}
         end
         
         proc {IsIn ?X Xs} {Append _ X|_ Xs} end
         
         proc {Append ?Xs ?Ys ?Zs}
            choice
               Xs = nil 
               Ys = Zs
            [] X Xr in
               Xs = X | Xr
               Zs = X | {Append Xr Ys}
            end
         end
         
         % Creates a list of the values for Field in the elements
         % of Elts. Assumes Elts is a homgeneous list whose 
         % members are records with a field named Field.
         fun {GetFields Field Elts}
            {Map Elts fun {$ Elt} Elt.Field end}
         end
         
         % Returns the first index of X in Xs.  X and Xs must be
         % instantiated or will suspend until they are.
         % Fails if X is not in Xs.
         fun {IndexOf X Xs}
            fun {IndexOf3 X Xs N}
               case Xs of
                  nil then fail
               [] Y | Rest then
                  if X == Y then N else {IndexOf3 X Rest N+1} end
               end
            end
         in
           {IndexOf3 X Xs 1}
         end
         
         proc {IsAnElt ?X Elts} {IsIn X {Record.toList Elts}} end
         
      % CONTRAINTS
         % Generate thread bombs that ensure that all the members
         % of List are distinct.
         proc {AllDistinct List}
            L = {Length List} in
            for I in 1; I =< L-1; I+1 do
               for J in I+1; J =< L; J+1 do
                  {NotEqual {Nth List I} {Nth List J}}
               end
            end
         end
        
         % Plant a thread bomb that goes off if X and Y become
         % instantiated to the same value.
         proc {NotEqual X Y} thread X == Y = false end end
         
         % A thread bomb that ensures that X1 precedes X2 in Xs. 
         proc {Precedes ?X1 ?X2 Xs}
            thread {IndexOf X1 Xs} < {IndexOf X2 Xs} = true end
         end
      
         % Add two Follows procs
         % A thread bomb that ensures that X1 follows X2 in Xs. 
         proc {Follows ?X1 ?X2 Xs}
            thread {IndexOf X1 Xs} > {IndexOf X2 Xs} = true end
         end
         
         % A thread bomb that ensures that X1 follows X2 in Xs. 
         proc {ImmediatelyFollows ?X1 ?X2 Xs}
            thread {IndexOf X1 Xs} == {IndexOf X2 Xs} + 1  = true end
         end
         
      % PROPAGATOR UTILITIES
         % If the fields common to R1 and R2 are all instantiated, returns 
         % true/false depending on whether they are all equal (==).
         % Suspends until fields become instantiated.
         fun {Match R1 R2}
            {Record.all
             {Record.zip R1 R2 fun {$ A B} A == B end}
             fun {$ X} X == true end}
         end
         
         % If {Match Condition R} then {UnifyRecs Result R}.
         % Does this in a thread to avoid blocking the main thread.
         % Also acts as a constraint in case the unification fails.
         proc {Propagate Condition Result R}
            thread if {Match Condition R} then {UnifyRecs Result R} end end    
         end
         
         % Propagates Condition -> Result to all the fields in the record Rec.
         % Each field is done in its own thread.  See Propagate.
         proc {PropagateAll Condition Result Rec}
            {Record.forAll Rec proc {$ R} {Propagate Condition Result R} end}
         end
         
         % Unifies the values of the fields common to R1 and R2
         proc {UnifyRecs R1 R2}
            {Record.zip R1 R2 fun {$ A B} A = B end _}
         end
      
      % PROBLEM SPECIFIC
         local
            Times = ['6:30' '6:45' '7:00' '7:15' '7:30']
      
         proc {Clue1 Elts}
            Time
         in
            %The giraffes were fed
            Elts.giraffes.time = Time
            %before the zebras
            {Precedes Time Elts.zebras.time Times}
            %but after the monkeys.
            {Follows Time Elts.monkeys.time Times}
         end
      
         proc {Clue2 Elts}
            Time
         in
            %The bears were fed 
            Elts.bears.time = Time
            %15 minutes after the monkeys.
            {ImmediatelyFollows Time Elts.monkeys.time Times}
         end
      
         proc {Clue3 Elts}
            Time
         in
            %The lions were fed
            Elts.lions.time = Time
         
            %after the zebras. 
            {Follows Time Elts.zebras.time Times}
         end
         
         fun {ZooFeedingTime}
            Elts = {MakeRecord animals [bears giraffs lions monkeys zebras] }
            {Browse 'ZooFeedingTime-Elts:'#Elts}
            Tm
            Animals = {Record.toList Elts}
         in
            % Create property records for each animal
            {Record.forAll
             Elts proc {$ A} A =
      	       {Record.make properties [time]}
      	    end}
            {Browse 'ZooFeedingTime-Elts:'#Elts}
            
            % Get the list of property variables.
            % Constrain them to be distinct.
            Tm = {GetFields times Animals}
            {AllDistinct Tm}
            {Browse 'ZooFeedingTime-Tm:'#Tm}
      
            % Run the clues
            {Clue1 Elts}
            %{Clue2 Elts}
            %{Clue3 Elts}
            
            % Ensure that every property has a value.
            {AllInstantiated Tm Animals}
      
            % Return Elts as the answer
            Elts
         end
      in
         {Browse {SearchAll ZooFeedingTime}}
      end