volvemos a la carga: rellenando espacios

Hola de nuevo, crases! Mil perdones por mi desconexion del mundo estas ultimas semanas. He tenido algunos lios que atender que han ido postponiendo la publicacion de mas problemas. La buena noticia es que me ha dado tiempo a pensar algunos problemas mas asi que… espero resarcirme publicando a un ritmo mas acelerado en los proximos dias!


Como deciamos en los ultimos posts, habia pensado seguir con algunos ejercicios de algoritmia basica y que nos permitan repasar conceptos como la ordenacion, la insercion y distintas tecnicas que nos serviran mas adelante. Para empezar a calentar despues de esta pausa, os propongo un problema sencillo:


Imaginemos que tenemos un array de caracteres que representa una cadena de texto formada por palabras separadas por espacios. Imaginemos que tenemos una cantidad N de caracteres de subrayado (‘_’) por los que queremos sustituir los espacios, de una forma uniforme. Es decir: si tenemos los caracteres que representan «una frase cualquiera» y tenemos 4 caracteres de subrayado, querriamos algo como «una__frase__cualquiera» (2 signos de subrayado por espacio). Si solo tuvieramos 3 caracteres, tanto «una_frase__cualquiera» (un subrayado primero, dos en el segundo) como «una__frase_cualquiera»  (dos subrayados en el primero, uno en el segundo) serian validas.



taken from http://flickr.com/photos/ashleylynn/252023013/)


Asi que en resumidas cuentas: podrias escribir una funcion que dado el array de caracteres que representa la cadena, y un numero N de caracteres de subrayado, devuelva la cadena resultante de sustituir los espacios por subrayados de forma uniforme?


Si quieres complicarlo un poco mas podrias intentar tambien devolver todas las posibles cadenas (si hay mas de una) 


Actualizacion: Parece ser que no me explique del todo bien en este problema, lo siento. Para que no haya equivocos sobre que quiere decir «distribucion uniforme» una definicion «formal» seria: no puede haber una diferencia de mas de 1 entre el numero de subrayados que asignamos a cada espacio. Asi por ejemplo:



  • Si tenemos «frase con tres espacios» y 7 signos de subrayado, la distribucion «frase__con__tres___espacios» (2 al primero, 2 al segundo y 3 al tercero) es uniforme, pero la distribucion «frase___con___tres_espacios» (3 al primero, 3 al segundo y uno al tercero) no lo es

  • Si tenemos «frase mas larga que la anterior», la distribucion «frase_mas_larga_que__la__anterior» (1-1-1-2-2 signos de subrayado) es uniforme, pero la distribucion «frase___mas_larga_que_la_anterior» (3-1-1-1-1 signos de subrayado) no lo es

Asimismo, para efectos de «precondiciones» podeis suponer que la frase siempre tiene al menos un espacio, y que solo hay un espacio entre palabra y palabra.