Link do código: GitHub
Overview
Tudo começou com um trabalho passado pelo professor em Linguagens Formais e Autômatos. O que o trabalho pediu era a modelagem de um problema em autômatos finitos determinísticos.
Bolando como fazer o trabalho eu comecei a procurar uma forma mais visual de visualizar o jogo e achei um joguinho já implementado. Nisso eu descobri qual era o ponto otimo e então poderia expandir os outros por que não é só o caminho ótimo que eu teria que mostrar.
Nisso começei a rabiscar os modelos num caderno mas percebi que não ia terminar tão cedo.
Implementação
Ai eu lembrei do GraphViz. Já tinha arranhado algumas coisas por lá, mais especificamente no PlantText. Já tinha tentado modelar o Jogo da Velha, o que me isolou de toda uma classe de problemas por que uma jogada de jogo da velha não pode ser desfeita mas aproveitei muitas ideias desse primeiro projeto.
Como o Jogo da Velha, eu fiz um script Python que percorre o espaço de estados usando Busca Aprofundada Limitada para evitar ter que expandir muitos estados e entrar em um loop infinito, no Jogo da Velha nem faz lá tão sentido implementar algo assim porque como eu disse, jogadas não podem ser desfeitas e existe um conjunto limite de jogadas (pior dos casos, 9).
As torres de Hanoi com 3 torres tem um ótimo em 7 jogadas mas eu limitei a busca de estados a 15 e mesmo assim estava tendo explosões de estados. Realizo que estou fazendo cagada. Renderizações estavam levando um tempo inviável com saídas usando centenas de MBs. Nisso eu descobri que o GraphViz tem o strict digraph que deduplica as arestas e um acompanhamento dos estados já visitados para não ter que recalcular esses estados.
Busca em profundidade eu considero um algoritmo simples de se implementar e usa recursão, o controle de recursão é através de um parâmetro chave que a cada nivel vai sendo decrescido. Se chegar a zero, vai desenrolando de volta.
Um problema que eu tive que lidar nesse projeto foi a cópia das estruturas de dados. Por padrão o código fazia modificações inplace da estrutura de dados e isso atrapalhava totalmente o resultado, felizmente achei a função copy.deepcopy que gera uma cópia independente do objeto inicial e assim eu consegui resolver aquele problema.
Para melhor visualizar o algoritmo eu então gerei as transições, estava usando profundidade limitada pra mitigar loops infinitos causados pela minha ingenuidade. Achei uma abordagem mais senior mantendo um dicionário dos nós visitados. Um estado pode ser facilmente derivado para uma string que é a chave desse dicionário. Isso me permitiu remover essa limitação de profundidade e me deu a segurança de que iria encontrar todos os estados.
Do jeito que estava ele estava gerando 59 nós, na hora eu não me toquei disso mas trocando ideia com meu brodi da facul, o Hugo, ele questionou a quantidade de estados. Na hora eu não botei muita fé mas quase que em ultima hora eu percebi uma falha na validação das regras do jogo que abaixou o numero de estados para 25. Isso gerou o seguinte grafo não direcionado.
Agora eu tenho uma representação visual porém eu preciso da representação em um Autômato FInito Não Determinístico, a regra de negócio estava feita, agora é gerar a modelagem do grafo.
A estratégia escolhida é usar um caractere para o pino de entrada e outro para um pino de saída. Para enviar o que está no primeiro pino para o ultimo pino usaria-se a cadeia ac, logo o ótimo para Hanoi com 3 pinos é acabcbacbabcac. Eu tinha que também minimizar o autômato eliminando estados inúteis e inacessíveis. Como os estados eram gerados sob demanda todos eram acessíveis então a minimização era basicamente remover estados fim de linha até não ter mais o que remover. Ao remover um estado fim de linha ele pode tornar outro estado fim de linha por isso as iterações. Quando não houver estados para remover então a minimização está concluída. Este autômato gerado ficou com 102 estados que se tornam 76 com o autômato minimizado que desenhado fica o seguinte:
Também tinha que implementar a geração da expressão regular do autômato porém essa não deu muito certo, mesmo utilizando um esquema de classes para evitar alocações gigantes de string. Certamente eu fiz algo errado ai mas já era. Não tinha mais tempo. Final das contas tiramos 60/100, e como dizem: “Na federal 60 é o novo 100” :v.
Códigos:
