algorithm

There are 11 posts tagged algorithm (this is page 3 of 3).

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.

Problem: Sphere Online Judge (SPOJ) – Problem TOANDFRO

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.

Problem: Sphere Online Judge (SPOJ) – Problem CTGAME

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.

Problem: Sphere Online Judge (SPOJ) – Problem JAVAC

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!"