In which we potentially miss the point of the exercise.
Putting the beholders to the side for a bit, let’s talk about practice problems.
Switches #
Many years ago, I used to do a lot of programming practice problems (what one coworker calls “katas”, and another calls “interview questions”). I even got into Project Euler for a bit while I was learning Ruby; I worked on each question until I could craft a solution that took less than a second to run, until I started hitting questions where that was actually impossible.
So the other day, I ran into a fairly standard one while brushing up on my Python. You have set of n switches, and some defined sequence of toggling them, and at the end you need to describe the final state of the switches. In this case it was described as follows:
“There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.”
I know I was supposed to sit down and puzzle out the mathematical sequence (the first bulb is toggled only once, the second twice, the third twice, the fourth three times, hmmm), but it was the end of a long day at the day job and it just wasn’t coming to me.
Brute Force #
The brute force solution in this case is to fully simulate the process. Efficiency be darned, let’s just do the thing.
def bulbSwitch(n):
"""
:type n: int
:rtype: int
"""
bulbs = [False] * n
for round in xrange(n):
i = round
while i < n:
bulbs[i] = not bulbs[i]
i += round + 1
print bulbs
retval = 0
for i in xrange(n):
if bulbs[i]:
retval += 1
print "n of {} = {}".format(n, retval)
[True, True, True, True, True]
[True, False, True, False, True]
[True, False, False, False, True]
[True, False, False, True, True]
[True, False, False, True, False]
n of 5 = 2
Ok, so that works.
Spot the Pattern #
Humans are fairly good as spotting patterns, so let’s do a bunch of runs and see what emerges:
def bulbSwitch(m):
"""
:type n: int
:rtype: int
"""
for n in xrange(m):
bulbs = [False] * n
for round in xrange(n):
i = round
while i < n:
bulbs[i] = not bulbs[i]
i += round + 1
retval = 0
for i in xrange(n):
if bulbs[i]:
retval += 1
print "n of {} = {}".format(n, retval)
With m of 11, we see:
n of 0 = 0
n of 1 = 1
n of 2 = 1
n of 3 = 1
n of 4 = 2
n of 5 = 2
n of 6 = 2
n of 7 = 2
n of 8 = 2
n of 9 = 3
n of 10 = 3
…and I think I see the pattern. Is it that simple? Let’s tweak the code to show us only when the result changes:
def bulbSwitch(m):
"""
:type n: int
:rtype: int
"""
old_result = None
for n in xrange(m):
bulbs = [False] * n
for round in xrange(n):
i = round
while i < n:
bulbs[i] = not bulbs[i]
i += round + 1
retval = 0
for i in xrange(n):
if bulbs[i]:
retval += 1
if retval != old_result:
print "n of {} = {}".format(n, retval)
old_result = retval
And with an m of 101, we now see:
n of 0 = 0
n of 1 = 1
n of 4 = 2
n of 9 = 3
n of 16 = 4
n of 25 = 5
n of 36 = 6
n of 49 = 7
n of 64 = 8
n of 81 = 9
n of 100 = 10
…and now it’s super-clear.
Simplicity #
The efficient solution for this version of the switch problem is:
def bulbSwitch(n):
"""
:type n: int
:rtype: int
"""
return int(math.sqrt(n))
Is it valid to use the brute-force simulation to show the way to the elegant math solution? It certainly had me writing more code than if I had just puzzled out the equation. And maybe that’s what I wanted to do anyway.
Useful Stuff #
