Resolvi mudar o meu blog, levá-lo um pouco mais a sério, e dispor de um pouco mais de recursos.
O novo endereço do meu blog é este:
http://crbonilha.com
Layout novo, host novo e até domínio novo!
Os posts que eu julgava mais interessantes foram e alguns ainda serão transferidos para lá.
Não farei mais nenhum post aqui, apenas lá.
Considerem este blog aposentado.
Não vou excluí-lo, porém, pois há bastante conteúdo bacana aqui ainda.
Vejo vocês lá.
Mostrando postagens com marcador Guia. Mostrar todas as postagens
Mostrando postagens com marcador Guia. Mostrar todas as postagens
segunda-feira, 17 de março de 2014
sexta-feira, 15 de novembro de 2013
Inverting Huffman
Pra quem não sabe, semana passada, 9 de novembro, aconteceu a fase final da maratona de programação em toda a américa latina, antecedendo apenas a fase mundial que acontecerá [em breve], e o campeão foi o time Ñtemtempabobagi, da USP.
Mais informações aqui: http://maratona.ime.usp.br/resultados13/
Nesse post vou falar sobre o exercício I da fase final, Inverting Huffman, o qual, curiosamente, ninguém resolveu.
Vocês podem baixar o PDF dele e submeter o código para teste neste link:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=615&page=show_problem&problem=4544
A codificação de Huffman trata-se de uma forma de re-codificar os caracteres de um texto, de modo que o comprimento do código de cada caractere seja proporcional ao seu número de ocorrências no texto. Por exemplo, na palavra "Abacate", a letra 'a' receberia um código curto, pois aparece várias vezes, enquanto todas as outras letras, que aparecem apenas uma vez, iriam receber um código longo.
Mais informações: http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/huffman.html
Ok, mas o que pedia o exercício I da maratona? Para se codificar um texto?
Quase. O exercício trata-se de uma variação bem criativa da codificação de Huffman, na qual, em vez de lhe passar a frequência das letras para que se monte a árvore, passa-lhe a árvore para que se descubra a frequência das letras.
O único requisito para se resolver o exercício é ter um conhecimento de como a árvore é montada, para que seja possível atribuir valores consistentes nos nós, de tal modo que a árvore pudesse ser montada pelo algoritmo de Huffman.
Ok, como ele funciona? No enunciado do exercício há uma explicação do funcionamento do algoritmo de Huffman junto com uma sequência de passos, mas eu vou citar aqui algumas considerações.
- Entenda por "valor" a frequência de ocorrência do caractere no texto. O valor de 'a' acima seria 3.
- Todos os caracteres são folhas, por mais que no exercício não nos preocupemos em si com os caracteres, mas sim com o seu valor e seu nível.
- Os nós que não são folhas são nós criados no decorrer do algoritmo, de tal modo que o seu valor é consequência do valor de ambos os filhos.
- Na nossa lista, sempre haverá no mínimo um par de nós no nível mais abaixo da árvore, a não ser que estejamos no último nó (Figura B).
Vamos ao exercício: Como atribuir consistentemente um valor a um nó folha, de modo que a árvore seja montada da forma especificada? Basta simular o funcionamento do algoritmo!
Lembre-se que se deseja o menor valor possível paraa soma de todos os nós.
Digamos que a entrada do exercício seja:
4
1 2 3 3
A estrutura da árvore ficará assim:
Mais informações aqui: http://maratona.ime.usp.br/resultados13/
Nesse post vou falar sobre o exercício I da fase final, Inverting Huffman, o qual, curiosamente, ninguém resolveu.
Vocês podem baixar o PDF dele e submeter o código para teste neste link:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=615&page=show_problem&problem=4544
A codificação de Huffman trata-se de uma forma de re-codificar os caracteres de um texto, de modo que o comprimento do código de cada caractere seja proporcional ao seu número de ocorrências no texto. Por exemplo, na palavra "Abacate", a letra 'a' receberia um código curto, pois aparece várias vezes, enquanto todas as outras letras, que aparecem apenas uma vez, iriam receber um código longo.
Mais informações: http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/huffman.html
Figura A
Ok, mas o que pedia o exercício I da maratona? Para se codificar um texto?
Quase. O exercício trata-se de uma variação bem criativa da codificação de Huffman, na qual, em vez de lhe passar a frequência das letras para que se monte a árvore, passa-lhe a árvore para que se descubra a frequência das letras.
O único requisito para se resolver o exercício é ter um conhecimento de como a árvore é montada, para que seja possível atribuir valores consistentes nos nós, de tal modo que a árvore pudesse ser montada pelo algoritmo de Huffman.
Ok, como ele funciona? No enunciado do exercício há uma explicação do funcionamento do algoritmo de Huffman junto com uma sequência de passos, mas eu vou citar aqui algumas considerações.
- Entenda por "valor" a frequência de ocorrência do caractere no texto. O valor de 'a' acima seria 3.
- Todos os caracteres são folhas, por mais que no exercício não nos preocupemos em si com os caracteres, mas sim com o seu valor e seu nível.
- Os nós que não são folhas são nós criados no decorrer do algoritmo, de tal modo que o seu valor é consequência do valor de ambos os filhos.
Figura B
- Na nossa lista, sempre haverá no mínimo um par de nós no nível mais abaixo da árvore, a não ser que estejamos no último nó (Figura B).
Vamos ao exercício: Como atribuir consistentemente um valor a um nó folha, de modo que a árvore seja montada da forma especificada? Basta simular o funcionamento do algoritmo!
Lembre-se que se deseja o menor valor possível paraa soma de todos os nós.
Digamos que a entrada do exercício seja:
4
1 2 3 3
A estrutura da árvore ficará assim:
Figura C
O algoritmo de Huffman cria uma lista com os valores de cada nó, e escolhe os dois com os menores valores para criar um nó pai e construir a árvore.
Está vendo aqueles dois nós no nível 3? Se eles estão lá embaixo, devem ter sido escolhidos primeiro na execução do tal algoritmo de Huffman, e, consequentemente, o valor de seus nós deve ser baixo, bem baixo. Que tal 1?
Figura D
O algoritmo de Huffman agora monta-lhes o nó pai, sendo o valor a soma dos nós filhos.
Figura E
Os nós folhas são removidos da lista, e o nó pai adicionado. O algoritmo agora irá escolher os dois nós com o menor valor da lista, e continuar sua execução.
Atente a essa situação da árvore: Que valor poderia ser atribuído ao nó sinalizado de forma que pudéssemos conduzir o algoritmo de Huffman a montar a árvore como planejamos?
Figura F
Se atribuíssimos um valor muito baixo, talvez o algoritmo não tivesse se comportado conforme planejávamos até aquele momento. Por exemplo, se atribuíssemos o valor 2, o algoritmo, no passo anterior, não teria escolhido os nós de valor 3 e 5, mas sim os nós com valor 2 e 3, mudando a estrutura da árvore que esperávamos.
Figura G
Qual seria o menor valor que eu poderia colocar ali então?
O resto eu deixo com vocês.
domingo, 13 de outubro de 2013
Ajude seu General
“Porque recalcular um caminho do
início, se eu já sei metade?”, eis a questão que justifica o
post de hoje.
Figura A
Para os interessados, eu escrevi um
exercício, e o mesmo está disponível para ser resolvido no portal
do URI, no seguinte link:
Ajude seu General foi um exercício
escrito com o propósito de estimular a implementação de formas
mais eficientes de se calcular o famoso caminho mínimo em um grafo,
dado um devido contexto.
Figura A
Todos estamos acostumados com o contexto padrão: Temos um grafo, e nos é requisitado descobrir qual é o caminho mínimo do vértice S até o vértice D (Figura A).
Para isso usamos os nossos velhos amigos DFS, BFS, Bellman-Ford, Dijkstra, entre outros.
Mas e se o contexto mudar um pouco? E
se o nosso grafo fosse dinâmico? E se as arestas pudessem sumir ou
aparecer? Eis o contexto DSSSP (Dynamic Single Source Shortest Path).
Figura B.1
Conforme ilustrado pela Figura B.1, a
remoção de uma aresta pode inutilizar nosso antigo caminho mínimo,
nos forçando a encontrar outro, assim como a inserção de uma nova
aresta (Figura B.2) pode nos apresentar um novo caminho, nos forçando a aos menos
tentar encontrá-lo.
Figura B.2
A primeira vista, não
parece nos restar escolha: devemos recalcular todo nosso grafo,
sempre que uma aresta é inserida ou removida, pois só assim podemos
ter certeza que o nosso caminho mínimo é de fato o caminho mínimo.
Uma coisa é clara: Tal
solução é cara.
E mais: Muito cara.
Figura C
Note que ao remover a
aresta em vermelho, temos que recalcular o caminho mínimo para todos
os vértices, em especial para o vértice D, entre os N vértices do
grafo. Ou seja, custo N (multiplicado pela complexidade do seu
algoritmo preferido).
Note ainda que tal aresta
não compunha o caminho mínimo (caminho em azul). Poxa, fomos
enganados! Recalculamos todo o nosso grafo, e nem precisávamos!
Uma solução mais viável
seria tentar “isolar” um conjunto de vértices que realmente
fossem “afetados” pela inserção/remoção, conforme ilustrado
na Figura D.
Figura D
O fato de não haver uma
aresta direcionada saindo do conjunto B em direção ao conjunto A
torna fácil perceber que há uma imensa diferença entre tais dois
grupos:
a) O caminho mínimo para
qualquer que seja o vértice do conjunto A não foi alterado.
b) O caminho mínimo para
qualquer que seja o vértice do conjunto B pode ou não ter sido
alterado, assim como o caminho mínimo até o vértice D.
Resumindo: Porque recalcular um caminho do início, se eu já sei metade?
Resumindo: Porque recalcular um caminho do início, se eu já sei metade?
Isolamos, então, um
conjunto de vértices “afetados” pela remoção de uma aresta, e
um recálculo sobre tal conjunto me parece uma escolha bem prudente.
A brecha foi aberta, basta
explorá-la. Para isso recomendo lerem o artigo dos cientistas da
computação Ramalingam e Reps, que descreve um algoritmo que aborda
o tema DSSSP, e resolve o problema descrito com eficácia.
http://pages.cs.wisc.edu/~ramali/jl-algorithms.html
domingo, 25 de agosto de 2013
Abstraindo um problema
Os enunciados dos exercícios escondem o tesouro, e você deve estar atento as pistas (mas apenas as importantes).
Nesse post vou citar um exemplo de como abstrair um exercício, ou seja, ignorar todas as informações inúteis e saber identificar os pontos chaves que nos levam à resolução. Isso inclui identificar pistas "falsas" ou "desnecessárias".
O exercício que vou usar como exemplo aqui é o Fechem as portas! (http://www.urionlinejudge.com.br/judge/problems/view/1371).
Antes de continuar, leiam o enunciado do exercício, e tirem suas conclusões iniciais.
A ordem em que eles entram não faz a menor diferença, visto que todos vão entrar e vão abrir (ou fechar) suas respectivas portas. Veja, se o estado da porta 3 vai ser trocado pelo descendente 1 e 3, nesta ordem, temos um total de duas trocas, e se vai ser trocado pelo descendente 3 e 1, nesta ordem, temos ainda um total de duas trocas, ou seja, a ordem é indiferente, e o total é o mesmo.
Objetivo: Descobrir quantas portas terminarão abertas.
Solução? Força bruta? Não! Veja, temos um valor máximo de 25milhões de portas e descendentes, um valor extremamente alto para se pensar em força bruta.
Pensem comigo: uma porta ou está fechada, ou está aberta, e seu estado troca de um para o outro apenas. Se inicia fechada, com uma troca de estados vai para aberta, e com duas volta para fechada. Se continuarmos nesse ritmo, notaremos que um número par de trocas de estados faz com que a porta termine fechada, e um número ímpar de trocas de estados faz com a porta termine aberta.
A porta número 3 vai ter seu estado trocado por dois descendentes. Vimos que a ordem não importa, o que nos importa mesmo é o número de vezes em que ela vai ter seu estado trocado. No caso da porta número 3, duas vezes. Como vimos no parágrafo anterior, quando o estado da porta é trocado um número par de vezes, ela terminará fechada, portanto temos uma resposta: terminará fechada.
Abstração: Descobrir o número Q de divisores de um valor N, e, com base nesse valor Q, imprimir N ou não.
Exemplo: Vamos descobrir o número de divisores dos valores de 1 até 10.
N Q
1: 1 = 1
2: 1, 2 = 2
3: 1, 3 = 2
4: 1, 2, 4 = 3
5: 1, 5 = 2
6: 1, 2, 3, 6 = 4
7: 1, 7 = 2
8: 1, 2, 4, 8 = 4
9: 1, 3, 9 = 3
Solução: Os valores N tal que o número Q total de divisores de N é impar -> 1, 4 e 9.
Abstraído o problema, resta encontrar uma forma eficaz de descobrir esse valor Q, mas com um pouco de observação, é fácil encontrar o padrão. Vou deixar essa tarefa pra vocês.
Nesse post vou citar um exemplo de como abstrair um exercício, ou seja, ignorar todas as informações inúteis e saber identificar os pontos chaves que nos levam à resolução. Isso inclui identificar pistas "falsas" ou "desnecessárias".
O exercício que vou usar como exemplo aqui é o Fechem as portas! (http://www.urionlinejudge.com.br/judge/problems/view/1371).
Antes de continuar, leiam o enunciado do exercício, e tirem suas conclusões iniciais.
Considerando que todas as portas estão inicialmente fechadas (todos os descendentes fecham as portas antes de descer para o jardim) e que cada descendente entra exatamente uma vez na mansão (a confusão é tão grande que não sabemos em que ordem), quais portas estarão abertas após a entrada de todos os descendentes na mansão?Pista falsa: "(a confusão é tão grande que não sabemos em que ordem)".
A ordem em que eles entram não faz a menor diferença, visto que todos vão entrar e vão abrir (ou fechar) suas respectivas portas. Veja, se o estado da porta 3 vai ser trocado pelo descendente 1 e 3, nesta ordem, temos um total de duas trocas, e se vai ser trocado pelo descendente 3 e 1, nesta ordem, temos ainda um total de duas trocas, ou seja, a ordem é indiferente, e o total é o mesmo.
Objetivo: Descobrir quantas portas terminarão abertas.
Solução? Força bruta? Não! Veja, temos um valor máximo de 25milhões de portas e descendentes, um valor extremamente alto para se pensar em força bruta.
Pensem comigo: uma porta ou está fechada, ou está aberta, e seu estado troca de um para o outro apenas. Se inicia fechada, com uma troca de estados vai para aberta, e com duas volta para fechada. Se continuarmos nesse ritmo, notaremos que um número par de trocas de estados faz com que a porta termine fechada, e um número ímpar de trocas de estados faz com a porta termine aberta.
A porta número 3 vai ter seu estado trocado por dois descendentes. Vimos que a ordem não importa, o que nos importa mesmo é o número de vezes em que ela vai ter seu estado trocado. No caso da porta número 3, duas vezes. Como vimos no parágrafo anterior, quando o estado da porta é trocado um número par de vezes, ela terminará fechada, portanto temos uma resposta: terminará fechada.
Abstração: Descobrir o número Q de divisores de um valor N, e, com base nesse valor Q, imprimir N ou não.
Exemplo: Vamos descobrir o número de divisores dos valores de 1 até 10.
N Q
1: 1 = 1
2: 1, 2 = 2
3: 1, 3 = 2
4: 1, 2, 4 = 3
5: 1, 5 = 2
6: 1, 2, 3, 6 = 4
7: 1, 7 = 2
8: 1, 2, 4, 8 = 4
9: 1, 3, 9 = 3
Solução: Os valores N tal que o número Q total de divisores de N é impar -> 1, 4 e 9.
Abstraído o problema, resta encontrar uma forma eficaz de descobrir esse valor Q, mas com um pouco de observação, é fácil encontrar o padrão. Vou deixar essa tarefa pra vocês.
quarta-feira, 15 de maio de 2013
Gerador de Casos de Teste
Um dos grandes desafios envolvidos em resolver um exercício da maratona de programação é pensar em um caso de teste onde seu programa vai falhar.
Os casos de teste oferecidos na descrição do exercício geralmente cobrem a parte mais simples e superficial do mesmo, mas quando chega a hora de submeter o código, ele deve passar por casos de testes gigantescos e complexos, os quais você nem de longe tratou.
Nesse post vou dar um breve exemplo de como criar um gerador de casos de teste, o qual pode lhe ajudar a testar o programa e verificar por si mesmo em quais casos seu programa está falhando.
Aqui está o código que eu montei para exemplificar esse post:
https://github.com/crbonilha/codes/blob/master/Exemplo%20Gerador%20Casos%20de%20Teste
(Linha 6 do código):
Caso esteja programando na linguagem C ou C++ (meu caso), será necessário utilizar alguns metodos responsáveis por manipular arquivos externos, tais como arquivos .txt, ou arquivos sem extensão alguma, mas que contenham nele apenas valores que serão usados no seu programa.
Esses metodos manipulam variáveis do tipo FILE, que serão responsáveis por representar seu arquivo externo. Quem ainda não tem muita familiaridade com essa abordagem, procure estudar algo na internet, em especial o método "fopen()" e "fprintf()", que, para o nosso caso, é mais do que o suficiente.
Voltando ao contexto da maratona, para que você pense em como gerar um caso de teste, primeiro você tem que entender a "hierarquia" de cada caso de teste, por exemplo, no exercicio Bilhetes Falsos (http://www.urionlinejudge.com.br/judge/problems/view/1318), cada caso de teste contém dois inteiros, N e M, e logo após, M inteiros. Seu gerador será responsável por gerar os dois inteiros iniciais (N e M), e logo após, M inteiros. Sim, é bobagem, mas é importante (Linhas 15 e 21).
Outro detalhe que pode passar em branco é que dentre todos os M valores gerados, todos devem estar no intervalo de 1 a N, portanto cuidado na hora de chamar o método de valores aleatórios (Linha 19).
Eu costumo deixar a parte do N e M por minha conta (Linha 13), assim eu decido se quero um caso de teste grande ou pequeno, porém esses mesmos valores poderiam facilmente serem gerados aleatoriamente, como os outros.
Ok, após todos os valores gerados, basta adaptar seu programa que resolve o exercício para ler as entradas do arquivo de teste que você gerou, em vez de ler da entrada padrão como estamos acostumados. Para isso estudem o método "fscanf()".
Agora é possível criar milhares de casos de teste e fazer seu programa rodar todos em segundos. A última parte é saber identificar, dentre milhares de saidas, qual está errada. Restam-lhe duas alternativas: na internet é possivel encontrar os casos de teste de entrada e suas saidas utilizados nas maratonas anteriores, portanto basta encontrá-los e compará-los ao teu; o site com juiz online do URI tem uma ferramenta chamada toolkit, e com ele é possível entregar um caso de teste gerado por você e verificar qual seria a saída de um programa que está funcionando corretamente.
Obviamente, ambas as formas de comparar a saida com algum recurso da internet não lhe será útil na hora da maratona, porém bugs nos quais o seu programa aparentemente para de funcionar, ou estoura o tempo limite, podem ser visivelmente notados com esse tipo de abordagem.
A ferramenta está aí, basta saber quando e como usá-la...
Os casos de teste oferecidos na descrição do exercício geralmente cobrem a parte mais simples e superficial do mesmo, mas quando chega a hora de submeter o código, ele deve passar por casos de testes gigantescos e complexos, os quais você nem de longe tratou.
Nesse post vou dar um breve exemplo de como criar um gerador de casos de teste, o qual pode lhe ajudar a testar o programa e verificar por si mesmo em quais casos seu programa está falhando.
Aqui está o código que eu montei para exemplificar esse post:
https://github.com/crbonilha/codes/blob/master/Exemplo%20Gerador%20Casos%20de%20Teste
(Linha 6 do código):
Caso esteja programando na linguagem C ou C++ (meu caso), será necessário utilizar alguns metodos responsáveis por manipular arquivos externos, tais como arquivos .txt, ou arquivos sem extensão alguma, mas que contenham nele apenas valores que serão usados no seu programa.
Esses metodos manipulam variáveis do tipo FILE, que serão responsáveis por representar seu arquivo externo. Quem ainda não tem muita familiaridade com essa abordagem, procure estudar algo na internet, em especial o método "fopen()" e "fprintf()", que, para o nosso caso, é mais do que o suficiente.
Voltando ao contexto da maratona, para que você pense em como gerar um caso de teste, primeiro você tem que entender a "hierarquia" de cada caso de teste, por exemplo, no exercicio Bilhetes Falsos (http://www.urionlinejudge.com.br/judge/problems/view/1318), cada caso de teste contém dois inteiros, N e M, e logo após, M inteiros. Seu gerador será responsável por gerar os dois inteiros iniciais (N e M), e logo após, M inteiros. Sim, é bobagem, mas é importante (Linhas 15 e 21).
Outro detalhe que pode passar em branco é que dentre todos os M valores gerados, todos devem estar no intervalo de 1 a N, portanto cuidado na hora de chamar o método de valores aleatórios (Linha 19).
Eu costumo deixar a parte do N e M por minha conta (Linha 13), assim eu decido se quero um caso de teste grande ou pequeno, porém esses mesmos valores poderiam facilmente serem gerados aleatoriamente, como os outros.
Ok, após todos os valores gerados, basta adaptar seu programa que resolve o exercício para ler as entradas do arquivo de teste que você gerou, em vez de ler da entrada padrão como estamos acostumados. Para isso estudem o método "fscanf()".
Agora é possível criar milhares de casos de teste e fazer seu programa rodar todos em segundos. A última parte é saber identificar, dentre milhares de saidas, qual está errada. Restam-lhe duas alternativas: na internet é possivel encontrar os casos de teste de entrada e suas saidas utilizados nas maratonas anteriores, portanto basta encontrá-los e compará-los ao teu; o site com juiz online do URI tem uma ferramenta chamada toolkit, e com ele é possível entregar um caso de teste gerado por você e verificar qual seria a saída de um programa que está funcionando corretamente.
Obviamente, ambas as formas de comparar a saida com algum recurso da internet não lhe será útil na hora da maratona, porém bugs nos quais o seu programa aparentemente para de funcionar, ou estoura o tempo limite, podem ser visivelmente notados com esse tipo de abordagem.
A ferramenta está aí, basta saber quando e como usá-la...
domingo, 28 de abril de 2013
As famosas Pilhas
Você já ouviu falar de pilhas? (me refiro a estrutura de dados)
A estrutura de dados pilha pode parecer simples e inofensiva, porém em certos contextos, principalmente em problemas específicos da maratona de programação, a implementação de uma pilha pode ser fatal.
Um exercício aparemente difícil se torna fácil com uma pilha.
Uma prova? O exercício Ácido Ribunocléico Alienígena é um problema que caiu na maratona alguns anos atrás, e é um dos tópicos mais acessados deste blog, por viajantes do google a procura de resoluções do mesmo. Na época, eu não conhecia a implementação em pilhas, e nem eu lembro como resolvi, mas garanto que hoje eu resolveria algo parecido em metade do tempo só implementando uma pilha.
O link do exercicio, caso esteja curioso, é esse: http://www.urionlinejudge.com.br/judge/problems/view/1242
Meu objetivo não é explicar aqui como funciona o conceito de pilhas, mas sim dizer que esse conceito existe.
Tem bastante material na internet, então procurem um pouco, e saibam que esse exercício pode ser resolvido, de forma ridiculamente fácil, utilizando pilhas.
Alguns outros exercícios que utilizam pilhas podem ser encontrados no site URI, na aba de estrutura de dados dos problemas.
Por hoje é só, estudem!
A estrutura de dados pilha pode parecer simples e inofensiva, porém em certos contextos, principalmente em problemas específicos da maratona de programação, a implementação de uma pilha pode ser fatal.
Um exercício aparemente difícil se torna fácil com uma pilha.
Uma prova? O exercício Ácido Ribunocléico Alienígena é um problema que caiu na maratona alguns anos atrás, e é um dos tópicos mais acessados deste blog, por viajantes do google a procura de resoluções do mesmo. Na época, eu não conhecia a implementação em pilhas, e nem eu lembro como resolvi, mas garanto que hoje eu resolveria algo parecido em metade do tempo só implementando uma pilha.
O link do exercicio, caso esteja curioso, é esse: http://www.urionlinejudge.com.br/judge/problems/view/1242
Meu objetivo não é explicar aqui como funciona o conceito de pilhas, mas sim dizer que esse conceito existe.
Tem bastante material na internet, então procurem um pouco, e saibam que esse exercício pode ser resolvido, de forma ridiculamente fácil, utilizando pilhas.
Alguns outros exercícios que utilizam pilhas podem ser encontrados no site URI, na aba de estrutura de dados dos problemas.
Por hoje é só, estudem!
domingo, 24 de fevereiro de 2013
Path Finding
Eae, como estão?
Essa semana passei um sufoco tentando implementar um protótipo de jogo de RPG pra android, e me deparei com a necessidade de implementar um esboço de uma inteligência artificial em um personagem.
Se você apenas joga jogos, e nunca imaginou como seria programar um, vou dar uma breve explicação do que seria uma inteligência artificial, a qual você interagiu o tempo todo.
De acordo com o livro 'Programming Game AI by Example', "...se o jogador acredita que o seu adversário é inteligente, então ele é inteligente..." (tradução livre).
Ou seja, se o seu adversário no jogo apresenta ações que são satisfatoriamente coerentes com a situação, então há a impressão de que ele tomou uma decisão inteligente, e a partir dai, ele se tornou inteligente.
Sabe aqueles inimigos nos jogos de luta que se defendem ou até se esquivam de seu golpe? Essa simples ação que o computador executa está contidas no código do jogo, e cada uma é acionada seguindo um padrão, fazendo com que cada ação esteja intimamente ligada com a situação, e simulando ao máximo uma decisão humana, criando assim a ilusão de inteligência.
Esse tópico sobre inteligência artificial ainda vai muito longe, e existem vários livros por aí muito mais coerentes e didáticos do que eu, portanto aconselho-os que os procurem.
O que eu queria falar hoje é sobre o algoritmo Path Finding.
Que algoritmo é esse? Bom, esse é um nome dado a um algoritmo o qual busca por um caminho, desde um ponto (x, y) até outro ponto (x, y) de um mapa, desviando de obstáculos e, em alguns casos, encontrando o caminho mais curto.
Esse tipo de algoritmo é implementado em jogos de múltiplos gêneros, porém com mais ênfase em jogos de RPG.
Ok, mas esse algoritmo é importante ou dispensável? Deveria eu, como programador, prestar atenção a ele ou simplesmente implementá-lo de forma porca?
Na minha humilde opinião, esse algoritmo é importantíssimo, e deveria, assim como qualquer aspecto de seu jogo, ser testado e implementado com cuidado, para evitar bugs.
Quando ele funciona, os jogadores mal notarão, porém quando ele buga, com certeza eles notarão, e como qualquer bug, não deixarão barato. Veja um exemplo do famoso jogo Skyrim, uma super produção que não escapou do bug do PathFinding.
Ok, é importante, mas por onde eu começo?
Bom, me fiz a mesma pergunta alguns dias atrás.
Há algum tempo que eu aprendi um pouco sobre grafos, e conheci um algoritmo chamado A*, o qual na época achei complexo demais.
Essa semana me vi forçado a implementá-lo, e depois de um pouco de suor, consegui.
Aconselho, para aqueles que ainda não conhecem nenhuma técnica, estudem esse algoritmo citado, o A*. Aqui está uma página bem teórica e didática, que explica passo a passo os fundamentos do algoritmo:
http://www.policyalmanac.org/games/aStarTutorial_port.htm
Outro site muito interessante que oferece uma boa explicação, exemplos e até um simulador, é o site do Abrindo o Jogo, nessa pagina: http://abrindoojogo.com.br/inteligencia-artificial-nos-games-%E2%80%93-pathfinding
Bom, acho que isso era tudo que eu tinha pra falar sobre. Caso eu grave o resultado da minha experiência, eu postar aqui mesmo, para que possam ter uma ideia de como ficou.
Até mais.
Essa semana passei um sufoco tentando implementar um protótipo de jogo de RPG pra android, e me deparei com a necessidade de implementar um esboço de uma inteligência artificial em um personagem.
Se você apenas joga jogos, e nunca imaginou como seria programar um, vou dar uma breve explicação do que seria uma inteligência artificial, a qual você interagiu o tempo todo.
De acordo com o livro 'Programming Game AI by Example', "...se o jogador acredita que o seu adversário é inteligente, então ele é inteligente..." (tradução livre).
Ou seja, se o seu adversário no jogo apresenta ações que são satisfatoriamente coerentes com a situação, então há a impressão de que ele tomou uma decisão inteligente, e a partir dai, ele se tornou inteligente.
Sabe aqueles inimigos nos jogos de luta que se defendem ou até se esquivam de seu golpe? Essa simples ação que o computador executa está contidas no código do jogo, e cada uma é acionada seguindo um padrão, fazendo com que cada ação esteja intimamente ligada com a situação, e simulando ao máximo uma decisão humana, criando assim a ilusão de inteligência.
Esse tópico sobre inteligência artificial ainda vai muito longe, e existem vários livros por aí muito mais coerentes e didáticos do que eu, portanto aconselho-os que os procurem.
O que eu queria falar hoje é sobre o algoritmo Path Finding.
Que algoritmo é esse? Bom, esse é um nome dado a um algoritmo o qual busca por um caminho, desde um ponto (x, y) até outro ponto (x, y) de um mapa, desviando de obstáculos e, em alguns casos, encontrando o caminho mais curto.
Ok, mas esse algoritmo é importante ou dispensável? Deveria eu, como programador, prestar atenção a ele ou simplesmente implementá-lo de forma porca?
Na minha humilde opinião, esse algoritmo é importantíssimo, e deveria, assim como qualquer aspecto de seu jogo, ser testado e implementado com cuidado, para evitar bugs.
Quando ele funciona, os jogadores mal notarão, porém quando ele buga, com certeza eles notarão, e como qualquer bug, não deixarão barato. Veja um exemplo do famoso jogo Skyrim, uma super produção que não escapou do bug do PathFinding.
Ok, é importante, mas por onde eu começo?
Bom, me fiz a mesma pergunta alguns dias atrás.
Há algum tempo que eu aprendi um pouco sobre grafos, e conheci um algoritmo chamado A*, o qual na época achei complexo demais.
Essa semana me vi forçado a implementá-lo, e depois de um pouco de suor, consegui.
Aconselho, para aqueles que ainda não conhecem nenhuma técnica, estudem esse algoritmo citado, o A*. Aqui está uma página bem teórica e didática, que explica passo a passo os fundamentos do algoritmo:
http://www.policyalmanac.org/games/aStarTutorial_port.htm
Outro site muito interessante que oferece uma boa explicação, exemplos e até um simulador, é o site do Abrindo o Jogo, nessa pagina: http://abrindoojogo.com.br/inteligencia-artificial-nos-games-%E2%80%93-pathfinding
Bom, acho que isso era tudo que eu tinha pra falar sobre. Caso eu grave o resultado da minha experiência, eu postar aqui mesmo, para que possam ter uma ideia de como ficou.
Até mais.
sábado, 29 de setembro de 2012
Guia: Tipos de Entrada do SPOJ
Bom, quem já utiliza o SPOJ a algum tempo deve ter notado que existem certos "padrões" em que seu código deve se encaixar, porém estes não são sempre os mesmos. Foi preciso algum tempo até me acostumar com todos, porém hoje vou repassar alguns aqui para quem não está acostumado.
Tipos de Entrada:
Vou citar alguns tipos de entrada comuns no SPOJ.
- "O final da entrada é indicado por uma linha que contém apenas dois zeros, separados por um espaço em branco", como citado no exercício SUBPRIME.
Este tipo de entrada significa que o seu programa deve continuar rodando, mesmo após ter mostrado os resultados do primeiro teste, parando apenas quando as entradas forem iguais a 0.
Para casos como este, basta um loop infinito que abranja todo o código, com excessão das inicializações das variáveis (conselho pessoal), e com a leitura de entrada logo como primeira instrução do loop. Após a leitura, uma condição para que se caso os valores sejam iguais a zero poderia levar a quebra desse loop, que levaria ao fim do programa.
- "A entrada contém um único conjunto de teste ...", como citado no exercício CHOCPJ09.
Entre os mais comuns tipos de entrada, a entrada contém apenas um único conjunto de testes. Portanto, não é necessário nenhum loop de repetição.
Como um algoritmo comum, basta que rode apenas uma vez e termine.
- "A entrada é composta por diversos casos de teste.", como citado no exercício FOCO, ou "O final da entrada deve ser o final do arquivo.", como retirado da minha memória.
Esta é uma das entradas que mais confundem os programadores inexperientes.
O segundo exemplo que citei é mais claro, porém o primeiro deixou a desejar.
Trata-se do seguinte: Seu programa deverá receber as entradas, até que se encontre o "final do arquivo", que seria algo como o fim do arquivo do qual está sendo retirado os testes.
A única forma que encontrei de lidar com este tipo de entrada, em c ou c++, foi utilizar o scanf dentro da condição do loop while, tal como while(scanf("%d",&num)!=EOF).
Pra quem não entendeu, EOF significa End of File( ou fim do arquivo), portanto o algoritmo irá entrar no loop caso a entrada seja diferente do fim do arquivo.
Bom, esses são os mais comuns e os que eu me lembro por hora. Caso ainda tenha ficado alguma dúvida, ou caso encontrem algum tipo de entreda que não entendam, postem nos comentários.
Em breve farei um post sobre os não menos importantes tipos de saída do SPOJ.
Até mais.
Tipos de Entrada:
Vou citar alguns tipos de entrada comuns no SPOJ.
- "O final da entrada é indicado por uma linha que contém apenas dois zeros, separados por um espaço em branco", como citado no exercício SUBPRIME.
Este tipo de entrada significa que o seu programa deve continuar rodando, mesmo após ter mostrado os resultados do primeiro teste, parando apenas quando as entradas forem iguais a 0.
Para casos como este, basta um loop infinito que abranja todo o código, com excessão das inicializações das variáveis (conselho pessoal), e com a leitura de entrada logo como primeira instrução do loop. Após a leitura, uma condição para que se caso os valores sejam iguais a zero poderia levar a quebra desse loop, que levaria ao fim do programa.
- "A entrada contém um único conjunto de teste ...", como citado no exercício CHOCPJ09.
Entre os mais comuns tipos de entrada, a entrada contém apenas um único conjunto de testes. Portanto, não é necessário nenhum loop de repetição.
Como um algoritmo comum, basta que rode apenas uma vez e termine.
Esta é uma das entradas que mais confundem os programadores inexperientes.
O segundo exemplo que citei é mais claro, porém o primeiro deixou a desejar.
Trata-se do seguinte: Seu programa deverá receber as entradas, até que se encontre o "final do arquivo", que seria algo como o fim do arquivo do qual está sendo retirado os testes.
A única forma que encontrei de lidar com este tipo de entrada, em c ou c++, foi utilizar o scanf dentro da condição do loop while, tal como while(scanf("%d",&num)!=EOF).
Pra quem não entendeu, EOF significa End of File( ou fim do arquivo), portanto o algoritmo irá entrar no loop caso a entrada seja diferente do fim do arquivo.
Bom, esses são os mais comuns e os que eu me lembro por hora. Caso ainda tenha ficado alguma dúvida, ou caso encontrem algum tipo de entreda que não entendam, postem nos comentários.
Em breve farei um post sobre os não menos importantes tipos de saída do SPOJ.
Até mais.
sexta-feira, 14 de setembro de 2012
Guia: Expressões
Pois é, como eu prometi a um tempinho, esse post será um mini tutorial sobre como resolver um exercício, nesse caso, o exercício Expressões.
Tenho em mente não entregar o código do exercício resolvido, porém apenas a ideia, deixando assim a implementação por conta do leitor. Acredito que a ideia já é suficiente, e a implementação por si próprio é um bom treino.
Bom, chega de papo, vamos ao exercício.
Exercício: 11014 - Expressões
Link: http://br.spoj.pl/problems/EXPRES11/
Clique em mais informações para ver o post completo.
Tenho em mente não entregar o código do exercício resolvido, porém apenas a ideia, deixando assim a implementação por conta do leitor. Acredito que a ideia já é suficiente, e a implementação por si próprio é um bom treino.
Bom, chega de papo, vamos ao exercício.
Exercício: 11014 - Expressões
Link: http://br.spoj.pl/problems/EXPRES11/
Clique em mais informações para ver o post completo.
Assinar:
Postagens (Atom)