Friday, June 22, 2007

Burglars cops treasures and python, this time we got it all.

So we got these burglars who have this map that shows where the treasures are. Hmmm right, this is clear. Then we got these cops that want to stop the burglars. Now the map looks something like this.

4 3 3 3
3 -1 2
-1 -1 -1
3 12 7

The first row contains some stupid numbers showing different things, because the solution of this problem is supposed to be written in C, but hey fuck C and it's stupid libraries ( this from a guy who makes a living like a professional C programmer - me ) The most important number from the first row is the second one which shows the time ticks the burglars have before the cops show up. The rest of the numbers say what's the array height and width (useless in python and in fact in C if you take the time to code is right).

Now the rules are simple. The burglars have the map so they know where the treasures are. Each treasure is represented by a positive number showing the amount of money the gain when they reach it. The cells with negative numbers does not contain treasures and they cost money to be dug. Each cell is dug for one tick time. The cops will come in K ticks of time where K is the second number in the first row. In order to get to a cell the burglars must dug out all the cell in it's column prior to it. The burglars may start from any column and stop digging within the column whenever they want.

Make a program that finds the maximum amount of money the burglars can gain without being caught from the cops.

He he, me lazy so code in python.

#!/usr/bin/env python
import os, sys
K = 0 # edinici vreme, broi kletki koito mogat da izkopaqt

def GetData(file=''):
f = open(file, 'r')
data = f.readlines()
f.close()
params = []

for i in data[0].split():
params.append(int(i))

data = data[1:data.__len__()]
array = []
for d in data:
array.append(d.split())

return (params, array)

class PreData:
def __init__(self, t=0, m=0):
self.time = t
self.money = m
def __repr__(self):
return 'Time: '+str(self.time)+' Money: '+str(self.money)
def __str__(self):
return 'Time: '+str(self.time)+' Money: '+str(self.money)

def GetPreData():
columns = []
tmpK = 0
tmpAward = 0
r = 0
c = 0
global K


((N,K,L,D), data) = GetData('input')
for c in xrange(0, L):
treasures = []
tmpC = PreData(0,0)

for r in xrange(0, D):
tmpC.time = tmpC.time + 1
tmpC.money = tmpC.money + int(data[r][c])

if int(data[r][c]) > 0:
if tmpC.time > int(K):
break
if tmpC.money > 0:
treasures.append(PreData(tmpC.time, tmpC.money))
tmpC.time = 0
tmpC.money = 0

columns.append(treasures)
return columns

maxMoney=0
def Recursion(cols=[], c=0, r=0, money=0, time=0):
global maxMoney

if c >= cols.__len__():
return
if r >= cols[c].__len__():
return
if (cols[c][r].time+time) > K:
return

cmoney = money + cols[c][r].money
ctime = time + cols[c][r].time
if maxMoney < cmoney:
maxMoney = cmoney

Recursion(cols, c + 1, r, cmoney , ctime )
Recursion(cols, c, r + 1, cmoney , ctime )

cols = GetPreData()
for i in range(0, cols.__len__()):
Recursion(cols, i, 0, 0, 0)
print maxMoney



Now test it!
serj@tokamak ~> cat input
4 3 3 3
3 -1 2
-1 -1 -1
3 12 7
serj@tokamak ~> ./stamen.py
10

Now test it again.
serj@tokamak ~> cat input; ./stamen.py
4 3 3 3
3 -1 24
-1 -1 -1
3 12 7
30

Yes it wErks! :-D