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

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

  1. MenTaLguY

    MenTaLguY Guest

    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
    #1
    1. Advertising

  2. MenTaLguY

    MenTaLguY Guest

    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] }
    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[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|
    ZERO_P[q][ID][FLIP[rec[rec]][q]][CONS[ADD[r][CHAR_0]]]
    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 }][[]].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
    #2
    1. Advertising

  3. 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
    #3
  4. MenTaLguY

    MenTaLguY Guest

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

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

    --=-CDSr6rtc6gt2MoSqYcIb--
     
    MenTaLguY, Jun 6, 2007
    #4
  5. 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
    #5
  6. MenTaLguY

    Brad Phelan Guest

    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
     
    Brad Phelan, Jun 6, 2007
    #6
  7. MenTaLguY

    MenTaLguY Guest

    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
    #7
  8. MenTaLguY

    MenTaLguY Guest

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

    --=-fQeRyKvHwV87qm/WDkXj--
     
    MenTaLguY, Jun 7, 2007
    #8
  9. MenTaLguY

    Robert Dober Guest

    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
    #9
  10. MenTaLguY

    Brad Phelan Guest

    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
     
    Brad Phelan, Jun 7, 2007
    #10
  11. MenTaLguY

    MenTaLguY Guest

    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
    #11
  12. MenTaLguY

    MenTaLguY Guest

    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
    #12
  13. MenTaLguY

    MenTaLguY Guest

    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
    attr_reader :value

    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
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ruby Quiz

    [QUIZ] FizzBuzz (#126)

    Ruby Quiz, Jun 1, 2007, in forum: Ruby
    Replies:
    153
    Views:
    1,361
    Brad Phelan
    Jun 11, 2007
  2. Rick DeNatale
    Replies:
    0
    Views:
    118
    Rick DeNatale
    Jun 3, 2007
  3. philip

    [solution] quizz 126

    philip, Jun 3, 2007, in forum: Ruby
    Replies:
    0
    Views:
    126
    philip
    Jun 3, 2007
  4. doug meyer

    [QUIZ] FizzBuzz (#126) [SOLUTION]

    doug meyer, Jun 3, 2007, in forum: Ruby
    Replies:
    0
    Views:
    152
    doug meyer
    Jun 3, 2007
  5. Ruby Quiz

    [SUMMARY] FizzBuzz (#126)

    Ruby Quiz, Jun 7, 2007, in forum: Ruby
    Replies:
    0
    Views:
    97
    Ruby Quiz
    Jun 7, 2007
Loading...

Share This Page