Brain Dump: Tatuagens em cadeia

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.

Marcadores: code, complexidade, python, ricbit jam

29 Comentários:

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

Por Renato "Trovão", Às 17 de janeiro de 2010 19:41
Quero só ver o cara ter culhões de conquistar a Angelina Jolie só por causa da tatuagem, hoho. ;-)

Por ila fox, Às 17 de janeiro de 2010 21:08
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!

Por Ricardo, Às 17 de janeiro de 2010 21:54
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

Por K-prA, Às 18 de janeiro de 2010 07:40
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?

Por Renato "Trovão", Às 18 de janeiro de 2010 16:21
Eita. Agora que reli notei o "ele não acha todas as soluções". :)

Por Renato "Trovão", Às 18 de janeiro de 2010 16:23
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!

Por ricbit, Às 18 de janeiro de 2010 16:27
pow, mais ninguém vai se dignar a submeter uma solução? :-(

Por girino, Às 18 de janeiro de 2010 21:16
Tem 15 dias ainda :)

Por ricbit, Às 18 de janeiro de 2010 21:19
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

Por trovao, Às 21 de janeiro de 2010 11:58
@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...

Por girino, Às 22 de janeiro de 2010 15:30
@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! :-)

Por trovao, Às 22 de janeiro de 2010 21:42
Às vezes o overhead de calcular um hash é menor que o cache miss quando você usa estruturas de dados enormes.

Por ricbit, Às 23 de janeiro de 2010 09:57
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.

Por DaFFes, Às 25 de janeiro de 2010 21:59
O spoj usa -O2 por default.

Por ricbit, Às 25 de janeiro de 2010 22:00
Estou em último lugar, devo estar enferrujado demais ...

Por Pedro, Às 26 de janeiro de 2010 10:17
E aí? fechou???

Tem como a galera divulgar o que usou?

Por girino, Às 2 de fevereiro de 2010 08:58
seria legal mostrar as soluções, até porque tem algoritmos duas ordens de grandeza melhores que o meu ...

Por Pedro, Às 4 de fevereiro de 2010 10:02
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

Por Pedro, Às 4 de fevereiro de 2010 15:08
Faz um post no forum do spoj avisando os caras do bug.

Por Ricardo Bittencourt, Às 4 de fevereiro de 2010 15:12
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).

Por girino, Às 7 de fevereiro de 2010 12:26
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.

Por DaFFes, Às 8 de fevereiro de 2010 01: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

Por Pedro, Às 9 de fevereiro de 2010 18:44
@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

Por girino, Às 10 de fevereiro de 2010 20:30
@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);
}
};

Por DaFFes, Às 19 de fevereiro de 2010 01:29
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.

Por trovao, Às 19 de fevereiro de 2010 18:07
Cá está o código que submeti por último: http://blog.renatocunha.com/chainerpy.html

Por trovao, Às 19 de fevereiro de 2010 18:28
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...

Por girino, Às 19 de fevereiro de 2010 19:50
hehe, e eu tava me sentindo culpado de fazer busca binária no tamanho da entrada pra usar só um fread()

Por DaFFes, Às 19 de fevereiro de 2010 21:40