O projeto Prolog consiste em escrever um programa para resolver chapas de carro. Uma chapa de carro é um conjunto de quatro dígitos (estamos ignorando as letras neste projeto) e o objetivo é formar uma sentença matematicamente correta com os dígitos. Por exemplo, se a chapa for 4529, uma solução seria
4 = sqrt(5 + 2 + 9)
Você deve escrever um predicado resolve(Chapa,Expr) que recebe uma chapa na forma de uma lista de quatro dígitos e retorna uma expressão correta envolvendo estes dígitos, conforme as regras especificadas a seguir. Seu programa não pode definir nenhum predicado comecado pelas letras "jm", uma vez que ele será testado por um outro programa cujos predicados todos começam por "jm". Este programa testador está disponível nesta página também.
O progama deverá ser entregue até o dia 21/10/97
às 23:59, por e-mail para o endereco do professor (
meidanis@dcc.unicamp.br).
O predicado principal que você deverá implementar
chama-se resolve(+Chapa,-Expr). Não use
outros nomes, pois o testador se baseará neste nome.
A entrada será dada através do parâmetro
Chapa, na forma de uma lista contendo quatro
dígitos. Por exemplo, a chapa 4529 será passada
como [4,5,2,9].
A saída deve ser uma expressão representada em forma
de listas usando notação prefixa, ou seja, com os
operadores precedendo seus operandos. O predicado
resolve
deve
instanciar o parâmetro Expr com a
solução.
Há operadores unários e binários. Um operador unário na expressão será representado por uma lista de dois elementos, sendo o primeiro o operador e o segundo seu operando. Por exemplo, -4 será representado por [-,4], 5! será representado por [fat,5] e sqrt(16) será [sqrt,16].
Um operador binário na expressão será representado por uma lista de três elementos, sendo o primeiro o operador e o segundo e terceiro seus operandos. Por exemplo, 5+4 será representado por [+,5,4] e 8 mod 3 será [mod,8,3].
Os operadores deverão ser combinados com os dígitos da chapa para formar a expressão que será a resposta. Por exemplo, a expressão 4 = sqrt(5+2+9) deverá ser retornada como
[=,4,[sqrt,[+,5,[+2,9]]]]
Em geral haverá várias soluções para uma dada chapa. Que eu saiba, não existe chapa sem solução, pelo menos com os operadores e regras especificados abaixo.
Os operadores unários que podem ser utilizados são os seguintes: +, -, fat (fatorial) e sqrt (raiz quadrada). O + e o - podem ser aplicados a qualquer valor. O fatorial só pode ser aplicado a inteiros maiores ou iguais a zero. Lembre-se que fatorial de zero é um. Este fato é imensamente útil para resolver chapas que de outra forma seriam dificílimas ou até impossíveis. A raiz quadrada pode ser aplicada apenas a valores maiores ou iguais a zero, não necessariamente inteiros.
Os operadores binários que podem ser utilizados são os seguintes: +, -, *, /, mod, ^, log, raiz e dec. Os quatro primeiros são os operadores aritméticos pardrão. Observe que a divisão representada por / não é divisão inteira, ou seja, seu resultado pode não ser inteiro. Não é permitida divião por zero.
O operador mod retorna o resto da divisao do primeiro operando pelo segundo. Ambos operandos devem ser inteiros e o segundo deve ser estritamente maior que zero. Isto pode parecer estranho, visto que muitas linguagens, incluindo Prolog, permitem divisores negativos em mod, mas eu não gosto. A semântica é mal definida. Não quero e pronto!
O operador ^ representa exponenciação. Para ser válida, esta operação deve ser efetuada com o primeiro operando sendo um valor estritamente positivo, não necessariamente inteiro. Neste caso, segundo operando pode ter qualquer valor no campo dos números reais. Admite-se também a possibilidade de o primeiro operando ser zero. Neste caso, o segundo operando deverá ser estritamente positivo, e o resultado será invariavelmente zero.
O operador log atua sobre dois operandos, o primeiro sendo a base e o segundo o logaritmando. As restrições sobre a base são: tem que ser positiva e diferente de 1. O logaritmando deve ser estritamente positivo.
O operador raiz serve para extrair raízes genéricas, mas o índice da raiz deve estar presente na expressão também, ao contrário do operador unário da raiz quadrada. Por exemplo, a chapa 3811 pode ser resolvida com:
raiz(3,8) = 1 + 1
onde raiz(3,8) significa a raiz cúbica de 8. A raiz é está relacionada à exponenciação, pois raiz(x,y) equivale a y^(1/x). Por isso, as restrições ao uso da raiz são: y deve ser estritamente maior que zero, e x não pode ser zero (já que vai ser necessário calcular 1/x).
Por fim, o operador dec é especial. Seu objetivo é permitir a utilização de dois dígitos consecutivos como representando um nú mero decimal, como no exemplo abaixo, que resolve a chapa 5868:
sqrt(58 + 6) = 8
No programa, esta resposta deve ser escrita como
[=,[sqrt,[+,[dec,5,8],6]],8]
Assim, dec é um operador binario tal que dec(x,y) = 10*x+y. Contudo, como seu propósito é simplesmente permitir a construção de números decimais a partir de dígitos, sua utilização é restrita da seguinte forma. Seu segundo operando deve ser necessariamente um dígito. Seu primeiro operando pode ser um dígito ou o resultado de um outro dec. Não é permitido seu uso fora destas situações.
Além destas restrições, há as seguintes. A expressão como um todo deve possuir apenas um sinal de igual, que será o operador binário mais externo a ser aplicado. A expressão deve ser uma fórmula matemática verdadeira. Os dígitos presentes na expressão devem ser exatamente aqueles passados na chapa, e devem estar na mesma ordem em que aparecem na chapa. Apenas quatro dígitos devem estar na expressão, portanto, o que dá lugar para três operadores binários. Um deles é necessariamente o =. Há liberdade de escolha dos dois outros, bem como da associatividade dos operandos, mas não é permitido mudar a ordem em que aparecem. Não há limite na quantidade de operadores unários utilizados.
Bem, bem, estamos ainda discutindo isso, mas minha tendência é pedir que o programa acerte pelo menos 50% das chapas que lhe são dadas. Depois da entrega de todos os programas, escolherei uma coleção de 100 chapas ao acaso, e usarei esta mesma coleção para testar todos os programas. A nota do aluno será igual ao número de chapas resolvidas dividido por 10.
Simples. Rápido. Seguro. Eficiente.
Não é muito difícil fazer um programa que atinja o funcionamento mínimo. Eu fiz uma pequena experiência e escrevi um programa que tentava apenas operadores binários, mas tentava todas as possibilidades. Pois bem, este programa acertava entre 70 e 80% das chapas que lhe eram dadas. Como vêeem, não é difícil fazer um programa com o funcionamento mínimo. Observe que não estou preocupado com chapas com sintaxe errada nem nada disso. Quero apenas que resolva 50%. Nos outros 50% pode até xingar a minha mãe que não vai afetar o funcionamento mínimo.
Depois resolvi sofisticar um pouco o programa que escrevi e coloquei-o para vocês darem uma olhada aqui. Com estas modificações o programa acerta tipicamente 100% de chapas aleatórias. Na verdade, do total de 10000 chapas poss&ieacute;veis, ele deixa de fazer apenas umas 20 ou 30. Contudo, isto pode ser ilusório. Veja observações na página de uso do programa testador.