Petando la pila. Problemas y retos usando recursividad.

[HackmanC]

Hola,

Creo que voy a hacer un poco de trampa, me voy a saltar algunos ejercicios, primero porque las soluciones expuestas son difíciles de mejorar. Segundo porque las combinatorias y el tema en sí ha sido algo 'recursivo' (no pun intended) para mí en foros del web, por ejemplo, 1, 2, 3; y por eso ya lo he tratado varias veces.

Así que mejor solamente expongo mis soluciones a los problemas actuales,

Problema #1

Iniciado por Pantaláimon

... Como restricción de diseño, decir que dentro de noRep no se reservará memoria dinámica tal que luego tenga que ser liberada fuera de la función. Vaya, que en caso de que queráis reservar memoria dinamicamente para destino, hacedlo fuera de la función. ...

No estoy completamente seguro, pero voy a suponer que fuera de la función significa en el main, por lo menos en el caso de C, de otra forma solo conozco dos soluciones, una variable global o un memory leak. Así que en mi caso preferí dejarlo en el main.

Código C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
char* norep(char* dst, const char* src) {
    if (*src == 0x0) {
        *(dst + 1) = *src;
    } else {
        if (*src == *dst) {
            norep(dst, src + 1);
        } else {
            *(dst + 1) = *src;
            norep(dst + 1, src + 1);
        }
    }
    return dst;
}
 
char* noRep(char* destino, const char* origen) {
    *destino = *origen;
    return norep(destino, origen);
}
 
int main(int argc, char** argv) {
    char data[] = "abccccfabaddeff";
    char* destino = calloc(strlen(data) + 1, sizeof(char));
    printf("%s\n", noRep(destino, data));
    free(destino);
    return (EXIT_SUCCESS);
}
 

Problema #2

Iniciado por Pantaláimon

... el conjunto de dígitos de los dos colmillos ha de ser el mismo conjunto que los digitos del número vampiro. ...

Esa parte no la entendí muy bien, la parte de los conjuntos y multiconjuntos, y las permutaciones, así que básicamente permuté todas las posibilidades sin orden de los números. Por este concepto en algunos casos duplica algunos cálculos dependiendo del número, por ejemplo 611161, en ese caso al permutar el 1 con los otros 1 realiza operaciones duplicadas, pero siguiendo la función de las permutaciones 6! pues es lo que hay :D. El problema, posiblemente, es que para evitarlo tendría que guardar en una lista todas las operaciones anteriores o la lógica sería demasiado compleja.

Código C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int fact(const int i) {
    return i == 0 ? 1 : i * fact(i - 1);
}
 
int count(const int value, const int i) {
    return value == 0 ? i : count(value / 10, i + 1);
}
 
void split(const int value, int dst[], const int i) {
    if (value > 0 && i >= 0) {
        dst[i] = value % 10;
        split(value / 10, dst, i - 1);
    }
}
 
int join(int value, const int src[], const int end, const int begin, const int dec) {
    if (end >= begin) {
        value += src[end] * dec;
        return join(value, src, end - 1, begin, dec * 10);
    }
    return value;
}
 
void swap(int dst[], const int a, const int b) {
    int t = dst[b]; dst[b] = dst[a]; dst[a] = t;
}
 
int esvampiro_row(const int value, int src[], const int digits, const int i, const int row) {
    int value1 = join(0, src, (digits / 2) - 1, 0, 1);
    int value2 = join(0, src, digits - 1, (digits / 2), 1);
 
    printf("%.4d : %.3d x %.3d\n", row, value1, value2);
 
    if (value1 * value2 == value && !(value1 % 10 == 0 && value2 % 10 == 0)) {
        return 1;
    } else {
        if (i < digits - 1) {
            swap(src, i, i + 1);
            return esvampiro_row(value, src, digits, i + 1, row + 1);
        }
    }
 
    return 0;
}
 
int esvampiro(const int value, int src[], const int digits, const int i, const int row, const int f, const int visited) {
    int tmp[digits];
 
    memcpy(tmp, src, digits * sizeof(int));
    if (!visited && esvampiro_row(value, tmp, digits, 0, row + 1)) {
        return 1;
    } else {
        if (i > 1) {
            swap(src, i, i - 1);
            return esvampiro(value, src, digits, i - 1, row + digits, f, 0);
        } else {
            if (row < f) {
                return esvampiro(value, src, digits, digits - 1, row, f, 1);
            }
        }
    }
 
    return 0;
}
 
int esVampiro(int num) {
    int digits = count(num, 0);
    int n[digits];
 
    split(num, n, digits - 1);
 
    if (digits % 2 == 0) {
        int f = fact(digits);
        return esvampiro(num, n, digits, digits - 1, 0, f, 0);
    }
 
    return 0;
}
 
int main(int argc, char** argv) {
    printf("%d\n", esVampiro(1395));
    return (EXIT_SUCCESS);
}
 

Como siempre, los algoritmos no están optimizados ni especializados, y posiblemente se me haya pasado mas de algún error, y como ya es la una de la mañana por aquí, pues básicamente ese es el concepto de mis propuestas.

Saludos,