domingo, 17 de janeiro de 2010

Tatuagens em cadeia

Uma classe de artistas que eu admiro muito são os tatuadores, e por um motivo simples: eles não podem errar. Um desenhista pode usar borracha, um arte-finalista pode cobrir o erro com tinta branca, um artista digital pode apertar control-Z, mas o tatuador não pode fazer nada disso. Um escultor, se erra, tem a opção de jogar fora o bloco de pedra e começar de novo, mas o tatuador nem essa opção tem.

Exatamente por isso, tem um tatuador que eu conheço que se recusa a tatuar nomes de namorados. Tatuagens são permanentes, mas namoros são efêmeros: imagine namorar alguém que tem uma tatuagem com o nome do ex? Nesse caso, uma solução prática é reciclar a tatuagem e namorar alguém que tenha o mesmo nome do seu ex. Não é elegante, mas funciona.



Isso leva a conclusões curiosas. Veja o meu caso, por exemplo. Se eu tatuar ILA e minha esposa tatuar RICARDO, aparentemente ela estaria levando vantagem. É muito mais fácil arrumar outro Ricardo que arrumar outra Ila. Por outro lado, eu não precisaria procurar apenas Ilas, eu poderia arranjar uma Priscila ou uma Camila, bastando adicionar mais letras na tatuagem!

Isso naturalmente leva à pergunta: qual é o máximo de namoradas que um Serial Tatuator pode ter? Por exemplo, uma pessoa poderia ir de Ana para Iana e depois Fabiana. Será que dá pra achar uma cadeia de tatuagens de tamanho quatro? Cinco? Hora de fazer uma simulação!

Antes de começar, precisamos de um corpus de nomes. O jeito mais fácil de conseguir o corpus é escrevendo um crawler para um desses sites com nomes de bebês. Uma busca rápida e eu achei o Babyhold, que tem a vantagem de separar os nomes por sexo.

Script python para fazer crawling de nomes de meninas

O script retornou mais de 7100 nomes de meninas. Agora é só fazer um outro script que calcule a máxima cadeia de nomes. Como a quantidade de nomes não é tão grande assim, um algoritmo cúbico bobo dá conta do recado:

Script python para achar cadeias máximas

O script acabou achando várias soluções de tamanho seis, mas sem dúvida a seqüência mais curiosa foi a abaixo :)


Li -> Lin -> Elin -> Elina -> Angelina -> Angelina Jolie

Bônus!

Embora o algoritmo cúbico funcione bem para 7100 nomes, certamente há como otimizá-lo. Ao invés de fazer uma solução mais rápida, dessa vez eu vou abrir para os leitores enviarem suas soluções! Clicando no link abaixo você vai para o primeiro Ricbit Jam, feito com a engine do spoj. Ganha quem enviar a solução mais rápida nos próximos quinze dias. Não tem prêmio, mas o vencedor terá seu nome divulgado no próximo post :)

Ricbit Jam #1

Não adianta tentar mandar o programa em python acima, ele não acha todas as soluções e vai dar TLE no servidor do spoj. Mas você pode usar como base pra fazer a sua solução.

29 comentários:

  1. Como sempre, muito criativo. Parabéns, ricbit. O Johnny Depp teve exatamente esse problema (mais gente deve ter tido, mas não leio tanto sobre a vida dos outros): Winona Forever -> Wino Forever. De namorador a bebum. :) http://en.wikipedia.org/wiki/Johnny_Depp

    ResponderExcluir
  2. Quero só ver o cara ter culhões de conquistar a Angelina Jolie só por causa da tatuagem, hoho. ;-)

    ResponderExcluir
  3. Ricbit... Eu poderia escrever algo CURTO em Ruby que certamente não seria a melhor solução! Hehehe... Seria Ruby uma linguagem para preguiçosos? Boa história para refrescar a cabeça depois dos Universos Paralelos! Abraços!

    ResponderExcluir
  4. Então foi assim que o Billy Bob Torton fez... ele começou namorando a Shun Li!!! Genial!!

    Ainda acho que nomes masculinos e femininos devam ser considerados... visto que o cara ou a moça pode mudar de opção sexual quando bem entender!
    heheheh

    ResponderExcluir
  5. ricbit, me corrija se eu estiver enganado, mas acho que há um bug em seu script. Ou, em outras palavras, ele não resolve o problema caso ocorra o seguinte:

    Suponha a seguinte lista de nomes (input):

    cam
    ila
    camila
    camilalouca

    Se eu entendi o problema direito, as sequencias máximas são:

    cam -> camila -> camilalouca
    ila -> camila -> camilalouca

    Você pode ver que seu script píton imprime uma única sequência, que depende da ordem em que os nomes são dados. Culpa do backlink, que só salva um link.

    Certo?

    ResponderExcluir
  6. Eita. Agora que reli notei o "ele não acha todas as soluções". :)

    ResponderExcluir
  7. Sim, lá no finzinho do post eu avisei que esse script não acha todas as soluções. Mas pra passar no Ricbit Jam você precisa achar todas!

    ResponderExcluir
  8. pow, mais ninguém vai se dignar a submeter uma solução? :-(

    ResponderExcluir
  9. Algumas coisas interessantes têm ocorrido no ricbit jam #1.

    1- Aprendi que dá pra testar bem o tempo de execução no ideone.com sem precisar contar submissões no scarky.

    2- Nunca estudei busca a fundo, logo fico intrigado com o uso de memória do @girino no script python dele. Claramente, ele usa uma idéia bem diferente das demais.

    3- Agora a coisa mais intrigante é que está complicado fazer um programa em C mais rápido que o equivalente em python. Enquanto a parte mais pesada do meu algoritmo roda em 300ms em Python, estou preso em 1.3s em C puro. :( Até agora, minhas implementações customizadas de strstr foram um desastre.

    A conclusão disso tudo é que espero uma boa explicação quando tudo terminar. :P

    ResponderExcluir
  10. @trovao

    como você já viu, o lance não é busca e sim o psyco :-D

    o psyco, segundo o ricbit me contou, só otimiza funções, e não o "corpo" do script. Então coloque tudo numa funçãozona e apenas chame essa função do corpo do script (ou quebre em pequenas funções mesmo, igual eu acabei fazendo).

    O lance de C puro vai ser a falta de estruturas de dados adequadas. tente usar C++ (eu gastei 5 vezes mais tempo pra implementar em C++, mas primeira versão do primeiro algoritmo que usei foi 2 vezes mais rapida) que tem vector e map pra substituir as listas e dicionarios do python.

    e agora a gente tem de conseguir alcançar o fserb...

    ResponderExcluir
  11. @girino

    Confesso que você acabou com toda minha inocência quando anunciou que estava usando o psyco. Eu estava imaginando estruturas de dados monstruosas. Hehe. Ainda assim, sua solução tá ótima no placar. ;)

    Conheço o psyco faz algum tempo e, na verdade, uma das técnicas que usei para enxugar o tempo foi fazer um código bem dividido, já que o overhead de busca de nomes em escopo global é mais lento que em escopo local e como tenho algumas funções recursivas, esse foi o jeito. Eu sinceramente acredito que, no estado atual do código, o psyco realmente nada tem a acrescentar. Terei que mudar um pouco a estrutura dele antes de pedir ajuda ao psyco.

    Sobre o lance de C/C++/Python, vale lembrar um velho dito da engenharia: "Pra quem tem só um martelo, tudo é prego". Os dicionários de python implementam uma estrutura de dados maravilhosa e, por isso, usei e abusei dela em minha solução. Quando comecei a reescrever o código em C, pensei "droga! não tem hash em C", mas aí me ocorreu que nem é necessário, basta alocar quantidades horrorosas de memória. A única parte de minha solução que realmente precisa de dicionários (em python) é a parte que exibe a solução. A razão disso é que preciso implementar um grafo para isso. Deve ter um jeito mais fácil, mas não o descobri. :-(

    Quanto ao fserb, a esperança era que ele não encontrasse o psyco, né? Mas ainda falta uma semana! :-)

    ResponderExcluir
  12. Às vezes o overhead de calcular um hash é menor que o cache miss quando você usa estruturas de dados enormes.

    ResponderExcluir
  13. Meus parabéns pela criatividade, participo de algumas competições e essa é uma das melhores historinhas que já tive a oportunidade de ler.

    Fiz uma solução em c++ utilizando uma boa estrutura de dados e fiquei bem encucado de implementações de python terem ficado na frente. Desconheço esse psyco mas to pensando em portar minha solução pra python e utilizá-lo. Porém isso é meio controverso, pois eu não tenho a opção de compilar meu programa com -o2 por exemplo.

    Após o término do contest gostaria que todos comentassem alguns detalhes de algoritmos e implementação que acreditem ter feito a diferença.

    Até mais.

    ResponderExcluir
  14. Estou em último lugar, devo estar enferrujado demais ...

    ResponderExcluir
  15. E aí? fechou???

    Tem como a galera divulgar o que usou?

    ResponderExcluir
  16. seria legal mostrar as soluções, até porque tem algoritmos duas ordens de grandeza melhores que o meu ...

    ResponderExcluir
  17. A engine SPOJ do scarky está bichada em lua

    O código abaixo roda em qualquer lua e dá erro de compilação no RicBit Jam

    function tblcmp(t1,t2)
    if (#t1~=#t2) then
    return false;
    end
    for i=1,#t1,1 do
    if (t1[i]~=t2[i]) then
    return false;
    end
    end
    return true;
    end
    names = {};
    cnt = 1;
    for i in io.lines() do
    names[cnt]={name=i,suc={},pred={}};
    cnt = cnt + 1
    end
    for i,val in ipairs(names) do
    for j = i+1,table.getn(names),1 do
    if (not(string.find(names[j].name,val.name,1,true)==nil)) then
    naoins=0
    for k=1,table.getn(val.suc),1 do
    if (not (string.find(names[j].name,names[val.suc[k]].name,1,true)==nil)) then
    naoins=1;
    break;
    end
    end
    if (naoins==0) then
    table.insert(names[i].suc,j);
    table.insert(names[j].pred,i);
    end
    end
    end
    end

    md=0
    length_to = {}
    for i=1,table.getn(names),1 do
    length_to[i]=0;
    end


    for i,val in ipairs(names) do
    for oo,e in ipairs(val.suc) do
    if (length_to[e] <= (length_to[i]+1)) then
    length_to[e] = length_to[i]+1;
    if (length_to[e]>md) then
    md=length_to[e];
    end
    end
    end
    end

    ll = {};
    for i,v in ipairs(length_to) do
    if (v==md) then
    table.insert(ll,i);
    end
    end

    function bfs (v)
    paths = {{v}};
    for k=1,md,1 do
    tmp = {}
    for pp,ppv in ipairs(paths) do
    tmp[pp]=ppv;
    end
    for i,vv in ipairs(tmp) do
    path = tmp[i];
    for oo,ii in ipairs(paths) do
    if (tblcmp(ii,path)) then
    table.remove(paths,oo);
    end
    end
    for v2,j in ipairs(names[path[#path]].pred) do
    ctmp = {};
    for pp,ppv in ipairs(path) do
    ctmp[pp]=ppv;
    end
    table.insert (ctmp,j)
    table.insert (paths,ctmp)
    end
    end
    end
    return paths;
    end

    result = {}
    for i,v in ipairs(ll) do
    for tt1,j in ipairs(bfs(v)) do
    l1 = {};
    for tt2=#j,1,-1 do
    k = j[tt2];
    table.insert(l1,names[k].name)
    end
    table.insert(result,table.concat(l1," --> "));
    end
    end

    table.sort(result)
    for kk,i in ipairs(result) do
    print (i)
    end

    ResponderExcluir
  18. Faz um post no forum do spoj avisando os caras do bug.

    ResponderExcluir
  19. Bom, eu vou considerar que já terminou tudo e postar mais ou menso como foram as minhas soluções, se não tiver terminado o desafio, o ricbit pode censurar :-D

    Eu fiz basicamente duas soluções dirferentes, uma que foi rápida em python, outra que foi rápida em C++. Não sei bem explicar porque...

    1- Em python:

    A solução que eu usei foi quebrar os nomes em "substrings" de N letras (que eu chamei de n-grafos, originalmente eram dígrafos, de 2 letras, mas esse parâmetro era ajustável), como por exemplo: "girino" -> ['gi', 'ir', 'ri', 'in', 'no'].

    Quebradas as palavras em seus n-grafos, eu crio um mapa n-grafo->[lista de nomes] onde cada entrada contem uma lista de todos os nomes que contenham aquele n-grafo.

    Numa segunda etapa eu itero pela lista de nomes montando um mapa de "sucessores", i.e. todos os outros nomes que contenham aquele nome. Nessa fase eu uso o mapa de n-grafos para estreitar o espaço de busca de sucessores apenas entre aqueles que contem os mesmos n-grafos que o nome sendo analisado. Para isso eu faço busco no mapa todas as listas relacionadas a todos os n-grafos daquela palavra e depois faço uma interseção de conjunto entre elas, de forma a obter o conjunto mínimo de possíveis sucessores. Itero então por esse conjunto para encontrar os sucessores e armazeno num mapa tendo como chave o nome atual. Todo nome que for usado como sucessor de alguém é retirado do conjunto de possíveis "raízes".

    por fim, numa 3a fase, eu percorro a lista de raízes e monto recursivamente, usando as listas de sucessores, as sequencias de nomes, descartando sempre as subsequencias que forem menores que as outras.

    2- Em c++

    Em c++ eu iterava sobre a lista de nomes montando a lista de sucessores (algoritmo O(n^2) mesmo). De posse dessa lista, eu sei que todos os sucessores de um nome na lista estão também na lista, logo, eu chamo recursivamente uma função de encontrar sucessores dentro da lista, passando a cada chamada, a lista de sucessores da palavra "pai". Cada palavra analisada pela função recursiva era "marcada" de forma a não ser analisada novamente pelo algoritmo O(n^2).

    No final, o algoritmo O(n^2) continuava sendo meu gargalo, e implementei um misto do algoritmo usado no python com este pra diminuir o numero de comparações de string.

    Ficou tudo meio confuso :P Mas acho que taí o que eu usei! Quem mais vai contar pra gente o ue usou?

    Ah sim, eu "roubei" nos dois algoritmos com alguns detalhes: descobri que as sequencias de nomes começavam sempre com nomes de duas letras, então nunca considerava nomes com mais de 2 letras como sendo "raízes". Nos dígrafos, eu descobri que os n-grafos menos frequentes nunca estavam nas maiores sequencias, por isso "filtrava" algumas palavras como sendo inúteis (ganhei 0.03s com isso, não é quase nada, mas fez diferença).

    ResponderExcluir
  20. Olá,

    Bom, minha implementação teve um melhor sucesso em c++, apesar de eu não tentar melhorar muito a implementação de python.

    A primeira coisa a se notar é que esse problema é equivalente a encontrar o maior caminho em um DAG, onde existe uma aresta da palavra A para a palavra B se A é substring de B. Esse é um problema clássico resolvido por uma ordenação topológica O(n + m) seguida de uma PD O(n).

    PD(i) = maxj(PD(j) + 1), em que j possui uma aresta para i. E o caso base é quando o grau de entrada for 0 a PD tem valor 1.

    Então a grande dificuldade é montar esse grafo rapidamente.
    Bom minha idéia foi utilizar uma estrutura de dados chamada Trie. http://pt.wikipedia.org/wiki/Trie

    Cada nó da Trie armazena duas informações:

    1) Todas as palavras ou prefixo de palavras que visitaram esse nó

    2) Um apontador pra todos os nós filhos, utilizando um map pra caber na memória

    Inicialmente eu ordeno as palavras primeiro pelo critério de tamanho e depois desempatava pelo lexicográfico. Essa parte já faz a ordenação topológica implicitamente.

    Então eu ia processando da maior pra menor string, a cada palavra "S" eu primeiro inseria ela inteira na Trie. Se tiver alguma palavra "W" que a contém, ela já foi inserida pela ordem do processamento. Então basta pegar o vetor do último nó visitado da Trie e esse vetor conterá o índice de todas as palavras "W" que "S" é substring.

    Logo após precisa inserir também todos os sufixos de "S" ou só encontraríamos substrings do tipo prefixo. (parte mais demorada)

    Para não inserir um índice duas vezes no vetor do nó basta comparar com o último índice inserido naquele nó, pois uma palavra nunca é reprocessada.

    Com o procedimento acima monta-se o DAG. Ou pode até mesmo fazer a PD diretamente.

    Pode-se fazer alguns cortes na hora de inserir todos os sufixos mas as condições ("ifs") parecem piorar ou não modificar o tempo de execução.

    Fazendo uma análise agora não só no número de palavras mas também na quantidade de caracteres da entrada, seja MAXL o tamanho da maior palavra e n o número de palavras, o grafo é montado em n*MAXL^2.

    Fazendo uma busca binária na entrada descobri que MAXL era proximo de 40.

    Isso acaba sendo bem melhor do que o algoritmo mais básico O(n^2). Lembrando ainda que dependendo da implementação de encontrar uma string em outra existe um fator MAXL^2 ou otimizando com um KMP aproximadamente 2*MAXL.

    Aí na hora de escovar um pouco os bits precisei testar tamanhos de alocacao estática que coubessem no limite de memória, utilizando alocação dinâmica apenas nos nós da Trie. Percebi também que na solução ótima nenhuma palavra contém mais de 2 pais que também estão na solução ótima. Mas essa última parte acho que não fez muita diferença.

    Se alguma coisa não ficou clara só falar que eu tento explicar melhor.

    Até mais,
    Davi Costa.

    ResponderExcluir
  21. Comentários da minha solução (confesso que ficou meio tosca) em http://bugsa.blogspot.com/2010/02/ricbit-jam-1-solucoes.html

    Tem em C++, Python e Lua

    ResponderExcluir
  22. @DaFFes

    Eu imaginei que a trie fosse fazer bem o serviço (até comentei com o ricbit), mas fiquei com preguiça de implementar :-D Se tivesse uma estrutura de trie ja pronta em python eu até usava, mas implementar uma trie do 0 não me pareceu agradável :P

    ResponderExcluir
  23. @girino

    Opa, mal a demora pra responder tava viajando.

    Bem essa trie acaba sendo simples, pois você não precisa implementar coisas como remoção e a busca pode ser junto com a inserção. Eu até tinha uma trie na minha biblioteca pessoal completa mas preferi fazer uma simplificada do zero do que ficar otimizando a pronta, segue o código:

    int vid; (variavel global)

    struct Trie {
    map e;
    vector ids;
    int last;
    vector &add(char *s) {
    if (last != vid) ids.push_back(vid), last = vid;
    if (*s == '\0') return ids;
    Trie *&ele = e[*s];
    if (ele == NULL) ele = new Trie();
    return ele->add(s+1);
    }
    };

    ResponderExcluir
  24. Comentando minha solução, depois de ler a do girino e a do DaFFes, estou certo de que ela é a mais tosca.

    Mas antes, um pequeno comentário: devido a uma série de combinações de disciplinas, nunca havia estudado busca e, durante o período em que brinquei no jam, acabei conhecendo diversos algoritmos de busca exata de strings interessantes. Ao menos, cheguei a conhecer um dos benchmarks, segundo a Wikipedia, o Boyer-Moore-Horspool (e, consequentemente, Boyer-Moore e outros como o KMP e o Two-Way). Valeu pela proposta do problema, ricbit.

    Agora, sobre a solução: do parágrafo anterior é possível perceber que optei por fazer buscas num stringão na memória (até comecei a fazer uma árvore de sufixos, mas sem conhecer a teoria tinha ficado uma zona completa :D).

    A idéia geral é a seguinte: assumindo uma lista de nomes ordenada em tamanho crescente, todas as "raízes" de nomes virão primeiro. Logo, para cara nome, eu procurava seus filhos na string na memória. Algumas estruturas de dados auxiliares guardavam offsets interessantes, como, por exemplo, uma lista que, dado o comprimento da palavra atual (chamado l), retornava o primeiro offset de string de comprimento l+1.

    Pronto, à medida que filhos eram encontrados, eles eram cadastrados em uma lista de cache que apontava, para cada "raiz", seus filhos.

    As posições dos filhos é encontrada pelo belo loop (pos é um offset inicial, append é uma referencia para o metodo append da lista de filhos):

    while True:
    pos = find(name, pos + 1)
    if pos <= 0:
    break
    append(pos)

    Montada a estrutura gigantesca com os filhos, que pode ser entendida como um grafo, basta achar as raízes das maiores sequencias (o tamanho da maior sequencia é encontrado no mesmo loop que encontra os filhos) e fazer uma busca no grafo. Acho que é isso para a versão sem roubo.

    Essa versão rodava em uns 600ms em meu computador com a entrada obtida pelo crawler do ricbit. Daí eu fui enfeiando o script pra reduzir o tempo, só que o tempo total era dominado pelo loop supracitado, que rodava em 300ms. Deixei de assumir que a entrada era ordenada e o script continuou a funcionar, aliás.

    A partir daí, o roubo começou. Ao que me parece, o ricbit cadastrou apenas um arquivo de entrada para testes. Como o scarky permite envio infinito de tentativas, isso dá um belo ataque. :) No meu caso, "notei" que as entradas que realmente interessavam eram as iniciadas em 'ad', 'al', 'an', 'at', 'el', 'em', 'li', 'ma', 'mi', 'na', 'ni' e 'ta'. Logo, arranquei todas as outras da minha string. Pronto, magicamente o script rodou rápido. Esse daí é o cara que, sem o psyco, ficou rapidinho. Como eu disse, uma solução tosca.

    ResponderExcluir
  25. Cá está o código que submeti por último: http://blog.renatocunha.com/chainerpy.html

    ResponderExcluir
  26. Trovão: seu roubo foi bem melhor que o meu ;) Eu fiquei com preguiça de fazer uma busca mais extensiva de padrões a eliminar nas palavras de entrada...

    ResponderExcluir
  27. hehe, e eu tava me sentindo culpado de fazer busca binária no tamanho da entrada pra usar só um fread()

    ResponderExcluir