#| 

  XKCD knapsack/subset-sum puzzle in Racket/Rosette.
 
  http://xkcd.com/287/

  Some amount (or none) of each dish should be ordered to give a total of exact 15.05
  for prices: 2.15 2.75 3.35 3.55 4.2 5.8.

  Solution:

  xkcd
  (prices (215 275 335 355 420 580) total 1505)
  (7 0 0 0 0 0)
  (1 0 0 2 0 1)

  xkcd-float
  (prices (2.15 2.75 3.35 3.55 4.2 5.8) total 15.05)
  (1 0 0 2 0 1)
  (7 0 0 0 0 0)


  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Racket page: http://www.hakank.org/racket/

|#

#lang rosette

(provide (all-defined-out))
;;; (require racket/trace)
(require "rosette_utils.rkt")
(require rosette/solver/smt/z3)


(define (xkcd prices total)
  (show "prices" prices "total" total)
  ; Convert to integer
  (current-solver (z3 #:logic 'QF_FD))
  
  (define len (length prices))
  
  (define x (make-var-array-integer len 0 10))
  (assume (= total (scalar-product prices x)))
  
  (for ([sol (get-all-solutions x #:debug? #f)])
    (displayln sol))
  )


; Float version: price and total is real integer of adjusted integers
(define (xkcd-float prices total)
  (clear-vc!)
  (show "prices" prices "total" total)

  ; Cannot use QF_FD on floats...
  (current-solver (z3))
  
  ; Convert to integer
  (define len (length prices))
  
  (define x (make-var-array-integer len 0 10))
  (assume (= total (scalar-product prices x)))
  
  (for ([sol (get-all-solutions x #:debug? #f)])
    (displayln sol))
  )

(displayln "xkcd")
(xkcd '(215 275 335 355 420 580) 1505)

(displayln "\nxkcd-float")
(xkcd-float '(2.15 2.75 3.35 3.55 4.20 5.80) 15.05)