## Miscellanea

### April 26, 2011

We have three short exercises today.

FizzBuzz: Looking back over past exercises, I was surprised to find that we haven’t done this classic interview question. You are to write a function that displays the numbers from 1 to an input parameter n, one per line, except that if the current number is divisible by 3 the function should write “Fizz” instead of the number, if the current number is divisible by 5 the function should write “Buzz” instead of the number, and if the current number is divisible by both 3 and 5 the function should write “FizzBuzz” instead of the number. For instance, if n is 20, the program should write 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, and Buzz on twenty successive lines.

Prime Words: Consider that a word consisting of digits and the letters A through Z can represent an integer in base 36, where the digits represent their base-10 counterparts, A is a decimal 10, B is a decimal 11, and so on, until Z is a decimal 35. For instance, PRAXIS36 = P36 × 365 + R36 × 364 + A36 × 363 + X36 × 362 + I36 × 361 + S36 × 360 = 25 × 365 + 27 × 364 + 10 × 363 + 33 × 362 + 18 × 361 + 28 × 360 = 25 × 60466176 + 27 × 1679616 + 10 × 46656 + 33 × 1296 + 18 × 36 + 28 × 1 = 1557514036. You are to write a function that takes a base-36 number as input and returns true if the number is prime and false if the number is composite.

Split A List: You are to write a function that takes an input list and returns two lists, the first half of the input list and the second half of the input list. If the input list has an odd number of elements, it is your choice in which half to place the center element. You are only permitted to scan the list once.

Your task is to write the three functions 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.

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 […]

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

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

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

```;;https://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

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