Universidad Nacional Mayor de San Marcos Facultad de Ciencias Matemáticas
E.A.P de Computación Científica (2010)
Posible solución a dos problemas del concurso de programación de la ACM 2010
Resumen
Proponemos posibles soluciones a dos problemas propuestos por la ACM (Association for Computing Machinery) en el último concurso realizado a nivel regional. Planteamos el problema y exponemos una idea de solución. Implementamos el algoritmo de solución en Python. Los problemas resueltos son los siguientes: Tracking Bio-bots y Sharing Chocolate
1.- Tracking Bio-bots
Se tiene un Bio-bot (para nuestros propósitos un pequeño robot), que funciona en un entorno que podemos describir como una rejilla de tamaño m x n. La salida de la rejilla esta al noreste (esquina superior izquierda). En la rejilla hay paredes que le impiden el paso a nuestro robot. El Bio-bot solo puede avanzar una hacia arriba y hacia una celda a la vez. Su objetivo es salir de la rejilla.
Claramente el robot localizado sobre el cuadrado A es capaz de abandonar la rejilla, mientras que si comienza en el cuadrado B quedara atrapado. La pregunta es: ¿Cuándo quedara atrapado? El problema consiste en encontrar el numero de celdas en las cuales, si el Bio-bot se localiza ahí, no podrá salir de la rejilla.
Lo primer que vamos hacer para resolver el problema es girar 90º la rejilla e identificar las paredes con 1s y las demás celdas con cero. En la frontera también pondremos 1s.
Ahora podemos ver que para nuestro pequeño robot sólo se presentan cuatro situaciones.
La idea de solución es hacer que el robot avance según sus posibilidades (derecha o abajo), y si puede elegir a donde avanzar, entonces que avance abajo y que guarde esta posición de ambiguedad (pues podía avanzar arriba o a abajo). Luego que siga avanzando, si fracasa (si tiene un cero abajo y a la derecha), que vuelva a la posición de ambiguedad y se mueva a la derecha, y que avance. El robot siempre guarda las posiciones de ambigüedad, pues, si después de haber avanzado abajo, fracasa, entonces vuelve a la posición de ambiguedad y avanza a la derecha.
Viendo a la rejilla como una matriz de ceros y unos, implementamos el algoritmo en Python. Primero creamos una clase robot con todos los métodos necesarios para guardar las posiciones y hacer mover al robot.
class Robot:
def __init__(self,xini,yini):
#inicializa el vector que guarda las posiciones y el vector que
guarda las ambiguedades
#guarda la posición inicial y guardo la posición actual
#inicializo el numero de ambiguedades con cero
def abajo(self): #aumenta la posición y en 1, avanza abajo
def derecha(self): #aumenta la posición x en 1, avanza derecha
def posicion(self):
def guardaP(self): #guarda la posición actual
def guardaA(self,amb): #guarda la ambiguedad
def aumen_amb(self): #aumenta el número de ambigüedades
También implementamos una clase matriz para la rejilla.
class Matriz:
def __init__(self,_l,col,numpar,par):
#_l es el número de _las
#col es el número de columnas
#numpas es el número de paredes
#par es una matriz donde se eespeci_can las coordenadas de las
paredes
def retur_M(self):
#devuelve la matriz con ceros y unos
La función búsqueda es la que hace mover al robot desde todas las posiciones identificadas con cero, verifica en cual de las cuatro situaciones se encuentra y decide a donde avanzar. Si encuentra una ambiguedad la guarda y avanza hacia abajo; si después fracasa, entonces vuelve a la posición de ambiguedad y avanza a la derecha. Siempre vuelve a la última posición de ambiguedad guardada. El código completo es el siguiente
class Robot:
def __init__(self,xini,yini):
self.P=[]#inicializa el vector que guarda las posiciones
self.A=[]#inicializa el vector que guarda las anbiguedades
self.xini=xini#posicion inicial x
self.yini=yini#posicion inicial y
self.amb=0#inicializo la ambiguedad actual con cero
#en este punto no se conoce el verdadero valor de la amb
self.posx=self.xini#posicion actual x
self.posy=self.yini#posicion actual y
def abajo(self):
self.posx=self.posx+1#aumneta la posicion y en 1, baja
def derecha(self):
self.posy=self.posy+1#aumenta la posicion x en 1, avanza der
def posicion(self):
print 'posicion inicial',self.xini,self.yini
print 'posicion actual ',self.posx,self.posy
for i in range(0,len(self.L)):
print self.L[i][0],self.L[i][1]
def guardaP(self):
self.P.append([self.posx,self.posy])
def guardaA(self,amb):
self.A.append(amb)
def aumen_amb(self):
self.amb=self.amb+1
class Matriz:
def __init__(self,fil,col,numpar,par):
self.M=[]
self.b=[]
#se llena de ceros la matriz
for i in range(0,fil+1):
for j in range(0,col+1):
self.b.append(0)
self.M.append(self.b)
self.b=[]#se llenan de unos las paredes
for i in range(0,numpar):
for j in range(par[i][0],par[i][2]+1):
for k in range(par[i][1],par[i][3]+1):
self.M[j][k]=1
#se llenan de unos la ultima fila y la ultima column
for i in range(0,col+1):
self.M[fil][i]=1
for i in range(0,fil+1):
self.M[i][col]=1
#se pone dos a la salida
self.M[fil-1][col]=2
#ahora ya tenemos la matriz
def retur_M(self):
return self.M
def busqueda(fil,col,n_pardes,pardes):
#creo y inicializo mi matriz
Fra=0#el numero de fracasos
Ma=Matriz(fil,col,n_pardes,pardes)
M=Ma.retur_M()
#recorremos todos los elementos de la matriz que sean
#iguales a ceros
for i in range(0,fil):
for j in range(0,col):
if M[i][j]==0 :
#print i,j,'ddd'
#al comensar debemos crear un objeto robot
#y lo inicializamos con la posicion inicial
robot=Robot(i,j)
q=1#q solo para comenzar el bucle
aviso=0
while q==1 :
K=robot.posx
L=robot.posy
#print K,L
M1=M[K+1][L]
M2=M[K][L+1]
if((M1==0)and(M2==0)):
if aviso==1:
robot.abajo()
aviso=0
else:
robot.aumen_amb() robot.guardaA(robot.amb)
robot.guardaP()
robot.derecha()
continue
#caso B
if (M1==0)and(M2==1) :
robot.guardaA(0)
robot.guardaP()
robot.abajo()
continue
#caso C
if (M1==1)and(M2==0) :
robot.guardaA(0)
robot.guardaP()
robot.derecha()
continue
#caso Fracaso
if (M1==1)and(M2==1) :
if robot.amb>0 :
ind=robot.A.index(robot.amb)
robot.posx=robot.P[ind][0]
robot.posy=robot.P[ind][1]
robot.P=robot.P[0:ind]
robot.A=robot.A[0:ind]
robot.amb=robot.amb-1
aviso=1
else :
q=0 Fra=Fra+1
continue
#caso Exito
if (M2==2) :
q=0
return Fra
def C():
j=0
while 1:
pardes=[]
c1=raw_input()
if c1[0]=='0':
break
for i in range(0,int(c1[4])):
c2=raw_input()
c3=[int(c2[0]),int(c2[2]),int(c2[4]),int(c2[6])]
pardes.append(c3)
fra=busqueda(int(c1[0]),int(c1[2]),int(c1[4]),pardes)
j=j+1
print 'Case ',j,': ',fra
2.- Sharing Chocolate
Ud. tiene una barra de chocolate que quiere compartir con sus amigos. Sus amigos son muy exigentes, algunos quieren más que otros. Para compartir la barra de chocolate puede partir el chocolate horizontal o verticalmente. Sus amigos son aún más exigentes, quieren una única porción rectangular de chocolate, que tenga el número de piezas que ellos deseen. Ud. decide compartir el chocolate solamente si puede complacer a todos sus amigos. El problema consiste en saber cuándo será posible repartir el chocolate entre todos sus amigos.
Por ejemplo, se tiene una barra de chocolate de 3x4. Tiene 4 amigos, y ellos quieren 6, 3, 2 y 1 piezas cada uno. Tendrá que romper el chocolate 3 veces.
Entonces podemos plantear las siguientes reglas:
1.-Sus amigos sólo quieren porciones rectangulares de chocolate
2.-Solo puede partir el chocolate horizontal y verticalmente.
Comencemos a construir una idea de solución. Consideremos una barra de chocolate de 3x4. Nuestros amigos quieren 6, 3, 2, 1 trozos de chocolate respectivamente. En este caso veamos el problema de esta forma:
3x4 y {6, 3, 2, 1}
Podemos ver que podemos hacer un corte vertical y obtener una porción rectangular que satisface el pedido del primer amigo: 6 trozos.
Entonces la otra parte del chocolate seria: 3x2 y {3, 2, 1}. Otra opción seria hacer un corte vertical y obtener un trozo de 3 trozos de chocolate.
Lo podemos ver así: {6, 3, 2, 1} -{3} = {6, 2, 1}.
Consideremos el mismo chocolate pero con más amigos que tienen los siguientes pedidos: {2, 2, 2, 2, 2, 2}. Vemos que no es posible satisfacer a algún amigo con solamente un corte horizontal o vertical. En cambio si tomamos: {2, 2}, podríamos hacer un corte horizontal para obtener 4 trozos de chocolate, es decir un rectángulo de 1x4, al cual deberíamos hacer un corte vertical para obtener dos porciones de 2 trozos cada una. Así dos amigos quedaran satisfechos.
Podemos intuir que la idea es ir probando con los subconjuntos del conjunto de pedidos, ver de alguna manera si es posible hacer un corte horizontal o vertical tal que una de los trozos obtenidos contenga tantos trozos de chocolate como la suma de los pedidos del subconjunto elegido. Entonces la idea es ir probando para todos los subconjuntos, es decir, si fuera el conjunto de pedidos {6, 3, 2, 1}, entonces todos los subconjuntos serian:
{6} {3} {2} {1}
{6,3} {6,2} {6,1} {3,1} {2,1} {3,2}
{6, 3, 2} {6, 3, 1} {3, 2, 1} {1, 6, 2}
Deberíamos verificar si podemos hacer un corte tal que podamos obtener una porción que contenga un número de piezas igual a la suma de los elementos de algún subconjunto. Es decir, que la suma sea múltiplo del número de filas o de columnas. Esta última condición es crucial, y no es difícil darse cuenta que es necesaria. También observamos que debemos hacer lo mismo con las dos partes de chocolate que resultan después de hacer un corte horizontal o vertical. Entonces el proceso es repetitivo. Mas adelante veremos que es recursivo.
Por ejemplo, consideremos el mismo chocolate y los mismos pedidos.
Concretamos nuestras ideas desarrollando un programa en Python. Explicaremos brevemente como plasmamos las ideas anteriores en código Python.
def principal(anc,alt,par):
# anc : ancho del chocolate
#alt : alto del chocolate
L=g([],par) # devuelve una lista con todas las combinaciones
for i=0 hasta Número Total de Combinaciones:
Si sum(L[i])%anc==0:
div=sum(L[i])/anc
alt=alt-div
A=principal(anc,alt,otraparte)
B=principal(div,alt,L[i])
Sino sum(L[i])%alt==0:
div=sum(L[i])/alt
anc=anc-div
A=principal(anc,alt,otraparte)
B=principal(div,alt,L[i])
En L guardamos una lista con todas las combinaciones del conjunto de pedidos. Para cada combinación verificamos si es posible hacer un corte vertical u horizontal tal que la suma de los elementos del subconjunto sea múltiplo del numero de filas o columnas del chocolate. Si es posible hacer el corte, realizamos el mismo procedimiento con las dos partes resultantes del corte realizado, es decir, se tienen dos nuevos chocolates y dos nuevos conjuntos de pedidos. A estos dos nuevos trozos se aplica el mismo procedimiento. Aquí está la recursividad. Si no es posible hacer el corte se prueba con el siguiente subconjunto. Por otro lado, para generar las combinaciones también usamos recursividad. Por ejemplo, si quisiéramos generar todas las combinaciones de {1, 2, 3, 4}
Podríamos hacer el diagrama anterior para visualizar todas las combinaciones. Claramente existe un patrón de formación. En cada nivel se ve el mismo comportamiento para cada ramificación. El 4 nunca tiene enlaces, el 3, 2, y 1 siempre tienen 1,2, y 3 enlaces respectivamente. Esta es la idea para generar los subconjuntos. De nuevo usamos recursividad.
El código completo es el siguiente
def principal(anc,alt,par):
t=len(par)
if t>1:
L_comb=g([],par)
num_comb=len(L_comb)
for i in range(0,num_comb):
if sum(L_comb[i])%anc==0:
for j in range(0,len(L_comb[i])):
par.remove(L_comb[i][j])
div=sum(L_comb[i])/anc
alt=alt-div
A=principal(anc,alt,par)
B=principal(anc,div,L_comb[i])
if A==1 & B==1:
return 1
break
else:
return 0
break
elif sum(L_comb[i])%alt==0:
for j in range(0,len(L_comb[i])):
#print anc,alt,par,L_comb[i][j]
par.remove(L_comb[i][j])
div=sum(L_comb[i])/alt
anc=anc-div
A=principal(anc,alt,par)
B=principal(div,alt,L_comb[i])
if A==1 & B==1:
return 1
break
else:
return 0
break
else:
if i==num_comb-1:
return 0
break
else:
return 1
def sum(L):
s=0
for ele in L:
s=s+ele
return s
def f(a,L):
vect=[]
h=len(L)#tamano de L.
if len(L)>0:#si L es no vacia.
for i in range(0,h):#recorremos todo L.
b=a[:]#usamos otra variable : esto es paso por valor.
b.append(L[i])
vect +=[b]
L2=L[i+1:h]
vect +=f(b,L2)
return vect
def g(a,L):
vect=f(a,L)
vect.remove(L)
return vect
def J():
j=0
while 1:
c1=raw_input()
if c1[0]=='0':
break
c2=raw_input()
anc=int(c2[0])
alt=int(c2[2])
c3=raw_input()
par=[]
for i in range(0,int(c1[0])):
par.append(int(c3[2*i]))
resp=principal(anc,alt,par)
j=j+1
if resp==1:
print 'CASE ',j,':YES'
else:
print 'CASE ',j,':NO'
No hay comentarios:
Publicar un comentario