Velocity Reviews > Ruby > [SOLUTION][QUIZ] FizzBuzz (#126) [solution #1]

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

MenTaLguY
Guest
Posts: n/a

 06-05-2007
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
Guest
Posts: n/a

 06-06-2007
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[b][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] }
FIVE = ADD[TWO][THREE]
SIX = ADD[THREE][THREE]
SEVEN = ADD[FIVE][TWO]
EIGHT = ADD[FIVE][THREE]
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[s][LAMBDA { |k| rec[rec][f][f[s][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|
ZERO_P[q][ID][FLIP[rec[rec]][q]][CONS[ADD[r][CHAR_0]][s]]
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_i = ADD[A_HUNDRED][FIVE]
CHAR_z = ADD[A_HUNDRED][ADD[MULTIPLY[TWO][TEN]][TWO]]
CHAR_B = MULTIPLY[SIX][ADD[TEN][ONE]]
CHAR_u = ADD[A_HUNDRED][ADD[TEN][SEVEN]]

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 }][[]][s].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[i]] }]
][
LAMBDA { OUTPUT_STRING[CONS[CHAR_NEWLINE][NIL_]] }
]
][
LAMBDA { rec[rec][SUCC[i]][CDR[r]] }
][nil]
end[DIVISIBLE_BY_P[i][THREE]][DIVISIBLE_BY_P[i][FIVE]]
end][nil]
end }]

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

FIZZBUZZ[A_HUNDRED]

Joel VanderWerf
Guest
Posts: n/a

 06-06-2007
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

MenTaLguY
Guest
Posts: n/a

 06-06-2007
--=-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
reader.

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

iD8DBQBGZimbSuZBmZzm14ERAkRJAKDCEMBIIo2JN6MwZyYtFb NhKWVmZQCgtNT6
xMuk4StpuXruofgxo2OmZyg=
=qLIF
-----END PGP SIGNATURE-----

--=-CDSr6rtc6gt2MoSqYcIb--

James Edward Gray II
Guest
Posts: n/a

 06-06-2007
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

Brad Phelan
Guest
Posts: n/a

 06-06-2007
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

MenTaLguY
Guest
Posts: n/a

 06-07-2007
--=-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)

iD8DBQBGZ2yiSuZBmZzm14ERAoihAKCHqbO946qw6jrjFAyAS0 uVbw8yxQCePr67
TAHDqrtESdJh/r+Kgi6hLjM=
=BMRu
-----END PGP SIGNATURE-----

--=-jTvpSXKJkl41Tfq3wU9t--

MenTaLguY
Guest
Posts: n/a

 06-07-2007
--=-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
XJyADigFwFzb6a1CNXN5Vi0=
=+8jj
-----END PGP SIGNATURE-----

--=-fQeRyKvHwV87qm/WDkXj--

Robert Dober
Guest
Posts: n/a

 06-07-2007
On 6/7/07, MenTaLguY <(E-Mail Removed)> 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

Brad Phelan
Guest
Posts: n/a

 06-07-2007
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

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Bill Python 3 03-14-2010 11:25 AM globalrev Python 32 10-06-2008 09:50 AM Ruby Quiz Ruby 153 06-11-2007 08:50 AM Rick DeNatale Ruby 0 06-03-2007 02:48 PM Brian Adkins Ruby 31 03-08-2007 07:48 AM

Advertisments