Documentation:CrossWordHelperProlog

What is the problem?

The program is a crossword solver.[?, e, l, l, o]
The input is an array, representing a word, with one or more missing letters in the form of a question-mark (?), for example: [?, e, l, l, o], and a variable such as Result to store the output.
The output is all the words matching that format, in this case: Result = Cello; Result=Hello; Result=Jello
The program interacts with a user on the command line.
The program provides an example of a crossword game the user can play from the command line while using the crossword helper

What is the something extra?

The program will take the asterisk (*) to represent one or more missing letters.
The program will have a crossword game the user can interact with

What did we learn from doing this?

We'll learn about implementing recursive algorithms in prolog
We'll learn about ways for a user to interact with the command line using prolog

Conclusions

We have found prolog to be very efficient at implementing the crossword solver. The logic required for the solver algorithm was much easier to write in Prolog than in Haskell, and therefore our code was shorter and simpler. Howeever, we found that Haskell has nicer built in methods to interact with the user than prolog. User interaction through the console is less intuitive in prolog and makes use of the program less clean. Further, we found it more difficult to implement a recursive algorithm that operates on strings in Prolog, and ended up modelling the words as an array.

Lesson 1. Prolog is a declarative programming language. (Upside)

Our star "*" operator is synonymous to regex's "[a-z, A-Z]*". A pattern only consisting of the star "*" operator matches with any string of length 0 or more. On the other hand, a pattern that starts with the star "*" operator followed by a pattern T matches a string S if there exists two sub-strings A and B such that B matches the pattern T and A appended to B forms S. The Prolog implementation maps very easily to this verbal description. Both descriptions of the star "*" operator answers "what does this function do" rather than "how does this function do what it's supposed to do". This makes Prolog a declarative language rather than a procedural language.

patternMatch([L], [L]).

patternMatch([?], [L]).

patternMatch([*], _).

patternMatch([LH|LT], [LH|Tail]) :- patternMatch(LT, Tail).

patternMatch([?|LT], [_|Tail]) :- patternMatch(LT, Tail).

patternMatch([*| T], W) :- append(_, R, W), patternMatch(T, R).

Lesson 2. Depth first search is built into Prolog. (Upside)

Our star "*" operator makes use of backtracking search / depth first search.

For example, the pattern "b*ana" and the string "banana" might first try to match on "bana" where the star "*" operator takes on the value of the "" null string. The algorithm would move onto matching the rest of the pattern "" with the rest of the string "na". The pattern "" and the string "na" does not match and hence, the algorithm would backtrack. After backtracking, the algorithm might match "b*" to "ban" with the star "*" operator being assigned the value of "an". The rest of the pattern "ana" would match with the rest of the string "ana" and our algorithm would return true.

Prolog has backtracking / depth first search built into it via its top - down proof solving capabilities implemented using the the box model. As a result, our pattern matching code does not explicitly display any backtracking logic. There's are no explicit if then statements nor are there any explicit stacks. Backtracking / depth first search is entirely implemented via prolog.

Lesson 3. io in Prolog causes undesirable backtracking. (Downside)

We initially tried to implement tic tac toe. It works but the ai isn't too smart. You can check it out at this link (https://github.com/Haximilian/TicTacToe/blob/master/win.pl). While writing this, I found that rules that evaluate to true or false depending on user input can cause undesirable backtracking. Suppose we have the following code:

myrule() :-

read(X),

X \= 5,

write(awesome)

myrule() :-

read(X),

X =:= 5,

write(try another number)

myrule()

If the user inputs 5, our program will move on to the second definition of the rule. Now, if we type a number other than 5, our program will fail. The desired behaviour is for the program to print "try another number" every time we input 5. Otherwise, our program should print "awesome" for any other input.

How to Run

$ swipl
Welcome to SWI-Prolog (threaded, 64 bits, version 8.2.4)

-- Load the main program with `[crossword].`
?- [crossword].
| true

-- Call the crosswordSolver function with a test input once loaded with `crossword`
?- crosswordSolver([h,e,l,?,o], Result).
Result=hello

-- press ; to get other solutions until the program outputs false

-- use viewBoard to view sample crossword puzzle
?- viewboard.
    0 1 2 3 4 5 6 7
0  [-,-,-,-,-,t,-,-]
1  [-,*,e,*,*,o,-,-]
2  [-,-,*,-,-,*,-,-]
3  [-,-,*,-,-,*,i,m]
4  [m,-,h,*,l,*,-,-]
5  [*,-,-,*,-,-,-,-]
6  [*,a,*,e,-,-,-,-]
7  [*,-,-,-,-,-,-,-]
true.

-- use checkBoard to edit sample crossword puzzle
?- addWord([h,e,l,l,o], 1, 1, horizontal).
true 

-- use checkBoard to check your solution for certain words
-- checkBoard takes takes in a word, coord, and orientation (horzional or vertical), as checkBoard(word, x_coord, y_coord, orientation)
?- checkBoard(hello, 1, 1, horizontal).
true.

Links

CPSC 312 Wiki - CrosswordHelper: https://wiki.ubc.ca/CrossWordHelperProlog

Github Repository: https://github.com/Haximilian/CrossWordHelper