Linguagem de Programação e Compiladores: Dicas e preferências

[Amon_Gwareth]

Aqui um site muito foda:http://projecteuler.net/

No começo eu achava que todos esses problemas poderiam sair usando matemática pura, consegui resolver alguns assim*, mas chegou uma hora que percebi que estava fazendo um trabalho desnecessário .

Por isso resolvi aprender a programar, mas ainda tô num nível bem básico.

* 1, 5 e 6. Deu até pra encontrar a quantidade de dígitos do número do problema 16 usando a característica do logaritmo decimal, mas ainda não pensei nenhum modo de calcular a soma dos dígitos.

uia, eu faço parte deste projeto tem um tempinho já

a real é que todos os problemas são bastante resolvíveis via bruteforce básico. a questão é o quanto vc consegue otimizá-los. a partir do nível 20, fica impossível resolver qualquer problema sem um pouco de otimização e/ou alguma marotada matemática.

 

[Clown or Minstrel]

Já me cadastrei. Vamos zerar a bagaça!

 

[Thorin Escudo de Carvalho]

a real é que todos os problemas são bastante resolvíveis via bruteforce básico. a questão é o quanto vc consegue otimizá-los. a partir do nível 20, fica impossível resolver qualquer problema sem um pouco de otimização e/ou alguma marotada matemática.

Verdade, a 2ª acabou de sair na força bruta também, mas é foda, tipo, enquanto vocês tão criando algoritmos e curtindo a vida eu tô com tendo que me virar na mão mesmo.

Mesmo com otimização acabam saindo alguns resultados um pouco (muito) grandes.

 

[Amon_Gwareth]

Tem, por exemplo, o caso do problema 67 vs problema 18

Spoiler: Problema 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

Spoiler: Problema 67

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Esse é um dos primeiros casos q vc vai se deparar com a questão. N sei se vc tem 20 bilhões de anos pra resolver esse problema, provavelmente vai ter q se preocupar com questões tais como o sol morrendo enquanto teu processamento tá rolando, entre outros detalhes. Eu nem lembro qual método utilizei pra resolver, uma vez q n salvei os fontes das soluções (mas deveria ter salvado)

edit:
lembrei 0.3sec de processamento

tem uma regrinha que eles deixam no site: se a tua solução requer um tempo de processamento maior que 1 minuto, então mude alguma coisa nela, pq ela n está OK. os problemas são todos desenvolvidos pensando nessa regra. a real é que é realmente difícil atingir isso em determinados problemas. teve uns q precisei de uns 40~60min de processamento para formular a solução inicial, mas o importante é não desistir do problema até chegar no 1 minuto.

 

[Mariana Hoffmann]

Parabéns pelo Dia do Programador, seus limdos!

 

[Thorin Escudo de Carvalho]

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)[/spoiler]



Esse é um dos primeiros casos q vc vai se deparar com a questão. Eu nem lembro qual método utilizei pra resolver, uma vez q n salvei os fontes das soluções (mas deveria ter salvado)

O que seria considerado Força Bruta? Por que eu prefiro não fazer o problema a ter de ficar somando infinitamente ou testando centenas de possibilidades.

Tipo, no problema 2 eu tentei conjecturar uma fórmula geral pra soma dos n primeiros números de Fibonacci pares, depois que tinha uma hipótese eu tentava verificar a veracidade dela por indução, como os primeiros casos deram errado acabei mudando de estratégia e fui procurar um padrão dentro os próprios números.

No final, o padrão nos pares era bem mais óbvio e deu pra fazer normalmente, só o tamanho das contas que assusta um pouco.

 

[Amon_Gwareth]

Eu n sei se vou agora chover no molhado, mas vou falar desde o começo, pq mesmo q vc já saiba das coisas q vou dizer, n sei se todos os leitores do tópico sabem.

Vou usar o caso crássico de quebra de senhas.

Se vc tem o hash md5 'e7d80ffeefa212b7c5c55700e4f7193e', gerado pelo string 'senha123'.

Se vc quer descobrir a senha, mas não tem nenhuma informação sobre ela, vc pode tentar um loop entre todas as combinações de caracteres possíveis, aplicando md5 e comparando com o hash q vc tem, e interrompendo o loop no caso de um retorno positivo na comparação. Isso é computacionalmente inviável, uma vez que o tempo de processamento seria gigantesco (tome como exemplo o caso do problema 67: 20 bilhões de anos é algo relativamente inviável).

Porém, por exemplo, se vc descobre (não importa como) que a senha tem 8 caracteres, sendo eles somente a combinação de letras minúsculas e números, vc diminui astronomicamente o tempo de processamento. ainda assim é beeeem inviável testar todas as possibilidades, mesmo tendo essa heurística pista.

Agora, se vc descobre (novamente não importa como), por exemplo, que o cara que fez a senha é brasileiro, e que ele gosta de usar palavras, então vc pode executar combinações de palavras do dicionário pt-br com complementos aleatórios para tentar chegar na senha. assim, vc, novamente, diminui astronomicamente o domínio de processamento em relação ao cenário produzido pela pista anterior.

a diferença básica deste último processamento é que ele usa "conhecimento" para otimizar a busca. ou seja: ele assume algumas possibilidades do conjunto universo como falsas, baseado em algum conhecimento. brute force é toda busca que não utiliza qualquer conhecimento para diminuir o número de elementos do domínio de busca. ou seja: se vc não aplica nenhuma regra, nenhum conhecimento na busca da solução do problema, vc está executando brute-force.

o lance é que se vc aplica uma regra ruim que não ajuda em praticamente nada para restringir o domínio de processamento, isso é considerado também um brute force (embora tecnicamente não seja, pq vc efetivamente diminuiu o domínio de busca).

no caso do problema 2 (é contra as regras do site postar fora de lá qualquer indicativo para solução de algum dos problemas. mas po, é o problema 2, não o problema 300, então lá vai):

Spoiler: Problema 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

vc pode executar um brute force e calcular manualmente todos os primeiros n termos da série fibonacci que satisfazem o critério (< 4.000.000, par) e somá-los, ou então usar o conhecimento matemático: a constante phi é aproximadamente a razão entre termos consecutivos da série fibonacci, e phi^3 é a razão aproximada entre termos pares. como arredondamento não é um impeditivo para um problema simples como esse, fica fácil chegar na solução utilizando este conhecimento.

no primeiro cenário, vc testou exaustivamente a série inteira. no segundo, vc utilizou uma solução otimizada e somou somente os termos pares.

edit:
complementando - o domínio do problema é os termos da série fibonacci menores que 4.000.000. se vc testou todos eles, então vc executou um bruteforce. se vc testou todos eles menos um, então vc tecnicamente não executou um bruteforce (embora o bom senso diga que vc executou um bruteforce). dá pra usar como regra básica a do 1 minuto, pros problemas posteriores.

se o tempo computacional da tua solução for maior que 1 minuto, então vc executou um bruteforce.

 

[Thorin Escudo de Carvalho]

Got it.