Some people have been asking for a Python implementation of the Tatami challenge. I wasn't really interested for a number of reasons but finally got caught nevertheless. But I wanted a version that is more versatile (being able to find solutions for larger values of s) and while working on it I found an optimization which should be applicable to most other implementations as well.

Both versions I provide (tatami.py and tatami_opt.py) may take up to two arguments: s and nMax. So it's possible to play arround with different values. The current algorithm will break with nMax >= 147026880, because the stored values may be bigger than 255. So the program uses bytearrays, Python list or arrays from the array module (as a last resort, because it is the slowest), depending on the size of nMax, maximum size of Python lists and memory usage. Here is the standard version (tatami.py):

Code: Select all

```
#!/usr/bin/python3
import sys
from math import sqrt
def tatami(s):
for i in range(7,nMaxSqrt,2):
k2 = i + 3
k3 = i + i - 4
while ((k2 <= k3) and ((i * k2) < nMax)):
k4 = (nMax-1) // i
if k3 < k4:
k4 = k3
for j in range(k2,k4+1,2):
v[i*j] += 1
k2 += i+1
k3 += i-1
for i in range(8,nMaxSqrt,2):
k2 = i + 3
k3 = i + i - 4
while ((k2 <= k3) and ((i * k2) < nMax)):
k4 = (nMax-1) // i
if k3 < k4:
k4 = k3
for j in range(k2,k4+1):
v[i*j] += 1
k2 += i + 1
k3 += i - 1
try:
return v.index(s)
except:
return -1
s = 200
nMax = 100000000
if len(sys.argv) > 1:
try:
s = int(sys.argv[1])
except:
pass
if len(sys.argv) > 2:
try:
nMax = int(sys.argv[2])
except:
pass
if (nMax & 1) != 0:
nMax += -1
if nMax > 536870912 and sys.maxsize == 2147483647:
try:
from array import array
v = array('I',[0])*nMax
except:
print("Not enough memory!")
sys.exit(0)
elif nMax >= 147026880:
try:
v = [0]*nMax
except:
try:
from array import array
v = array('I',[0])*nMax
except:
print("Not enough memory!")
sys.exit(0)
else:
v = bytearray(nMax)
nMaxSqrt = int(sqrt(nMax))
res = tatami(s)
if res > -1:
print("The smallest room size s for which T(s) = "+str(s)+" is "+str(res))
else:
print("No solution found for s=" +str(s)+" and nMax="+str(nMax))
maxs = 0
maxi = 0
for i in range(0,nMax):
if v[i] > maxs:
maxs = v[i]
maxi = i
print("Maximal T(s) found = "+str(maxs)+" for room size = "+str(maxi))
```

Of course it will run much slower than a C version.:

Code: Select all

```
time ./tatami.py
The smallest room size s for which T(s) = 200 is 85765680
real 1m29,730s
user 1m29,230s
sys 0m0,240s
```

But it will give a nice performance time when run from pypy3:

Code: Select all

```
time pypy3 ./tatami.py
The smallest room size s for which T(s) = 200 is 85765680
real 0m16,484s
user 0m16,034s
sys 0m0,430s
```

The optimization takes into account, that only even room sizes are allowed. Half of the size of the v-Array is never used. So it's possible to reduce the dimension of the v-array to nMax/2. It needs an additional shift by one to the right within the tatami function: v[(i*j) >> 1] += 1. The result has to be multiplied by 2 in the end. The overhead should be small and the search time for the result will be reduced. Here's the code of the optimized Python version (tatami_opt.py):

Code: Select all

```
#!/usr/bin/python3
import sys
from math import sqrt
def tatami(s):
for i in range(7,nMaxSqrt,2):
k2 = i + 3
k3 = i + i - 4
while ((k2 <= k3) and ((i * k2) < nMax)):
k4 = (nMax-1) // i
if k3 < k4:
k4 = k3
for j in range(k2,k4+1,2):
v[(i*j) >> 1] += 1
k2 += i+1
k3 += i-1
for i in range(8,nMaxSqrt,2):
k2 = i + 3
k3 = i + i - 4
while ((k2 <= k3) and ((i * k2) < nMax)):
k4 = (nMax-1) // i
if k3 < k4:
k4 = k3
for j in range(k2,k4+1):
v[(i*j) >> 1] += 1
k2 += i + 1
k3 += i - 1
try:
return v.index(s)
except:
return -1
s = 200
nMax = 100000000
if len(sys.argv) > 1:
try:
s = int(sys.argv[1])
except:
pass
if len(sys.argv) > 2:
try:
nMax = int(sys.argv[2])
except:
pass
if (nMax & 1) != 0:
nMax += -1
if nMax > 536870912*2 and sys.maxsize == 2147483647:
try:
from array import array
v = array('I',[0])*(nMax//2)
except:
print("Not enough memory!")
sys.exit(0)
elif nMax >= 147026880:
try:
v = [0]*(nMax//2)
except:
try:
from array import array
v = array('I',[0])*(nMax//2)
except:
print("Not enough memory!")
sys.exit(0)
else:
v = bytearray(nMax//2)
nMaxSqrt = int(sqrt(nMax))
res = tatami(s)*2
if res > -1:
print("The smallest room size s for which T(s) = "+str(s)+" is "+str(res))
else:
print("No solution found for s=" +str(s)+" and nMax="+str(nMax))
maxs = 0
maxi = 0
for i in range(0,nMax//2):
if v[i] > maxs:
maxs = v[i]
maxi = i*2
print("Maximal T(s) found = "+str(maxs)+" for room size = "+str(maxi))
```

It runs a bit slower in interpreter mode, but even faster with pypy3:

Code: Select all

```
time ./tatami_opt.py
The smallest room size s for which T(s) = 200 is 85765680
real 1m39,995s
user 1m39,781s
sys 0m0,140s
time pypy3 ./tatami_opt.py
The smallest room size s for which T(s) = 200 is 85765680
real 0m15,124s
user 0m14,871s
sys 0m0,210s
```

Now let us search for a solution for T(s) = 300:

Code: Select all

```
time pypy3 ./tatami_opt.py 300 300000000
The smallest room size s for which T(s) = 300 is 294053760
real 0m49,615s
user 0m48,143s
sys 0m1,400s
```

All timings are from a RPi 4B/4G