Project Euler: Problema 40 (python). 8e-05 segundos
El problema 40 de Project Euler dice lo siguiente:
An irrational decimal fraction is created by concatenating the positive integers:
0.123456789101112131415161718192021…
It can be seen that the 12th digit of the fractional part is 1.
If dn represents the nth digit of the fractional part, find the value of the following expression.
d1d10d100d1000d10000d100000d1000000
Respuesta: 210
El problema trata de un número cuya parte decimal viene dada por la concatenación de los números (1, 2, 3, 4, 5, 6, …). Ahora bien, la primera idea que a uno se le viene a la mente es concatenar todos los números como si fuera strings, s = ‘0’ + ‘1’ + ‘2’ + ‘3’ + ‘4’ + ‘5’ + … hasta que la longitud de s, len(s), dé como resultado un número igual a 1000000. Luego simplemente multiplicamos “int(s[1]) * int(s[10]) * … int(s[1000000])” y eso sería la respuesta. Así es como lo hacen acá
Ello toma al rededor de 0.17 segundos en mi computadora. Sin embargo, me pregunté si había una manera más óptima de resolverlo. Entonces logré dar con una solución que es aproximadamente 1276 veces más rápido.
Sea ‘dig’ el dígito ‘n’-ésimo de la parte decimal del número 0.12345678910111213… Supongamos que queremos encontrar el dígito en la posición 2798. Según la imagen, nosotros sabemos que este corresponde a un número de 4 cifras, el cual es 1002. Sabemos también que el mayor número de (4 - 1) cifras se sitúa en la posición 2789. Si restamos 2798 - 2789 obtenemos 9 dígitos restantes por contar, los cuáles se encuentran definitivamente en los números de 4 cifras. Finalmente, solo tenemos que contar 9 dígitos desde el primer número de 4 cifras, 1000. O lo que es lo mismo, hacer la división entera del número de dígitos resasntes entre el número de cifras (9 // 4 == 2) y sumarle 1, lo que da 3. Entonces, dígito se ubica en un número que es igual a 1000 + ( 3 - 1).
Obviamente, sin la imagen dada, nosotros no sabemos el número de cifras (n_cif) ni la posición que ocupa el dígito en el máximo número de (n_cif - 1). Todo esto lo hará el programa por nosotros. A diferencia de la solución del enlace, las iteraciones son mínimas. Lo siguiente es el código:
def dig_enesimo(n):
n_cif = 0 #n corresponde a un numero de n_cif cifras
suma = 0
while suma < n:
n_cif += 1
digitos = 9 * n_cif * 10 ** (n_cif - 1) #{1cif->9 dig;2cif->180dig;3dig->2700dig...}
suma += digitos
suma = suma - digitos
n_dig = n - suma #digitos restantes en un numero de n_cif cifras
numero = n_dig // n_cif #contando de n_dig en n_dig
pos_num = n_dig % n_cif #digitos sobrantes
if pos_num != 0: numero += 1
else: pos_num = n_cif
pos_num = pos_num - 1 #dado un numero 'numero', pos_num es el digito en la posicion pos_num
numero = 10 ** (n_cif - 1) + numero - 1
dig = int(str(numero)[pos_num])
return dig
result = 1
for i in [1, 10, 100, 1000, 10000, 100000, 1000000]:
result *= dig_enesimo(i)
print result
Project Euler: Problema 39 (python)
El problema 39 de Project Euler dice lo siguiente:
If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.
{20,48,52}, {24,45,51}, {30,40,50}
For which value of p 1000, is the number of solutions maximised?
Respuesta: 840
La manera en que he pensado este problema es analizar todos los triángulos rectángulos posibles con lados enteros. El siguiente código genera una lista con todos los triángulos rectángulos de hipotenusa menor o igual a n. Si n == 20: triangulos_menores(20), entonces esta función devuelve [(5, 3, 4), (13, 5, 12), (10, 6, 8), (17, 8, 15), (15, 9, 12), (20, 12, 16)]
def triangulos_menores(n):
#lista de triangulos con hipotenusa
#menor o igual a n
l = []
n += 1
for i in range(1, n):
for j in range(i, n):
h = (i ** 2 + j ** 2) ** 0.5 #hipotenusa
if (h <= n) and (h == round(h)):
t = (int(h), i, j) #triangulo
l.append(t)
return l
Sin embargo el problema no está en función a la hipotenusa, sino al perímetro máximo. Sea p_max el perímetro máximo que puede tener nuestro triángulo y supongamos que tenemos un triángulo de lados variables de catetos ‘i’, ‘j’ e hipotenusa ‘h’, entonces se cumple: ‘h <= p_max - i - j’. La función devuelve un diccionario donde los índices son los perímetros y sus valores son las veces que se repiten: {perimetro: veces-que-se-repite, …}. El código es el siguiente:
import time
inicio = time.time()
def perimetros(p_max):
dic = {}
p_max += 1
for i in range(1, p_max):
for j in range(i, p_max):
h = (i ** 2 + j ** 2) ** 0.5 #hipotenusa
if (h <= p_max - i -j) and (h == round(h)):
p = int(h + i + j)
if p in dic:
dic[p] += 1
else:
dic[p] = 1
return dic
p_max = 1000
d = perimetros(p_max)
d_values = d.values()
d_keys = d.keys()
i = d_values.index(max(d_values))
final = time.time()
tiempo = final - inicio
print "Respuesta: ", d_keys[i]
print "Tiempo: ", tiempo
Primera experiencia en C con GLIB. Problema 3 (Project Euler)
Si bien ya he probado GLib anteriormente, creo que lo hice casi a ciedas y muy apresuradamente: empezando con él en un proyecto real. Luego de unos meses, he decidido hacer experimentos con problemas que solía programar en Python de Project Euler. No sé si la solución que mostraré a continuación sea la mejor, pero más que nada quiero mostrar cómo usé GLib.
La solución (6857):
/*
* PROBLEMA 3 (HECHO)
* The prime factors of 13195 are 5, 7, 13 and 29.
* What is the largest prime factor of the number 600851475143 ?
*/
#include <stdio.h>
#include <glib.h>
gboolean primo (gint64 numero) {
gint64 j;
gboolean is_primo;
if (numero != 2) {
is_primo = TRUE;
j = 2;
while ((j < numero) && (is_primo)) {
if (numero % j == 0) {
is_primo = TRUE;
}
j++;
}
}
else {
is_primo = TRUE;
}
return is_primo;
}
void main(void) {
gboolean is_primo, is_factor;
gint64 numero, i, mayor;
i = 2;
numero = 600851475143;
mayor = i;
while (i 2) {
if (i > mayor) {
mayor = i;
}
}
}
}
i++;
}
printf("%llu\n", mayor);
}
GLib en C usando Geany
Quiero ir rápido con este post. Estoy volviendo a trabajar con C, así que como IDE estoy usando Geany. Como estoy usando la librería “GLib” de GNOME, he tenido que configurar los comandos para construir mi programa..
Primero voy a “Construir” —> “Establecer comandos de configuración”
Allí agrego en el comando de Construcción lo siguiente:
Finalmente, podemos construir nuestros programas en C usando GLib sin problemas.
Rombo (texto) en Python
Este programa lo hice hace un año o tal vez hace 8 meses. Crea un rombo según el número de líneas. Si el número es par es imposible crear el rombo. El resultado queda algo como lo siguiente:
def intercalar(i):
inter = "*x"
inter = inter*i
return inter[:len(inter)-1]
n = raw_input("lineas: ")
n = int(n)
if n%2 == 0:
print "No me sale con pares :("
if n%2 != 0:
esp = (n-1)/2
for i in range (1,esp+1):
print "-"*(esp-i)+"-" + intercalar(i)+ "-"*(esp-i)+"-"
print intercalar(esp+1)
for i in range (esp,-1,-1):
if i >0:
print "-"*(esp-i)+"-" + intercalar(i) + "-"*(esp-i)+"-"
program Carrera;
function clima_funct(): String;
var aleatorio: Integer;
begin
randomize;
aleatorio := random(101);
if aleatorio in [0..25] then begin
clima_funct := 'Mojado';
end
else begin
clima_funct := 'Seco';
end;
end;
function tiempo_mala_maniobra(p: Real): Integer;
var aleatorio: Integer;
begin
randomize;
if (p > random())then begin
tiempo_mala_maniobra := 0
end
else begin
aleatorio := random(24) + 7;
tiempo_mala_maniobra := aleatorio;
end;
end;
function work_funct(p: Real): Boolean;
begin
randomize;
if (p > random()) then begin
work_funct := False;
end
else begin
work_funct := True;
end;
end;
var f_piloto, f_circuito, f_out: Text;
//
cant_pilotos: Integer;
h_pista_seca, h_pista_moj, prob_mala_man,
prob_falla_mec: Real;
vel_prom_rect, vel_prom_curv: Integer;
//
//
vueltas, tipo_curva, rect_dist, curv_deg,
curv_radio: Integer;
//
//
dist_total_recta: Integer;
dist_total_curva, dist_total: Real;
vel_prom: Real;
t_curva, t_recta: Real;
clima: String;
tiempo: Real;
i, j: Integer;
ganador: Integer;
tiempo_ant: Real;
work: Boolean;
//
begin
//
assign(f_piloto, 'piloto.txt');
assign(f_circuito, 'circuito.txt');
assign(f_out, 'resumen.txt');
reset(f_piloto);
reset(f_circuito);
rewrite(f_out);
//
dist_total_curva := 0;
dist_total_recta := 0;
while not eof(f_circuito) do begin
read(f_circuito, vueltas, tipo_curva);
while not eoln(f_circuito) do begin
if tipo_curva = 1 then begin
read(f_circuito, rect_dist);
dist_total_recta := dist_total_recta +
rect_dist;
end;
if tipo_curva = 2 then begin
read(f_circuito, curv_deg, curv_radio);
dist_total_curva := dist_total_curva +
curv_radio*(pi()*curv_deg/180);
end;
read(f_circuito, tipo_curva);
end;
end;
writeln('sali');
dist_total := dist_total_recta + dist_total_curva;
clima := clima_funct();
writeln(f_out, 'Longitud de pista: ', dist_total:1:2);
writeln(f_out, 'Numero de vueltas: ', vueltas);
writeln(f_out, 'Condicion de pista: ', clima);
writeln(f_out, 'Piloto/Tiempo');
//
read(f_piloto, cant_pilotos);
//
ganador := 1;
for i:= 1 to cant_pilotos do begin
work := True;
read(f_piloto, h_pista_seca, h_pista_moj,
vel_prom_rect, vel_prom_curv,
prob_mala_man, prob_falla_mec);
t_recta := dist_total_recta/vel_prom_rect;
t_curva := dist_total_curva/vel_prom_curv;
vel_prom := dist_total/(t_recta + t_curva);
if clima = 'Mojado' then begin
vel_prom := vel_prom * h_pista_moj;
end;
if clima = 'Seco' then begin
vel_prom := vel_prom * h_pista_seca;
end;
tiempo := (dist_total/vel_prom)*vueltas;
j := 0;
while (j 1 then begin
if tiempo < tiempo_ant then begin
ganador := i;
end;
tiempo_ant := tiempo; //¿Es la mejor manera?
end;
end
else begin
writeln(f_out, 'Piloto ', i, ': AFUERA');
ganador := 0;
end;
end;
writeln(f_out, 'El ganador fue el piloto ', ganador);
close(f_piloto);
close(f_circuito);
close(f_out);
end.
PiTiVi: La vida está llena de insectos… y no tengo Raid Max
Problema raro en PiTiVi
Problema extraño en PiTiVi. Vean como parpadea el Timeline, no se previsualizan los frames y si agrego otro video esto termina congelándose totalmente.
d10
1000, is the number of solutions maximised?
