(load "load.scm")
The rats are quantum rats, so they can jump back their tracks. For
example, the fat rat explores the edge B->C and then the edge B->D.
This would require him to jump back to B from C, which it cannot
classically do since there isn't any edge C->B. Since both
breath-first and depth-first strategies will explore all nodes in a
connected graph, both rats, being quantum, will find all the food.
When the mole rat finds the food at D, it hasn't yet explored the
edges B->D or B->C, so the distance from the start to D appears to be
5. Later, when the rat explores the edge B->C, it relaxes the
distance to 2 (via the procedure graph:min-edges).
|#
The user merely calls (make-starting-lazy-node next-values starting-value),
providing:
(1) a function next-values that takes a node value and outputs a list
of the next node values
(2) the starting value
I will transform his next-values function into the function next that
takes a node and returns nodes (as opposed to merely values) , making
sure to always return the same structure for nodes that have the same
value (using equal?) by keeping the already created nodes in a hash
table.
|#
(define-record-type <graph-lazy-node>
(%make-lazy-node next value)
lazy-node?
(value lazy-node->value )
(next lazy-node->next))
(define (next-values->next next-values)
(let ((table (make-equal-hash-table)))
(define (next node)
(let ((value (lazy-node->value node)))
(hash-table/lookup
table
value
(lambda (d) #t)
(lambda () (hash-table/put! table value node)))
(map (lambda (next-value)
(hash-table/lookup
table
next-value
(lambda (next-node) next-node)
(lambda ()
(let ((next-node (%make-lazy-node next next-value)))
(hash-table/put! table next-value next-node)
next-node))))
(next-values value))))
next))
(define (node->out-edges node)
(let ((next (lazy-node->next node)))
(map (lambda (next-node)
(%make-edge node next-node))
(next node))))
(define (make-starting-lazy-node next-values starting-value)
(let ((next (next-values->next next-values)))
(%make-lazy-node next starting-value)))
(define zero-in-number-line
(make-starting-lazy-node (lambda (n)
(if (= n 0)
(list 1)
(list (- n 1) (+ n 1))))
0))
(define (first-target edges)
(edge->target (car edges)))
(define (node->next-first-node node)
(first-target (node->out-edges node)))
(lazy-node->value
(node->next-first-node zero-in-number-line))
(lazy-node->value
(node->next-first-node
(node->next-first-node
zero-in-number-line)))
(lazy-node->value
(node->next-first-node
(node->next-first-node
(node->next-first-node
zero-in-number-line))))
|#
A Ramanujan number is a number that is the sum of two cubes in two different ways:
n is a Ramanjuan number
<=>
there exists a,b,c,d s.t. a^3+b^3=c^3+d^3=n and {a,b}!={c,d}
My strategy is to have all pairs of numbers (a,b with a<=b) as nodes.
When a node is being tested for acceptance, I record this pair in a
table with the potential ramajunan number as key (the sum of their
cubes). If this list was not empty before the recording, then, we have
a hit. (I don't mind reporting a hit again, every time a new pair is
found for a number.)
|#
(define (cube x)
(* x x x))
(define (sum-cubes x y)
(+ (cube x) (cube y)))
(define (cubic-root x)
(expt x (/ 1 3)))
(define (floor-cubic-root x)
(inexact->exact
(floor (cubic-root x))))
(define (r-value a b)
(list (sum-cubes a b) a b))
(define (r->n node)
(car node))
(define (r->a node)
(cadr node))
(define (r->b node)
(caddr node))
(define (r->ab node)
(cdr node))
(define (r-next r)
(let ((a (r->a r))
(b (r->b r)))
(let ((lst '()))
(define (add! x)
(set! lst (cons x lst)))
(add! (r-value a (+ b 1)))
(if (< a b)
(add! (r-value (+ a 1) b)))
lst)))
(define (new-ramajunan-recorder)
(let ((table (make-eq-hash-table)))
(define (accept-node? node)
(let* ((r (lazy-node->value node))
(n (r->n r))
(ab (r->ab r)))
(let ((lst (hash-table/get table n '())))
(hash-table/put! table n (cons ab lst))
(not (null? lst)))))
(define (print-found node)
(let* ((r (lazy-node->value node))
(n (r->n r))
(lst (hash-table/get table n '())))
(write-line
`(ramajunan number ,n with pairs ,@lst))))
(list accept-node? print-found)))
(define (ramajunan-search until-count)
(let ((recorder (new-ramajunan-recorder)))
(let ((accept-node? (car recorder))
(print-found (cadr recorder))
(count 0))
(graph:search
(make-starting-lazy-node r-next (r-value 0 0))
accept-node?
(lambda (found proceed)
(print-found found)
(set! count (+ count 1))
(if (< count until-count)
(proceed)
proceed)) breadth-first-add-edges!
(lambda (edge) 'done) ))))
(ramajunan-search 50)
(ramajunan number 1729 with pairs (9 10) (1 12))
(ramajunan number 4104 with pairs (9 15) (2 16))
(ramajunan number 13832 with pairs (18 20) (2 24))
...
(ramajunan number 1016496 with pairs (66 90) (47 97))
(ramajunan number 1370304 with pairs (48 108) (34 110))
(ramajunan number 1092728 with pairs (64 94) (1 103))
(define ramajunan-search-on-demand
(let ((squeeze (ramajunan-search 1)))
(lambda ()
(squeeze)
'done)))
(ramajunan number 1729 with pairs (9 10) (1 12))
(ramajunan-search-on-demand)
(ramajunan number 4104 with pairs (9 15) (2 16))
(ramajunan-search-on-demand)
(ramajunan number 13832 with pairs (18 20) (2 24))
|#
It should be possible to have a best-first-add-edges! which add the
new edges, maintaining the queue to be sorted by the best edges
first. The edges should carry along a linear score for this purpose,
and the nodes can add to this score. However, then, a queue is not the
best data structure to keep the edges in, because we'd want to add to
the queue anywhere, not necessarily just at the front or the end. So,
perhaps, the queue abstraction should be changed or augmented. In
addition, for games, it might be useful to have a pruning mechanism so
that not all edges are considered.
|#