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

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

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]

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.

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

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

-mental