CTF Writeup: return of fzz buzz
I didn’t formally compete in ACM UMN’s 2025 Spring CTF last week (I provided a challenge and had access to the others, so I was ineligible), but I did try to complete one of the challenges, “return of fzz buzz.”
It was a lot of fun, and the writeup seemed like a good way to showcase some program reasoning stuff that we teach in our functional programming course in a setting that’s totally outside the classroom.
The challenge is as follows:
Oh no, keys are breakng on my keyboard!! Please help me wrte Fzz Buzz usng Python, but wth a twst!
Read 1 lne of nput as n, a, b.
For ntegers 1 .. n.
- dvsble by a => prnt
"Fizz"
- dvsble by b => prnt
"Buzz"
- dvsble by both => prnt
"FizzBuzz"
- otherwse => prnt the number
You get 2000 chars of source, no eval/exec, most of stdlb dsabled
Example nput
12 2 3
Example output
1
Fizz
Buzz
Fizz
5
FizzBuzz
7
Fizz
Buzz
Fizz
11
FizzBuzz
The “broken keys” turn out to be Ii and :; — our code can’t contain any of those four characters. The standard library modules that were removed also turned out to essentially just be those involved in performing IO, so we can’t do a reverse shell or something similar.
The straightforward solution would essentially be:
n, a, b = map(int, input().split())
for i in range(1, n + 1):
if i % b != 0:
if i % a != 0:
print(i)
else:
print("Fizz")
else:
if i % a != 0:
print("Buzz")
else:
print("FizzBuzz")
There are three main problems with using this code for this challenge.
- The expression
map(int, input().split())
is full ofi
’s, andprint
has one too. - We can’t use
if
to branch, since theif
keyword has ani
in it. This applies to bothif
statements (which also have a:
) andif
expressions (likex = (3 if y == z else 4)
). - We can’t use
for
orwhile
to iterate, or even a list comprehension or generator expression — the former two require a:
, while the latter two require thein
keyword.
We can do some mild refactoring to split these problems up from each other:
n, a, b = map(int, input().split())
def fizzbuzz_one(i) -> str:
if i % b != 0:
if i % a != 0:
return str(i)
else:
return "Fizz"
else:
if i % a != 0:
return "Buzz"
else:
return "FizzBuzz"
for i in range(1, n + 1):
out = fizzbuzz_one(i)
print(out)
Now, we can look at solving each problem separately. This is gonna be a bit long, since I hope this can introduce people unfamiliar with these kinds of tricks to them, plus jog some readers’ memories of their functional programming courses.
Builtin Functions and IO
The first thing to do will be to read the n
, a
, and b
parameters, and find a way to print
our eventual output.
Not being able to use i
means we can’t just call print
or input
.
This is actually fairly easy to work around, with some knowledge about where builtin functions in Python come from.
First, we define j
to be the string i
.
We do this with the chr
function, which accepts a Unicode code point and returns a string with that single code point in it.
j = chr(105)
We can use j
in format strings to (relatively) readably write strings with i
in them (e.g. f"str{j}ng"
instead of "string"
).
With this, we can get access to builtin functions like print via the builtins module, which is available via globals()["__builtins__"]
.
bujltjns = globals()[f"__bu{j}lt{j}ns__"]
This module contains all the familiar (and some unfamiliar) pre-defined functions in Python.
We start by getting access to the input
, int
, list
, and print
functions.
getattr
is the function equivalent of the dot operator, so getattr(x, "y")
is the equivalent of x.y
and getattr(bujltjns, "list")
is the equivalent of bujltjns.list
.
jnput = getattr(bujltjns, f"{j}nput")
jnt = getattr(bujltjns, f"{j}nt")
ljst = getattr(bujltjns, f"l{j}st")
prjnt = getattr(bujltjns, f"pr{j}nt")
Next, we’ll need the functools.partial
function.
This lets us construct a new callable object with some parameters already provided to a function, like what currying lets us do in many functional languages.
This lets us avoid writing some lambdas (which we can’t use because they contain :
), which will end up being pretty useful.
This also makes functools
the first module we need to import.
We can’t use the import
keyword as-is, because it contains an i
.
Instead, we can rely on another builtin function — __import__
.
Since this is just a normal function, we can get it the same way we got print
and use it to do the import.
jmport = getattr(bujltjns, f"__{j}mport__")
partjal = getattr(jmport("functools"), f"part{j}al")
With all the parts we have, we can read the inputs to our program.
Note that we can use getattr
for method calls as well.
n, a, b = map(jnt, getattr(jnput(), f"spl{j}t")())
Now that we have our inputs and a way to print, we can get on to the restrictions caused by missing keywords.
Conditionals
We can’t use if
statements or expressions, so we need to find a different way to express conditional control flow.
Two different ways come to mind for how to do this in “normal” programming (these tricks can be useful when writing SIMD code or GPU shaders):
- Figure out some formula that computes the right answer at the points we care about (possibly producing nonsense at the points we don’t care about).
- Turn the code into a pure function, compute all possibilities, then select the right one (e.g. by reading it out of a table).
There might be some fancy way to use the former for Fizzbuzz, but I mostly think of it as being applicable when the result is a number rather than a string, so I pursued the latter option.
That option would mean turning code like this:
def fizzbuzz_one(i) -> str:
if i % b != 0:
if i % a != 0:
return str(i)
else:
return "Fizz"
else:
if i % a != 0:
return "Buzz"
else:
return "FizzBuzz"
into code like this:
def fizzbuzz_one(i) -> str:
# We still need a formula for this part!
if i % b != 0:
if i % a != 0:
index = 0
else:
index = 1
else:
if i % a != 0:
index = 2
else:
index = 3
answers = [str(i), "Fizz", "Buzz", "FizzBuzz"]
return answers[index]
As noted in the code block, we still need a way to compute index
without branching.
The benefit of the table-based approach is that since we control the layout of the table, we can choose the indices we want to compute, so the formula for them is usually a lot simpler.
In this case, we can see the index as being a two-bit number, with each bit being one of the i % a != 0
flags.
This lets us compute it as:
def fizzbuzz_one(i) -> str:
a_flag = (1 if i % a == 0 else 0)
b_flag = (1 if i % b == 0 else 0)
index = b_flag * 2 + a_flag
answers = [str(i), "Fizz", "Buzz", "FizzBuzz"]
return answers[index]
This is now using if
expressions, but we can get rid of them by relying on a possibly-questionable design choice in Python: the bool
class extends the int
class, such that, for example, (True + True) = 2
.
This simplifies the code down to:
def fizzbuzz_one(i) -> str:
a_flag = i % a == 0
b_flag = i % b == 0
index = b_flag * 2 + a_flag
answers = [str(i), "Fizz", "Buzz", "FizzBuzz"]
return answers[index]
At this point we’ve gotten rid of if
, so our next challenge is getting rid of the function definition.
We’ll see exactly why next section, but it’s useful that we still have a single fizzbuzz_one
function — we just can’t use def
or lambda
to define it, because that requires a :
.
Iteration
In solving the problem, we can’t use for
or while
, since they would require a :
.
We can’t use list comprehensions or generator expressions either, since they would require the in
keyword.
One remaining way to iterate that we do still have available is the map
function.
As long as we’re operating on iterables, we can run functions on them.
It’s also worth noting that map
can operate on multiple iterables at a time.
We’ll use this to transform our code next. At the end of our chain of iterables, we have to demand all the items, which we do by collecting them into a list.
def fizzbuzz_one(i) -> str:
a_flag = i % a == 0
b_flag = i % b == 0
index = b_flag * 2 + a_flag
answers = [str(i), "Fizz", "Buzz", "FizzBuzz"]
return answers[index]
outs = map(fizzbuzz_one, range(1, n + 1))
list(map(print, outs))
This is why we want to keep fizzbuzz_one
as a function.
We can still define this function as method that we assign, like f = x.g
.
We’ll rely on this to define our function.
However, we need to find a way to keep i
passed around.
We can split fizzbuzz_one
apart to make the separate dependencies more evident:
def get_a_flag(i):
return i % a == 0
a_flags = map(get_a_flag, range(1, n + 1))
def get_b_flag(i):
return i % b == 0
b_flags = map(get_b_flag, range(1, n + 1))
def get_index(a_flag, b_flag):
return a_flag + b_flag * 2
indices = map(get_index, a_flags, b_flags)
def get_answers(i):
return [str(i), "Fizz", "Buzz", "FizzBuzz"]
answers_lists = map(get_answers, range(1, n + 1))
def index_into_answers(answers, index):
return answers[index]
outs = map(index_into_answers, answers_lists, indices)
list(map(print, outs))
We can then start transforming away each of these smaller functions.
The easiest one to start with is index_into_answers
.
It’s actually already equivalent to list.__getitem__
, the method used to implement the a[i]
syntax:
def get_a_flag(i):
return i % a == 0
a_flags = map(get_a_flag, range(1, n + 1))
def get_b_flag(i):
return i % b == 0
b_flags = map(get_b_flag, range(1, n + 1))
def get_index(a_flag, b_flag):
return a_flag + b_flag * 2
indices = map(get_index, a_flags, b_flags)
def get_answers(i):
return [str(i), "Fizz", "Buzz", "FizzBuzz"]
answers_lists = map(get_answers, range(1, n + 1))
outs = map(list.__getitem__, answers_lists, indices)
list(map(print, outs))
We next work on transforming away get_a_flag
and get_b_flag
.
One standard way to get rid of function definitions you might recall from a functional programming course is eta contraction.
This is the transformation from lambda x: f(x)
into f
.
We can rewrite get_a_flag
as a lambda to see more obviously how to apply this.
get_a_flag = lambda i: i % a == 0
a_flags = map(get_a_flag, range(1, n + 1))
To make it more clear, i % a == 0
can be transformed into method calls:
get_a_flag = lambda i: i.__mod__(a).__eq__(0)
a_flags = map(get_a_flag, range(1, n + 1))
This isn’t the form we want though: we have two function calls, not one, and the argument to the lambda is in the exact wrong spot! We can split the function into two to fix the first problem.
This relies on the identity map(lambda x: f(g(x)), xs) = map(f, map(g, xs))
— another one you might remember from a functional programming class.
mod_by_a = lambda i: i.__mod__(a)
get_a_flag = lambda x: x.__eq__(0)
a_flags = map(get_a_flag, map(mod_by_a, range(1, n + 1)))
Now we just need to get rid of the lambdas in the two functions.
This is easy for get_a_flag
: since int.__eq__
is commutative, we could instead write it as:
mod_by_a = lambda i: i.__mod__(a)
get_a_flag = lambda x: (0).__eq__(x)
a_flags = map(get_a_flag, map(mod_by_a, range(1, n + 1)))
We can then apply eta contraction:
mod_by_a = lambda i: i.__mod__(a)
get_a_flag = (0).__eq__
a_flags = map(get_a_flag, map(mod_by_a, range(1, n + 1)))
Then, since the definition is simple, we can inline it:
mod_by_a = lambda i: i.__mod__(a)
a_flags = map((0).__eq__, map(mod_by_a, range(1, n + 1)))
Flipping int.__mod__
is a bit tricker, since it’s not commutative.
However, as part of operator overloading, Python defines “reflected” versions of all the overloadable operators.
Basically, when you run 1 + x
, Python doesn’t just call (1).__add__(x)
; instead, it’s more like it does:
out = (1).__add__(x)
# NotImplemented is a special constant
if out == NotImplemented:
out = x.__radd__(1)
This gives x
the ability to define how it behaves when it’s added to 1
, even when it’s on the right-hand side of the addition.
Conveniently for us, there’s a reflected version of mod, int.__rmod__
.
Because the arguments are reversed, (3).__mod__(2) = (2).__rmod__(3)
.
If we rewrite mod_by_a
to use __rmod__
instead, we get:
mod_by_a = lambda i: a.__rmod__(i)
a_flags = map((0).__eq__, map(mod_by_a, range(1, n + 1)))
This can then be eta-contracted and inlined as well:
a_flags = map((0).__eq__, map(a.__rmod__, range(1, n + 1)))
We can apply the same reasoning for get_b_flag
:
b_flags = map((0).__eq__, map(b.__rmod__, range(1, n + 1)))
The remaining part of the program is then:
def get_index(a_flag, b_flag):
return a_flag + b_flag * 2
indices = map(get_index, a_flags, b_flags)
def get_answers(i):
return [str(i), "Fizz", "Buzz", "FizzBuzz"]
answers_lists = map(get_answers, range(1, n + 1))
outs = map(list.__getitem__, answers_lists, indices)
list(map(print, outs))
We can use a similar process to transform away get_index
.
First, we split it into two functions and transform them into method calls in lambdas as before:
double = lambda b_flag: b_flag.__mul__(2)
get_index = lambda a_flag, b_flag: a_flag.__add__(b_flag)
indices = map(get_index, a_flags, map(double, b_flags))
We can flip, eta-contract, and inline double
:
get_index = lambda a_flag, b_flag: a_flag.__add__(b_flag)
indices = map(get_index, a_flags, map((2).__mul__, b_flags))
get_index
can then be transformed to use int.__add__
as a function, rather than calling it as a method:
get_index = lambda a_flag, b_flag: int.__add__(a_flag, b_flag)
indices = map(get_index, a_flags, map((2).__mul__, b_flags))
It, too, can be eta-contracted and inlined.
jndjces = map(jnt.__add__, a_flags, map((2).__mul__, b_flags))
This leaves us with just:
def get_answers(i):
return [str(i), "Fizz", "Buzz", "FizzBuzz"]
answers_lists = map(get_answers, range(1, n + 1))
outs = map(list.__getitem__, answers_lists, indices)
list(map(print, outs))
Putting it all together
I wasn’t actually able to figure out how to write get_answers
as the composition of simpler functions.
Instead, I took a different approach: separating where i
gets passed in from where the list gets constructed.
If instead of a function that returns a list, we have a list of functions, it might look like:
answer_funcs = [
lambda i: str(i),
lambda i: "Fizz",
lambda i: "Buzz",
lambda i: "FizzBuzz",
]
def get_answer(index, i):
return answer_funcs[index](i)
outs = map(get_answer, indices, range(1, n + 1))
list(map(print, outs))
This once again gives us some lambdas to translate away.
Applying eta-contraction to answer_funcs[0]
and splitting up get_answer
as before gets us to:
answer_funcs = [
str,
lambda i: "Fizz",
lambda i: "Buzz",
lambda i: "FizzBuzz",
]
def get_func(index):
return answer_funcs[index]
def get_answer(answer_func, i):
return answer_func(i)
funcs = map(get_func, indices)
outs = map(get_answer, funcs, range(1, n + 1))
list(map(print, outs))
get_func
can be written as a call to the __getitem__
method:
answer_funcs = [
str,
lambda i: "Fizz",
lambda i: "Buzz",
lambda i: "FizzBuzz",
]
def get_answer(answer_func, i):
return answer_func(i)
funcs = map(answer_funcs.__getitem__, indices)
outs = map(get_answer, funcs, range(1, n + 1))
list(map(print, outs))
The biggest remaining issue is how to write a function that ignores its argument.
This is where functools.partial
comes in, along with max.
max
on strings uses lexicographic comparison on Unicode scalar values, so any string that starts with an ASCII digit (e.g. 2
) will be less than any string that starts with an ASCII letter (e.g. L
).
Because of this, max("Fizz", x)
is equal to x
whenever x
starts with an ASCII digit.
If x
is str(i)
, this will always be the case, so partial(max, "Fizz")
will always return "Fizz"
on these inputs.
Simply applying this transformation gets us to:
answer_funcs = [
str,
lambda i: partial(max, "Fizz")(str(i)),
lambda i: partial(max, "Buzz")(str(i)),
lambda i: partial(max, "FizzBuzz")(str(i)),
]
def get_answer(answer_func, i):
return answer_func(i)
funcs = map(answer_funcs.__getitem__, indices)
outs = map(get_answer, funcs, range(1, n + 1))
list(map(print, outs))
We could almost eta-contract away the i
, except for the str
call this introduces.
It’s necessary to keep that call, though, because max("Fizz", 2)
is a type error.
If we move the str
call out to the caller (get_answer
), though, we can eta contract.
This doesn’t break answer_funcs[0]
, because the str
function is the identity when applied to a string.
answer_funcs = [
str,
partial(max, "Fizz"),
partial(max, "Buzz"),
partial(max, "FizzBuzz"),
]
def get_answer(answer_func, i):
return answer_func(str(i))
funcs = map(answer_funcs.__getitem__, indices)
outs = map(get_answer, funcs, range(1, n + 1))
list(map(print, outs))
Our final challenge is getting rid of get_answer
.
We can again split it, letting the str
call end up in the iterators:
answer_funcs = [
str,
partial(max, "Fizz"),
partial(max, "Buzz"),
partial(max, "FizzBuzz"),
]
def call_answer_func(answer_func, i):
return answer_func(i)
funcs = map(answer_funcs.__getitem__, indices)
outs = map(call_answer_func, funcs, map(str, range(1, n + 1)))
list(map(print, outs))
At this point, it’d be really nice if we could do something like our previous trick of replacing index_into_answers
with list.__getitem__
.
Calls are in fact overloadable, with the __call__
method.
However, we don’t know what class to call it on!
The answer_funcs[0]
function is of the actual function
class, while the rest are of the partial
class.
One last bit of cleverness gets around this: if we just pass a function to the partial
constructor with no arguments, it gets wrapped in the partial
class, but no additional arguments are passed.
We can apply this to change the code to:
answer_funcs = [
partjal(str),
partjal(max, f"F{j}zz"),
partjal(max, "Buzz"),
partjal(max, f"F{j}zzBuzz"),
]
funcs = map(getattr(answer_funcs, f"__get{j}tem__"), jndjces)
outs = map(partjal.__call__, funcs, map(str, range(1, n + 1)))
ljst(map(prjnt, outs))
This completes the challenge! The complete code is as follows:
j = chr(105)
bujltjns = globals()[f"__bu{j}lt{j}ns__"]
jnput = getattr(bujltjns, f"{j}nput")
jnt = getattr(bujltjns, f"{j}nt")
ljst = getattr(bujltjns, f"l{j}st")
prjnt = getattr(bujltjns, f"pr{j}nt")
jmport = getattr(bujltjns, f"__{j}mport__")
partjal = getattr(jmport("functools"), f"part{j}al")
n, a, b = map(jnt, getattr(jnput(), f"spl{j}t")())
a_flags = map((0).__eq__, map(a.__rmod__, range(1, n + 1)))
b_flags = map((0).__eq__, map(b.__rmod__, range(1, n + 1)))
jndjces = map(jnt.__add__, a_flags, map((2).__mul__, b_flags))
answer_funcs = [
partjal(str),
partjal(max, f"F{j}zz"),
partjal(max, "Buzz"),
partjal(max, f"F{j}zzBuzz"),
]
funcs = map(getattr(answer_funcs, f"__get{j}tem__"), jndjces)
outs = map(partjal.__call__, funcs, map(str, range(1, n + 1)))
ljst(map(prjnt, outs))
This code works, and doesn't use Ii
nor :;
.
Doing this challenge was a lot of fun, and I'm glad I was able to find the time to do it!