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

From CSWiki

Jump to: navigation, search

[edit] ArborDay

  • This program was presented in class
  • Arbor Day Planting Puzzle creates a TreePlanters record with surname and tree as properties. It then assigns a first name to each surname and tree based on the following clues:
  1. George, Mr. Clary and Mr. Becker (who got his tree from HomeTown Garden Center) all live within three blocks of one another.
  2. Mr. Clary planted neither the cedar tree or the maple tree.
  3. Harvey and Mr. Clary live next door to one another.
  4. The ash tree was not planted by neither John nor Ivan
  5. The maple tree was not the tree planted by George (who is not surnamed Delgado).
  6. Mr. Erichsen isn't the man who planted the ash tree.
  7. John, who purchased his tree at the Green Thumb Greenhouse, isn't the man who planted the sycamore. 
    % Arbor Day Planting Puzzle
local
   GivenName = ['George' 'Harvey' 'Ivan' 'John']
   Surname = ['Becker' 'Clary' 'Delgado' 'Erichsen']
   Tree = [ash cedar maple sycamore]

   % If Zs is not instantiated (or at least not bounded, then 
   % Xs and Ys should be or the number of solutions will grow 
   % without limit.
   proc {Append ?Xs ?Ys ?Zs}
      choice
	 Xs = nil
	 Ys = Zs
      [] Head XRest ZRest in
	 Xs = Head|XRest 
	 Zs = Head|ZRest
	 {Append XRest Ys ZRest}
      end
   end

   % Value is the value of field Property in the record TPs
   % Both Property and Value may be uninstantiated
   proc {IsAPropertyValue TPs ?Property ?Value}
      {IsAMember Property#Value {Record.toListInd TPs}}
   end

   % Name is a given name.  
   proc {IsAGivenName ?Name} {IsAMember Name GivenName} end

   % Name is a surname
   proc {IsASurname ?Name} {IsAMember Name Surname} end

   % Tree is a tree.
   proc {IsATree ?TreePlanted} {IsAMember TreePlanted Tree} end

   % Look at this neat definition for IsAMember/2.
   % X is a member of Xs.
   proc {IsAMember ?X Xs} {Append _ X|_ Xs} end

   proc {Clue1 TPs}
      % George, Mr. Clary & Mr. Becker (who got his tree from
      % HomeTown Garden Center) all live within three blocks of one
      % another
      FirstName1 FirstName2 in

      % Assign Mr. Becker & Mr. Clary unique first names that aren't
      % George
      {IsAGivenName FirstName1}
      {IsAGivenName FirstName2}
      FirstName1 == 'George' = false
      FirstName2 == 'George' = false
      FirstName1 == FirstName2 = false
      {IsAPropertyValue TPs 'Becker' FirstName1}
      {IsAPropertyValue TPs 'Clary' FirstName2}
   end

   proc {Clue2 TPs}
      % Mr. Clary planted neither a cedar or a maple
      FirstName1 FirstName2 in
      
      % Assign cedar and maple each a set of unique first names that
      % aren't the same as Mr. Clary's
      {IsAGivenName FirstName1}
      {IsAGivenName FirstName2}
      FirstName1 == TPs.'Clary' = false
      FirstName2 == TPs.'Clary'  = false
      FirstName1 == FirstName2 = false
      {IsAPropertyValue TPs cedar FirstName1}
      {IsAPropertyValue TPs maple FirstName2}
   end

   proc {Clue3 TPs}
      % Harvey & Mr. Clary live next door to one another
      
      % Mr. Clary received a set of potential first names in Clue1
      % we just need to make sure one of those names is not Harvey
      TPs.'Clary' == 'Harvey' = false
   end

   proc {Clue4 TPs}
      % An ash was planted by neither Ivan nor John
      FirstName in

      % Assign ash a set of unique first names that aren't Ivan or
      % John
      {IsAGivenName FirstName}
      FirstName == 'Ivan' = false
      FirstName == 'John' = false
      FirstName == TPs.cedar = false
      FirstName == TPs.maple = false
      {IsAPropertyValue TPs ash FirstName}
   end

   proc {Clue5 TPs}
      % George did not plant a maple & his last name is not Delgado
      FirstName in

      % maple acquired a set of first names in Clue2
      % make sure George is not one of them
      TPs.maple == 'George' = false
      
      % Assign Delgado a unique first name that is not George
      {IsAGivenName FirstName}
      FirstName == 'George' = false
      FirstName == TPs.'Becker' = false
      FirstName == TPs.'Clary' = false
      {IsAPropertyValue TPs 'Delgado' FirstName}
   end

   proc {Clue6 TPs}
      % Mr. Erichsen did not plant an ash.
      FirstName in

      % must first get unique potential first names for Mr. Erichsen
      {IsAGivenName FirstName}
      FirstName == TPs.'Becker' = false
      FirstName == TPs.'Clary' = false
      FirstName == TPs.'Delgado' = false
      {IsAPropertyValue TPs 'Erichsen' FirstName}

      % now I can assign ash some potential first names
      TPs.ash == TPs.'Erichsen' = false
   end

   proc {Clue7 TPs}
      % John purchased from Green Thumb Greenhouse & it wasn't a
      % sycamore
      FirstName in
      
      % Clue1 has Mr. Becker purchasing his tree from another store
      TPs.'Becker' == 'John' = false

      % now I can assign sycamore some potential first names
      {IsAGivenName FirstName}
      FirstName == 'John' = false
      FirstName == TPs.ash = false
      FirstName == TPs.cedar = false
      FirstName == TPs.maple = false
      {IsAPropertyValue TPs sycamore FirstName}
   end

   fun {ArborDay}
      Properties = {FoldR [Surname Tree] Append nil}
      TPs = {MakeRecord treePlanters Properties}
   in
      % To debug, comment out all the clues except the one 
      % you are working on and the ones that already work.
      {Clue1 TPs}
      {Clue2 TPs}
      {Clue3 TPs}
      {Clue4 TPs}
      {Clue5 TPs}
      {Clue6 TPs}
      {Clue7 TPs}
      TPs
   end
in
   {Browse {SearchAll ArborDay}}
end

    [edit] TheBand

    • The Band Mate Puzzle creates a bandMate record with givenName, surname, instrument, instMake and magazine as property value pairs. It then assigns a value for each property in each of 5 of these records representing a member of the band 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. 
      % The Band Mate Puzzle
local   
   proc {Append Xs Ys Zs}
      choice
	 Xs = nil Ys = Zs
      [] Xr X in
	 Xs = X | Xr
	 Zs = X | {Append Xr Ys}
      end
   end
   
   proc {IsABandMate Props Ms}
      {IsMember {BandMate Props} Ms}
   end
      
   proc {IsMember X Xs}
      H Tail in
      Xs = H | Tail
      choice H = X [] {IsMember X Tail} end
   end
   
   proc {MakeBandMate M}
      {Record.make bandMate [givenName surname instrument instMake magazine] M}
   end
   
   % BandMate M has properties Properties, which is a list 
   % of the form: [prop1#value1 prop2#value2 ...]
   proc {BandMate Properties M}
      {MakeBandMate M}
      {ForAll
       Properties
       % Apparently anonymous function parameters can be structures.
       proc {$ Property#Value} M.Property = Value end}
   end

   % Succeed if each of the BandMembers in Ms has property values
   % that no other BandMember has. Should really do this one property 
   % at a time. In this case all property values are distinct.
   proc {AllDistinct Ms}
      {FoldR
       Ms
       % Accumulate the values of all the properties. 
       % If any appear twice, fail.  (The nil's ensure failure.)
       fun {$ M OldPVs} 
          % {Record.toList N} returns a list of the values of the fields in record N.
          PVs = {Record.toList M} in
          % Partition the PVs into those that have and have not appeared
          % before, i.e., in OldPVs.
          % The final two arguments (nil and PVs) are what the input PVs are
          % partitioned into. In other words, all PVs fail the List.member test.
	  {List.partition PVs fun {$ PV} {List.member PV OldPVs} end nil PVs}
	  {Append PVs OldPVs}
       end
       nil
       _}
   end

   proc {TheBand Bm}
      % position is irrelevant for this puzzle.
      Bm = [{BandMate [givenName#'Angie']}
	    {BandMate [givenName#'Mark']}
	    {BandMate [givenName#'Robert']}
	    {BandMate [givenName#'Shelley']}
	    {BandMate [givenName#'Steve']}]
      choice 
	 {IsABandMate [givenName#'Angie' magazine#'EQ'] Bm} 
      [] {IsABandMate [givenName#'Shelley' magazine#'EQ'] Bm}
      end
      {IsABandMate [instrument#sound magazine#'Mix'] Bm}
      {IsABandMate [surname#'Hydal' instrument#drums instMake#'Yamaha'] Bm}
      {IsABandMate [givenName#'Mark' surname#'Scott' instrument#sound] Bm}
      {IsABandMate [givenName#'Steve' surname#'McArthur' instrument#guitar] Bm}
      {IsABandMate [instrument#sound instMake#'Mackie'] Bm}
      {IsABandMate [givenName#'Robert' surname#'Magnus' instrument#keyboard] Bm}
      {IsABandMate [givenName#'Shelley' surname#'Engel'] Bm}
      {IsABandMate [givenName#'Angie' surname#'Hydal'] Bm}
      {IsABandMate [givenName#'Shelley' instrument#bass instMake#'Ibanez'] Bm}
      {IsABandMate [givenName#'Steve' instMake#'Peavey'] Bm}
      {IsABandMate [givenName#'Robert' instMake#'Roland'] Bm}
      {IsABandMate [givenName#'Angie' magazine#'Musician'] Bm}
      {IsABandMate [givenName#'Steve' magazine#'Home Recording'] Bm}
      {IsABandMate [givenName#'Robert' magazine#'Recording'] Bm}
   end
in
   {Browse {SearchAll TheBand}}
end
Retrieved from "http://cs.calstatela.edu/wiki/index.php/Courses/CS_460/Fall_2005/Homework/Cynthia_York/Oct_22"
Personal tools