lif*_*nce 10 algorithm scheme racket
我从各种来源一起破解了几个代码片段,并在http://bit.ly/HWdUqK上创建了Wolfram博客文章的粗略实现 - 对于那些在数学上倾向的人来说,它非常有趣!
毫不奇怪,鉴于我仍然是Racket的新手,代码需要花费太多时间来计算结果(> 90分钟而不是作者的49秒)并且占用了大量内存.我怀疑这是关于定义(expListY)需要重做的全部内容.
虽然我有它在DrRacket的工作,我也有问题字节编译源,并且仍然在它的工作(错误消息:+: expects type <number> as 1st argument, given: #f; other arguments were: 1 -1)
有人想要提高性能和效率吗？我为无法理解的代码和缺乏更好的代码注释道歉.
PS:我应该直接在这里剪切和粘贴代码吗？
可能类似于soegaard的解决方案,除了这个解决方案滚动它自己的"解析器",所以它是自包含的.它在我的机器上产生了不到6秒的完整100年上市.这段代码使用了很多技巧,但它并不是真正以任何严肃的方式被称为"优化"的东西:我确信它可以通过一些记忆,关注最大化树共享等来加快速度.但是对于这么小的域名来说,这不值得努力...(同样的代码质量......)
BTW#1,不仅仅是解析,原始解决方案的使用eval不会让事情变得更快......对于这样的事情,通常最好手动编写"评估者".BTW#2,这并不意味着Racket比Mathematica更快 - 我确信该帖子中的解决方案也使得它也在研究冗余cpu周期,类似的解决方案会更快.
#lang racket
(define (tuples list n)
(let loop ([n n])
(if (zero? n)
'(())
(for*/list ([y (in-list (loop (sub1 n)))] [x (in-list list)])
(cons x y)))))
(define precedence
(let ([t (make-hasheq)])
(for ([ops '((#f) (+ -) (* /) (||))] [n (in-naturals)])
(for ([op ops]) (hash-set! t op n)))
t))
(define (do op x y)
(case op
[(+) (+ x y)] [(-) (- x y)] [(*) (* x y)] [(/) (/ x y)]
[(||) (+ (* 10 x) y)]))
(define (run ops nums)
(unless (= (add1 (length ops)) (length nums)) (error "poof"))
(let loop ([nums (cddr nums)]
[ops (cdr ops)]
[numstack (list (cadr nums) (car nums))]
[opstack (list (car ops))])
(if (and (null? ops) (null? opstack))
(car numstack)
(let ([op (and (pair? ops) (car ops))]
[topop (and (pair? opstack) (car opstack))])
(if (> (hash-ref precedence op)
(hash-ref precedence topop))
(loop (cdr nums)
(cdr ops)
(cons (car nums) numstack)
(cons op opstack))
(loop nums
ops
(cons (do topop (cadr numstack) (car numstack))
(cddr numstack))
(cdr opstack)))))))
(define (expr ops* nums*)
(define ops (map symbol->string ops*))
(define nums (map number->string nums*))
(string-append* (cons (car nums) (append-map list ops (cdr nums)))))
(define nums (for/list ([i (in-range 10 0 -1)]) i))
(define year1 2012)
(define nyears 100)
(define year2 (+ year1 nyears))
(define years (make-vector nyears '()))
(for ([ops (in-list (tuples '(+ - * / ||) 9))])
(define r (run ops nums))
(when (and (integer? r) (<= year1 r) (< r year2))
(vector-set! years (- r year1)
(cons ops (vector-ref years (- r year1))))))
(for ([solutions (in-vector years)] [year (in-range year1 year2)])
(if (pair? solutions)
(printf "~a = ~a~a\n"
year (expr (car solutions) nums)
(if (null? (cdr solutions))
""
(format " (~a more)" (length (cdr solutions)))))
(printf "~a: no combination!\n" year)))
以下是我的实施.我在你的笔记本电脑中调整并优化了一两件事,在我的笔记本电脑中完成需要大约35分钟(当然是一个改进!)我发现表达式的评估是真正的性能杀手 - 如果它不是为了调用程序to-expression,程序将在一分钟内完成.
我想在本地使用中缀表示法的编程语言中,评估速度会快得多,但在Scheme中,解析然后使用中缀表达式评估字符串的成本太高了.
也许有人可以指出合适的soegaard/infix包装替代品？或者,直接评估考虑运算符优先级的中缀表达式列表的方法,例如'(1 + 3 - 4 & 7)- 其中&代表数字连接并具有最高优先级(例如:) 4 & 7 = 47,其他算术运算符(+, -, *, /)遵循通常的优先级规则.
#lang at-exp racket
(require (planet soegaard/infix)
(planet soegaard/infix/parser))
(define (product lst1 lst2)
(for*/list ([x (in-list lst1)]
[y (in-list lst2)])
(cons x y)))
(define (tuples lst n)
(if (zero? n)
'(())
(product lst (tuples lst (sub1 n)))))
(define (riffle numbers ops)
(if (null? ops)
(list (car numbers))
(cons (car numbers)
(cons (car ops)
(riffle (cdr numbers)
(cdr ops))))))
(define (expression-string numbers optuple)
(apply string-append
(riffle numbers optuple)))
(define (to-expression exp-str)
(eval
(parse-expression
#'here (open-input-string exp-str))))
(define (make-all-combinations numbers ops)
(let loop ((opts (tuples ops (sub1 (length numbers))))
(acc '()))
(if (null? opts)
acc
(let ((exp-str (expression-string numbers (car opts))))
(loop (cdr opts)
(cons (cons exp-str (to-expression exp-str)) acc))))))
(define (show-n-expressions all-combinations years)
(for-each (lambda (year)
(for-each (lambda (comb)
(when (= (cdr comb) year)
(printf "~s ~a~n" year (car comb))))
all-combinations)
(printf "~n"))
years))
像这样使用它来复制原始博客文章中的结果:
(define numbers '("10" "9" "8" "7" "6" "5" "4" "3" "2" "1"))
(define ops '("" "+" "-" "*" "/"))
; beware: this takes around 35 minutes to finish in my laptop
(define all-combinations (make-all-combinations numbers ops))
(show-n-expressions all-combinations
(build-list 5 (lambda (n) (+ n 2012))))
更新:
我咆哮了Eli Barzilay的表情评估器并将其插入我的解决方案中,现在所有组合的预先计算都在大约5秒内完成!该show-n-expressions过程仍然需要一些工作来避免每次迭代整个组合列表,但这留给读者练习.重要的是,现在强制所有可能的表达组合的值非常快.
#lang racket
(define (tuples lst n)
(if (zero? n)
'(())
(for*/list ((y (in-list (tuples lst (sub1 n))))
(x (in-list lst)))
(cons x y))))
(define (riffle numbers ops)
(if (null? ops)
(list (car numbers))
(cons (car numbers)
(cons (car ops)
(riffle (cdr numbers)
(cdr ops))))))
(define (expression-string numbers optuple)
(string-append*
(map (lambda (x)
(cond ((eq? x '&) "")
((symbol? x) (symbol->string x))
((number? x) (number->string x))))
(riffle numbers optuple))))
(define eval-ops
(let ((precedence (make-hasheq
'((& . 3) (/ . 2) (* . 2)
(- . 1) (+ . 1) (#f . 0))))
(apply-op (lambda (op x y)
(case op
((+) (+ x y)) ((-) (- x y))
((*) (* x y)) ((/) (/ x y))
((&) (+ (* 10 x) y))))))
(lambda (nums ops)
(let loop ((nums (cddr nums))
(ops (cdr ops))
(numstack (list (cadr nums) (car nums)))
(opstack (list (car ops))))
(if (and (null? ops) (null? opstack))
(car numstack)
(let ((op (and (pair? ops) (car ops)))
(topop (and (pair? opstack) (car opstack))))
(if (> (hash-ref precedence op)
(hash-ref precedence topop))
(loop (cdr nums)
(cdr ops)
(cons (car nums) numstack)
(cons op opstack))
(loop nums
ops
(cons (apply-op topop (cadr numstack) (car numstack))
(cddr numstack))
(cdr opstack)))))))))
(define (make-all-combinations numbers ops)
(foldl (lambda (optuple tail)
(cons (cons (eval-ops numbers optuple) optuple) tail))
empty (tuples ops (sub1 (length numbers)))))
(define (show-n-expressions all-combinations numbers years)
(for-each (lambda (year)
(for-each (lambda (comb)
(when (= (car comb) year)
(printf "~s ~a~n"
year
(expression-string numbers (cdr comb)))))
all-combinations)
(printf "~n"))
years))
像这样使用它:
(define numbers '(10 9 8 7 6 5 4 3 2 1))
(define ops '(& + - * /))
; this is very fast now!
(define all-combinations (make-all-combinations numbers ops))
(show-n-expressions all-combinations numbers
(build-list 5 (lambda (n) (+ n 2012))))