Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fizz Buzz without conditionals or booleans

evanhahn.com

Post reply on HN
Print view View original

31–40 of 72 posts

Re: Fizz Buzz without conditionals or booleans

#31

Post by abustamam »

swisniewski wrote: post #17
swisniewski wrote: post #12

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 condi…

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.

I didn't down vote, but it does seem like unnecessary pedantry. Maybe it could be better phrased as "without writing any conditionals"

Re: Fizz Buzz without conditionals or booleans

#32

Post by nodja »

kiratp wrote: post #28
WhyNotHugo wrote: post #26

Earlier quoted context omitted.

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.

Count down i from 100 to 0 and do 1/i at the end of the loop :)

Re: Fizz Buzz without conditionals or booleans

#33

Post by buzer »

kiratp wrote: post #28
WhyNotHugo wrote: post #26

Earlier quoted context omitted.

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.

Other would be to use goto (though Python doesn't have it) & introduce something that will panic/throw exception, like creating variable with value 1/(max-i).

Re: Fizz Buzz without conditionals or booleans

#35

Post by hug »

kstrauser wrote: post #30
kiratp wrote: post #24

Earlier quoted context omitted.

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 a…

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.

Re: Fizz Buzz without conditionals or booleans

#36

Post by kstrauser »

swisniewski wrote: post #12

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 condi…

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.

Re: Fizz Buzz without conditionals or booleans

#37

Post by MathMonkeyMan »

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):]))
Here's a version that uses generators instead of multiple passes over a list:

    # 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):]))
Edit: Can't resist -- unbounded without loops, but recursion blows the call stack (granted, well after 100):

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

Re: Fizz Buzz without conditionals or booleans

#38

Post by andriamanitra »

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

Re: Fizz Buzz without conditionals or booleans

#40

Post by kqr »

brudgers wrote: post #27

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]

How is this without conditionals?
Post reply on HN