tudo pela ciência [ALGORITMOS+PYTHON] - soma de todos os múltiplos xn até um limite L

Porque um dia vou me esquecer disto e vou precisar para uma entrevista, de certeza.

Problem 1

05 October 2001

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

A pergunta tá demasiado fácil, melhor generalizá-la, só porque sou do IST, CARALHO:

Problem 1RELOADED

30 November 2011

Find the sum of all the multiples of x₁,x₂,...,x_n below L.

Continua fácil do ponto de vista funcional, mas agora há um potencial de optimização maior: porque tamos a lidar com potencialmente infinitas variáveis de entrada, quantos menos loops no algoritmo, melhor - porque um loop implica complexidade pelo menos o(n) e eu quero complexidade o(1) pra podermos \o/ (ganhar (wohoooo)).

Funcionalmente, quer-se um algoritmo que:

1. Desdobre x₁, x₂, ..., x_n nos seus múltiplos até L
2. Elimine os múltiplos em duplicado (por exemplo 15 é múltiplo de 3 e 5 e então não deve ser contabilizado duas vezes)
3. Faça a soma de tudo e retorne o resultado

1. Abordagem brute-force, em pseudocódigo:

Given arbitrary x₁,...,x_n and L

i, j = 0                      // inicializa contadores i e j a 0 b c d e f 12

multiple = 0             // inicaliza multiple a 0, a variávele que contém o múltiplo a tratar

multiples = []           // inicializa vector de múltiplos já conhecidos a vazio

sum_of_multiples = 0 // inicializa variável acumuladora da soma dos múltiplos

for i=1, i < N, i+1                         // para todos os valores de entrada x₁,...,x_n

    for j=1, multiple < L, j+1          // para todos os múltiplos até L de um determinado xi

        if multiple is not on multiples    // se o múltiplo é novo (não está no vector de múltiplos)

            add multiple to multiples                // 1. adiciona o múltiplo ao vector de múltiplos

            sum_of_multiples+=multiple         // 2. adiciona o valor à actual soma dos múltiplos

        else                                                 // SENÃO

            pass                                               // caga pra tudo, rapaz, mais uma volta

Esta merda funciona, e não precisa de muitas linhas de código para ser implementado em Python, por exemplo. O PROBLEMA É QUE : dois ciclos esticados até N e L (mais a procura do múltiplo dentro do vector de múltiplos) significam que vamos precisar no pior dos casos de pelo menos o(N*sqrt(L)*sqrt(L)) operações pra resolver isto. Isto quer dizer que se houver um maluco que queira saber a soma de todos os múltiplos de 1 milhão de números diferentes com o limite superior dos múltiplos a 10²⁰ , vamos precisar, de qualquer merda como 10⁶ * 10²⁰ = 10²⁶ operações, ou seja, 100 triliões de triliões de operações, e é capaz que o meu comp de 7 anos arda no processo. A propósito, um trilião de operações é o que o nosso cérebro é capaz de fazer por segundo, mas a merda é que é em fuzzy logic, nem sequer é só em binário, portanto nem tem comparação.

CONCLUSÃO: ESTA MERDA TEM COMPLEXIDADE o(N*L), SE EU APRESENTAR UMA SOLUÇÃO ASSIM AO ANDRIY SHNYR E AO CIPRIAN CUDALBU NA ENTREVISTA OS GAJOS DESINTEGRAM-SE

Baza então adicionar um requisito não funcional, fingindo que tamos nas entrevistas da nokia:

•  Quero um algoritmo de complexidade o(1)

2. Implementação heurística, em Python:

Given arbitrary x₁,...,x_n and L

roots = {x₁,...,x_n}       // cria uma lista (tuple) de "roots" com todos os valores de entrada

upper_bound = L      // açucar sintático, o L é efectivamente um upper bound

range_subsets=[]      // só pra dizer que a lista de subconjuntos de múltiplos tá vazia e é uma lista

for root in roots:  // para cada valor de entrada na lista de valores de entrada

range_subsets+=range(root,upper_bound,root) // coleciona o subconjunto que vai do valor de entrada, ao limite superior, com incrementos do valor de entrada (os múltiplos de xi até L)

result=sum(set(range_subsets)) // faz um XOR dos subconjuntos colecionados (todos os múltiplos) - um set pega em vários valores de entrada (incluindo listas), agrega tudo e elimina duplicados. No fim o sum soma tudo. Voilá.

Isto parece um bocado mais pro, e só precisa de 3 linhas de código, mas ainda tem a merda dum ciclo for. Isto é inevitável, porque não se sabe o número de valores de entrada que vamos ter. Basicamente, reduzimos a complexidade, mas só para o(n). Já é uma melhoria do caralho mas eu quero o(1), é possível? Para a pergunta  RELOADED, a resposta é não - exactamente porque precisamos dum iterador para percorrer um número desconhecido de valores de entrada, que depende do utilizador. MAS, se soubermos quantos são e quais são, é possível - o que nos remete de volta ao problema original. 

Voltando à pergunta inicial e reestabelecendo as condições iniciais (N=2, x₁=3, x₂=5, L=1000)

roots = {x₁,...,x_n}              // OBSOLETO: os valores de entrada são conhecidos, pode ser hard-coded

upper_bound = L              // OBSOLETO: valor limite conhecido, pode ser durócodificado

range_subsets=[]              // OBSOLETO: não é necessária uma estrutura intermédia para colecionar um número desconhecido de subconjuntos

result=sum(set(range(3,1000,3), range(5,1000,5)) // Faz a soma da agregação exclusiva (set) de dois subconjuntos de números gerados de 3 e 5 a 1000 com saltos 3 e 5, respectivamente (os múltiplos de 3 e 5 até 1000).

CONCLUSÃO: apesar de se conseguir para o problema original, FILHA DA PUTA DA CENA ITERATIVA a N IMPEDE-ME DE RESOLVER O PROBLEMA GENERALIZADO COM COMPLEXIDADE o(1). A única solução é inventar o computador quântico. Já venho.

obrigado por tudo, IST, a resposta é 233168, PROVA: