|
 |
Kevin Wampler wrote:
>
> Now for a tricker question, say I add another loop:
>
> n = 2
> for(a = n; a > 0; a--)
> for(b = n; b > 0; b--)
> for(c = n; c > 0; c--)
> for(d = n; d > 0; d--)
> for(e = n; e > 0; e--)
> n++
> print n
>
> What are the last five digits printed?
>
Don't read if you don't want the puzzle spoiled for you.
Ok, since nobody's posted in a while I'll assume that either everyone's
lost interest or they're ready to hear the solution. Invisible had the
right answer (minus some minor analysis issues) for the case with four
loops, but the technique he used doesn't extend well beyond that.
To figure out how to make things work for more nested for-loops, let's
consider the function representing the body of the innermost loop:
f_0(n) = n+1
On successive iterations of the innermost loop, we end up computing:
f_0(n)
f_0(f_0(n))
f_0(f_0(f_0(n)))
etc...
Of course, we're only interested in the last k digits of the answer, so
the values of these successive iterations end up repeating. Obviously
it's easy to represent this in closed from, but let's say we don't want
to do that. Then we can explicitly represent this with:
orbit_0 = []|[2,3,4,...,10^k,0,1]
The notation A|B here indicates that the initial value of n (2 in this
case) goes through the values in A once, and then loops through the
values in B forever. We'll call this the orbit of n mod 10^k under f_0,
meaning that these are the values we get if we start at n and then keep
applying f_0. For convienence I'll call A and B the prefix and loop of
the orbit respectively.
The method of solving the puzzle for many nested loops will involve
computing orbit_i, which is the orbit of n mod 10^k under f_i, where f_i
is the function defined by i nested for-loops. The a'th element in this
orbit will be given by f_i^a(n), which stands for a compositions of f_i,
so f_i^3(n) = f_i(f_i(f_i(n))).
In this approach to solving the problem, we'll store each orbit_i
explicitly. Thus we can get the value of f_i^a(n) by simply indexing
into orbit_i. In the case that the orbit's prefix is empty, then we can
do this by f_0^a(n) = orbit_i.loop[ (indexOf(n,orbit_i) + a) mod
period(orbit_i) ], which we'll write as orbit_i[n,a] for shorthand. If
the or orbit's prefix is non-empty, then the formula is a bit more
complicated, but still not too bad, and we'll denote it with
orbit_i[n,a] in any case.
So far this may not seem very interesting, but the power of this way of
looking at things will become apparent if we consider the function
defined by having a single for-loop:
for(a = n; a > 0; a--)
n = f_{i-1}(n)
As noted before, this loop defines the function:
f_i(n) = f_{i-1}^n(n)
Now, the trick to getting this whole approach to work is to directly
calculate orbit_i entirely in terms of the initial value of n (2 in this
case) and orbit_{i-1}. Since we show that the first element in orbit_i
(it's 2), it's sufficient to be able to calculate element a in orbit_i
given element a-1. It's pretty direct to see how to do this:
Since: orbit_{i-1}[n,a] = f_{i-1}^a(n)
and: f_i(n) = f_{i-1}^n(n)
then: f_i(n) = orbit_{i-1}[n,n]
So to generate the orbit defined by f_i, we can use the procedure:
f_i^0(n) = 2
f_i^a(n) = orbit_{i-1}[f_i^{a-1}(n), f_i^{a-1}(n)]
= orbit_i[n,a]
This allows us to generate values of f_i^a(n) until we hit a repeated
value, at which point we have the full definition of orbit_i. Thus if
we want the last m digits of the result if we start at n and use i
nested loops, we just look up the value of orbit_i[n,n]. Thus the
algorithm requires linear time in the numeber of nested loops, although
exponential time in the number of digits you want to return (which is
why I changed the problem to only ask for five digits).
The Python code I udes to solve this problem (posted below) uses this
procedure to get the answer for the case with five nested for-loops: 86528
Even better, the Python code allows you to create an orbit of orbits,
and thus find that the last five digits for the case with 10^100 nested
for-loops are 45728! Not bad considering how completely intractable the
problem appears at first. I also think it's sort of nifty that the
entire algorithm is basically just fancy array indexing, so in some
sense it's quite simple. Also, I haven't quite proved rigorusly that
this algorithm works, and I double I'll bother to, so let me know if you
find an error. I also suspect it might even be possible to make an
algorithm which is sub-exponential in the number of digits, but I
haven't look into this much.
At any rate, here's the code which I used to compute all these answers:
-------------------------------------------------------------------------------
class InvertibleList(object):
"""Like a list, but also allows you to efficiently find the index
at which a given element appears. All elements in the list are assumed
to be unique. Python probably has something like this built in, but it
was easy enough to code that I just implemented it myself."""
def __init__(self, items=[]):
self.values = []
self.invValues = {}
self.extend(items)
def __len__(self):
return len(self.values)
def __getitem__(self, key):
return self.values[key]
def indexOf(self, value):
return self.invValues[value]
def append(self, item):
self.values.append(item)
self.invValues[item] = len(self.values)-1
def extend(self, items):
for item in items:
self.append(item)
def __contains__(self, value):
return value in self.invValues
def __eq__(self, other):
if len(self) != len(other): return False
for v1, v2, in zip(self.values, other.values):
if v1 != v2: return False
return True
def __hash__(self):
h = hash(len(self))
for i, v in enumerate(self.values):
h ^= hash(i) + hash(v)
return h
def __str__(self):
return str(self.values)
class Orbit(object):
"""Represents the orbit which a value takes under the composition of a
function in a finite field. For convienence you can give the value and
the function to be composed as parameters to the constructor."""
def __init__(self, n=None, f=None):
self.prefix = InvertibleList()
self.loop = InvertibleList()
if n is not None:
assert f is not None
# generate values until we hit a repeat
o = InvertibleList()
o.append(n)
n = f(n)
while n not in o:
o.append(n)
n = f(n)
# partition o into perfix and loop components
ind = o.indexOf(n)
for i in xrange(ind):
self.prefix.append(o[i])
for i in xrange(ind,len(o)):
self.loop.append(o[i])
def itemFrom(self, n, a):
"""Get the a'th item after the appearance on n in this orbit."""
if n in self.loop:
nInd = self.loop.indexOf(n)
return self.loop[(a+nInd) % len(self.loop)]
else:
assert n in self.prefix
nInd = self.prefix.indexOf(n)
nInd2 = a + nInd
if nInd2 < len(self.prefix):
return self.prefix[nInd2]
else:
return self.loop[(nInd2-len(self.prefix)) % len(self.loop)]
def __str__(self):
return str(self.prefix) + "|" + str(self.loop)
def __len__(self):
return len(self.loop)
def __eq__(self, other):
return (self.prefix == other.prefix) and (self.loop == other.loop)
def __hash__(self):
return hash(self.prefix) ^ hash(self.loop)
def reduceOrbit(n, o1):
"""Given an orbit for f, returns an orbit of n under the function
f^n(n). This assumes n is in the orbit o1, and that the sizes of
these orbits behave nicely."""
o2 = Orbit(n, lambda i: o1.itemFrom(i,i))
assert len(o1.loop) % len(o2.loop) == 0
return o2
def getLastDigits(n, numLevels, numDigits):
mod = 10**numDigits
o = Orbit(2, lambda i: (i+1) % mod)
for i in xrange(1, numLevels):
o = reduceOrbit(n, o)
return o.itemFrom(n, n)
def getLastDigitsOrbit(n, numDigits):
mod = 10**numDigits
metaOrbit = Orbit(
Orbit(2, lambda i: (i+1) % mod),
lambda orb: reduceOrbit(n, orb))
return metaOrbit
#-----------------------------[ main ]----------------------------#
if __name__ == "__main__":
numDigits = 5
print "These are the last five digits for the case with five nested
for-loops:"
print getLastDigits(2, 5, numDigits)
print
print "The last five digits for the case with 10^100 nested for-loops:"
metaOrbit = getLastDigitsOrbit(2, numDigits)
print metaOrbit.itemFrom(metaOrbit.prefix[0], 10**100).itemFrom(2,2)
Post a reply to this message
|
|
