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 \sum_{i=1}^{n} = \frac{n(n+1)}2, 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.

About these ads

Pages: 1 2

25 Responses to “Miscellanea”

  1. Rainer said

    My try in REXX

    numeric digits 30                                             
                                                                  
    call fizzbuzz 20                                              
    call prime_words 'PRAXIS'                                     
    call split_a_list 'This is a list'                            
    call split_a_list 'This is a second list'                     
    exit                                                          
                                                                  
    fizzbuzz: procedure                                           
        parse arg nbr                                             
        do i = 1 to nbr                                           
            aus = ''                                              
            if i//3 == 0 then aus = 'Fizz'                        
            if i//5 == 0 then aus = strip(aus)||'Buzz'            
            if length(aus) > 0 then say aus                       
                               else say i                         
        end                                                       
        return                                                    
                                                                  
    prime_words: procedure                                        
        parse arg nbr                                        
        base36 = '123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'       
        sum = 0                                              
        exp = 0                                              
        rnbr = reverse(nbr)                                  
        do i = 1 to length(rnbr)                             
            z = substr(rnbr,i,1)                             
            p = pos(z,base36)                                
            erg = p * (36 ** exp)                            
            sum = sum + erg                                  
            exp = exp + 1                                    
        end                                                  
        aus = nbr '(Decimal:'sum')'                          
        if is_prime(sum) then say aus 'is prime'             
                         else say aus 'is not prime'         
        return                                               
                                                             
    split_a_list: procedure                                  
        parse arg text                                       
        w = words(text)                                      
        m = w % 2                                            
        say 'List 1: ' subword(text,1,m)     
        say 'List 2: ' subword(text,m+1)     
        return                               
                                             
    is_prime: procedure                      
        parse arg nbr                        
        do x = 2 to nbr-1                    
            if nbr//x == 0 then return 0     
        end                                  
        return 1           
    
  2. […] today’s Programming Praxis exercise, our goal is to write three fucntions: FizzBuzz, a function to […]

  3. My Haskell solution (see http://bonsaicode.wordpress.com/2011/04/26/programming-praxis-miscellanea/ for a version with comments):

    import Data.Foldable (toList)
    import Data.Numbers.Primes
    import Data.Sequence (ViewL(..), (|>), fromList, viewl, empty)
    
    fizzbuzz :: Integral a => a -> IO ()
    fizzbuzz n = mapM_ (putStrLn . f) [1..n] where
        f n = case (mod n 3, mod n 5) of (0, 0) -> "FizzBuzz"
                                         (0, _) -> "Fizz"
                                         (_, 0) -> "Buzz"
                                         _      -> show n
    
    isPrimeWord :: String -> Bool
    isPrimeWord = isPrime . sum . zipWith (*) (iterate (* 36) 1) . reverse .
        map (\c -> maybe 0 id . lookup c $ zip (['0'..'9'] ++ ['A'..'Z']) [0..])
    
    splitList :: [a] -> ([a], [a])
    splitList = f True (empty, empty) where
        f _     (l,r) []     = (toList l, toList r)
        f True  (l,r) (x:xs) = f False (l, r |> x) xs
        f False (l,r) (x:xs) = f True ((\(h :< t) -> (l |> h, t |> x)) $ viewl r) xs
    
  4. Vikas Tandi said

    my implementation in c

    #include <stdio.h>
    #include <math.h>
    
    void FizzBuzz(int n)
    {
    	int i;
    
    	for(i = 1; i <= n; i++)
    	{
    		/* if divisible by three */
    		if((i % 3) == 0 && (i % 5) == 0)
    			printf("FizzBuzz\n");
    		else if((i % 3) == 0)
    			printf("Fizz\n");
    		else if((i % 5) == 0)
    			printf("Buzz\n");
    		else
    			printf("%d\n", i);
    	}
    }
    
    int PrimeWords(char *word)
    {
    	int i;
    	long long val;
    	long long sqt;
    
    	/* convert the base 36 word to decimal */
    	for(i = 0, val = 0; word[i] != '\0'; i++)
    	{
    		if(word[i] >= '0' && word[i] <= '9')
    			val = val * 36 + (word[i] - '0');
    		else
    			val = val * 36 + (word[i] - 'A' + 10);
    	}
    
    	/* test primality */
    
    	if((val % 2) == 0)		/* check divisibility by 2 */
    		return 0;
    
    	if((val % 3) == 0)		/* check divisibility by 2 */
    		return 0;
    
    	/* check the divisibilty of val by 6k-1 or 6k+1 upto squre root of val */
    	sqt = (long long)sqrt((double)val);
    
    	for(i = 1; ;i++)
    	{
    		int j;
    
    		/* test for 6k-1 */
    		j = 6*i - 1;
    		if(j > sqt)
    			return 1;
    
    		if((val % j) == 0)
    			return 0;
    
    		/* test for 6k+1 */
    		j = 6*i + 1;
    		if(j > sqt)
    			return 1;
    
    		if((val % j) == 0)
    			return 0;
    	}
    }
    
    /*
    Split the nodes of the given list into front and back halves,
    and return the two lists using the reference parameters.
    If the length is odd, the extra node should go in the front list.
    */
    void FrontBackSplit(struct Node* source, struct Node** frontRef, struct Node** backRef)
    {
    	struct Node* singleJump = source;
    	struct Node* doubleJump = source;
    
    	if(singleJump == NULL || singleJump->next == NULL)
    	{
    		*frontRef = source;
    		*backRef = NULL;
    		return;
    	}
    
    	while(doubleJump->next != NULL && doubleJump->next->next != NULL)
    	{
    		singleJump = singleJump->next;
    		doubleJump = doubleJump->next->next;
    	}
    
    	*frontRef = source;
    	*backRef = singleJump->next;
    	singleJump->next = NULL;
    }
    
  5. arturasl said

    Solution in Python (for simple tests look at github):

    def fizz_buzz(number):
        for i in range(1, number + 1):
            if i % 15 == 0:
                print 'FizzBuzz'
            elif i % 3 == 0:
                print 'Fizz'
            elif i % 5 == 0:
                print 'Buzz'
            else:
                print i
    
    def is_prime(number):
        if number == 1:
            return False
        if number == 2:
            return True
        if number % 2 == 0:
            return False
    
        for i in range(3, int(sqrt(number)) + 1, 2):
            if number % i == 0:
                return False
    
        return True
    
    def hexatridecimal_to_dec(test_str):
        pos = len(test_str) - 1
        result = 0
    
        for character in list(test_str):
            code = ord(character)
            if ord('0') <= code and code <= ord('1'):
                result += (code - ord('0')) * 36 ** pos
            elif ord('A') <= code and code <= ord('Z'):
                result += (code - ord('A') + 10) * 36 ** pos
            else:
                print ('illegal character ', character)
    
            pos -= 1
    
        return result
    
    def split_list(first_node):
        split_at = first_node
        double_next = first_node
    
        if first_node is None:
            return (None, None)
    
        while double_next.next_node is not None and double_next.next_node.next_node is not None:
            double_next = double_next.next_node.next_node
            split_at = split_at.next_node
    
        prev_node = split_at
        split_at = split_at.next_node
        prev_node.next_node = None
    
        return (first_node, split_at)
    
  6. Veer said

    I have been trying to learn macros , so here is my code
    using predicate dispatch paper, implemented using macros.

    (module example3 "../method.rkt"
      
      (define (div-3 x)
        (zero? (remainder x 3)))
      
      (define (div-5 x)
        (zero? (remainder x 5)))
      
      (define (div-3-5 x)
        (and (div-3 x) (div-5 x)))
      
      (add-subclass div-3 (div-3-5 0))
      (add-subclass div-5 (div-3-5 0))
      (add-subclass div-3-5 (0))
      
      (define-method fizbuz (n)
        (when: (div-5 n) (fizbuz (- n 1)) 
               (printf "~a\n" "Buzz"))
               
        (when: (div-3 n) (fizbuz (- n 1))  (printf "~a\n" "Fizz"))
                         
        (when: (div-3-5 n) (fizbuz (- n 1))  (printf "~a\n" "FizzBuzz")))
    
      
      (define-method fizbuz (#:n 0)
        (printf "\n"))
      
      (define-method fizbuz (n)
        (fizbuz (- n 1))
        (printf "~a\n" n)
        )
          
      (fizbuz 20)
      
      )
    
  7. arturasl said

    @Vikas Tandi – how about PrimeWords(“3″) and PrimeWords(“2″) :)

    Oh and in my code instead of:

    if ord('0') <= code and code <= ord('1'):
    

    should be

    if ord('0') <= code and code <= ord('9'):
    
  8. Dan Harasty said

    My solution to “FizzBuzz”: write a generator “fizzer()” that accepts an argument list of the “fizz-buzz” parameters.

    # "args" must be a zero or more of tuples ("word", modulo)	 
    def fizzer(*args):
    	cnt = 0
    	while True:
    		cnt += 1
    		out = ""
    		for word, modulo in args: 
    			if cnt % modulo == 0: out += word
    		if out == "": out = cnt
    		yield out
    

    This is how you call it:

    
    # create a "fizz-buzz" generator
    fb = fizzer(("Fizz", 3), ("Buzz", 5))
    for n, fizz in zip(range(25), fb):
    	print(fizz, end=" ")
    
    print()
    
    # alternate way to call it
    fb = fizzer(("Fizz", 3), ("Buzz", 5))
    for n in range(25):
    	print(fb.__next__(), end=" ")
    
    print()
    
    
    # just for grins: create a "fizz-buzz-bang" generator
    fbb = fizzer(("Fizz", 3), ("Buzz", 5), ("Bang", 7))
    for n, fizz in zip(range(25), fbb):
    	print(fizz, end=" ")
    
    print()
    
    

    This is the output:

    
    1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 
    
    1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 
    
    1 2 Fizz 4 Buzz Fizz Bang 8 Fizz Buzz 11 Fizz 13 Bang FizzBuzz 16 17 Fizz 19 Buzz FizzBang 22 23 Fizz Buzz 
    
    
  9. Vikas Tandi said

    @arturasl – Thanks for pointing that out :(
    This check should be added after decimal conversion

    if(val == 2 || val == 3)
    	return 1;
    
  10. Graham said

    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).

  11. slabounty said

    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.

    #
    # FizzBuzz
    (1..ARGV[0].to_i).each do |v|
        if v % 15 == 0
            puts "FizzBuzz"
        elsif v % 5 == 0
            puts "Buzz"
        elsif v % 3 == 0
            puts "Fizz"
        else
            puts "#{v}"
        end
    end
    
    # Prime Words
    # Require mathn for the prime? method.
    require 'mathn'
    
    class String
        def prime_word?
            self.to_i(36).prime?
        end
    end
    
    puts "\n\nPrime Words:"
    praxis = "praxis"
    puts "praxis is #{praxis.prime_word? ? "prime" : "not prime"}"
    lisp = "lisp"
    puts "lisp is #{lisp.prime_word? ? "prime" : "not prime"}"
    
    # Split List (assumes we can't just do l.length). On an odd numbered list
    # it will put the extra in the first list.
    def split_list(l)
        split = size = 0
        l.each_index do |current|
            split = current / 2
            size = current
        end
        puts "split = #{split} size = #{size}"
        l1 = l[0..split]
        l2 = l[split+1..size]
        return l1, l2
    end
    
    puts "\n\nSplit List:"
    list = %w[this is a list of six elements]
    l1, l2 = split_list(list)
    puts "first half = #{l1} second half = #{l2}"
    
    list = %w[this is a list of six]
    l1, l2 = split_list(list)
    puts "first half = #{l1} second half = #{l2}"
    
  12. arturasl said

    @Graham – is_prime_word_horner will not work if you pass it word with digits:

    >>> reduce(lambda x, y: 36 * x + ord(y) - 55, '123', 0)
    -7960
    >>> int('123', 36)
    1371
    

    Anyway neat solution, especially the usage of all() and reduce() q:-)

  13. Ryan said

    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)

  14. Ryan said

    Sorry I dont know how to retain the indentation and code look

  15. slabounty said

    Ryan Take a look at http://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.

  16. Graham said

    @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!

  17. Kevin Millikin said

    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)))))

  18. Kevin Millikin said

    Err, I’ll try formatted:

    (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)))))
    
  19. Mike said

    Here’s my 2 cents:

    FizzBuzz

    Thought I’d do something different than the standard if-elif-type answer.

    from itertools import cycle, izip
    
    def fizzbuzz(n):
        fizzer = cycle(['','','Fizz'])
        buzzer = cycle(['','','','','Buzz'])
        counter = xrange(1,n+1)
        
        for f,b,c in izip(fizzer, buzzer, counter):
    	    print f+b if f or b else c
    
    

    Prime Words

    isprime() is from a prior exercise

    from itertools import count
    from operator import mul
    from primes import isprime
    from string import digits, ascii_uppercase
    
    # translation table base-36 -> decimal
    xlat = {c:n for n,c in enumerate(digits + ascii_uppercase)}
    
    def prime_words(s):
        digits = (xlat[c] for c in reversed(s.upper()))
        powers = (pow(36,e) for e in count())
        return isprime(sum(imap(mul, digits, powers)))
    
    

    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.

    from collections import deque
    
    def split_a_list(lst, front_heavy=True):
        '''returns front/back halves of a list.  front_heavy determines which half is longer (heavy)
        if the list has an odd number of items.
        '''
    
        front = deque()
        back = deque()
    
        for item in lst:
            back.append(item)
    
            if front_heavy:
                front.append(back.popleft())
    
            front_heavy = not front_heavy
    		
        return list(front), list(back)
    
    
  20. yaq said

    Tested in MIT Scheme

  21. yaq said

    praxis.scm

    ;;http://programmingpraxis.com/2011/04/26/miscellanea/
    ;FizzBuzz
    
    (define (enumerate-interval low high)
      (if (> low high)
          '()
          (cons low (enumerate-interval (+ low 1) high))))
    
    (define (fizz-buzz n)
      (for-each (lambda (x) (display x) (newline))
                (map fizz-buzz-func (enumerate-interval 1 20))))
    
    (define (fizz-buzz-func n)
      (cond ((and (= (remainder n 3) 0) (= (remainder n 5) 0))
             'fizz-buzz)
            ((= (remainder n 3) 0)
             'fizz)
            ((= (remainder n 5) 0)
             'buzz) 
            (else n)))
    
    (fizz-buzz 20)
    ;prime words
    ;prime? is from SICP
    (define (prime? n)
      (define (smallest-divisor n)
        (find-divisor n 2))
      (define (find-divisor n test-divisor)
        (cond ((> (square test-divisor) n) n)
              ((divides? test-divisor n) test-divisor)
              (else (find-divisor n (+ test-divisor 1)))))
      (define (divides? a b)
        (= (remainder b a) 0))
      (= n (smallest-divisor n)))
    
    (define (string-to-number-list s n)
      (let ((numbers "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"))
        (cond ((= n (string-length s)) '())
              (else
               (cons (cons (string-find-next-char
                            numbers
                            (string-ref s n))
                           (- (string-length s) (+ n 1)))
                     (string-to-number-list s (+ n 1)))))))
    
    (define (prime-words? w)
      (prime? (fold-left + 0 (map (lambda (x)
                                    (* (car x)
                                       (expt 36 (cdr x))))
                                  (string-to-number-list w 0)))))
    
    (prime-words? "LISP") ;#t
    (prime-words? "PRAXIS") ;#f
    ;split a list
    ;if length is odd, put the center element in first half
    (define (col first-half second-half)
      (cons first-half second-half))
    
    (define (split-a-list l col)
      (define (split-a-list-internal l c cn col)
        (cond ((null? l) (col '() '()))
              ((< c cn)
               (split-a-list-internal (cdr l) (+ c 1) cn
                                      (lambda (first-half second-half)
                                        (col (cons (car l) first-half)
                                             second-half))))
              (else
               (split-a-list-internal (cdr l) (+ c 1) cn
                                      (lambda (first-half second-half)
                                        (col first-half
                                             (cons (car l) second-half)))))))
      (split-a-list-internal l 0 (/ (length l) 2) col))
    
    (define test-list (list 1 2 3 4 5))
    ;return a list contains two lists (first-half and second-half)
    (split-a-list test-list col)
    ;output: ((1 2 3) 4 5)
    
  22. Here’s my Ruby solution:

    def fizz_buzz(n)
    	1.upto(n) do |i|
    		case 
    		when i % 3 == 0 && i % 5 == 0
    			puts "FizzBuzz"
    		when i % 3 == 0
    			puts "Fizz"
    		when i % 5 == 0
    			puts "Buzz"
    		else
    			puts i
    		end
    	end
    end
    
    def get_numeric_value(word)
    	exp, sum = word.length - 1, 0
    	word.bytes{ |char|
    		if char >= 0 && char <= 9 then
    			sum += char * 36 ** exp
    		else
    			sum += (char - 55) * 36 ** exp
    		end
    		exp = exp - 1	
    	}
    	return sum
    end
    
    require 'mathn'
    def is_prime_word(word)
    	return Prime.instance.prime?(get_numeric_value(word))
    end
    
    def split_list(list)
    	if list.length % 2 == 0 then 
    		return [list.slice(0, list.length / 2), list.slice(list.length / 2, list.length - 1)]
    	else
    		return [list.slice(0, list.length / 2 + 1), list.slice(list.length / 2 + 1, list.length - 1)] 
    	end
    end
    
    puts fizz_buzz(20)
    puts is_prime_word('PRAXIS')
    puts split_list([1,2,3,4]).to_s
    puts split_list([1,2,3]).to_s
    

    I feel I cheated a bit with my solution for the 3rd assignment because I’m not scanning the list in situ. Oh well… =)

  23. Axio said

    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"])

  24. Axio said

    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)))

  25. Axio said

    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))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: