Alba on Tech

Talking about technology

Kata: Media inversa

Todo el mundo sabe hacer una media. Es uno de los primeros ejercicios de programación que se hacen. Pero en un caso real he tenido que calcular una media inversa, y me ha parecido muy interesante para plantearlo aquí como kata.

Pero, ¿qué quiero decir con “media inversa” de un número n?. Se trata de una lista con el mínimo número de enteros del 1 al 10 cuya media sea ese número n. Por ejemplo:

  • 5.5 –> 5, 6   ( Ya que (5+6) / 2 es 5.5 ). También sería válido: 10,1   ( Ya que (10+1) / 2 es 5.5 )
  • 4.25 –> 10, 5, 1, 1 ( Ya que (10+5+1+1) /4 es 4.25 )
  • 9.88 –> 10, 10, 10, 10, 10, 10, 10, 9 ( Ya que (10+10+10+10+10+10+10+9) /8 es 9.88 )

Esto tiene varias consideraciones y límites:

  • La precisión de los números será de 2 decimales.
  • El número máximo de elementos de la lista será 10.
  • El número para el que se busque la media debe estar entre 1 y 10.
  • Hay que buscar siempre el mínimo número de elementos en la lista.
  • Existen números para los que es imposible obtener su media inversa en estas condiciones. Por ejemplo, es imposible obtener la media inversa de 3.73. En este caso obtendremos la media que más se aproxime. En este caso, sería 1,1,3,10 (3.75).

Es aconsejable pensar un poco antes de lanzarse a programar como locos. Mi primera versión de esta Kata era un backtraking sin mucho criterio y, aunque funcionaba, podía tardar varios minutos. La versión que utilizo ahora tarda menos de un segundo. ¡Y está en javascript!

Pongo mi solución en el primer comentario.

Y recuerda, no se trata de un concurso. Se trata de una kata. Practica y mejora. Siempre

Advertisements

25 June, 2012 - Posted by | Kata, Programación

17 Comments »

  1. Mi solución en Javascript, usando recursividad. Ha sido crítico para el rendimiento probar los números de mayor a menor. La función principal es “inverseAverage”

    /**
    * Calculates the average of the numbers on an array
    **/
    function average(vals){
        var num = vals.length;
        if (num == 0) {
            return 0;
        }
        
        var total = 0;    
        var i;
        for (i=0; i< num; i++){
            total = total + vals[i];        
        }
        var avg = total / num;
        
        //Round a number for two decimal places
        var result = Math.round(avg*Math.pow(10,2))/Math.pow(10,2);
        return result;
    }
    
    /**
    * Copy an array
    */
    function copy(a){
        var i = 0;
        var b = [];
        for (i=0; i<a.length;i++){
            b[i]=a[i];
        }
        return b;
    }
    
    
    
    /**
    * Recursive function to calculate the inverse sum, IE, given an objetive number, the list of numbers that adds to this number
    * @param val The value objetive
    * @param numbers The list of numbers so long
    * @param numNumbers How much numbers left to put on the list
    */
    function calculateInverseSum(val, numbers, numNumbers){
        if (numNumbers == 1){ //If only one number left
            if (val <= 10){ //If only left one number, and the objetive number is reachable (below 10)
                numbers[numbers.length] = val; //Add number to list
                return numbers; //Return list
            }else{
                return false; //We can't reach the objetive with one number
            }
        }
        
        var n;
        for (n=10;n>=1; n--){ //Let's try all numbers from 10 to 1
            var val2 = val-n; //Substract a number from the objetive
            if (val2>=1){ //If the new objetive is 1 or more
                var numbers2 = copy(numbers); //Get a copy of the array
                numbers2[numbers2.length] = n; //Add number to list      
                var result = calculateInverseSum(val2, numbers2, numNumbers-1); //Call to recursive function, with the new objetive, the actual list, and one less number
                if (false != result){
                    return result;  //We get it!
                }
            }
        }
        return false; //There is no response
        
    }
    
    /**
    * Calculates the inverse average of a value
    */
    function inverseAverage(val){    
        var numNumbers; //Size of the list
        var margin = 0; //How close to the actual result is ok
        while (margin<1){    
            for (numNumbers = 1; numNumbers< 10; numNumbers++){ //Max size = 10
                var newVal = val * numNumbers; //The number to get is the value * the size of the list
                var roundVal = Math.round(newVal);
                    if (Math.abs(newVal-roundVal)<= margin){ //The number to get must be an integer, and be close (margin) to the objetive
                        var numbers = calculateInverseSum(roundVal, [], numNumbers); //Call to recursive function
                        if (false != numbers){
                            return numbers + " ("+average(numbers)+")"; //We get it!
                        }
                    }
                
            }
            margin = margin+0.05; //Make margin greater and try again
        }
        
        return false; //There is no response
    }
    

    Comment by Pablo Alba | 25 June, 2012 | Reply

  2. Curioso ejercicio, es más reto de lo que parece. Estoy mirando a ver hasta dónde llego sin mirar la solución. Por ahora estoy con el backtracking, efectivamente más lento que el copón.

    Comment by Andrés Moya | 27 June, 2012 | Reply

  3. Me la apunto! Comentaré mis avances.

    Comment by Antonio de la Torre | 27 June, 2012 | Reply

  4. ¡¡Buena pinta!! Yo estoy haciendo con python una aproximación por tipos de número, para ver si puedo hacer salidas rápidas. Ya voy contando…

    Comment by Yamila Moreno (@yamila_moreno) | 27 June, 2012 | Reply

  5. Mi propuesta es bastante sencilla. He probado con los valores de ejemplo y funciona. Está escrito en Python. Estoy seguro de que se pueden eliminar un montón de líneas que se pueden simplificar con comandos que no conozco, pero bueno. El quid de la cuestión es multiplicar el valor por 1, por 2, por 3,…, por 10 y ver el resultado que más se parezca a un entero. Luego consiste en buscar una cantidad de números (el multiplicando) en la lista que sumen ese resultado.

    ###################################################################

    #media inversa (kata)
    
    #numero del que se quiere calcular la media inversa
    num = 4.25
    
    #lista con los valores de 1 a 10
    ls_1_10 = [1,2,3,4,5,6,7,8,9,10]
    
    #otra lista con el numero multiplicado por 1, por 2... hasta 10
    ls = []
    for i in ls_1_10:
        ls.append(round(i*num,2))
    
    #lista que almacena las diferencias entre
    #el valor y el entero mas cercano
    ls_dif=[]
    for i in ls:
        ls_dif.append(round(abs(i-round(i)),2))
    
    #calculo la posicion y el valor 
    indice = ls_dif.index(min(ls_dif))
    N = round(ls[indice])
    
    #recibe como entrada la cantidad de numeros para hacer media. busca 
    #combinaciones de esa cantidad de numeros que hacen que la suma sea N,
    #o sea, cuya media se parezca a num
    def busca(indice):
        
        lista_total = [1]*(indice+1)
            
        for i in ls_1_10:
            for j in range(indice+1):
                lista_total[j] = i
                if sum(lista_total) == N:
                    return lista_total
    
    resultado = busca(indice)
    
    print resultado
    

    #######################################################################

    Comment by Martxelo | 27 June, 2012 | Reply

    • ¡Una solución muy interesante, Martxelo! Me gusta mucho tu idea de buscar el número entero más cercano, para saber de antemano cuantos números harían falta. Por cierto, ya te lo he formateado, que el wordpress da problemillas con el código

      Comment by Pablo Alba | 27 June, 2012 | Reply

      • Me estoy dando cuenta de un pequeño error. Elijo el valor que más se parece a un entero, pero lo que hay que hacer es otra cosa. Hay que hacer una lista que contenga

        [round(valor_entrada*i)/i] i = 1..10

        el valor de esa lista que más se parezca al valor de entrada es el que bueno y su posición dará el número de elementos de la lista.

        Comment by Martxelo | 27 June, 2012

  6. Bueno, espero que podáis indentar automáticamente lo que he escrito. No sé por qué pero ha salido así. Aquí lo tenéis mejor puesto:

    http://pastebin.com/Yak4f3Q7

    Comment by Martxelo | 27 June, 2012 | Reply

  7. Bueno, aquí va otra vez el código mejorado. He cambiado el error que tenía y he acelerado la manera de llenar la lista resultado. Ahora lo que hago es lo siguiente. Se coge la media aritmética de la lista y se redondea. Se llena toda la lista con esos valores. Se mira lo que sobra o lo que falta para que sumen lo que deben sumar y se corrigen los valores que sean mayores que 10 o menores que 1.

    He calculado todos los valores desde 1.00 hasta 10.00 en pasos de 0.01 (901 valores) y ha tardado 0.2 segundos.

    Vuelvo a copiar el código y supongo que se tendrá que volver a editar:

    ###################################################################
    import datetime
    import scipy as sp

    #media inversa (kata)
    def media_inversa(num):

    #lista con los valores de 1 a 10
    ls_1_10 = [1,2,3,4,5,6,7,8,9,10]

    #otra lista con el numero multiplicado por 1, por 2… hasta 10
    #redondeando y divididiendo por la posicion
    ls = []
    for i in ls_1_10:
    ls.append(round(i*num)/i)

    #lista que almacena las diferencias entre
    #el valor de ls y num
    ls_dif=[]
    for i in ls:
    ls_dif.append(round(abs(i-num),2))

    #calculo la posicion de la diferencia minima y el valor como el
    #elemento de ls que esta en la posicion marcada por indice. En el
    #documento N=round(4v).
    indice = ls_dif.index(min(ls_dif))
    N = round(ls[indice]*(indice+1))

    #llenamos el array resultado
    resultado = [int(round(N/(indice+1)))]*(indice+1)
    resto = int(N-sum(resultado))
    resultado[indice] += resto

    #corregir el ultimo valor si se ha pasado de 10
    if resultado[indice]>10:
    resto = resultado[indice]-10
    resultado[indice] = 10
    resultado[indice-1] -= resto

    #corregir el ultimo valor si esta por debajo de 1
    if resultado[indice]<1:
    resto = resultado[indice] – 1
    resultado[indice] = 1
    resultado[indice-1] -= resto

    return resultado

    #tiempo
    time = datetime.datetime.now()

    f=open('media_inversa.txt','w')

    for i in sp.arange(1,10.01,0.01):
    resultado = media_inversa(i)
    f.write(str(resultado) + '\n')

    f.close()

    print 'Tiempo = ', datetime.datetime.now() – time
    #######################################################################

    Comment by Martxelo | 28 June, 2012 | Reply

  8. Por si acaso:

    http://pastebin.com/SkPEEnyU

    Comment by Martxelo | 28 June, 2012 | Reply

  9. […] este problema hay dos casos: los que tienen una solución exacta y los que necesitan una aproximación. […]

    Pingback by Medias inversas | (void *) blog | 1 August, 2012 | Reply

  10. Hola:

    Dejo aquí mi solución, he intentado atacarla un poco más desde el aspecto matemático 🙂

    También he escrito una explicación un poco más detallada en mi blog: http://p.jdiez.me/index.php/medias-inversas/

    from math import floor, ceil, modf
    
    target = 
    max_k = 10.0
    
    def compute_avg(list):
    	if len(list) == 0:
    		return 0
    	sum = reduce(lambda i, j: i + j, list)
    	return round(float(sum) / len(list), 2)
    
    def generate_list(target, n, m):
    	result = [target + 1 for i in range(0, n)]
    	map(lambda x: result.append(target), range(0, m))
    
    	return result
    
    def round_approximation(n, m):
    	(decn, intn) = modf(n)
    	(decm, intm) = modf(m)
    
    	return (int(ceil(n)), int(floor(m))) if decn > decm else (int(floor(n)), int(ceil(m)))
    
    def inverse_avg(target, n, m):
    	res = generate_list(target, n, m)
    	avg = compute_avg(res)
    
    	return (avg, res)
    
    def sort_attempts(x, y):
    	dx = abs(target - x['average'])
    	dy = abs(target - y['average'])
    
    	if dx > dy:
    		return 1
    	elif dx == dy:
    		return 0
    	else:
    		return -1
    
    (decimal, integer) = modf(target)
    decimal = round(decimal, 2)
    k = 1
    
    while k  max_k:
    	"""
    		n/k = n'/10
    		m/k = m'/10
    
    		n' = 10n/k
    		m' = 10m/k
    	"""
    	attempts = []
    
    	for i in range(1, 10):
    		(t_n, t_m) = ((i*n)/(n+m), (i*m)/(n+m))
    		(t_n, t_m) = round_approximation(t_n, t_m)
    
    		(avg, elements) = inverse_avg(int(target), t_n, t_m)
    		attempts.append({'average': avg, 'n': t_n, 'm': t_m})
    
    	attempts.sort(sort_attempts)
    	winner = attempts[0]
    
    	print inverse_avg(int(target), winner['n'], winner['m'])
    else:
    	print inverse_avg(int(target), n, m)
    

    Una Kata verdaderamente interesante. 😀

    Comment by José Manuel Díez | 1 August, 2012 | Reply

  11. Interesante kata, gracias Pablo.
    He puesto una posible solución Java en http://t.co/ytMNIwtH
    Lo creo que es un poco especial del algoritmo que he usado es que no me interesan los números concretos de la secuencia, si no solo cuantos números hay y cuánto sumas, de hay se puede sacar la media, digamos que podemos hacer clases de equivalencia con esos datos. Por ejemplo 5,5,5 a efectos de calcular la media es equivalente a tener 10,2,3.
    Así que ni siquiera me fijo en que secuencia que genera la media, la calculo a posteriori una vez que se cuántos números tengo y que suma tiene que dar. Hay muchas secuencias que generar dicha media, yo por ejemplo he usado unos y dieces, y en el último número ajusto.

    Comment by Leo Antoli | 10 September, 2012 | Reply

  12. Tengo una dudilla

    “Existen números para los que es imposible obtener su media inversa en estas condiciones. Por ejemplo, es imposible obtener la media inversa de 3.73. En este caso obtendremos la media que más se aproxime. En este caso, sería 1,1,3,10 (3.75).”

    Creo que una media media inversa más aproximada para 3,73 puede ser (4+4+4+4+4+3+3)/7=3,71 (realmente 3,714285…).

    3,73 * 4 = 14,92 -> Error = |15 – 14,92| / 4 = 0,02
    3,73 * 7 = 26,11 -> Error = |26 – 26,11| / 7 = 0,01571428…

    ¿Ningún cálculo puede hacerse con más de dos decimales o ni multiplicar por cien?

    Comment by itmares | 31 October, 2012 | Reply

  13. Hola, itmares.
    ¡Tienes razón! Tu media inversa es más exacta. En mi caso, estaba trabajando con un márgen de 0.05, por lo que encontré antes la solución de 4 números.

    Los cálculos se pueden hacer con la precisión que prefieras, pero los resultados deben tener 2 decimales.

    ¡Gracias por tu interés!

    Comment by Pablo Alba | 31 October, 2012 | Reply


  14. function invAvg(avg) {
    strRes = "111111:::::9887766655599444777::3333888555779999222";
    ent = avg | 0;
    frac = Math.round((avg - ent) * 100);
    if (frac > 49) {
    frac = 100 - frac;
    }
    nList = strRes.charAt(frac) - '0';
    result = [];
    for (i = 0; i < nList; i++) {
    result[i] = ent;
    if (i < Math.round(avg * nList) % nList) {
    result[i]++;
    }
    }
    return result;
    }

    avg = prompt("Introduzca media: ", 3.73);
    alert("Resultado: " + invAvg(avg));

    http://jsfiddle.net/VCPQV/

    Comment by itmares | 2 November, 2012 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: