fork download
copy 
  1. ; stock prices
  2.  
  3. (define (take n xs)
  4.   (let loop ((n n) (xs xs) (ys '()))
  5.     (if (or (zero? n) (null? xs))
  6.         (reverse ys)
  7.         (loop (- n 1) (cdr xs)
  8.               (cons (car xs) ys)))))
  9.  
  10. (define (range . args)
  11.   (case (length args)
  12.     ((1) (range 0 (car args) (if (negative? (car args)) -1 1)))
  13.     ((2) (range (car args) (cadr args) (if (< (car args) (cadr args)) 1 -1)))
  14.     ((3) (let ((le? (if (negative? (caddr args)) >= <=)))
  15.            (let loop ((x(car args)) (xs '()))
  16.              (if (le? (cadr args) x)
  17.                  (reverse xs)
  18.                  (loop (+ x (caddr args)) (cons x xs))))))
  19.     (else (error 'range "unrecognized arguments"))))
  20.  
  21. (define sort #f)
  22. (define merge #f)
  23. (let ()
  24.   (define dosort
  25.     (lambda (pred? ls n)
  26.       (if (= n 1)
  27.           (list (car ls))
  28.           (let ((i (quotient n 2)))
  29.             (domerge pred?
  30.                      (dosort pred? ls i)
  31.                      (dosort pred? (list-tail ls i) (- n i)))))))
  32.   (define domerge
  33.     (lambda (pred? l1 l2)
  34.       (cond
  35.         ((null? l1) l2)
  36.         ((null? l2) l1)
  37.         ((pred? (car l2) (car l1))
  38.          (cons (car l2) (domerge pred? l1 (cdr l2))))
  39.         (else (cons (car l1) (domerge pred? (cdr l1) l2))))))
  40.   (set! sort
  41.     (lambda (pred? l)
  42.       (if (null? l) l (dosort pred? l (length l)))))
  43.   (set! merge
  44.     (lambda (pred? l1 l2)
  45.       (domerge pred? l1 l2))))
  46.  
  47. (define (shuffle x)
  48.   (do ((v (list->vector x)) (n (length x) (- n 1)))
  49.       ((zero? n) (vector->list v))
  50.     (let* ((r (randint n)) (t (vector-ref v r)))
  51.       (vector-set! v r (vector-ref v (- n 1)))
  52.       (vector-set! v (- n 1) t))))
  53.  
  54. (define rand #f)
  55. (define randint #f)
  56. (let ((two31 #x80000000) (a (make-vector 56 -1)) (fptr #f))
  57.   (define (mod-diff x y) (modulo (- x y) two31)) ; generic version
  58.   ; (define (mod-diff x y) (logand (- x y) #x7FFFFFFF)) ; fast version
  59.   (define (flip-cycle)
  60.     (do ((ii 1 (+ ii 1)) (jj 32 (+ jj 1))) ((< 55 jj))
  61.       (vector-set! a ii (mod-diff (vector-ref a ii) (vector-ref a jj))))
  62.     (do ((ii 25 (+ ii 1)) (jj 1 (+ jj 1))) ((< 55 ii))
  63.       (vector-set! a ii (mod-diff (vector-ref a ii) (vector-ref a jj))))
  64.     (set! fptr 54) (vector-ref a 55))
  65.   (define (init-rand seed)
  66.     (let* ((seed (mod-diff seed 0)) (prev seed) (next 1))
  67.       (vector-set! a 55 prev)
  68.       (do ((i 21 (modulo (+ i 21) 55))) ((zero? i))
  69.         (vector-set! a i next) (set! next (mod-diff prev next))
  70.         (set! seed (+ (quotient seed 2) (if (odd? seed) #x40000000 0)))
  71.         (set! next (mod-diff next seed)) (set! prev (vector-ref a i)))
  72.       (flip-cycle) (flip-cycle) (flip-cycle) (flip-cycle) (flip-cycle)))
  73.   (define (next-rand)
  74.     (if (negative? (vector-ref a fptr)) (flip-cycle)
  75.       (let ((next (vector-ref a fptr))) (set! fptr (- fptr 1)) next)))
  76.   (define (unif-rand m)
  77.     (let ((t (- two31 (modulo two31 m))))
  78.       (let loop ((r (next-rand)))
  79.         (if (<= t r) (loop (next-rand)) (modulo r m)))))
  80.   (init-rand 19380110) ; happy birthday donald e knuth
  81.   (set! rand (lambda seed
  82.     (cond ((null? seed) (/ (next-rand) two31))
  83.           ((eq? (car seed) 'get) (cons fptr (vector->list a)))
  84.           ((eq? (car seed) 'set) (set! fptr (caadr seed))
  85.                                  (set! a (list->vector (cdadr seed))))
  86.           (else (/ (init-rand (modulo (numerator
  87.                   (inexact->exact (car seed))) two31)) two31)))))
  88.   (set! randint (lambda args
  89.     (cond ((null? (cdr args))
  90.             (if (< (car args) two31) (unif-rand (car args))
  91.               (floor (* (next-rand) (car args)))))
  92.           ((< (car args) (cadr args))
  93.             (let ((span (- (cadr args) (car args))))
  94.               (+ (car args)
  95.                  (if (< span two31) (unif-rand span)
  96.                    (floor (* (next-rand) span))))))
  97.           (else (let ((span (- (car args) (cadr args))))
  98.                   (- (car args)
  99.                      (if (< span two31) (unif-rand span)
  100.                        (floor (* (next-rand) span))))))))))
  101.  
  102. (define-syntax assert
  103.   (syntax-rules ()
  104.     ((assert expr result)
  105.       (if (not (equal? expr result))
  106.           (for-each display `(
  107.             #\newline "failed assertion:" #\newline
  108.             expr #\newline "expected: " ,result
  109.             #\newline "returned: " ,expr #\newline))))))
  110.  
  111. (define (buy-sell-quadratic xs)
  112.   (let ((buy 0) (sell 0))
  113.     (do ((xs xs (cdr xs))) ((null? xs) (values buy sell))
  114.       (do ((ys (cdr xs) (cdr ys))) ((null? ys))
  115.         (let ((diff (- (car ys) (car xs))))
  116.           (when (< (- sell buy) diff)
  117.             (set! buy (car xs)) (set! sell (car ys))))))))
  118.  
  119. (define (buy-sell-linear xs)
  120.   (let ((buy (car xs)) (profit 0))
  121.     (do ((xs (cdr xs) (cdr xs)))
  122.         ((null? xs) (values buy (+ profit buy)))
  123.       (set! buy (min (car xs) buy))
  124.       (set! profit (max (- (car xs) buy) profit)))))
  125.  
  126. (define xs '(100 80 70 65 95 120 150 75 95 100 110 120 90 80 85 90))
  127.  
  128. (call-with-values
  129.   (lambda () (buy-sell-quadratic xs))
  130.   (lambda (buy sell)
  131.     (display buy) (newline)
  132.     (display sell) (newline)))
  133.  
  134. (newline)
  135.  
  136. (call-with-values
  137.   (lambda () (buy-sell-linear xs))
  138.   (lambda (buy sell)
  139.     (display buy) (newline)
  140.     (display sell) (newline)))
  141.  
  142. (newline)
  143.  
  144. (do ((k 100 (- k 1))) ((zero? k))
  145.   (let ((xs (take 20 (shuffle (range 1000)))))
  146.     (assert 
  147.       (call-with-values
  148.         (lambda () (buy-sell-linear xs))
  149.         (lambda (buy sell) (- sell buy)))
  150.       (call-with-values
  151.         (lambda () (buy-sell-quadratic xs))
  152.         (lambda (buy sell) (- sell buy))))))
Success #stdin #stdout 5.14s 45552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
65
150

65
150
https://ideone.com/R8ukSG
language:
Scheme (guile 2.2.4)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!