Fizz Buzz without conditionals or booleans(evanhahn.com)
evanhahn.com
Fizz Buzz without conditionals or booleans
https://evanhahn.com/fizz-buzz-without-conditionals-or-booleans/
71 comments
challenged listeners to “write Fizz Buzz with no booleans, no conditionals, no pattern matching, or other things that are like disguised booleans.”
Without any other constraints, this is not an interesting challenge.
Without any other constraints, this is not an interesting challenge.
print("<precalculated output goes here>") prompt("please enter the expected output of a solution to the fizz buzz problem, without any further enclosing text or explanations; especially: do not enter program code")
The suckless approach
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
void fizzbuzz(int i) {
uint32_t r3 = i % 3;
uint32_t r5 = i % 5;
uint32_t is_nonzero_3 = (r3 | -r3) >> 31;
uint32_t is_nonzero_5 = (r5 | -r5) >> 31;
uint32_t is_zero_3 = is_nonzero_3 ^ 1;
uint32_t is_zero_5 = is_nonzero_5 ^ 1;
uint32_t idx = (is_zero_5 << 1) | is_zero_3;
const char *fmt[] = {
"%d\n",
"Fizz\n",
"Buzz\n",
"FizzBuzz\n"
};
printf(fmt[idx], i);
}
typedef void (*func_t)(int);
void run_loop(int i);
void stop_loop(int i) { exit(0); }
func_t actions[] = { stop_loop, run_loop };
void run_loop(int i) {
fizzbuzz(i);
int d = 99 - i;
uint32_t is_neg = ((uint32_t)d) >> 31;
}
func_t actions_table[] = { run_loop, stop_loop };
void run_loop_wrapper(int i) {
fizzbuzz(i);
int d = 99 - i;
uint32_t is_neg = ((uint32_t)d) >> 31;
actions_table[is_neg](i + 1);
}
int main() {
actions_table[0] = run_loop_wrapper;
run_loop_wrapper(1);
return 0;
}Obviously FizzBuzz is a property of integers
Integer extend [
fizzbuzz [
(self \\ 15 = 0)
ifTrue: ['fizzbuzz' printNl]
ifFalse: [
(self \\ 3 = 0)
ifTrue: ['fizz' printNl]
ifFalse: [
(self \\ 5 = 0)
ifTrue: ['buzz' printNl]
ifFalse: [self printNl]
]
]
]
]
1 to: 100 by: 1 do: [:i | i fizzbuzz]A for loop has a conditional in it.
Unless by conditionals we mean “no if/else” and not “no branch instructions”.
Unless by conditionals we mean “no if/else” and not “no branch instructions”.
The conditional here only makes it stop when it reaches 100. The solution can be adapted to use a while loop if you’re okay with it running indefinitely.
A loop either never halts or has a conditional. I guess a compiler could elide a “while True:” to a branch-less jump instruction.
One hack would be to use recursion and let stack exhaustion stop you.
One hack would be to use recursion and let stack exhaustion stop you.
Count down i from 100 to 0 and do 1/i at the end of the loop :)
[deleted]
You could allocate 100 bytes and get a segfault on 101
3 lines of python, no imports.
fizzbuzz = [None, None, "Fizz", None, "Buzz", "Fizz", None, None, "Fizz", "Buzz", None, "Fizz", None, None, "FizzBuzz"]
for i in range(1,100):
print(fizzbuzz[i % 15] or i)
does not "or" imply a boolean
It does.Will you accept max?
fizzbuzz = ["", "", "Fizz", "", "Buzz", "Fizz", "", "", "Fizz", "Buzz", "", "Fizz", "", "", "FizzBuzz"]
for i in range(1,101):
print(max((fizzbuzz[(i-1)% 15],str(i),)))
Doesn't a for loop contain a conditional? (If i <101)
That is in arbitrary line I am willing to draw in the battle against pedantry. Surely though a fizzbuzz isn't supposed to run forever though right? Gotta end it somehow, and the for loop is idiomatic.
It's a challenge and you can do whatever version you want.
If I'm pedantring about it it's because it can be done with a stricter restriction (or at least I think it can be done).
I'd also add that it isn't a particularly hard problem, so I would recommend that if you are having trouble with solving for the hardest interpretation of the problem, that you keep on trying because there is quite a simple solution.
If I were hiring based on this, your answer is a pass for sure. But it isn't exactly clear to me that you know about cpu comparisions or conditional jumps. In fact I think if you knew about them you wouldn't call it an arbitrary line.
I think there is a python solution as a prototype, but of course the robust solution would be in python to ensure control over the cpu instructions and avoid conditionals for good.
If I'm pedantring about it it's because it can be done with a stricter restriction (or at least I think it can be done).
I'd also add that it isn't a particularly hard problem, so I would recommend that if you are having trouble with solving for the hardest interpretation of the problem, that you keep on trying because there is quite a simple solution.
If I were hiring based on this, your answer is a pass for sure. But it isn't exactly clear to me that you know about cpu comparisions or conditional jumps. In fact I think if you knew about them you wouldn't call it an arbitrary line.
I think there is a python solution as a prototype, but of course the robust solution would be in python to ensure control over the cpu instructions and avoid conditionals for good.
You got me. I'd surely fail your interview. I admit I know nothing about CPU comparisons and conditional jumps.
I gave it a go in C (I wanted to do assembly but couldn't be arsed to write string to int and int to string conversions). [1] The trickiest part was figuring out how to terminate the program. My first attempt invoked nasal demons through dividing by zero, but I then realized I could intentionally cause a segfault with high probability (which is much better, right?). One could argue that my `fizz` and `buzz` variables are still "disguised booleans", but at least the generated assembly contains no branching or cmov instructions (aside from the ones inside libc functions like atoi and sprintf).
[1] https://gist.github.com/Andriamanitra/5c20f367dc4570dd5c8068...
[1] https://gist.github.com/Andriamanitra/5c20f367dc4570dd5c8068...
What's a "disguised Boolean" in this context?
[deleted]
I think it was more about doing it without a Boolean-based branch construct like a ternary or switch or whatever flavor of thing that abstracts away the explicit checks for true/false by other means. Idk though for sure
Something like this: https://entropicthoughts.com/fizzbuzz-through-monoids
I'd imagine that as any variable that only has two states.
[deleted]
No matter how you calculate FizzBuzz, it is bad engineering.
const Fizzbuzz = "1 2. Fizz, 4 ... "
Print FizzbuzzWhat’s the point of the game without booleans?
Much like stop50's solution, I also used the modulo, but I make use of the terminal to overwrite the number. It's only three lines of code, but I split up the list to be more readable on here.
This works from 1 to 100000000000000000000 before it overflows, and 100000000000000000000 is above the max size of a unsigned 64 bit int, so I feel that it's good enough
This works from 1 to 100000000000000000000 before it overflows, and 100000000000000000000 is above the max size of a unsigned 64 bit int, so I feel that it's good enough
fizzbuzz = [
"fizzbuzz ",
"", "",
"fizz ",
"",
"buzz ",
"fizz ",
"", "",
"fizz ",
"buzz ",
"",
"fizz ",
"", "" ]
for n in range(99999999999999999999-30, 100000000000000000000):
print(f"{n}\r{fizzbuzz[n%15]}")A for loop has an implicit conditional in its stop condition check.
I could see that both ways. Python’s for loops are different than, say, C’s, in that they always consume an iterator. The implementation is that it calls next(iter) until it raises a StopIteration exception, but you could argue that’s just an implementation detail and not cheating.
If you wanted to be more general, you could use map() to apply the function to every member of the iterator, and implementation details aside, that feels solidly in the spirit of the challenge.
If you wanted to be more general, you could use map() to apply the function to every member of the iterator, and implementation details aside, that feels solidly in the spirit of the challenge.
The dirty solution I wrote in Powershell does something similar:
1..100 | % {"$_ $(('fizz','')[$_%3])$(('buzz','')[$_%5])"}
I am not sure that using [$_%3] to index into a two-value array doesn't count as a "disguised boolean" thought.
1..100 | % {"$_ $(('fizz','')[$_%3])$(('buzz','')[$_%5])"}
I am not sure that using [$_%3] to index into a two-value array doesn't count as a "disguised boolean" thought.
Very nice.
Simple solution using modulo arithmetic and arrays. Relies on python shorthands that hides implicit branches for the number case though.
def main():
fizz_array = ["Fizz", "", ""]
buzz_array = ["Buzz", "", "", "", ""]
for n in range(1, 101):
# Use modulo to index into arrays
f = fizz_array[n % 3]
b = buzz_array[n % 5]
# Combine fizz and buzz
result = f + b
output = result + str(n)[len(result):]
print(output)
main()
output = result + str(n)[len(result):]vim +'exec "norm 99o"|%s/$/\=line(".")/|vert new|exec "norm i\r\rFizz\r\rBuzz\rFizz\r\r\rFizz\rBuzz\r\rFizz\r\r\rFizzBuzz"|exec "norm gg\<c-v>G$y"|bd!|let @q="10a \<esc>\"0gpj"|exec "norm gg10@q"|silent /100/+,$d|silent %s/\d\+\s\+\(\w\+\)/\1'
Now I see it's the same solution as in the post.
Edit: Actually all you need is vim -es +'exec "norm! i\r\rFizz\r\rBuzz\rFizz\r\r\rFizz\rBuzz\r\rFizz\r\r\rFizzBuzz\<esc>Vggy7P101GdG"|%s/^$/\=line(".")/|%p|q!'
Now I see it's the same solution as in the post.
Edit: Actually all you need is vim -es +'exec "norm! i\r\rFizz\r\rBuzz\rFizz\r\r\rFizz\rBuzz\r\rFizz\r\r\rFizzBuzz\<esc>Vggy7P101GdG"|%s/^$/\=line(".")/|%p|q!'
> No disguised booleans
Do indexes count? If not, there's a simple one liner
Do indexes count? If not, there's a simple one liner
def fizzbuzz(n):
return [str(n), "fizz", "buzz", "fizzbuzz"][1-min(1, n%3) + (1-min(1,n%5))*2]Here's my attempt:
# Multi-pass FizzBuzz
n = 100
# [['1'], ['2'], ['3'], ['4'], ['5'], ...]
seq = [[str(i)] for i in range(1, n + 1)]
# [['1'], ['2'], ['3', 'Fizz'], ['4'], ['5'], ...]
for i in range(3, n + 1, 3):
seq[i-1].append('Fizz')
# [['1'], ['2'], ['3', 'Fizz'], ['4'], ['5', 'Buzz'], ..., ['15', ''Fizz', 'Buzz'], ...]
for i in range(5, n + 1, 5):
seq[i-1].append('Buzz')
# Arithmetic equivalent to:
# len=1 -> the whole thing (from zero to end, because zero = -zero)
# len=2 -> the length-1 suffix (just Fizz or Buzz)
# len=3 -> the length-2 suffix (Fizz and Buzz)
# The branch is hidden in the slice syntax:
# Python has to check whether `x` is negative in `terms[x:]`.
for terms in seq:
print(''.join(terms[-(len(terms) - 1):]))
# Single-pass FizzBuzz
n = 100
def numbers():
for i in range(1, n+1):
yield [str(i)]
def fizzies():
nums = numbers()
try:
while True:
yield next(nums)
yield next(nums)
yield [*next(nums), 'Fizz']
except StopIteration:
pass
def buzzies():
fzs = fizzies()
try:
while True:
yield next(fzs)
yield next(fzs)
yield next(fzs)
yield next(fzs)
yield [*next(fzs), 'Buzz']
except StopIteration:
pass
for terms in buzzies():
print(''.join(terms[-(len(terms) - 1):]))
def numbers(i=1):
yield [str(i)]
yield from numbers(i+1)
def fizzies(source=numbers()):
yield next(source)
yield next(source)
yield [*next(source), 'Fizz']
yield from fizzies(source)
def buzzies(source=fizzies()):
yield next(source)
yield next(source)
yield next(source)
yield next(source)
yield [*next(source), 'Buzz']
yield from buzzies(source)
def main(source=buzzies()):
terms = next(source)
print(''.join(terms[1-len(terms):]))
main(source)
main()Enumerating all values probably can't be done in python as that requires some sort of unchecked loop construct, that is a goto or bare loop nether of which is present in python. perhaps a recursive solution(throws up a little in mouth)
baring that I too got nerd sniped by this and unsatisfied by the limitations of the authors solution here is my attempt. and when I read up on fizzbuz to make sure I was solving the correct thing. (I was not and my elegant duel state engine was wasted) it turns out the problem solution could be as simple as
baring that I too got nerd sniped by this and unsatisfied by the limitations of the authors solution here is my attempt. and when I read up on fizzbuz to make sure I was solving the correct thing. (I was not and my elegant duel state engine was wasted) it turns out the problem solution could be as simple as
f_out = ['', '', 'fizz']
b_out = ['', '', '', '', 'buzz']
def fizz_buz(n):
return(f_out[n % 3] + b_out[n % 5])
f_state = {
0:1,
1:2,
2:0,
}
b_state = {
0:1,
1:2,
2:3,
3:4,
4:0,
}
def fizz_buzz_all():
f_index = 0
b_index = 0
while 1: #how to loop with no end check?
print(f_out([f_index] + b_out[b_index] )
f_index = f_state[f_index]
b_index = b_state[b_index]
def fizz_buzz_recurse(n):
print(fizz_buzz(n))
fizz_buzz_recurse(n + 1)Make it throw an exception with an index out of bounds to terminate the loop.
You can replace `while 1:` with `for x in iter(int, 1):` .
from itertools import cycle
fizz = cycle(["","","fizz"])
buzz = cycle(["","","","","buzz"])
for z in zip(fizz,buzz):
print(f"{z[0]}{z[1]}")When I find a problem I can solve with ciclical structures I always feel like Da Vinci.
Fizzbuzz is probably the perfect fit, which is sad since it is a synthetic problem. I did find one problem once where I could save about 30s of user waiting time by generating (had to be done dynamically) wheels in the 3-10k element range.
Fizzbuzz is probably the perfect fit, which is sad since it is a synthetic problem. I did find one problem once where I could save about 30s of user waiting time by generating (had to be done dynamically) wheels in the 3-10k element range.
Doesn't look right. The numbers are missing from the output. If you don't print the numbers, sure it's trivial.
I didn't know that was a requirement. OK then
from itertools import cycle
fizz = cycle(["","","fizz"])
buzz = cycle(["","","","","buzz"])
for idx, z in enumerate(zip(fizz,buzz)):
print(f"{idx}: {z[0]}{z[1]}")
This doesn't look right either. You should really look up what FizzBuzz is. The output should be like:
1
2
fizz
4
buzz
fizz
I should really look it up because it’s such an important thing to get canonically correct.
It's not important to look it up. I only suggested it because you posted two programs and neither solve the problem people are discussing here. If you really want to solve a boring version of the problem, by all means you should. I'm nobody to tell you otherwise.
All I'm saying is that if you water the problem down into something trivial and boring, the solution will be trivial and boring too. No surprise there. The other answers here are more complicated because they solve the canonical FizzBuzz problem, not the boring version of it that is trivial to solve without conditionals.
All I'm saying is that if you water the problem down into something trivial and boring, the solution will be trivial and boring too. No surprise there. The other answers here are more complicated because they solve the canonical FizzBuzz problem, not the boring version of it that is trivial to solve without conditionals.
it's more that fizzbuzz i think is one of the - if not the - simplest way to see if people understand requirements. some of the comments here remind me of thedailywtf.com comment sections.
being correct is good and being confused is bad
How about:
print(filter(None, [f + b, str(n)])[0])
I always wanted to write this with duff's device. switch with fall through is almost never a good thing but it allows for some 'interesting' tricks. Wouldn't be hard, but I have kids so finding half an hour to concentrate is hard.
Answer: Modulo or adding "%3" and "%5" before masking it
package main
import (
"fmt"
"math/rand"
)
var fb [4]string = [4]string{"", "fizz", "buzz", "fizzbuzz"}
var lucky int64 = 176064004
func main() {
for i := 1; i <= 100; i++ {
if i%15 == 1 {
rand.Seed(lucky)
}
fmt.Printf("%d: %s\n", i, fb[rand.Int63()%4])
}
}There's a conditional, though?
Yeah this is weird. It's against the rules to speculate about whether a commenter read the article, but what about the title of the article?
I did, in fact, read the article. I've offered my subversive FizzBuzz as an alternative. It's not according to the article's rules, but it's definitely against the grain of the normal FizzBuzz.
Sigh…
Saying the code doesn’t have conditions or booleans is only true if you completely ignore how the functions being called are being implemented.
Cycle involves conditionals, zip involves conditionals, range involves conditionals, array access involves conditionals, the string concatenation involves conditionals, the iterator expansion in the for loop involves conditionals.
This has orders of magnitude more conditionals than normal fizz buzz would.
Even the function calls involve conditionals (python uses dynamic dispatch). Even if call site caching is used to avoid repeated name lookups, that involves conditionals.
There is not a line of code in that file (even the import statement) that does not use at least one conditional.
So… interesting implementation, but it’s not “fizzbuzz without booleans or conditionals”.
Saying the code doesn’t have conditions or booleans is only true if you completely ignore how the functions being called are being implemented.
Cycle involves conditionals, zip involves conditionals, range involves conditionals, array access involves conditionals, the string concatenation involves conditionals, the iterator expansion in the for loop involves conditionals.
This has orders of magnitude more conditionals than normal fizz buzz would.
Even the function calls involve conditionals (python uses dynamic dispatch). Even if call site caching is used to avoid repeated name lookups, that involves conditionals.
There is not a line of code in that file (even the import statement) that does not use at least one conditional.
So… interesting implementation, but it’s not “fizzbuzz without booleans or conditionals”.
Not sure why this got downvoted.
The technique could be implemented without conditionals, but not in python, and not using iterators.
You could do it in C, and use & and ~ to make the cyclic counters work.
But, like I mentioned, the code in the article is very far from being free of conditionals.
The technique could be implemented without conditionals, but not in python, and not using iterators.
You could do it in C, and use & and ~ to make the cyclic counters work.
But, like I mentioned, the code in the article is very far from being free of conditionals.
I didn't down vote, but it does seem like unnecessary pedantry. Maybe it could be better phrased as "without writing any conditionals"
I think that’s kind of vacuously true. Like, good luck writing this in any language where the resulting assembler all the way at the bottom of the runtime has zero branch operations. And I bet even then that most CPUs’ microcode or superscalar engine would have conditionals underlying the opcodes.
I’d settle for just not writing conditionals in the user’s own code. Range doesn’t have to be implemented with branches. Hypothetically, Python could prefill a long list of ints, and range could return the appropriate slice of it. That’d be goofy, of course, but the main idea is that the user doesn’t know or really care exactly how range() was written and optimized.
I’d settle for just not writing conditionals in the user’s own code. Range doesn’t have to be implemented with branches. Hypothetically, Python could prefill a long list of ints, and range could return the appropriate slice of it. That’d be goofy, of course, but the main idea is that the user doesn’t know or really care exactly how range() was written and optimized.
What exactly are we counting as “a conditional”? Is it only “if” statements? Do “case” or “switch” statements count? Do loops with loop conditions count? Do all the included functions being abused count for all the conditionals in them? Do short-circuited boolean operations count, or only boolean variables?
I mean, if we want to play fast and loose with those definitions then this also has no conditionals and no booleans.(Warning: Perl, somewhat golfed)
I mean, if we want to play fast and loose with those definitions then this also has no conditionals and no booleans.(Warning: Perl, somewhat golfed)
$s = '', $i % 3 || ($s .= 'fizz'), $i % 5 || ($s .= 'buzz'), $s ||= $i, print "$s\n" while (++$i < 101)What is the canonical formulation of FizzBuzz?
i've seen worse than this sort of thing:
https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpris...
https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpris...
This is pretty cool, actually
itertools.count is probably what OP is looking for