# [SOLUTION][QUIZ] FizzBuzz (#126) [solution #1]

Discussion in 'Ruby' started by MenTaLguY, Jun 5, 2007.

1. ### MenTaLguYGuest

I've got two solutions this go-round. First, the solution I would present were I asked to do this in an actual job interview:

for n in 1..100
mult_3 = ( n % 3 ).zero?
mult_5 = ( n % 5 ).zero?
if mult_3 or mult_5
print "Fizz" if mult_3
print "Buzz" if mult_5
else
print n
end
puts
end

-mental

MenTaLguY, Jun 5, 2007

2. ### MenTaLguYGuest

Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

And, here's my second one, written in a subset of Ruby which corresponds
to a pure (though strict) lambda calculus, building up numbers, strings,
and everything else entirely from scratch. (Okay, I cheated a little
bit for actual IO)

Sadly Church numerals are very slow for non-tiny numbers, and Ruby
doesn't do tail recursion optimization which just makes matters worse.
But it does work, given enough time and stack space. Try running it and
see how high you can get!

-mental

alias LAMBDA lambda
def LAMBDA2(&f) ; LAMBDA { |x| LAMBDA { |y| f[x, y] } } ; end
def LAMBDA3(&f) ; LAMBDA { |x| LAMBDA { |y| LAMBDA { |z| f[x, y, z] } } } ; end

U = LAMBDA { |f| f[f] }

ID = LAMBDA { |x| x }
CONST = LAMBDA2 { |y, x| y }
FLIP = LAMBDA3 { |f,a,b| f[a] }
COMPOSE = LAMBDA3 { |f,g,x| f[g[x]] }

ZERO = CONST[ID]
SUCC = LAMBDA3 { |n,f,x| f[n[f][x]] }
ONE = SUCC[ZERO]
TWO = SUCC[ONE]
THREE = SUCC[TWO]
ADD = LAMBDA { |n| n[SUCC] }
MULTIPLY = COMPOSE
FOUR = MULTIPLY[TWO][TWO]
NINE = MULTIPLY[THREE][THREE]
TEN = MULTIPLY[FIVE][TWO]
POWER = LAMBDA2 { |m, n| n[m] }
A_HUNDRED = POWER[TEN][TWO]

FALSE_ = ZERO
TRUE_ = CONST
NOT = FLIP
OR = LAMBDA2 { |m,n| m[m][n] }
AND = LAMBDA2 { |m,n| m[n][m] }

ZERO_P = LAMBDA { |n| n[CONST[FALSE_]][TRUE_] }

NIL_ = LAMBDA { |o| o[nil][TRUE_] }
CONS = LAMBDA2 { |h,t| LAMBDA { |o| o[LAMBDA { |g| g[h][t] }][FALSE_] } }
NULL_P = LAMBDA { |p| p[FALSE_] }
CAR = LAMBDA { |p| p[TRUE_][TRUE_] }
CDR = LAMBDA { |p| p[TRUE_][FALSE_] }
GUARD_NULL = LAMBDA3 { |d,f,l| NULL_P[l][CONST[d]][f][l] }
FOLDL = U[LAMBDA { |rec| LAMBDA3 { |f,s,l| GUARD_NULL[LAMBDA { |k| rec[rec][f][f[CAR[k]]][CDR[k]] }][l] } }]
DROP = LAMBDA { |n| n[GUARD_NULL[NIL_][CDR]] }
LENGTH = FOLDL[LAMBDA2 { |a, e| SUCC[a] }][ZERO]

MAKE_LIST = LAMBDA2 { |v,n| n[LAMBDA { |p| CONS[v][p] }][NIL_] }

LESSER_P = LAMBDA2 { |m,n| NOT[NULL_P[DROP[m][MAKE_LIST[ID][n]]]] }

DIVMOD_HELPER = U[LAMBDA { |rec| LAMBDA3 do |q,l,n|
NULL_P[l][CONST[CONS[q][ZERO]]][
LAMBDA2 do |r, t|
AND[NULL_P[t]][LESSER_P[r][n]][CONST[CONS[q][r]]][
rec[rec][SUCC[q]][t]
][n]
end[LENGTH[l]]
][DROP[n][l]]
end }]
DIVMOD = LAMBDA2 { |m,n| DIVMOD_HELPER[ZERO][MAKE_LIST[ID][m]][n] }

DIVISIBLE_BY_P = LAMBDA2 { |m,n| ZERO_P[CDR[DIVMOD[m][n]]] }

CHAR_0 = MULTIPLY[SIX][EIGHT]

FORMAT_NUM_HELPER = U[LAMBDA { |rec| LAMBDA2 do |s, n|
LAMBDA do |qr|
LAMBDA2 do |q, r|
end[CAR[qr]][CDR[qr]]
end[DIVMOD[n][TEN]]
end }]

FORMAT_NUM = LAMBDA do |n|
ZERO_P[n][CONST[CONS[CHAR_0][NIL_]]][FORMAT_NUM_HELPER[NIL_]][n]
end

CHAR_F = MULTIPLY[SEVEN][TEN]

CHAR_NEWLINE = TEN

FIZZ = CONS[CHAR_F][CONS[CHAR_i][CONS[CHAR_z][CONS[CHAR_z][NIL_]]]]
BUZZ = CONS[CHAR_B][CONS[CHAR_u][CONS[CHAR_z][CONS[CHAR_z][NIL_]]]]

OUTPUT_STRING = LAMBDA do |s|
print FOLDL[LAMBDA2 { |a,e| a << e }][[]].map { |i| i[LAMBDA { |s| s + 1 }][0] }.pack("C*")
end

SEQUENCE = FLIP[COMPOSE]

FIZZBUZZ_HELPER = U[LAMBDA { |rec| LAMBDA2 do |i,r|
NULL_P[r][ID][LAMBDA do
LAMBDA2 do |mult_3, mult_5|
SEQUENCE[
SEQUENCE[
OR[mult_3][mult_5][
SEQUENCE[
mult_3[LAMBDA { OUTPUT_STRING[FIZZ] }][ID]
][
mult_5[LAMBDA { OUTPUT_STRING[BUZZ] }][ID]
]
][LAMBDA { OUTPUT_STRING[FORMAT_NUM] }]
][
LAMBDA { OUTPUT_STRING[CONS[CHAR_NEWLINE][NIL_]] }
]
][
LAMBDA { rec[rec][SUCC][CDR[r]] }
][nil]
end[DIVISIBLE_BY_P[THREE]][DIVISIBLE_BY_P[FIVE]]
end][nil]
end }]

FIZZBUZZ = LAMBDA do |c|
FIZZBUZZ_HELPER[ONE][MAKE_LIST[ID][c]]
end

FIZZBUZZ[A_HUNDRED]

MenTaLguY, Jun 6, 2007

3. ### Joel VanderWerfGuest

Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

MenTaLguY wrote:
> And, here's my second one, written in a subset of Ruby which corresponds
> to a pure (though strict) lambda calculus, building up numbers, strings,
> and everything else entirely from scratch. (Okay, I cheated a little
> bit for actual IO)
>
> Sadly Church numerals are very slow for non-tiny numbers, and Ruby
> doesn't do tail recursion optimization which just makes matters worse.
> But it does work, given enough time and stack space. Try running it and
> see how high you can get!

Ok, you're hired. Your first project is to write a web server in Malbolge.

--
vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

Joel VanderWerf, Jun 6, 2007
4. ### MenTaLguYGuest

Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

--=-CDSr6rtc6gt2MoSqYcIb
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

Incidentally, this second solution could probably be made to run in a
reasonable time if the mod-15 pattern in the output were exploited. But
I'm lambda'd out at the moment, so it will remain an exercise for the

-mental

--=-CDSr6rtc6gt2MoSqYcIb
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)

iD8DBQBGZimbSuZBmZzm14ERAkRJAKDCEMBIIo2JN6MwZyYtFbNhKWVmZQCgtNT6
xMuk4StpuXruofgxo2OmZyg=
=qLIF
-----END PGP SIGNATURE-----

--=-CDSr6rtc6gt2MoSqYcIb--

MenTaLguY, Jun 6, 2007
5. ### James Edward Gray IIGuest

Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

On Jun 5, 2007, at 8:36 PM, MenTaLguY wrote:

> And, here's my second one, written in a subset of Ruby which
> corresponds to a pure (though strict) lambda calculus, building up
> numbers, strings, and everything else entirely from scratch.
> (Okay, I cheated a little bit for actual IO)

That is wild.

I'm just staring at the code. I know enlightenment is hidden in
there somewhere...

James Edward Gray II

James Edward Gray II, Jun 6, 2007
6. ### Brad PhelanGuest

Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

MenTaLguY wrote:
> And, here's my second one, written in a subset of Ruby which corresponds
> to a pure (though strict) lambda calculus, building up numbers, strings,
> and everything else entirely from scratch. (Okay, I cheated a little
> bit for actual IO)
>
> Sadly Church numerals are very slow for non-tiny numbers, and Ruby
> doesn't do tail recursion optimization which just makes matters worse.
> But it does work, given enough time and stack space. Try running it and
> see how high you can get!

I thought it was randomly generated joke code jibberish till I copied
and ran it and it worked .. slowly. So I started revising my lambda
calculus till my brain hurt... So I ask a question...

Using your Ruby Church numerals is it possible to test for equality?
Perhapps you are doing it but I was unable to parse the
whole algorithm out and figure out exactly what all the lambdas
you use do.

Cheers

Brad Phelan, Jun 6, 2007
7. ### MenTaLguYGuest

Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

--=-jTvpSXKJkl41Tfq3wU9t
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

On Thu, 2007-06-07 at 02:25 +0900, Brad Phelan wrote:
> Using your Ruby Church numerals is it possible to test for equality?=20

Sure!

EQUAL_P =3D LAMBDA2 { |m,n| NOT[OR[LESSER_P[m][n]][LESSER_P[n][m]]] }

-mental

--=-jTvpSXKJkl41Tfq3wU9t
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)

iD8DBQBGZ2yiSuZBmZzm14ERAoihAKCHqbO946qw6jrjFAyAS0uVbw8yxQCePr67
TAHDqrtESdJh/r+Kgi6hLjM=
=BMRu
-----END PGP SIGNATURE-----

--=-jTvpSXKJkl41Tfq3wU9t--

MenTaLguY, Jun 7, 2007
8. ### MenTaLguYGuest

Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

--=-fQeRyKvHwV87qm/WDkXj
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

On Thu, 2007-06-07 at 02:25 +0900, Brad Phelan wrote:
> Perhapps you are doing it but I was unable to parse the
> whole algorithm out and figure out exactly what all the lambdas
> you use do.

If it helps, what a lot of the math stuff does is create lists of the
length specified by a number, manipulate those, and then count their
lengths to get back to a number. For instance, subtraction would be:

SUBTRACT =3D LAMBDA2 { |m,n| LENGTH[DROP[n][MAKE_LIST[ID][m]]] }

(here, ID is just used as a dummy value to populate the list with)

-mental

--=-fQeRyKvHwV87qm/WDkXj
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)

iD8DBQBGZ4rLSuZBmZzm14ERApC/AJ4v49mNvUhEl2sD/1NOFE1m5a1qVACgue23
=+8jj
-----END PGP SIGNATURE-----

--=-fQeRyKvHwV87qm/WDkXj--

MenTaLguY, Jun 7, 2007
9. ### Robert DoberGuest

Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

On 6/7/07, MenTaLguY <> wrote:
> On Thu, 2007-06-07 at 02:25 +0900, Brad Phelan wrote:
> > Perhapps you are doing it but I was unable to parse the
> > whole algorithm out and figure out exactly what all the lambdas
> > you use do.

>
> If it helps, what a lot of the math stuff does is create lists of the
> length specified by a number, manipulate those, and then count their
> lengths to get back to a number. For instance, subtraction would be:
>
> SUBTRACT = LAMBDA2 { |m,n| LENGTH[DROP[n][MAKE_LIST[ID][m]]] }

must work nicely for n>m
But interesting stuff.

Cheers
Robert
>
> (here, ID is just used as a dummy value to populate the list with)
>
> -mental
>
>

--
You see things; and you say Why?
But I dream things that never were; and I say Why not?
-- George Bernard Shaw

Robert Dober, Jun 7, 2007
10. ### Brad PhelanGuest

Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

MenTaLguY wrote:
> On Thu, 2007-06-07 at 02:25 +0900, Brad Phelan wrote:
>> Perhapps you are doing it but I was unable to parse the
>> whole algorithm out and figure out exactly what all the lambdas
>> you use do.

>
> If it helps, what a lot of the math stuff does is create lists of the
> length specified by a number, manipulate those, and then count their
> lengths to get back to a number. For instance, subtraction would be:
>
> SUBTRACT = LAMBDA2 { |m,n| LENGTH[DROP[n][MAKE_LIST[ID][m]]] }
>
> (here, ID is just used as a dummy value to populate the list with)
>
> -mental

Thanks for the pointers. I don't have too much time today to think about
this ( public holiday and I'm going out in the sun ) but I know when
I do I'll want to know the concept here behind lists. Are they real
lists as in Ruby Array which I doubt or abstract concepts like
the Church Numerals.

I'll take a look Monday and see if I can understand more.

Regards

Brad Phelan, Jun 7, 2007
11. ### MenTaLguYGuest

Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

On Thu, 7 Jun 2007 18:04:02 +0900, "Robert Dober" <> wrote:
>> SUBTRACT = LAMBDA2 { |m,n| LENGTH[DROP[n][MAKE_LIST[ID][m]]] }

> must work nicely for n>m

Church numerals correspond to the natural numbers, so negative results aren't possible. For n>m, I could either let the computation diverge or return ZERO -- I opted to return ZERO.

It is possible to build a representation of general integers atop Church numerals (one obvious way would be to use a pair consisting of a sign flag and a magnitude), but that was more than I needed for this particular problem.

-mental

MenTaLguY, Jun 7, 2007
12. ### MenTaLguYGuest

Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

On Thu, 7 Jun 2007 20:45:04 +0900, Brad Phelan <> wrote:
> Thanks for the pointers. I don't have too much time today to think about
> this ( public holiday and I'm going out in the sun ) but I know when
> I do I'll want to know the concept here behind lists.

Lists are linked lists made of pairs, as in Lisp. Since we chose to represent true and false as two-argument functions which return their first or second argument, respectively, we can take advantage of this to describe a pair as a function which takes true or false as an argument to select an element of the pair.

Such a pair can be created by a function like:

MAKE_PAIR = LAMBDA2 { |first, second| LAMBDA { |which| which[first][second] } }

And functions for extracting the first or second value from a pair constructed by MAKE_PAIR can be written like this:

FIRST = LAMBDA { |pair| pair[TRUE_] }
SECOND = LAMBDA { |pair| pair[FALSE_] }

My definitions for CONS, CAR, and CDR in fizzbuzz were a little more involved, because I also needed to be able to represent an empty list (and test for it). So, what I did is roughly equivalent to:

NIL_ = MAKE_PAIR[nil][TRUE_]
CONS = LAMBDA2 { |head, tail| MAKE_PAIR[MAKE_PAIR[head, tail]][FALSE_] }
CAR = LAMBDA { |cell| FIRST[FIRST[cell]] }
CDR = LAMBDA { |cell| SECOND[FIRST[cell]] }
NULL_P = LAMBDA { |cell| SECOND[cell] }

A tagged data structure, basically, with a flag indicating whether a cell is a null list or not.

-mental

MenTaLguY, Jun 7, 2007
13. ### MenTaLguYGuest

Re: [SOLUTION][QUIZ] FizzBuzz (#126) [solution #2]

On Thu, 7 Jun 2007 20:45:04 +0900, Brad Phelan <> wrote:
> Are they real lists as in Ruby Array which I doubt or abstract concepts like
> the Church Numerals.

In some sense, these things are only as abstract as you want them to be. Instead of implementing Church numerals like this (expanded a bit for clarity):

ZERO = LAMBDA2 { |f,x| x }
ONE = LAMBDA2 { |f,x| f[x] }
SUCC = LAMBDA { |n| LAMBDA2 { |f,x| f[n[f][x]] } }
ADD = LAMBDA2 { |m,n| m[SUCC][n] }
MULTIPLY = LAMBDA2 { |m,n| LAMBDA2 { |f,x| m[n[f]][x] } }
POWER = LAMBDA2 { |m,n| n[m] }

I could also have done something like this:

class ChurchNumeral

def initialize(value)
@value = value
end

def call(f)
LAMBDA { |x| @value.times { x = f[x] } ; x }
end
alias [] call
end

ZERO = ChurchNumeral.new 0
ONE = ChurchNumeral.new 1
SUCC = LAMBDA do |n|
if ChurchNumeral === n
ChurchNumeral.new n.value + 1
else
LAMBDA2 { |f,x| f[n[f][x]] }
end
end
ADD = LAMBDA2 do |m,n|
if ChurchNumeral === m and ChurchNumeral === n
ChurchNumeral.new m.value + n.value
else
m[SUCC][n]
end
end
MULTIPLY = LAMBDA2 do |m,n|
if ChurchNumeral === m and ChurchNumeral === n
ChurchNumeral.new m.value * n.value
else
LAMBDA2 { |f,x| m[n[f]][x] }
end
end
POWER = LAMBDA2 do |m,n|
if ChurchNumeral === m and ChurchNumeral === n
ChurchNumeral.new m.value ** n.value
else
n[m]
end
end

As described in my previous email, I did take the former sort of approach for lists though.

-mental

MenTaLguY, Jun 7, 2007