-
-
Save lojic/d45437453ccc8bcba196 to your computer and use it in GitHub Desktop.
lunchbot program comparison
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#lang racket | |
;; lunchbot.rkt | |
;; | |
;; The lunchbot ranks restuarant locations by doing the following for a given set of users: | |
;; 1) Maximizing the sum of user ratings for a restaurant | |
;; 2) Minimizing the sum of visits | |
(define all-users '(brian duff fred jimmy john luke matthew michael nathaniel tom)) | |
(define restaurants '(chikfila chipotle dickeys mexican nwc pizza thai)) | |
; Edit present-users to match lunch goers for today | |
(define present-users '(brian duff fred jimmy john luke matthew michael nathaniel tom)) | |
; Edit lunch-history to reflect visit history | |
(define lunch-history | |
'(("2014-06-30" pizza (brian duff jimmy matthew nathaniel tom)) | |
("2014-06-15" thai (brian)) | |
("2014-06-09" thai (brian matthew nathaniel tom)) | |
("2014-06-02" pizza (brian jimmy john michael nathaniel tom)) | |
("2014-05-26" mexican (brian nathaniel)) | |
("2014-05-19" nwc (brian fred jimmy nathaniel tom)) | |
("2014-05-12" chipotle (brian fred jimmy michael nathaniel tom)) | |
("2014-05-05" thai (brian fred jimmy michael nathaniel tom)) | |
("2014-04-28" mexican (brian jimmy michael nathaniel tom)) | |
("2014-04-21" chikfila (fred jimmy nathaniel tom)) | |
("2014-04-14" pizza (brian fred jimmy michael nathaniel)) | |
("2014-04-07" mexican (brian jimmy michael tom)) | |
("2014-03-31" chipotle (fred nathaniel)) | |
("2014-03-24" nwc (brian fred jimmy michael nathaniel tom)) | |
("2014-03-17" mexican (brian duff fred jimmy michael nathaniel tom)) | |
("2014-03-10" pizza (brian jimmy nathaniel tom)) | |
("2014-03-03" mexican (brian john nathaniel tom)) | |
("2014-02-24" thai (brian jimmy michael nathaniel tom)) | |
("2014-02-17" pizza (brian nathaniel tom)) | |
("2014-02-10" mexican (brian fred jimmy luke tom)) | |
("2014-02-03" mexican (brian fred jimmy luke nathaniel tom)) | |
("2014-01-27" chipotle (brian fred jimmy nathaniel tom)) | |
("2014-01-20" pizza (brian luke nathaniel tom)) | |
("2014-01-13" thai (brian fred jimmy john michael nathaniel tom)) | |
("2014-01-06" mexican (brian fred jimmy nathaniel tom)) | |
("2013-12-30" pizza (brian jimmy nathaniel tom)) | |
("2013-12-23" dickeys (brian duff nathaniel tom)) | |
("2013-12-16" mexican (brian jimmy michael nathaniel tom)) | |
("2013-12-09" nwc (brian fred jimmy michael nathaniel tom)) | |
("2013-12-02" dickeys (brian fred jimmy john michael nathaniel tom)))) | |
;; --------------------------------------------------------------------------------------------------- | |
(define raw-ratings | |
'((chikfila | |
((brian 0.0) (duff 11.0) (fred 0.5) (jimmy 5.0) (matthew 0.5) (nathaniel 1.0) (tom 0.0))) | |
(chipotle | |
((brian 0.3) (duff 8.0) (fred 0.7) (jimmy 7.0) (matthew 1.0) (nathaniel 2.0) (tom 0.8))) | |
(dickeys | |
((brian 0.3) (duff 5.0) (fred 0.7) (jimmy 1.0) (matthew 0.0) (nathaniel 1.0) (tom 0.4))) | |
(mexican | |
((brian 1.5) (duff 10.0) (fred 1.0) (jimmy 10.0) (matthew 0.5) (nathaniel 2.0) (tom 0.6))) | |
(nwc | |
((brian 0.4) (duff 5.0) (fred 0.7) (jimmy 7.0) (matthew 0.0) (nathaniel 1.0) (tom 0.5))) | |
(pizza | |
((brian 0.9) (duff 12.0) (fred 0.7) (jimmy 10.0) (matthew 0.0) (nathaniel 2.0) (tom 0.7))) | |
(thai | |
((brian 0.9) (duff 11.0) (fred 0.8) (jimmy 5.0) (matthew 2.0) (nathaniel 2.0) (tom 0.8))))) | |
;; Return a list of (user rating) for each user in users. If a user is | |
;; not represented in ratings, assign a default rating of 1.0 | |
(define (filled-out users ratings) | |
(for/list ([user users]) | |
(or (assoc user ratings) (list user 1.0)))) | |
;; complete-ratings transforms raw-ratings by adding a default | |
;; (user 1.0) rating to restaurants that lack a rating from user | |
(define complete-ratings | |
(for/list ([entry raw-ratings]) | |
(match entry | |
[(list restaurant ratings) | |
(list restaurant (filled-out all-users ratings))]))) | |
;; user-sums is a #hash(user . sum) where sum is the sum of all the | |
;; user's ratings | |
(define user-sums | |
(let [(hsh (make-hash))] | |
(for ([pair (append-map second complete-ratings)]) | |
(match pair [(list user rating) | |
(hash-set! hsh user (+ rating (hash-ref hsh user 0.0)))])) | |
hsh)) | |
;; Normalize a (user rating) pair by dividing | |
;; the rating by the user's sum of ratings | |
(define (normalize sums pair) | |
(match pair [(list user rating) | |
(list user (/ rating (hash-ref sums user)))])) | |
;; Take the raw-ratings and normalize them so that: | |
;; 1) the sum of a user's ratings across all restaurants adds up to 1.0 | |
;; 2) each restaurant has a rating for all users | |
(define normalized-ratings | |
(for/list ([pair complete-ratings]) | |
(match pair [(list rest ratings) | |
(list rest (map (curry normalize user-sums) ratings))]))) | |
;; Return the list of (user rating) for a particular restaurant | |
(define (restaurant-ratings ratings rest) | |
(second (assoc rest ratings))) | |
;; Return a user's rating for a particular restaurant | |
(define (user-restaurant-rating user rest ratings) | |
(let [(rest-ratings (restaurant-ratings ratings rest))] | |
(second (assoc user rest-ratings)))) | |
;; Return #hash((user restaurant) . visit-count) | |
(define (summed-history history) | |
(foldl (λ (3tuple hsh) | |
(define rest (second 3tuple)) | |
(define users (third 3tuple)) | |
(foldl (λ (user hsh) | |
(hash-set hsh (list user rest) (+ 1 (hash-ref hsh (list user rest) 0)))) | |
hsh | |
users)) | |
(hash) | |
history)) | |
(define (rank-restaurants hist ratings users restaurants) | |
; Hash of visit counts for each (user restaurant) | |
(define user-counts (summed-history hist)) | |
(define (rank-user user rest user-counts) | |
(define rating-value (user-restaurant-rating user rest ratings)) | |
; Use a minimum of 2 for the count to weaken frequency weighting a little | |
(define count (+ 2 (hash-ref user-counts (list user rest) 0))) | |
(* (/ 1.0 count) rating-value 100.0)) | |
(define (rank rest user-counts users) | |
(if (empty? users) | |
0.0 | |
(+ (rank-user (car users) rest user-counts) | |
(rank rest user-counts (cdr users))))) | |
(for/list ([rest restaurants]) | |
(list rest (rank rest user-counts users)))) | |
(define raw-results | |
(rank-restaurants lunch-history normalized-ratings present-users restaurants)) | |
(module* main #f | |
(pretty-print (sort raw-results #:key second >))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{- | |
lunchbot.hs | |
The lunchbot ranks restuarant locations by doing the following for a given set of users: | |
1) Maximizing the sum of user ratings for a restaurant | |
2) Minimizing the sum of visits | |
-} | |
import Data.List | |
import qualified Data.Map as Map | |
import Data.Maybe | |
import Data.Time | |
import Data.Time.Clock | |
import Data.Time.Format | |
import System.Locale | |
data User = Brian | Duff | Fred | Jimmy | John | Luke | Matthew | Michael | | |
Nathaniel | Tom deriving (Eq, Ord, Show) | |
data Restaurant = Chik | Chipotle | Dickeys | Mexican | NWC | Pizza | Thai deriving (Eq,Ord,Show) | |
type History = (Day, Restaurant, [ User ]) | |
type UserRating = (User,Double) | |
type Rating = (Restaurant, [UserRating]) | |
type Rank = (Restaurant,Double) | |
users = [ Brian, Duff, Fred, Jimmy, John, Luke, Matthew, Michael, Nathaniel, Tom ] | |
restaurants = [ Chik , Chipotle , Dickeys , Mexican , NWC , Pizza , Thai ] | |
-- Edit presentUsers to match lunch goers for the day | |
presentUsers = [ Brian, Duff, Fred, Jimmy, John, Luke, Matthew, Michael, Nathaniel, Tom ] | |
-- Edit lunchHistory to reflect visit history | |
lunchHistory :: [History] | |
lunchHistory = [ (readTime defaultTimeLocale "%F" s, r, l) | (s, r, l) <- | |
[ | |
("2014-06-30", Pizza, [Brian, Duff, Jimmy, Matthew, Nathaniel, Tom]), | |
("2014-06-15", Thai, [Brian]), | |
("2014-06-09", Thai, [Brian, Nathaniel, Tom]), | |
("2014-06-02", Pizza, [Brian, Jimmy, John, Michael, Nathaniel, Tom]), | |
("2014-05-26", Mexican, [Brian, Nathaniel]), | |
("2014-05-19", NWC, [Brian, Fred, Jimmy, Nathaniel, Tom]), | |
("2014-05-12", Chipotle, [Brian, Fred, Jimmy, Michael, Nathaniel, Tom]), | |
("2014-05-05", Thai, [Brian, Fred, Jimmy, Michael, Nathaniel, Tom]), | |
("2014-04-28", Mexican, [Brian, Jimmy, Michael, Nathaniel, Tom]), | |
("2014-04-21", Chik, [Fred, Jimmy, Nathaniel, Tom]), | |
("2014-04-14", Pizza, [Brian, Fred, Jimmy, Michael, Nathaniel]), | |
("2014-04-07", Mexican, [Brian, Jimmy, Michael, Tom]), | |
("2014-03-31", Chipotle, [Fred, Nathaniel]), | |
("2014-03-24", NWC, [Brian, Fred, Jimmy, Michael, Nathaniel, Tom]), | |
("2014-03-17", Mexican, [Brian, Duff, Fred, Jimmy, Michael, Nathaniel, Tom]), | |
("2014-03-10", Pizza, [Brian, Jimmy, Nathaniel, Tom]), | |
("2014-03-03", Mexican, [Brian, John, Nathaniel, Tom]), | |
("2014-02-24", Thai, [Brian, Jimmy, Michael, Nathaniel, Tom]), | |
("2014-02-17", Pizza, [Brian, Nathaniel, Tom]), | |
("2014-02-10", Mexican, [Brian, Fred, Jimmy, Luke, Tom]), | |
("2014-02-03", Mexican, [Brian, Fred, Jimmy, Luke, Nathaniel, Tom]), | |
("2014-01-27", Chipotle, [Brian, Fred, Jimmy, Nathaniel, Tom]), | |
("2014-01-20", Pizza, [Brian, Luke, Nathaniel, Tom]), | |
("2014-01-13", Thai, [Brian, Fred, Jimmy, John, Michael, Nathaniel, Tom]), | |
("2014-01-06", Mexican, [Brian, Fred, Jimmy, Nathaniel, Tom]), | |
("2013-12-30", Pizza, [Brian, Jimmy, Nathaniel, Tom]), | |
("2013-12-23", Dickeys, [Brian, Duff, Nathaniel, Tom]), | |
("2013-12-16", Mexican, [Brian, Jimmy, Michael, Nathaniel, Tom]), | |
("2013-12-09", NWC, [Brian, Fred, Jimmy, Michael, Nathaniel, Tom]), | |
("2013-12-02", Dickeys, [Brian, Fred, Jimmy, John, Michael, Nathaniel, Tom]) | |
]] | |
rawRatings = [ | |
(Chik, [(Brian, 0.0), (Duff, 11.0), (Fred, 0.5), (Jimmy, 5.0), (Matthew, 0.5), (Nathaniel, 1.0), (Tom, 0.0)]), | |
(Chipotle, [(Brian, 0.3), (Duff, 8.0), (Fred, 0.7), (Jimmy, 7.0), (Matthew, 1.0), (Nathaniel, 2.0), (Tom, 0.8)]), | |
(Dickeys, [(Brian, 0.3), (Duff, 5.0), (Fred, 0.7), (Jimmy, 1.0), (Matthew, 0.0), (Nathaniel, 1.0), (Tom, 0.4)]), | |
(Mexican, [(Brian, 1.5), (Duff, 10.0), (Fred, 1.0), (Jimmy, 10.0), (Matthew, 0.5), (Nathaniel, 2.0), (Tom, 0.6)]), | |
(NWC, [(Brian, 0.4), (Duff, 5.0), (Fred, 0.7), (Jimmy, 7.0), (Matthew, 0.0), (Nathaniel, 1.0), (Tom, 0.5)]), | |
(Pizza, [(Brian, 0.9), (Duff, 12.0), (Fred, 0.7), (Jimmy, 10.0), (Matthew, 0.0), (Nathaniel, 2.0), (Tom, 0.7)]), | |
(Thai, [(Brian, 0.9), (Duff, 11.0), (Fred, 0.8), (Jimmy, 5.0), (Matthew, 2.0), (Nathaniel, 2.0), (Tom, 0.8)]) ] | |
-- completeRatings adds a default (User, 1.0) rating to | |
-- restaurants so each restaurant has a rating from every user | |
completeRatings = [ (rest, (filledOut ratings)) | (rest, ratings) <- rawRatings ] | |
where filledOut ratings = | |
[ (user, (fromMaybe 1.0 (Data.List.lookup user ratings))) | user <- users ] | |
-- Take the rawRatings and normalize them so that: | |
-- 1) the sum of a user's ratings across all restaurants adds up to 1.0 | |
-- 2) each restaurant has a rating for all users | |
normalizedRatings = [ (rest, (map normalize ratings)) | (rest, ratings) <- completeRatings ] | |
where | |
-- userSums is a Map of (User,sum) where sum is the sum of all the user's ratings | |
userSums = foldl addToUserSum Map.empty userRatings | |
where userRatings = concatMap snd completeRatings | |
addToUserSum map (k,v) = Map.insert k ((fromMaybe 0 (Map.lookup k map)) + v) map | |
normalize (user,rating) = (user, rating / fromMaybe 0.0 (Map.lookup user userSums)) | |
-- Return the list of (User, Rating) for a particular restaurant | |
restaurantRatings ratings rest = theValue (Data.List.lookup rest ratings) | |
where theValue Nothing = error "invalid restaurant" | |
theValue (Just a) = a | |
-- Return a user's rating for a particular restaurant | |
userRestaurantRating user rest ratings = theValue (Data.List.lookup user restRatings) | |
where restRatings = restaurantRatings ratings rest | |
theValue Nothing = error "invalid user" | |
theValue (Just a) = a | |
-- Return a list of counts for each (User,Restaurant) pair found in the history | |
summedHistory history = Map.toList (foldl addHistory Map.empty history) | |
where addHistory map (_, rest, users) = foldl addUser map users | |
where addUser map user = | |
Map.insert (user,rest) ((fromMaybe 0 (Map.lookup (user,rest) map)) + 1) map | |
rankRestaurants hist ratings users restaurants = | |
[ (rest, (rank rest userCounts users)) | rest <- restaurants ] | |
where userCounts = summedHistory hist -- [((User,Restaurant),count), ... ] | |
rank rest userCounts [] = 0.0 | |
rank rest userCounts (x:xs) = rankUser x rest userCounts + rank rest userCounts xs | |
rankUser user rest userCounts = (1.0 / count) * ratingValue * 100.0 -- 100 constant for prettier scores | |
-- Use a minimum of 2 for the count to weaken frequency weighting a little | |
where count = fromIntegral (2 + fromMaybe 0 (Data.List.lookup (user,rest) userCounts)) | |
ratingValue = userRestaurantRating user rest ratings | |
rawResults = rankRestaurants lunchHistory normalizedRatings presentUsers restaurants | |
main = do | |
print completeRatings | |
print " " | |
print (sortBy (\ a b -> compare (snd b) (snd a)) rawResults) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#| | |
lunchbot.rkt | |
The lunchbot ranks restuarant locations by doing the following for a given set of users: | |
1) Maximizing the sum of user ratings for a restaurant | |
2) Minimizing the sum of visits | |
|# | |
#lang racket | |
(define users '(brian duff fred jimmy john luke matthew michael nathaniel tom)) | |
(define restaurants '(chik chipotle dickeys mexican nwc pizza thai)) | |
; Edit presentUsers to match lunch goers for the day | |
(define presentUsers '(brian duff fred jimmy john luke matthew michael nathaniel tom)) | |
; Edit lunchHistory to reflect visit history | |
(define lunchHistory | |
'( ("2014-06-30" pizza (brian duff jimmy matthew nathaniel tom)) | |
("2014-06-15" thai (brian)) | |
("2014-06-09" thai (brian nathaniel tom)) | |
("2014-06-02" pizza (brian jimmy john michael nathaniel tom)) | |
("2014-05-26" mexican (brian nathaniel)) | |
("2014-05-19" nwc (brian fred jimmy nathaniel tom)) | |
("2014-05-12" chipotle (brian fred jimmy michael nathaniel tom)) | |
("2014-05-05" thai (brian fred jimmy michael nathaniel tom)) | |
("2014-04-28" mexican (brian jimmy michael nathaniel tom)) | |
("2014-04-21" chik (fred jimmy nathaniel tom)) | |
("2014-04-14" pizza (brian fred jimmy michael nathaniel)) | |
("2014-04-07" mexican (brian jimmy michael tom)) | |
("2014-03-31" chipotle (fred nathaniel)) | |
("2014-03-24" nwc (brian fred jimmy michael nathaniel tom)) | |
("2014-03-17" mexican (brian duff fred jimmy michael nathaniel tom)) | |
("2014-03-10" pizza (brian jimmy nathaniel tom)) | |
("2014-03-03" mexican (brian john nathaniel tom)) | |
("2014-02-24" thai (brian jimmy michael nathaniel tom)) | |
("2014-02-17" pizza (brian nathaniel tom)) | |
("2014-02-10" mexican (brian fred jimmy luke tom)) | |
("2014-02-03" mexican (brian fred jimmy luke nathaniel tom)) | |
("2014-01-27" chipotle (brian fred jimmy nathaniel tom)) | |
("2014-01-20" pizza (brian luke nathaniel tom)) | |
("2014-01-13" thai (brian fred jimmy john michael nathaniel tom)) | |
("2014-01-06" mexican (brian fred jimmy nathaniel tom)) | |
("2013-12-30" pizza (brian jimmy nathaniel tom)) | |
("2013-12-23" dickeys (brian duff nathaniel tom)) | |
("2013-12-16" mexican (brian jimmy michael nathaniel tom)) | |
("2013-12-09" nwc (brian fred jimmy michael nathaniel tom)) | |
("2013-12-02" dickeys (brian fred jimmy john michael nathaniel tom)))) | |
(define rawRatings | |
'((chik ((brian 0.0) (duff 11.0) (fred 0.5) (jimmy 5.0) (matthew 0.5) (nathaniel 1.0) (tom 0.0))) | |
(chipotle ((brian 0.3) (duff 8.0) (fred 0.7) (jimmy 7.0) (matthew 1.0) (nathaniel 2.0) (tom 0.8))) | |
(dickeys ((brian 0.3) (duff 5.0) (fred 0.7) (jimmy 1.0) (matthew 0.0) (nathaniel 1.0) (tom 0.4))) | |
(mexican ((brian 1.5) (duff 10.0) (fred 1.0) (jimmy 10.0) (matthew 0.5) (nathaniel 2.0) (tom 0.6))) | |
(nwc ((brian 0.4) (duff 5.0) (fred 0.7) (jimmy 7.0) (matthew 0.0) (nathaniel 1.0) (tom 0.5))) | |
(pizza ((brian 0.9) (duff 12.0) (fred 0.7) (jimmy 10.0) (matthew 0.0) (nathaniel 2.0) (tom 0.7))) | |
(thai ((brian 0.9) (duff 11.0) (fred 0.8) (jimmy 5.0) (matthew 2.0) (nathaniel 2.0) (tom 0.8))))) | |
;; completeRatings adds a default (User, 1.0) rating to | |
;; restaurants so each restaurant has a rating from every user | |
(define completeRatings | |
(local ((define (filledOut ratings) | |
(for/list ([user users]) (or (assoc user ratings) (list user 1.0))))) | |
(for/list ([entry rawRatings]) | |
(match entry [(list restaurant ratings) (list restaurant (filledOut ratings))])))) | |
;; Take the rawRatings and normalize them so that: | |
;; 1) the sum of a user's ratings across all restaurants adds up to 1.0 | |
;; 2) each restaurant has a rating for all users | |
(define normalizedRatings | |
(local | |
[; userSums is a #hash(user . sum) where sum is the sum of all the user's ratings | |
(define userSums | |
(let [(hsh (make-hash))] | |
(for ([pair (append-map second completeRatings)]) | |
(match pair [(list user rating) | |
(hash-set! hsh user (+ rating (hash-ref hsh user 0.0)))])) | |
hsh)) | |
(define (normalize pair) | |
(match pair [(list user rating) | |
(list user (/ rating (hash-ref userSums user 0.0)))]))] | |
(for/list ([pair completeRatings]) | |
(match pair [(list rest ratings) | |
(list rest (map normalize ratings))])))) | |
;; Return the list of (User, Rating) for a particular restaurant | |
(define (restaurantRatings ratings rest) | |
(second (assoc rest ratings))) | |
;; Return a user's rating for a particular restaurant | |
(define (userRestaurantRating user rest ratings) | |
(let [(restRatings (restaurantRatings ratings rest))] | |
(second (assoc user restRatings)))) | |
;; Return (User Restaurant) => VisitCount hash | |
(define (summedHistory history) | |
(foldl (lambda (3tuple hsh) | |
(let [(rest (second 3tuple)) (users (third 3tuple))] | |
(foldl (lambda (user hsh) | |
(hash-set hsh (list user rest) (+ 1 (hash-ref hsh (list user rest) 0)))) | |
hsh users))) | |
(hash) history)) | |
(define (rankRestaurants hist ratings users restaurants) | |
(local | |
[(define userCounts (summedHistory hist)) | |
(define (rankUser user rest userCounts) | |
(let [(ratingValue (userRestaurantRating user rest ratings)) | |
; Use a minimum of 2 for the count to weaken frequency weighting a little | |
(count (+ 2 (hash-ref userCounts (list user rest) 0)))] | |
(* (/ 1.0 count) ratingValue 100.0))) | |
(define (rank rest userCounts users) | |
(if (empty? users) | |
0.0 | |
(+ (rankUser (car users) rest userCounts) | |
(rank rest userCounts (cdr users)))))] | |
(for/list ([rest restaurants]) | |
(list rest (rank rest userCounts users))))) | |
(define rawResults (rankRestaurants lunchHistory normalizedRatings presentUsers restaurants)) | |
(pretty-print (sort rawResults #:key second >)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment