XKCD #287 Comic Solution

In today’s xkcd comic the joke was about using the knapsack problem at a restaurant. Just for fun, I solved it in scheme.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

(define (make-appetizer name cost)
  (cons name cost))
(define (name app)
  (car app))
(define (cost app)
  (cdr app))
 
(define delta 0.000001)
(define (float-equal? x y)
  (< (abs (- x y)) delta))
 
(define appetizers
  (list
   (make-appetizer "mixed fruit" 2.15)
   (make-appetizer "french fries" 2.75)
   (make-appetizer "side salad" 3.35)
   (make-appetizer "hot wings" 3.55)
   (make-appetizer "mozzarella sticks" 4.20)
   (make-appetizer "sampler plate" 5.80)))
 
(define (append-unless-null set elem)
  (if (null? set)
      '()
      (cons elem set)))
 
(define (appetizers-for-cost-n apps n)
  (if (null? apps)
      '()
      (cond ((float-equal? (cost (car apps)) n) (list (car apps)))
            ((> (cost (car apps)) n)
             (appetizers-for-cost-n (cdr apps) n))
            (else
             (append
              (map (lambda (x) (cons (car apps) x))
                   (appetizers-for-cost-n apps (- n (cost (car apps)))))
              (appetizers-for-cost-n (cdr apps) n))))))

Calling it with: (appetizers-for-cost-n appetizers 15.05)
Results in:

((("mixed fruit" . 2.15)
  ("mixed fruit" . 2.15)
  ("mixed fruit" . 2.15)
  ("mixed fruit" . 2.15)
  ("mixed fruit" . 2.15)
  ("mixed fruit" . 2.15)
  "mixed fruit"
  .
  2.15)
 (("mixed fruit" . 2.15)
  ("hot wings" . 3.55)
  ("hot wings" . 3.55)
  "sampler plate"
  .
  5.8))

About this entry

You’re currently reading “XKCD #287 Comic Solution,” an entry on Overflow: Auto

Published:
07.09.07 / 3pm
Category:
Programming, Scheme