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.

18 comentarios en “volvemos a la carga: rellenando espacios”

  1. Este es fácil: cuenta las palabras, divide N/palabras, y obtienes el número de subrayados que hay que insertar, con el módulo de lo de arriba sabes cuántos subrayados te sobran para, en el bucle de sustitución, cuando falten ese módulo de palabras, poner uno más.

    Y ahora te hago yo a ti otra pregunta: ¿cómo harías todo eso lo más rápido posible, incluso en una sola pasada? 🙂

  2. Me faltan datos…

    ¿Puede haber una separación de dos o más espacios entre las palabras, es decir palabra1[ES][ES]palabra2? ¿La sustitución en este caso es de un espacio = un guión?

    Luego, ¿es seguro que N es siempre mayor o igual al número de espacios?

    Por otro lado, Rafael, en una pasada no puedes sacar todas las combinaciones ¿no?

    Alejandro

  3. Se supone que al menos N es el número de palabras menos una, o más, Si no el ejercicio no tiene mucho sentido, y de la misma forma una palabra podría estar separada por varios espacios, no afecta para nada a las condiciones del problema.

    Sacar todas las combinaciones, o al menos calcularlas se puede hacer. Imaginemos que nos sobran A guiones, es decir, si tenemos P palabras, A es el número de guiones que nos sobran de separar todas las palabras por un guión. Con ese valor, A, y P, es posible buscar y calcular todas las combinaciones/permutaciones (ahora no sé exactamente cuál de las dos es, tendría que mirarlo). El problema visto de forma abstracta es de cuántas maneras se pueden juntar A elementos con P elementos.

  4. Buenas,

    Definitivamente, el problema es demasiado ambiguo.

    También estáis asumiendo que entre dos palabras hay “n” guiones, o “n+1″… y de eso tampoco se indica nada en el enunciado, jeje.

    Se puede hacer en una sola pasada, y el cálculo sería de permutaciones de “Numero de guiones MOD (Número de palabras – 1)”, siempre y cuando estemos asumiendo lo que os digo en el párrafo anterior.

    Llegados al punto en que tengamos menos guiones que huecos, se trataría de calcular el número de cadenas binarias con un número de dígitos igual al número de huecos, en las cuales hubiera tantos “1” como guiones nos queden (asumiendo que “1” signifique colocar un guión en ese hueco y “0” lo contrario).

    Por ejemplo, si tenemos 5 espacios y 3 guiones, tendríamos 32 combinaciones binarias posibles (2^5), de las cuales elegiríamos aquellas que tienen tres dígitos iguales a “1”, esto es:

    00111
    01011
    01101
    01110
    10011
    10101
    10110
    11001
    11010
    11100

    Que hacen un total de diez combinaciones posibles, o lo que es lo mismo en combinatoria:
    5 sobre 3 (5!/((5-3)!*3!))

    Dicho esto, cualquier solución que demos al problema me parece hablar por hablar, ya que el propósito no queda del todo claro… 🙁

    Un saludo

  5. Respecto a los guiones se habla que debe haber al menos uno, el problema está en cómo organizar los que sobran, y ahora acabo de darme cuenta de que ni mi cálculo ni el de Miguel son válidos: la ordenación de los que sobran ha de estar ordenados de manera uniforme, es decir 1, 1, 2, 2 o 1,1,2,2,3, etc, pero no 1,1,3,2… El problema así es más fácil: las posibles variantes son el triángulo de pascal respecto a los guiones que sobren, como se pueden poner al principio o al final, ese valor x2. Ahora sí que tengo claro que se puede hacer de una pasada sin saber antes el número de palabras que hay.

  6. No estoy de acuerdo contigo, Rafael. A pesar de que lo que tú planteas como “problema” y “solución” es correcto.

    Me parece que esa premisa no se establece en el enunciado, donde se dice:

    “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.”

    Por tanto, no se indica nada de orden creciente del número de guiones en cada espacio (o eso creo).

    En cualquier caso, yo lo había planteado como que la diferencia entre el número de guiones máximo y mínimo por hueco no excedía de 1. En cuyo caso, “1,1,2,2,3” no sería una solución válida.

    Lo dicho, enunciado ambiguo 🙁

  7. Coñe, ahora que dices eso de la diferencia… es cierto, enunciado ambiguo… Joer. 🙁

    Y en el caso de que fuera como dices, entonces el problema podría no tener solución por no quedar una combinación de guiones que permitieran ser incrementales en uno… Realmente todos los números que no pudieran descomponerse en 1+2+3+….

  8. hola crases!

    Parece que no deje claro lo de la “distribucion uniforme” asi que he puesto una notita en el enunciado… perdon por la ambiguedad!

    Rafael, Miguel: ya me decis si con esto queda mas clara la idea

    Alejandro: tambien he comentado lo de los “dos espacios”. Puedes suponer que no pasa. Y si te pasan una frase donde el numero de espacios sea mayor que el de signos de subrayado, siempre puedes insertar algunos de ellos aqui y alla y seguiria siendo “uniforme” (vease el ejemplo de las distribuciones de Miguel para 5 espacios, 3 guiones)

    Ah! y sobre la nota que proponia Rafael. Yo no he sido capaz de encontrar una solucion de menos de O(2n)… pero si a alguno se os ocurre, no dejeis de comentarlo! }:)

  9. Ahora sí queda más claro, gracias 🙂

    Por suerte, las “precondiciones” son las que yo intuía, por lo que no debo hacer muchos cambios en mi planteamiento (más bien, ninguno) xD

    Sobre el número de pasadas, podemos resolverlo “al vuelo” con un único elemento iterador, con lo que el número de pasadas será el cociente de la división entera “NumGuiones/NumEspacios”. De este modo, la solución tenderá a formas crecientes o decrecientes (1,1,1,2,2,2,2 o 3,3,3,3,2,2,2,2,2) según el extremo del array por el que comencemos.

    La solución que a mí me parece más “bonita” consiste en emplear dos iteradores, uno desde cada extremo del array y rellenar también desde la primera pasada. Con esto conseguiremos una tendencia probabilística a que el mayor número de guiones se sitúen en los espacios de la zona intermedia del array, resultando en una geometría “semejante” a la campana de Gauss (cada loco tiene sus manías, y una de las mías es que mis soluciones se asemejen a cosas por las que siento admiración…)

    Espero nuevos retos Richal! 🙂

  10. No se puede conseguir un algoritmo de orden < O(n) ya que no hay modo de saber los espacios sin recorrer completamente el array. ¿Me equivoco?

  11. penyaskito: efectivamente, no hay forma de hacer esto en menos de orden n (a no ser que tengamos algo de informacion previa, como el numero de espacios)

    Miguel & co: creo que teneis la solucion pero sigo viendo mucho lenguaje natural aqui… alguien se anima a poner un poco de codigo? }:)

  12. Vamos allá. Te defines un TDA que sea una lista doble enlazada cuyo elemento sea

    struct elem
    {
    string s;
    int spaces;
    };

    La implementación de la cadena, la que sea.

    Comenzamos un bucle que recorra el array origen, saque con strtok cada palabra y vaya creando un elemento por cada palabra con 1 guión. Cuando ya no hayan más palabras sabemos su número, lo restamos al total de los guiones, a lo que nos queda obtenemos el módulo y sabemos cuántos guiones nos queda por añadir (se puede emplear alguna otra cosa aquí).

    Ahora es cuestión de ir retrocediendo desde el final por el TDA e incrementar el número de guiones correspondiente.

    Hemos terminado.

    Un paso final opcional sería contruir un nuevo array a partir de la lista enlazada.

    El tiempo total es O(2n), como mucho se realizan DOS pasadas completas sobre el array, más la tercera para volverlo a componer con los guiones…

  13. Hola a todos:

    Particularmente me decanto por la opción más sencilla y después ya busco optimizaciones.
    Version sencilla pseudocodificada:

    giones=N
    int vuelta=0
    while (guiones>0){
    if EOF ->recomienza fichero
    a=leecaracter
    caso vuelta=0 if a=’ ‘ sustituye por _;
    default if a=’_’ añande guion entre a y a+1;
    guiones-1;
    }

    de esta manera, como muy descompensado queda 211111 o 44444444455,pero nunca con una diferencia de +1

    Optimicemos pues.

    Tras la primera vuelta sabemos: 1 ->cuantos espacios teniamos
    2 ->cuantos guiones nos quedan
    3 ->como de largo va a quedar el array final (total-espacios+N)
    4 ->posición de los espacios.
    Evidentemente es menor el coste de computación de calcular estas cosas que dar X vueltas.

    Optimizado quedaría:

    giones=N
    espacios=0
    esp_asignados=0
    total_char=0
    posiciones=*int
    inicio_pos=posiciones;

    pos=0

    while (not eof){
    a=leecaracter
    if a=’ ‘ sustituye por _; espacios+1M; &posiciones=pos; posiciones+1;
    guiones-1;
    if guiones ==0 break; //hay que pensar en to!
    total_char+1;
    pos+1;
    posciones=NIL

    }
    total_char=total_char+N-guiones; //no vale aqui para nada,pero en otro marco puede ser muy util.

    //calculamos a cuantos tocan
    esp_asignados=N/espacios;

    posiciones=inicio_pos;
    while (posiciones!=NIL){
    inserta esp_asignados’_’en array[&posiciones]
    posiciones+1
    }
    posiciones=inicio_pos;

    //colocamos los que sobran en las primeras extra posiciones

    extra=N mod espacios
    if extra!=0
    for (i=0, i

  14. Vale, 2 cosas que no había caido:

    1) Lo de varios espacios seguidos -> en la primera vuelta un análisis y en la colocación una distribución según nos haya salido, comprobando que tenemos _ suficientes
    2)Lo que propongo tiene una O(x)>O(2n) por que hace 3 bucles, aunque el último siempre sera

  15. Voy con meses de retraso, pero así igual se anima phobeo a postear otro nuevo:

    (ahí va el código, en PHP por supuesto :D)
    < ?php // Parametros de entrada... $cadena = "frase mas larga que la anterior"; $guiones = 7; // Preparamosnos.... $palabras = explode(" ",$cadena); // Separamos las palabras... $numespacios = count($palabras) - 1; // ¿Cuántos espacios hay? $numguiones = floor($guiones / ($numespacios)); // ¿Cuántos guiones por grupo? $guiones_de_regalo = $guiones % ($numespacios); // ¿Cuántos de regalo? // Reconstruimos la frase... foreach ($palabras as $i=>$palabra) {
    $nuevafrase .= $palabra; // Pegamos la palabra…
    if ($i < $numespacios) // ... los guiones (si no estoy pegando la última)... $nuevafrase .= implode("_",array_fill(0, $numguiones+1, "")); if ($guiones_de_regalo-- > 0) // … y un guión más a los de regalo…
    $nuevafrase .= “_”;
    }

    print($nuevafrase); // M4G1KKKKKK!
    ?>

    ¡Saludos desde Asturias!

  16. Ha pasado mucho tiempo, pero en fin…

    Ahí va mi solución. Lo que hace es: Lee la cadena (y mientras la lee, calcula el número de espacios 😉 ), y luego la recorre, metiendo los guiones.

    La fórmula es muy sencilla calcula el máximo de guiones a escribir:

    maxGuiones = numSubrayados/numEspacios + 1

    y luego calcula el número de espacios que tendrán el máximo de guiones:

    restoGuiones = numSubrayados % numEspacios

    y usamos una variable con el numero de guiones a escribir en el espacio actual (curGuiones).

    Inicialmente curGuiones = maxGuiones

    Al recorrer la cadena, cuando se encuentra un espacio, decrementa el número de espacios por con el número máximo de guiones. Si llegamos a cero, decrementamos en uno el número de guiones por espacio.

    Y ya está. El código:

    class Program
    {
    static void Main(string[] args)
    {
    StringBuilder sbCadena = new StringBuilder();
    string cadena;
    string strGuiones;
    int c;
    int numGuiones = 0;
    int numEspacios = 0;

    do
    {
    Console.Write(“Introduzca la cadena: “);
    do
    {
    c = Console.Read();
    if (c == ‘ ‘) numEspacios++;

    if(c != ‘n’ && c!= ‘r’)
    sbCadena.Append((Char)c);
    } while (c != ‘n’);
    } while (sbCadena.Length == 0);

    cadena = sbCadena.ToString();

    Console.Write(“Número de guiones: “);
    do
    {
    strGuiones = Console.ReadLine();
    } while (!int.TryParse(strGuiones, out numGuiones));

    if (numEspacios > 0)
    {
    int maxGuiones = (numGuiones / numEspacios) + 1;
    int restoGuiones = numGuiones % numEspacios;
    int curGuiones = maxGuiones;

    StringBuilder strResult = new StringBuilder();

    for (int i = 0; i < sbCadena.Length; i++) { if (cadena[i] == ' ') { strResult.Append('_', curGuiones); restoGuiones--; if (restoGuiones == 0) { curGuiones--; } } else { strResult.Append(cadena[i]); } } Console.WriteLine("Resultado: {0}", strResult.ToString()); } else { Console.WriteLine("La cadena no tiene espacios."); } Console.Write("Pulse retorno para terminar. "); Console.ReadLine(); } }

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *