http:^^www.cs.washington.edu^education^courses^415^prog3.solution.html

This data set contains WWW-pages collected from computer science departments of various universities

         (best_score (cdr list) (car (car list)))))
)

;"best_output" puts a cons cell with the score generated in best_score and its
; associated id# in a single element cons list with END_OF_LIST following it
; in order to make use of the print_cons_cell function.
  
(defun best_output (list)
  (format t "~&BEST SCORE~&")
  (print_cons_list (CONS (ASSOC (best_score list 0) list) '(END_OF_LIST)))
)

;==============================================================================
;
;  Familiarity and Simplification functions
;==============================================================================

; "match" takes an atom to be compared and searches through a list of features.
;  In practice it takes a subtree containing either the LS or RS of a known id
;  and an atom to be matched. It should return the score of the atom matched 
;  if there's a match and NIL if there is no match.

(defun match (sublist atom)
  (COND ((EQUAL sublist NIL) NIL)
        ((EQUAL atom (FIRST sublist)) (SECOND sublist))
        ((EQUAL 1 1) (match (cdr (cdr sublist)) atom)))
)

;"idchecker" compares one id to a single feature and determines whether or not
; there is a match.  If so, it returns a cons cell with 2 items: the id # and 
; familiarity score of the id. 

(defun idchecker (id atom)
  (COND ((NOT (EQUAL (match (car id) atom) NIL)) 
                     (CONS (FOURTH id) (THIRD id)))
        ((NOT (EQUAL (match (cadr id) atom) NIL)) 2)
        ((EQUAL 1 1) NIL))
)


; "fam" compares a list of features to each identity's features as it moves down
; through the list of identities.  When there is a match, it returns the 
; number and f-score of the identity, as generated in idchecker.

(defun fam (id p_features)
  (COND ((EQUAL p_features NIL) NIL)
        ((EQUAL (THIRD p_features) 3) NIL) 
        ((NOT (EQUAL (idchecker id (car p_features)) NIL))
                     (idchecker id (car p_features)))
        ((EQUAL (idchecker id (car p_features)) NIL) 
                     (fam id (cdr (cdr (cdr p_features))))))

)

; "familiarize" compares a given functions' list of features to a list of 
; identities.  Since fam prints out the values, this function simply 
; returns the id number and familiarity score generated in idchecker if a 
; match is found, and 'NO SOLUTION if there is no match.

(defun familiarization (idlist p_features)
  (COND ((EQUAL idlist NIL) 'END_OF_LIST)
        ((NOT (EQUAL (fam (car idlist) p_features) NIL)) 
               (LIST (fam (car idlist) p_features) 'END_OF_LIST))
        ((EQUAL 1 1) (familiarization (cdr idlist) p_features)))
)


;==============================================================================
;
;  Simplify 
;==============================================================================

;"simp_idchecker" compares one id to a single feature and determines whether or 
; not there is a match.  If so, it returns a list with the simplification score
; of that feature as well as the id # of the identity.  If no match, it returns
; NIL.

(defun simp_idchecker (id atom)
  (COND ((NOT (EQUAL (match (car id) atom) NIL)) 
                     (LIST (match (car id) atom) (THIRD id)))
        ((NOT (EQUAL (match (cadr id) atom) NIL)) 
                     (LIST (match (cadr id) atom) (THIRD id)))
        ((EQUAL 1 1) NIL))
)

;"simp_fam" compares a list of features to one identity's features as it moves 
; down through the list of identities.  When there is a match, it returns the 
; simplification score of that feature and id# of the identity as generated in 
; the simp_idchecker function.  Since we are only interested in matching to 
; features on the left side of the problem identity(stated in email on 
; applicability), we stop when we get to a feature with a location of 3, 
; meaning it is on the right side only.

(defun simp_fam (id p_features)
  (COND ((EQUAL p_features NIL) NIL)
        ((EQUAL (THIRD p_features) 3) NIL)
        ((NOT (EQUAL (simp_idchecker id (car p_features)) NIL))
                     (simp_idchecker id (car p_features)))
        ((EQUAL (simp_idchecker id (car p_features)) NIL) 
                     (simp_fam id (cdr (cdr (cdr p_features))))))

)

;"simp" recursively calls itself in order to compare a list of features to all
; of the id's in the idtree.  It uses "simp_fam" to check each id.  The function
; returns a list of cons cells containing a simplification score and id number
; for each id which is checked.
 
(defun simp (idlist p_features)
  (COND ((EQUAL idlist NIL) NIL)
        ((NOT (EQUAL (simp_fam (car idlist) p_features) NIL)) 
                     (CONS (simp_fam (car idlist) p_features) 
                           (simp (cdr idlist) p_features)))
        ((EQUAL (simp_fam (car idlist) p_features) NIL) 
                     (CONS (CONS 0 (THIRD (car idlist))) 
                           (simp (cdr idlist) p_features))))
) 

;"simplification" is the overall function for the simplification heuristic.  To
; prepare the list of cons cells(generated by simp) for the output functions, 
; an END_OF_LIST must be added after the last cons cell.

(defun simplification (idlist p_features)
  (APPEND (simp idlist p_features) '(END_OF_LIST))
)




;============================================================================
;
; EFFECTIVENESS
;

;"feature_match" compares one feature(atom) to all the features of a sublist.
; If it finds a match, it returns a 1.  Otherwise it returns 0.  The sublist,
; in practice, is either the left or right side of a known identity and the 
; feature is taken from the identity being proven.

(defun feature_match (sublist atom) 
  (COND ((NOT (EQUAL (match sublist atom) NIL)) 1)
        ((EQUAL 1 1) 0))
) 

;"match_both_idsides" compares a given feature to both the left and right side
; of a known identity.  It produces a list of 2 integers(1 or 0) which state 
; whether or not there is a match on the left or right side.

(defun match_both_idsides (id atom)
  (LIST (feature_match (FIRST id) atom) (feature_match (SECOND id) atom))
)

;"left_right_both" produces a 2 integer list based on whether or not a feature
; is in the left or right side of the identity being proven.  The lrb variable
; is drawn by the calling function from information stored in the to-be-proven
; identity's feature list.
  
(defun left_right_both (lrb)
  (COND ((EQUAL lrb 1) (LIST 1 0))
        ((EQUAL lrb 2) (LIST 1 1))
        ((EQUAL lrb 3) (LIST 0 1)))
)


;"match_one_feature_id" combines the information gained about the left and right
; sides of the 2 equations and forms a 4 integer list(2 sublists) with this 
; information

(defun match_one_feature_id (id p_features) 
  (LIST (match_both_idsides id (FIRST p_features)) 
        (left_right_both (THIRD p_features)))
) 

;"desirability" computes the desirability factor which is applicable to each
; 4 integer list generated in match_one_feature_id.

(defun desirability (list)
  (COND ((EQUAL list '((1 0) (1 0))) 4)
        ((EQUAL list '((1 0) (0 1))) 4)
        ((EQUAL list '((0 1) (1 0))) 4)
        ((EQUAL list '((0 1) (0 1))) 4)
        ((EQUAL list '((0 0) (1 0))) 0)
        ((EQUAL list '((0 0) (0 1))) 0)
        ((EQUAL list '((0 0) (1 1))) 0)
        ((EQUAL list '((1 1) (0 1))) 1)
        ((EQUAL list '((1 1) (1 0))) 1)
        ((EQUAL list '((1 0) (1 1))) 2)
        ((EQUAL list '((0 1) (1 1))) 2)
        ((EQUAL list '((1 1) (1 1))) 4))
)

;"score_for_feature" computes the score based on how many symbols are in the 
; feature and the desirability factor.  The function returns an integer which
; is the multiple of the two.

(defun score_for_feature (id p_features)
  (* (desirability (match_one_feature_id id p_features)) (SECOND p_features))
)

;"all_features_one_id" computes the sum of all the scores for features which
; may be applied to a given id.  This returns an integer which is the sum.

(defun all_features_one_id (id p_features)
  (COND ((EQUAL p_features NIL) 0)
        ((EQUAL 1 1) (+ (score_for_feature id p_features) 
                        (all_features_one_id id (cdr (cdr (cdr p_features)))))))
)
 

;"all_features_one_all_ids" generates a list of cons cells, each one with the 
; effectiveness score and it's corresponding id # - in that order.

(defun all_features_all_ids (idlist p_features)
  (COND ((EQUAL idlist NIL) NIL)
        ((EQUAL 1 1) (CONS (CONS (all_features_one_id (FIRST idlist) p_features)
                                 (THIRD (car idlist)))
                           (all_features_all_ids (cdr idlist) p_features))))
)

;"effectiveness" is the overall function for the simplification heuristic.  To
; prepare the list of cons cells(generated by all_features_all_ids) for the 
; output functions, an END_OF_LIST must be added after the last cons cell.

(defun effectiveness (idlist p_features)
  (APPEND (all_features_all_ids idlist p_features) '(END_OF_LIST))
)


;"demonstration" is used to show all the heuristics when used on a given
; identity list and to-be-proven identity.

(defun demonstration (idlist p_features)
  (format t "~&FAMILIARIZATION HEURISTIC~&")
  (print_output (familiarization idlist p_features))

  (format t "~&SIMPLIFICATION HEURISTIC~&")
  (print_output (simplification idlist p_features))
  (best_output (simplification idlist p_features))

  (format t "~&EFFECTIVENESS HEURISTIC~&")
  (print_output (effectiveness idlist p_features))
  (best_output (effectiveness idlist p_features))

)
<\pre>
<\body>