PilMCU is an implementation of 64-bit PicoLisp directly in hardware. A
truly minimalistic system. PicoLisp is both the machine language and the
In the following equation x, y and n are positive integers: 1 / x + 1 y = 1 / n. For n = 4 there are exactly three distinct solutions: 1/5 + 1/20 = 1/6 + 1/12 = 1/8 + 1/8 = 1/4. What is the least value of n for which the number of distinct solutions exceeds one thousand?
Your task is to solve Amazon’s question; you might also like to make a list of the x, y pairs that sum to a given n. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
(lambda (t) (/ (+ (* a t) b) (+ (* c t) d))). I'll represent a simple continued fraction as a stream of the integer terms in the denominators.
(define (partly-apply hf cf) (let ((a (first hf)) (b (second hf)) (c (third hf)) (d (fourth hf))) (if (empty-stream? cf) (values (list a a c c) cf) (let ((term (head cf))) (values (list (+ (* a term) b) a (+ (* c term) d) c) (tail cf))))))Partly evaluating a homographic function involves looking at the limits of the function as
tstarts at 1 and goes to infinity:
(define (partly-evaluate hf) (let ((a (first hf)) (b (second hf)) (c (third hf)) (d (fourth hf))) (if (and (same-sign? c (+ c d)) (let ((limit1 (quotient a c)) (limit2 (quotient (+ a b) (+ c d)))) (= limit1 limit2))) (let ((term (quotient a c))) (let ((new-c (- a (* c term))) (new-d (- b (* d term)))) (values term (list c d new-c new-d)))) (values #f #f))))We can combine these two steps and make something useful. For example, we can print the value of applying a homographic function to a continued fraction incrementally, printing the most significant digits before computing further digits.
(define (print-hf-cf hf cf) (call-with-values (lambda () (partly-evaluate hf)) (lambda (term hf*) (if (not term) (call-with-values (lambda () (partly-apply hf cf)) print-hf-cf) (begin (display term) ;; take reciprocal and multiply by 10 (let ((a (first hf*)) (b (second hf*)) (c (third hf*)) (d (fourth hf*))) (print-hf-cf (list (* c 10) (* d 10) a b) cf)))))))But how often are you going to apply a homographic function to a continued fraction? Fortunately, the identity function is homographic (coefficients are 1 0 0 1), so applying it to a continued fraction doesn't change the value. The square root of 2 is a simple continued fraction with coefficients [1 2 2 2 ...] where the 2s repeat forever. We apply the identity homographic function to it and print the results:
(printcf (list 1 0 0 1) sqrt-two) 14142135623730950488016887242096980785696718^G ; Quit!As you can see, we start printing the square root of two and we don't stop printing digits until the user interrupts.
In 1917, Henry Ernest Dudeney published a book Amusements in Mathematics of arithmetic puzzles. Today’s exercise solves puzzle 113 from that book:
A number n is a torn number if it can be chopped into two parts which, when added together and squared, are equal to the original number. For instance, 88209 is a torn number because (88 + 209)2 = 2972 = 88209.
Your task is to write a program to find torn numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
The GNU Guix project is organizing a hackathon on September 27th and 28th, 2014. The hackathon will take place primarily on-line, on the #guix IRC channel on Freenode. We have started collecting a list of hacking ideas. Feel free to stop by and make more suggestions!
The hackathon is accessible to anyone with experience in GNU/Linux packaging or systems hacking. Scheme programmers will find additional things to work on in the tool set. Finally, we will also be welcoming newcomers and helping them get started.
GNU Guix is the functional package manager for the GNU system, and a distribution thereof.
In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. It also offers a declarative approach to operating system configuration management. Guix uses low-level mechanisms from the Nix package manager, with Guile Scheme programming interfaces.
At this stage the distribution can be used on an i686 or x86_64 machine. It is also possible to use Guix on top of an already installed GNU/Linux system, including on mips64el.
In a previous exercise we computed the edit distance between two strings where the allowable operations were insert or delete characters; we made the calculation by determining the longest common subsequence. A different definition of edit distance allows substitutions as well as insertions and deletions, and is called the Levenshtein distance, since it was studied by Vladimir Levenshtein in 1965. For example, the edit distance between “hill” and “hilt” is 2 (delete the “l” and insert the “t”) but the Levenshtein distance is 1 (replace “l” by “t”).
The basic algorithm is recursive: if either string is empty, the Levenshtein distance is the length of the other string, otherwise it is the minimum of the Levenshtein distance computed by deleting the first character from the first string, by deleting the first character from the second string, or by deleting the first characters of each of the two strings (adding 1 if the two characters differ), plus the Levenshtein distance of the remaining substrings. That computation takes exponential time as it recomputes the same substring Levenshtein distances many times. A better algorithm uses dynamic programming to build up the substring distances, so they are always available as they are needed.
Your task is to write two functions to compute the Levenshtein distance between two strings. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Inspired by jtarbell's original fractal invaders, I took the liberty of implementing this in CHICKEN Scheme using doodle.
(use doodle matchable (srfi 1)) (define block-width 3) (define block-height 3) (define block-rows 5) (define block-cols 6) (new-doodle width: 840 height: 420 background: solid-white) (define (block x y row col) (let* ((x0 (+ x (* col block-width))) (y0 (+ y (* row block-height))) (x1 (+ x0 block-width)) (y1 (+ y0 block-height))) (list x0 y0 block-width block-height))) (define (color v) (if (= v 0) solid-black solid-white)) (define (mirror grid) (map (lambda (lst) (append lst (cdr (reverse lst)))) grid)) (define (draw-blocks x y blks color-chooser) (let loop ((bs (mirror blks)) (row 0)) (cond ((null? bs) #t) (else (fold (lambda (b col) (apply filled-rectangle `(,@(block x y row col) ,(color-chooser b))) (add1 col)) 0 (car bs)) (loop (cdr bs) (add1 row)))))) (define (random-blocks) (list-tabulate block-rows (lambda _ (list-tabulate (/ block-cols 2) (lambda _ (random 2)))))) (define (random-critter! x y) (draw-blocks x y (random-blocks) color)) (define (invaders) (let outer ((x 3)) (if (< x doodle-width) (begin (let inner ((y 3)) (if (< y doodle-height) (begin (random-critter! x y) (inner (+ y (* 2 block-width block-cols)))))) (outer (+ x (* 2 block-height block-rows)))))) (show!)) (define *painting* #t) (world-inits (lambda () (invaders))) (world-changes (lambda (events dt exit) (for-each (lambda (e) (match e (('key 'pressed #\esc) (exit #t)) (('key 'pressed #\space) (set! *painting* (not *painting*))) (else (void)))) events) (when *painting* (invaders)))) (run-event-loop)
It turned out to be a nice coffee break hack and the resulting images leave a lot of room for imagination. Maybe this is a nice way to create sprites for the next retro arcarde game procedurally? Try tuning the block rows and columns!
Given a small positive integer n, write a function that draws a diamond, either filled or in outline as specified by the user. For instance, here are filled and outline diamonds for n = 5:
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Note that there is a single space between asterisks in the filled version of the diamond.
Your task is to write a program that draws diamonds as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
((lambda (t) (/ (+ (* 70 t) 29) (+ (* 12 t) 5))) n)Which we intend to apply to some positive number
n. Even if all we know is that
nis positive, we can deduce that the value of the homographic function is between 29/5 (when
tis 0) and 70/12 (as
tgoes to infinity). The integer part of those values are the same, so we can factor that out:
(+ 5 (/ 1 ((lambda (t) (/ (+ (* 12 t) 5) (+ (* 10 t) 4))) n)))The partial answer has an integer value of 5 and a fractional part that contains a new homographic function applied to our original
n. We can do it again:
(+ 5 (/ 1 (+ 1 (/ 1 ((lambda (t) (/ (+ (* 10 t) 4) (+ (* 2 t) 1))) n)))))The fractional part of the answer can itself be factored into another integer and a new homographic function applied to our original
((lambda (t) (/ (+ (* 2 t) 1) (+ (* 1 t) 3))) (+ 3 (/ 1 (+ 7 (/ 1 16))))) ;; after one step ((lambda (t) (/ (+ (* 7 t) 2) (+ (* 6 t) 1))) (+ 7 (/ 1 16))) ;; after two steps ((lambda (t) (/ (+ (* 51 t) 7) (+ (* 43 t) 6))) 16)By partly apply a homographic function to a continued fraction, we can process the integer part separately and before the fractional part. By partly evaluating the application of a homographic function, we can often determine the integer part without fully evaluating the argument to the function. For example, after step one above, we could instead partially evaluate the application:
;; after one step ((lambda (t) (/ (+ (* 7 t) 2) (+ (* 6 t) 1))) (+ 7 (/ 1 16))) ;; Alternatively, partially evaluate first term (+ 1 (/ 1 ((lambda (t) (/ (+ (* 6 t) 1) (+ (* 1 t) 1))) (+ 7 (/ 1 16)))))
The Skyline Puzzle is a classic programming exercise; it draws a silhouette of a city skyline by blocking out portions of buildings that are masked by taller buildings. A city is a list of buildings specified as triples containing left edge, height, and right edge. For instance, the list of triples
(1 11 5) (2 6 7) (3 13 9) (12 7 16) (14 3 25) (19 18 22) (23 13 29) (24 4 28) encodes the eight buildings shown at the left of the diagram, and the path
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0 encodes the skyline shown at the right of the diagram, where the odd-indexed elements of the output are the x-coordinate of the skyline and the even-indexed elements of the output are the y-coordinate of the skyline. (It makes more sense to me that the output should look like
(1 11) (3 13) (9 0) (12 7) (16 3) (19 18) (22 3) (23 13) (29 0) but that’s not the way the puzzle is ever specified.) Notice that the second (2 6 7) and eighth (24 4 28) buildings are not part of the skyline.
Your task is to write a program that takes a list of buildings and returns a skyline. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
For those familiar with package.el, the main user interface is quite similar: commands like guix-newest-available-packages, guix-search-by-regexp, and guix-installed-packages present a browsable list of packages. Individual packages can be selected, which displays additional details and presents a button to install or delete them. It is also possible to mark a set of packages for installation, upgrade, or deletion, and execute the set of operations in a single transaction.
The interface has been developed by Alex Kost and was merged in Guix a day ago. It uses Geiser, the beloved Guile/Emacs interface and development environment, to communicate with the underlying Guile process. That Guile process, in turn, simply uses Guix and the whole distribution as libraries—the goodness of embedding the packaging DSL in a general-purpose language.
Try it out and let us know what you think!
(lambda (t) (/ (+ (* 3 t) 4) (+ (* 5 t) 2)))And here is what it's graph looks like:
d) by the same number, it doesn't change the function. For instance, this homographic function:
(lambda (t) (/ (+ (* 21 t) 28) (+ (* 35 t) 14)))is the same as the one above. If one of your coefficients isn't an integer, don't worry, you can multiply everything by the denominator and get an equivalent homographic function. On the other hand, you can divide all your coefficients by their greatest common divisor and get an equivalent homographic function with smaller coefficients. We'll keep our homographic functions in smallest integer form.
((lambda (t) (/ (+ (* a t) b) (+ (* c t) d))) (+ x y/z)) ;; substitute (/ (+ (* a (+ x y/z)) b) (+ (* c (+ x y/z)) d)) ;; distribute the multiplication (/ (+ (* a x) (* a y/z) b) (+ (* c x) (* c y/z) d)) ;; multiply top and bottom by z/y (/ (* z/y (+ (* a x) (* a y/z) b)) (* z/y (+ (* c x) (* c y/z) d))) ;; distribute the multiplication (/ (+ (* a x z/y) (* a y/z z/y) (* b z/y)) (+ (* c x z/y) (* c y/z z/y) (* d z/y))) ;; simplify (/ (+ (* a x z/y) a (* b z/y)) (+ (* c x z/y) c (* d z/y))) ;; rearrange terms (/ (+ (* a x z/y) (* b z/y) a) (+ (* c x z/y) (* d z/y) c)) ;; factor out z/y (/ (+ (* (+ (* a x) b) z/y) a) (+ (* (+ (* c x) d) z/y) c))Now we do something tricky. We abstract out the
((lambda (t) (/ (+ (* (+ (* a x) b) t) a) (+ (* (+ (* c x) d) t) c))) (/ z y))If introduce a
letform, we can see something interesting:
((lambda (t) (let ((a1 (+ (* a x) b)) (b1 a) (c1 (+ (* c x) d)) (d1 c)) (/ (+ (* a1 t) b1) (+ (* c1 t) d1)))) (/ z y))We find a new homographic function being applied to a new rational number. The new homographic function has coefficients related to the original one, and the new rational number is the reciprocal of the fractional part of the original rational number. So if we have a homographic function
hfapplied to a fraction of the form
x + y/z, we can easily find a new homographic function
hf'that when applied to
z/ywill produce the same answer as the original. Applying a homographic function to a fraction has the effect of "eating" the integer part of the fraction, which generates a new homographic function that is applied to the reciprocal of the fractional part.
A sequence is a list of integers (or any other ordered type, but we’ll use integers to keep things simple). A subsequence is any, possibly non-consecutive, list drawn from the parent sequence with items in the same order as the parent sequence. An increasing subsequence is a subsequence with all the items in increasing order. A longest increasing subsequence (there may be more than one with the same length) is an increasing subsequence of a parent sequence of the greatest possible length. For instance, the sequence (3 2 6 4 5 1) has longest increasing subsequences (2 4 5) and (3 4 5).
The algorithm to find the longest increasing subsequence is similar to the algorithm for patience sorting of a previous exercise, with a small modification. When dealing the cards, each time a card is placed on a pile, a back-pointer to the top card on the previous pile is placed along with the card. Then, when all the cards are dealt, the number of piles is the length of the longest increasing subsequence, and the longest increasing subsequence can be recovered by taking the top card from the last pile and following the back-pointers to previous piles.
For instance, with sequence (3 2 6 4 5 1) the cards are dealt with 3 and 2 on the first pile, 6 and 4 on the second pile, 5 on the third pile, and 1 on the first pile, so the longest increasing subsequence has length 3. The 5 on the third pile ends the longest increasing subsequence, it points to the 4 which was on the top of the second pile when 5 was added to the third pile, and 4 points to the 2 which was on the top of the first pile when 4 was added to the second pile; even though 1 was later added to the first pile, is wasn’t yet on the pile when 4 was added to the second pile, so it’s not part of the longest increasing subsequence.
Your task is to write a program to find the longest increasing subsequence of a sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.