Miscellanea
April 26, 2011
FizzBuzz: Our solution uses the modulo function to determine if one number divides another, then counts in a loop, testing each number for divisibility by 15, 5 and 3:
(define (divides? d n) (zero? (modulo n d)))
(define (fizz-buzz n)
(do ((i 1 (+ i 1))) ((< n i))
(cond ((divides? 15 i) (display "FizzBuzz"))
((divides? 5 i) (display "Buzz"))
((divides? 3 i) (display "Fizz"))
(else (display i)))
(newline)))
> (fizz-buzz 20)
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
A related function computes the sum of the FizzBuzz numbers from 1 to n. It uses Gauss’ rule , which is computed by the g
function, and a function f
that computes the number of times a multiple of k is less than n. Then the fizz-buzz sum is f(3) + f(5) - f(15)
, subtracting f(15)
because otherwise those numbers would be counted twice:
(define (fb-sum n)
(define (g n) (* 1/2 n (+ n 1)))
(define (f k) (* k (g (quotient n k))))
(+ (f 3) (f 5) (- (f 15))))
Your reward for computing the sum of the FizzBuzz numbers is this pretty tower of numbers:
> (do ((i 1 (+ i 1))) ((< 20 i))
(display (fb-sum (- (expt 10 i) 1)))
(newline))
23
2318
233168
23331668
2333316668
233333166668
23333331666668
2333333316666668
233333333166666668
23333333331666666668
2333333333316666666668
233333333333166666666668
23333333333331666666666668
2333333333333316666666666668
233333333333333166666666666668
23333333333333331666666666666668
2333333333333333316666666666666668
233333333333333333166666666666666668
23333333333333333331666666666666666668
2333333333333333333316666666666666666668
Prime Words: Our solution uses a built-in function of Scheme to perform the radix conversion:
(define (prime36? str)
(prime? (string->number str 36)))
Here’s a sample:
> (string->number "PRAXIS" 36)
1557514036
> (prime36? "PRAXIS")
#f
> (prime36? "LISP")
#t
Some versions of Scheme, including the one at codepad.org, limit the radix to 16, so here is a different version based on the undigits
function of the Standard Prelude:
(define (digit c)
(cond ((char<=? #\0 c #\9) (- (char->integer c) 48))
((char<=? #\A c #\Z) (- (char->integer c) 55))
((char<=? #\a c #\z) (- (char->integer c) 87))
(else (error 'digit "invalid character"))))
(define (radix36 s)
(undigits (map digit (string->list s)) 36))
(define (prime36? str)
(prime? (radix36 str)))
Here’s the same sample, which produces the same results:
> (radix36 "PRAXIS")
1557514036
> (prime36? "PRAXIS")
#f
> (prime36? "LISP")
#t
Both versions of the function require a prime-number tester. We’ve written several, and for today’s exercise we offer yet another. The basic idea is to perform a Miller-Rabin test, as in a previous exercise, but instead of choosing a random set of bases, to choose the first twelve prime numbers as bases; Zhenxiang Zhang and Min Tang, in their paper “Finding strong pseudoprimes to several bases II” in Mathematics of Computation, Volume 72 (2003), pp. 2085–2097, calculate that there are no mis-reported pseudo-primes less than 318665857834031151167461, which ought to be enough for most words. Here’s the code, which uses expm
from the Standard Prelude:
(define (strong-pseudo-prime? a n)
(let loop ((r 0) (s (- n 1)))
(if (even? s) (loop (+ r 1) (/ s 2))
(if (= (expm a s n) 1) #t
(let loop ((j 0) (s s))
(cond ((= j r) #f)
((= (expm a s n) (- n 1)) #t)
(else (loop (+ j 1) (* s 2)))))))))
(define (prime? n) ; n <= 318665857834031151167461
(let loop ((as '(2 3 5 7 11 13 17 19 23 29 31 37)))
(cond ((null? as) #t)
((strong-pseudo-prime? (car as) n)
(loop (cdr as)))
(else #f))))
Split A List: The trick here is to use two pointers. The first pointer, the tortoise, points to each list element in turn. The second pointer, the hare, runs twice as fast as the tortoise, skipping an element then pointing to the second, skipping an element and pointing to the fourth, and so on. When the hare reaches the end of the list, the tortoise points to the splitting element. Our version is destructive, reusing the original cons cells, changing the cdr of the splitting element to null:
(define (split! xs)
(let loop ((t xs) (h (cdr xs)))
(if (or (null? h) (null? (cdr h)))
(let ((h (cdr t)))
(set-cdr! t '))
(values xs h))
(loop (cdr t) (cddr h)))))
> (split! '(1 2 3 4))
(1 2)
(3 4)
> (split! '(1 2 3 4 5))
(1 2 3)
(4 5)
If you object to the destruction of the original list, here is a version that allocates a new list for the front of the split, returning the new list and the second half of the old list; it does the opposite thing with the central element of an odd-sized list, because the code seems more natural that way:
(define (split xs)
(let loop ((xs xs) (ts '()) (hs xs))
(cond ((null? hs) (values (reverse ts) xs))
((null? (cdr hs)) (values (reverse ts) xs))
(else (loop (cdr xs) (cons (car xs) ts) (cddr hs))))))
> (split '(1 2 3 4))
(1 2)
(3 4)
> (split '(1 2 3 4 5))
(1 2)
(3 4 5)
That approach requires that the front half of the list be reversed, which requires a second pass over half the list, which may or may not violate the “single-pass” rule, depending on how you interpret it.
You can run the program at http://programmingpraxis.codepad.org/830f0msv.
My try in REXX
[…] today’s Programming Praxis exercise, our goal is to write three fucntions: FizzBuzz, a function to […]
My Haskell solution (see http://bonsaicode.wordpress.com/2011/04/26/programming-praxis-miscellanea/ for a version with comments):
my implementation in c
Solution in Python (for simple tests look at github):
I have been trying to learn macros , so here is my code
using predicate dispatch paper, implemented using macros.
@Vikas Tandi – how about PrimeWords(“3”) and PrimeWords(“2”) :)
Oh and in my code instead of:
should be
My solution to “FizzBuzz”: write a generator “fizzer()” that accepts an argument list of the “fizz-buzz” parameters.
This is how you call it:
This is the output:
@arturasl – Thanks for pointing that out :(
This check should be added after decimal conversion
My Python solution, with multiple answers for each.
Some of it isn’t original, but I’m most proud of my list splitting and my use of Horner’s Method for
converting a word to a base 36 number (though Python’s
int()
provides all the functionality we need,anyway).
Here’s ruby versions of each. FizzBuzz is unimaginative, prime words is OK, split_list works for arrays, but I feel like it could be better.
@Graham – is_prime_word_horner will not work if you pass it word with digits:
Anyway neat solution, especially the usage of all() and reduce() q:-)
Here is an attempt in python
number = input(‘What number would you like to count to? ‘) + 1
whole = 0
fizzz = 0
buzzz = 0
def whole_number(num):
global whole
if num % 1 == 0:
whole = 1
else:
whole = 0
def fizz(num):
global fizzz
if num % 3 == 0:
fizzz = 1
else:
fizzz = 0
def buzz(num):
global buzzz
if num % 5 == 0:
buzzz = 1
else:
buzzz = 0
for N in range(1,number,1):
whole_number(N)
fizz(N)
buzz(N)
if fizzz is 1 and buzzz is 1:
print(‘FizzBuzz’)
elif buzzz is 1 and fizzz is 0:
print(‘Buzz’)
elif buzzz is 0 and fizzz is 1:
print(‘Fizz’)
else:
print(N)
Sorry I dont know how to retain the indentation and code look
Ryan Take a look at https://programmingpraxis.com/contents/howto-posting-source-code/. That should explain how to format your code. I was going to paste it in, but I’m pretty sure it wouldn’t do what I want.
@arturasl: Thanks for catching that. I only thought to work with letters, basing my
ord(y) - 55
off of the offset for the letters A through Z…Like I said, the use of Python’s integer
conversion is probably the preferred method—in this case, the only correct method :-)
—that I came up with. Thanks again!
A non-destructive solution without using reverse (in case that’s cheating):
(define (split xs)
(let loop ((xs xs) (rest xs))
(if (or (null? rest) (null? (cdr rest)))
(values ‘() xs)
(let-values (((first second) (loop (cdr xs) (cddr rest))))
(values (cons (car xs) first) second)))))
Err, I’ll try formatted:
Here’s my 2 cents:
FizzBuzz
Thought I’d do something different than the standard if-elif-type answer.
Prime Words
isprime() is from a prior exercise
Split A List
Uses deques to efficiently add/pop items from either end.
Basic idea is add each item in the list to the end of the ‘back’ half. Every other time an item is added to the back, an item
is popped off the front of the ‘back’ half and added to the ‘front’ half.
Tested in MIT Scheme
praxis.scm
Here’s my Ruby solution:
I feel I cheated a bit with my solution for the 3rd assignment because I’m not scanning the list in situ. Oh well… =)
Simple Haskell for FizzBuzz.
run n = mapM_ putStrLn $ take n $ zipWith (\a b -> if null b then show a else b) [1..] $ zipWith (++) (cycle ["","","Fizz"]) (cycle ["","","","","Buzz"])
Scheme.
In a table, I store a continuation that builds a list made of 1/ what’s on the stack, and 2/ what you give it, as well as the current rest of the list. Each time I scan one more element of the list, I put it on the stack (with CONS) and call myself recursively, after setting the continuation and the rest of the list in the table. When the list is empty, compute the middle index, fetch the continuation and rest at this time, save the rest somewhere, and call the continuation with ‘() to return the list up to the middle. Then assemble everything and you’re done. Lists of length 0 and 1 are edge cases.
(define (split l)
(define table (make-table))
(define cnt 0)
(define bottom '())
(define (aux l)
(if (null? l)
(case cnt
((0 1) '())
(else
(let* ((mid (floor (/ cnt 2)))
(val (table-ref table mid)))
(set! bottom (cdr val))
((car val) '()))))
(begin
(set! cnt (+ cnt 1))
(cons (car l)
(call/cc
(lambda (build-top)
(table-set! table cnt (cons build-top (cdr l)))
(aux (cdr l))))))))
(let ((res (aux l)))
(vector res bottom)))
Morally the same as above, but cleaner. Uses a hack (?) from gambit (4.2.8 in my test), the fact that ((lambda(x) x) (values a b)) will effectively return the two values.
(define (split l)
(define (aux l #!optional (table (make-table)) (cnt 1))
(if (null? l)
(let* ((mid (floor (/ cnt 2)))
(val (table-ref table mid (cons (lambda (x) x) '()))))
((car val) (values '() (cdr val))))
(call-with-values
(lambda ()
(call/cc
(lambda (build-top)
(table-set! table cnt (cons build-top (cdr l)))
(aux (cdr l) table (+ 1 cnt)))))
(lambda (val bot)
(values (cons (car l) val) bot)))))
(aux l))