Project Euler 100

[Bruno Oliveira]

Não sei se já alguém aqui, o tentou sequer resolver, mas vou deixar aqui o enunciado e apresentar a minha solução em Python:

If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)(14/20) = 1/2.

The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.

By finding the first arrangement to contain over discs in total, determine the number of blue discs that the box would contain.

[Bruno Oliveira]

Vou então deixar a minha tentativa de solução (que está errada ) neste novo post:

Considerando que é o número de bolas azuis que existem de entre o total e sendo o número total de bolas, creio que é correcto escrevermos que:
.

Mas como queremos que a probabilidade de tirar duas bolas azuis, uma depois da outra seja , ficamos com a equação:
, obviamente queremos resolver esta equação em ordem a .

Efectuando umas contas:


Depois será correcto montar a equação e tratá-la como uma quadrática em que:





?

Usando este método, o meu programa facilmente resolve o caso de exemplo, mas dá erro no caso pedido...

[jap]

Coloca aqui o teu programa para nós corrigirmos!

[Tharis]

Coloca aqui o teu programa para nós corrigirmos!

"Corrigir" ?

Se ele foi por brute-force sem optimizações, e mesmo um brute-force com optimizações, duvido que exista algo a corrigir para um limite tão grande.

Mas pronto, o professor pode ter aí alguma na manga. :p

[jap]

Acho que a resposta é (por brute force e sem problemas! ):

707106783028

Estarei errado? É que me parece muito fácil!

[Tharis]

Acho que a resposta é (por brute force e sem problemas! ):

707106783028

Estarei errado? É que me parece muito fácil!

Como é que se fazem tantos ciclos? Ou será que é um brute-force especial?

O meu "brute-force" seria testar todos os números, mas pronto, não sei ao certo...

[jap]

(...)
Como é que se fazem tantos ciclos? Ou será que é um brute-force especial?

O meu "brute-force" seria testar todos os números, mas pronto, não sei ao certo...

Bom, eu comecei em 10**12, o que está para trás não interessa...

[Bruno Oliveira]

Acho que a resposta é (por brute force e sem problemas! ):

707106783028

Estarei errado? É que me parece muito fácil!

Não prof. a resposta do project euler não é essa, aliás, a resposta certa (consegui entretanto encontrar um código em VB, que executei) é um número bastante maior:

756872327473

Acho que o erro no meu programa se deve a não conseguir arranjar uma precisão de muitas casas decimais só com o float...

[Tharis]

(...)
Como é que se fazem tantos ciclos? Ou será que é um brute-force especial?

O meu "brute-force" seria testar todos os números, mas pronto, não sei ao certo...

Bom, eu comecei em 10**12, o que está para trás não interessa...

Claro que sim, mas mesmo assim.... O professor, fez um ciclo em que a variável de iteracção é o total de CDs ou o número de CDs azuis?


@Bruno Oliveira, NUNCA DUVIDES DA PRECISÃO DO PYTHON. Python tem BigInts, floats tudo implementado out-of-the-box e com as melhores optimizações....

[Bruno Oliveira]

(...)
Como é que se fazem tantos ciclos? Ou será que é um brute-force especial?

O meu "brute-force" seria testar todos os números, mas pronto, não sei ao certo...

Bom, eu comecei em 10**12, o que está para trás não interessa...

Claro que sim, mas mesmo assim.... O professor, fez um ciclo em que a variável de iteracção é o total de CDs ou o número de CDs azuis?


@Bruno Oliveira, NUNCA DUVIDES DA PRECISÃO DO PYTHON. Python tem BigInts, floats tudo implementado out-of-the-box e com as melhores optimizações....

Não duvido, claro, até estive a ler sobre o modulo decimal e tudo, assim que o conseguir implementar como deve de ser no meu programa, tenho-o feito...bem, ou quase, depois tenho de fazer um ciclo entre 1 bilião e 2 biliões para obter a resposta por brute force

[Bruno Oliveira]

Aqui vai o meu código, para tratar do caso de exemplo:

Código: Seleccionar Todos

from math import *
a=1
b=-1
for t in range(100,150):
    c=-(t**2-t)/2
    s=(-b+sqrt(b**2-4*a*c)/(2*a)
    if float(str(s))-float(int(str(s)))==0:
       print t, "soluçao",s

Eu sei que não é pitónico, não tenham um ataque , agora estou a obter erro nesta linha:

Código: Seleccionar Todos

if float(str(s))-float(int(str(s)))==0:

Antes funcionava...

[Tharis]

O teu código como o tens seria mais assim:

Código: Seleccionar Todos

from math import *
a = 1; b = -1

for t in range(100, 150):
    c = -(t**2 - t) / 2.
    s = (-b + sqrt(b**2-4*a*c) / (2. * a)
    if (float(s) - int(s)) == 0:
       print t, "soluçao",s

Atenção que não estou a corrigir o método de resolução.

[jap]

Sorry, o meu programa tinha de facto um bug mas já corrigi, aliás arrangei uma solução mais elegante!

Aqui vai a minha solução (altamente não ortodoxa!):

Código: Seleccionar Todos

"""
EULER Project #100
Elegant solution, avoiding brute force methods
Map equation

a*(a-1)
------  = 0.5
t*(t-1)

into the well known diophantine equation z^2-2y^2 = -1
using the following transformations:

y = 2a-1
z = 2t-1

Solution of the above equation can be expressed from odd powers of
(1+sqrt(2))  and  (1-sqrt(2))
see, eg,  Wolfram Research or work it out yourself!

@jap 2009, who could not go to sleep before solving this problem! :)
"""

from math import *

# To test precision/roundoff errors you may uncomment the following lines to test the results with a precision of 50 decimals!
# (you may need to install the multiprecision math module in your system)
# Tested OK: math and mpmath with 50 decimals give the same results. ;)

#from mpmath import *
#mp.dps = 50


LIMIT = 10**12

n = 3
while True:
    z = ((1+sqrt(2))**n+(1-sqrt(2))**n)/2.
    y = ((1+sqrt(2))**n-(1-sqrt(2))**n)/(2*sqrt(2))
    t = int(round((z+1)/2))
    a = int(round((y+1)/2))
    print "Total discs",t,"blue disks",a,"red disks",t-a
    n += 2
    if t > LIMIT:
       print "\nFound the solution: number of blue disks is",a
       break


cujo output é

Código: Seleccionar Todos

Total discs 4 blue disks 3 red disks 1
Total discs 21 blue disks 15 red disks 6
Total discs 120 blue disks 85 red disks 35
Total discs 697 blue disks 493 red disks 204
Total discs 4060 blue disks 2871 red disks 1189
Total discs 23661 blue disks 16731 red disks 6930
Total discs 137904 blue disks 97513 red disks 40391
Total discs 803761 blue disks 568345 red disks 235416
Total discs 4684660 blue disks 3312555 red disks 1372105
Total discs 27304197 blue disks 19306983 red disks 7997214
Total discs 159140520 blue disks 112529341 red disks 46611179
Total discs 927538921 blue disks 655869061 red disks 271669860
Total discs 5406093004 blue disks 3822685023 red disks 1583407981
Total discs 31509019101 blue disks 22280241075 red disks 9228778026
Total discs 183648021600 blue disks 129858761425 red disks 53789260175
Total discs 1070379110497 blue disks 756872327473 red disks 313506783024

Found the solution: number of blue disks is 756872327473


[Tharis]

Ui, muito fixe.... Tenho de ir ver isso ao Wolframalpha.

[jap]

Ainda mais fixe!

Uma nova solução, mais elegante (mais pitónica!), usando recursão e apenas aritmética inteira...

Código: Seleccionar Todos

"""
EULER Project #100
Elegant solution, avoiding brute force methods, solution 2
much simpler and cleaner!


Map equation

a*(a-1)
------  = 0.5
t*(t-1)

into the well known diophantine equation z^2-2y^2 = -1
using the following transformations:

y = 2a-1
z = 2t-1

Solution of the above equation can be expressed recursively
from the fundamental solution z=1,y=1!

@jap 2009, Can't get much simpler than this! :)
"""

LIMIT = 10**12

z,y = 1,1

while True:
    z,y = 3*z +4*y,2*z + 3*y
    t,a = (z+1)/2,(y+1)/2
    print "Total discs",t,"blue disks",a,"red disks",t-a

    if t > LIMIT:
       print "\nFound the solution: number of blue disks is",a
       break


Resultado deste programa (confere com o anterior!):

Código: Seleccionar Todos

Total discs 4 blue disks 3 red disks 1
Total discs 21 blue disks 15 red disks 6
Total discs 120 blue disks 85 red disks 35
Total discs 697 blue disks 493 red disks 204
Total discs 4060 blue disks 2871 red disks 1189
Total discs 23661 blue disks 16731 red disks 6930
Total discs 137904 blue disks 97513 red disks 40391
Total discs 803761 blue disks 568345 red disks 235416
Total discs 4684660 blue disks 3312555 red disks 1372105
Total discs 27304197 blue disks 19306983 red disks 7997214
Total discs 159140520 blue disks 112529341 red disks 46611179
Total discs 927538921 blue disks 655869061 red disks 271669860
Total discs 5406093004 blue disks 3822685023 red disks 1583407981
Total discs 31509019101 blue disks 22280241075 red disks 9228778026
Total discs 183648021600 blue disks 129858761425 red disks 53789260175
Total discs 1070379110497 blue disks 756872327473 red disks 313506783024

Found the solution: number of blue disks is 756872327473


Isn't Python Beautiful?