Python - Programas de práctica Nuclear Reactors

Esta es una solución al problema de practica Nuclear Reactors de codechef.com, la solución es correcta pero para los casos grandes se pasa del tiempo.

Enunciado:

There are K nuclear reactor chambers labelled from 0 to K-1. Particles are bombarded onto chamber 0. The particles keep collecting in the chamber 0. However if at any time, there are more than N particles in a chamber, a reaction will cause 1 particle to move to the immediate next chamber(if current chamber is 0, then to chamber number 1), and all the particles in the current chamber will be be destroyed and same continues till no chamber has number of particles greater than N. Given K,N and the total number of particles bombarded (A), find the final distribution of particles in the K chambers. Particles are bombarded one at a time. After one particle is bombarded, the set of reactions, as described, take place. After all reactions are over, the next particle is bombarded. If a particle is going out from the last chamber, it has nowhere to go and is lost.

Enunciado completo

Código:

#!/usr/bin/env python
linea = raw_input()
i=0
c=0
linea = linea.split()
n_centrales = 0
n_centrales = int(linea[2])
max = 0 
max = int(linea[1])
n_bombardeos = 0 
n_bombardeos = int(linea[0])
centrales = [0] * n_centrales
def bombardear( n ):
 if n >= n_centrales:
  return
 else:
  centrales[n] = centrales[n] + 1
  if centrales[n] > max:
   centrales[n] = 0
   bombardear(n+1)
  return
  
while i < n_bombardeos:
 bombardear(0)
 i = i + 1

while c < n_centrales - 1:
 print centrales[c],
 c = c + 1

print centrales[n_centrales - 1], 

Para mejorar el tiempo habría que eliminar la recursividad.

Programación - Reglas para optimizar código en python

Como en anteriores entradas donde mostraba formas más eficientes de hacer operaciones de entrada/salida en C/C++ ahora voy a dar unos consejos parecidos para programar en Python con restricciones de tiempo.

1) Importar lo mínimo y siempre que sea extrictamente necesario:

Resolviendo un problema para una web, me lo rechazaban por no terminar en el tiempo límite, eliminé un import string que necesitaba para una función que necesitaba y mirad la diferencia.

Y eso que esa operación que eliminé solo la ultilizaba una vez para dar formato a la información de entrada, de haberla usado en un bucle por ejemplo la mejora sería mayor.
2) Evitar recursividad
Siempre es más eficiente, tanto en Python como en otros lenguajes hacer algo de forma iterativa que hacerlo con recursividad, el problema anterior tenia recursividad y para entradas muy grandes se quedaba sin tiempo.

3) Trabajar con listas

Intentar trbajar con listas ya que en Python están bastante optimizadas.