# SPOJ: 400. To and Fro

Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down

```t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x```

Note that Mo includes only letters and writes them all in lower case. In this example, Mo used the character ‘x’ to pad the message out to make a rectangle, although he could have used any letter. Mo then sends the message to Larry by writing the letters in each row, alternating left-to-right and right-to-left. So, the above would be encrypted as

toioynnkpheleaigshareconhtomesnlewx

Your job is to recover for Larry the original message (along with any extra padding letters) from the encrypted one.

Solution: Let’s do this on a small example. The message should be ABCDEFGHIJKL with three columns. Therefore we get:

```A E I
B F J
C G K
D H L
```

If we merge these lines together, we get:

`A E I   J F B   C G K   L H D`

You can see that you need the first character from the first element, the third from the second, the first from the third, etc. To make this a bit easier I decided to reverse every second element.

`A E I   B F J  C G K  D H L`

Now we can just take all the firsts characters from every element, then the second characters and finally the thirds and we’re done.

```while True:
code = int(raw_input())
if code == 0:
break

line = raw_input()

segments = []
j = 0

for i in xrange(0, len(line), code):
if j % 2 == 1:
# reverse every odd segment
tmp = list(line[i:i + code])
tmp.reverse()
segments.append("".join(tmp))
else:
segments.append(line[i:i+code])

j += 1

out = []
for i in xrange(0, code):
for f in segments:
out.append(f[i])

print "".join(out)

```

# SPOJ: 277. City Game

The strategic task of his game is to win as much rent money from these free spaces. To win rent money you must erect buildings, that can only be rectangular, as long and wide as you can. Bob is trying to find a way to build the biggest possible building in each area.

Solution: The basic idea behind my algorithm is to expand rectangles continuously. It looks for a free space, marks it as a rectangle with the size 1×1 and expands in each direction alternately.

```def checkRight(f, i, j):
if j >= int(w) - 1 or i > int(h) - 1:
return False
else:
if f[i][j+1] == 'F':
return True
else:
return False

def checkBottom(f, i, j):
if i >= int(h) - 1 or j > int(w) - 1:
return False
else:
if f[i+1][j] == 'F':
return True
else:
return False

def checkSelf(f, i, j):
if field[i][j] == 'F':
return True
else:
return False

def checkExpandWidth(f, i, j, height, width):
for y in xrange(i, height + i):
if checkRight(field, y, j + width - 1) == False:
return False

return True

def checkExpandHeight(f, i, j, height, width):
for x in xrange(j, width + j):
if checkBottom(field, i + height - 1, x) == False:
return False
return True

k = int(raw_input())

for areas in xrange(0, k):

line = raw_input()
h, w = line.split()
field = []

for li in xrange(0, int(h)):
line = raw_input()
field.append(line.split())

# blank line
try:
t = raw_input()
except:
break

maxSquare = 0

for i in xrange(0, int(h)):
for j in xrange(0, int(w)):
if checkSelf(field, i, j) == False:
continue
else:
height = 1
width = 1

eWidth = True
eHeight = True

# expand width first

while eWidth == True or eHeight == True:
if eWidth == True and checkExpandWidth(field, i, j, height, width) == True:
width += 1
else:
eWidth = False

if eHeight == True and checkExpandHeight(field, i, j, height, width) == True:
height += 1
else:
eHeight = False

# found bigger square
if height * width > maxSquare:
maxSquare = height * width

# reset vars
height = 1
width = 1

eWidth = True
eHeight = True

# expand height first

while eWidth == True or eHeight == True:
if eHeight == True and checkExpandHeight(field, i, j, height, width) == True:
height += 1
else:
eHeight = False

if eWidth == True and checkExpandWidth(field, i, j, height, width) == True:
width += 1
else:
eWidth = False

# found bigger square
if height * width > maxSquare:
maxSquare = height * width

print maxSquare * 3
```

# SPOJ: 1163. Java vs C ++ (JAVAC)

I started doing programming challenges again and chose SPOJ for it. I try to do about three challenges per week which should be possible. As Stephen King says:

Read and write four to six hours a day. If you cannot find the time for that, you can’t expect to become a good writer.

I actually wonder how much you would learn if you’re going to solve (harder) algorithmic problems four hours a day for a year. Probably a lot! In any case here’s the first problem and its solution.

```def recognize(s):
# -1: c++
#  0: error
# +1: java

if s == s.lower():
typ = 1
last = 0
for c in s:
if c == '_':
if last == 0: # last character was _
typ = -1
last = 1
else:
typ = 0
break
else:
last = 0

if s[-1] == '_' or s[0] == '_':
typ = 0
else:
if s[0] == s[0].lower():
typ = 1
# if _ in java => error
for c in s:
if c == '_':
typ = 0
else:
typ = 0
return typ

def transformJava(s):
l = list(s)
r = []
for i in xrange(0, len(l)):
if l[i] == l[i].upper():
r.append('_')
r.append(l[i].lower())
else:
r.append(l[i])

return "".join(r)

def transformCpp(s):
l = list(s)
r = []
for i in xrange(0, len(l)):
if i > 1 and l[i-1] == '_':
continue

if l[i] == '_':
r.append(l[i+1].upper())
continue
else:
r.append(l[i])

return "".join(r)

while True:
try:
s = raw_input()
except:
break

r = recognize(s)
if r == -1:
print transformCpp(s)
elif r == 1:
print transformJava(s)
else:
print "Error!"

```