Author Message

So did anyone at all look at this program?  I will include it here again, in text
form.  I am interested in comments, please.  Feel free to email me directly at

Quote:

> I have written the following program, using the strawberry prolog
> compiler (lite version).  Its goal is to solve number sequences, such as
> those given on math tests, mensa tests, and the like (I.E. 1, 2, 4, ?).
> I self-proclaim that I am definitely a rookie when it comes to Prolog,
> so I am interested in your comments, suggestions, and improvements.  I
> think this program works reasonably well for small problems, however it
> takes exponentially longer time to solve larger ones.  This is an
> unavoidable result of the algorithm that I am using, which is to make
> sub-lists by finding the sums, differences, products, and quotients of
> elements of the larger lists, and then look for identity lists (single
> element lists containing 1, 0, or -1).

> Anyhow, have a look, let me know what you think, and please feel free to
> criticize (or even rewrite) the code!

> Glenn Emelko

%*************************************
%
%
% Number Sequence Solver Version 1.1
%
% (C) 2000 Glenn A. Emelko
%
%
% This program tries to solve for a
% number at the end of a number sequence
%
%*************************************

%-------------------------------------
% is_sum(A,B,C) -- solve the equation C=A+B
%  if any two variables are known.

is_sum(A,B,C) :-
number(A), number(B), C is A + B;
number(A), number(C), B is C - A;
number(B), number(C), A is C - B.

%-------------------------------------
% is_prod(A,B,C) -- solve the equation C=A*B
%  if any two variables are known.

is_prod(A, B, C) :-
number(A), number(B), C is A * B;
number(A), number(C), A =\= 0, B is C / A;
number(B), number(C), B =\= 0, A is C / B.

%-------------------------------------
% is_diff(A,B,C) -- solve the equation C=A-B
%  if any two variables are known.

is_diff(A,B,C) :-
number(A), number(B), C is A - B;
number(A), number(C), B is A - C;
number(B), number(C), A is B + C.

%-------------------------------------
% is_div(A,B,C) -- solve the equation C=A/B
%  if any two variables are known.

is_div(A,B,C) :-
number(A), number(B), B =\= 0, C is A / B;
number(A), number(C), C =\= 0, B is A / C;
number(B), number(C), A is B * C.

%-------------------------------------
% first(L,F) -- F is the first element
% of list L

first([A|_],A).

%-------------------------------------
% solve_seq(I,O) -- given input list I,
% find a sub-list O which is a set of
% sums, products, differences, or quotients,
% predicted by recognizing sub-lists
% which ultimately boil down to one of the
% identity lists ([], [0], [1], and [-1]).

solve_seq([],[]) :- !.

solve_seq([_|[]],[0]).

solve_seq([_|[]],[1]).

solve_seq([_|[]],[-1]).

solve_seq([A|[]],[A]).

solve_seq([A|[B]],[C]) :-
number(C),
B is A + C, !.

solve_seq([A|[B]],[C]) :-
number(C),
B is A * C, !.

solve_seq([A|[B]],[C]) :-
number(C),
B is A - D, !.

solve_seq([A|[B]],[C]) :-
number(C),
C =\= 0,
B is A / C, !.

solve_seq([A|T],[D|R]) :-
solve_seq(T, R), first(T, N), is_sum(A, D, N), !;
solve_seq(T, R), first(T, N), is_prod(A, D, N), !;
solve_seq(T, R), first(T, N), is_diff(A, D, N), !;
solve_seq(T, R), first(T, N), is_div(A, D, N).

solve_seq([_|[_]],[_]).

%-------------------------------------
% solve(I, O) -- solve an input list
%  with a missing last element, filling
% in the last element into the output
% list, by using solve_seq, allowing
% backtracking to find all possible lists.

solve([],[]) :- !.

solve([_], [0]) :- !.

solve([_], [1]) :- !.

solve([_], [-1]) :- !.

solve([A], [A]).

solve(A, B) :-
B is A,
solve_seq(A, D),
solve(D, E),
solve_seq(B, E),
valid(B).

%-------------------------------------
% best_solve(I, O) -- solve an input list
%  with a missing last element, filling
% in the last element into the output
% list, by using solve_seq, preventing
% backtracking from finding all lists.

best_solve([],[]) :- !.

best_solve([_], [0]) :- !.

best_solve([_], [1]) :- !.

best_solve([_], [-1]) :- !.

best_solve([A], [A]).

best_solve(A, B) :-
B is A,
solve_seq(A, D),
!,
best_solve(D, E),
solve_seq(B, E),
valid(B).

%-------------------------------------
% valid(I) -- true if I is a list in which
% all elements are numbers

valid([]).

valid([A]) :-
!,
number(A).

valid([A|R]) :-
number(A),
!,
valid(R).

%-------------------------------------
% member(X,L) -- true if X is a member of
% list L

member(X,[X | L]).

member(X, [_ | L]) :-
member(X, L).

%-------------------------------------
% showsolutions(L) -- assuming L is a list
%  of valid solutions, display all
% unique solutions by only showing those
% which are not members of the remainder
% of the list

showsolutions([]).

showsolutions([A|B]) :-
member(A,B),
showsolutions(B).

showsolutions([A|B]) :-
write(A),nl,
showsolutions(B).

%-------------------------------------
% so here's the goal -- C is the input, with
% a missing last element, first find all
% possible solutions, then find only the best
% one(s).

?-
C is [1, 2, 4, _],
write("All solution(s):"), nl,
!,
findall(D,solve(C, D),Dlist),
showsolutions(Dlist),
write("Best solution(s):"),nl,
findall(E,best_solve(C,E),Elist),
showsolutions(Elist).

%
% Easy, right?
%

Sun, 29 Jun 2003 10:06:14 GMT

Quote:

>> I have written the following program, using the strawberry prolog
>> compiler (lite version).  Its goal is to solve number sequences, such as
>> those given on math tests, mensa tests, and the like (I.E. 1, 2, 4, ?).
>> I self-proclaim that I am definitely a rookie when it comes to Prolog,
>> so I am interested in your comments, suggestions, and improvements.  I
>> think this program works reasonably well for small problems, however it
>> takes exponentially longer time to solve larger ones.  This is an
>> unavoidable result of the algorithm that I am using, which is to make
>> sub-lists by finding the sums, differences, products, and quotients of
>> elements of the larger lists, and then look for identity lists (single
>> element lists containing 1, 0, or -1).

There is an exercise in "AI a modern approach" for solving such puzzles
using state space search, rather more general than your solution.  Its
somewhat arbitrary what the "correct" answer is, since any sequence of
numbers fits *some* function.  The aim is to find the "simplest"
function which fits, and there is no straightforward definition of
simplest.  For "hard" sequences the search space is very large - there is no
way around this.  Below is a spec I wrote for a student project based on the
excercise above (hopefully it gives an idea of the method).  It was from
a couple of years back, so feel free to post solutions, hints, etc.

lee

433-303 Artificial Intelligence

Project 1

Aim

The aim of this project is for you to get experience with programming in
Prolog and problem solving using the state space approach.

Outline

Tests of human intelligence contain sequence prediction problems. The aim of
such problems is to predict the next member of a sequence of integers,
assuming the number in position n of the sequence is generated by some
sequence function s(n), where the first element of the sequence corresponds
to n = 0. For example, the function s(n) = 2 + n^2 generates the sequence
[2, 3, 6, 11,...].

You will be provided with a Prolog code skeleton
/home/stude/data/303/proj1/seq.pl which you must extend to produce a working
program. The existing code should not be modified. There are also some

The algorithm

The state space approach to problem solving will be used. Each state is an
arithmetic function. The functions are represented as Prolog terms
consistsing of the constants 1 and n and the functors +, - and * of arity
two. For example, 2+n^2 can be represented by the term 1+1+n*n. The
successors of a state are computed by replacing a constant (a leaf node of
the expression tree) by an expression containing two constants. For example,
(n*n)+1+n*n and 1+1+ (1-n)*n are two succesors of the state above. The state
space will be searched using the depth first iterative deepening algorithm
(see dfid.pl).

* Complete the definitions of the predicates s/2, goal/1, predict_next/3
(to do so you will have to write some auxilliary predicates also). The
code should run under SWI-Prolog. An example would be:

?- [dfid, seq].
dfid compiled, 0.02 sec, 3,128 bytes.
seq compiled, 0.02 sec, 10,672 bytes.

Yes
?- predict([2, 3, 6, 11]).
Next number is 18
Solution path found was [1, 1+1, 1+ (1+1), 1+ (1+n*n)]

* At the start of the file, in a block of comments, write answers to the
following questions:
1. What inefficiencies are caused by this definition of a state space
representing the sequence prediction problem (eg redundencies
etc)? Note: discuss the state space definition rather than the
particular search algorithm (the dfid.pl file could easily be
replaced by code which implements a different search algorithm).
2. Discuss some ways these inefficiencies could be reduced or
avoided.
3. Why is your program unlikely to be able to predict the next number
in the following simple sequence: [10,11,12,13,...]?
4. How could your program be modified to find functions of the form
s(n) = k + f(n), where k is an integer, more quickly?

Questions and answers pertaining to the project will be available in
QandA.html and will be considered part of the specification of the project.

Marking

This project is worth 10% of the final mark for the subject. Approximately
half the marks will be based on the coding and the rest for answering the
questions. Marking of the code will be based on its overall quality
(correctness according to the specification, readability, etc).

Submission

You will need to submit your version of seq.pl (this filename must be used).
Submit using the command submit 303 1 on a Computer Science machine by
5:00pm on Friday 16 April. Verify your submission using the command verify
303 1. Late submissions will incur a penalty of two marks per day (or part
thereof) late. If you cannot submit on time you should contact the tutor in
charge or lecturer at the soonest possible opportunity (this generally means
before the deadline). Late submission will be done using the command submit
303 1.late

Mon, 30 Jun 2003 09:35:26 GMT
Lee,

search also produces the answer in terms of the formula, whereas my
"difference/product/sum/divisor" list produces only an answer without giving the
formula itself.  Although some clues can be determined by looking at the
sub-lists, there is no specific result as to the degree of the polynomial, etc.
I put 2,3,6,11 in, and in fact it does indicate the best solution is 18, so that
is in agreement, and you can do much harder problems without blowing the stack
if you comment out the "solve" goal and just do the "best_solve" and let it find
the easiest (?) solution.  In fact, modifying it in this small way, the sub-list
program solves both higher order functions as well as the simplest (like
[10,11,12,13]) and even things like 2*N^3-N^2/2-N+5!!!  (give it
[5,5.5,17,51.5,_] and it finds 121!!!).

Regardless, what I was really wondering is if I am thinking too "procedurally"
in writing this program, and are there better predicates which arrive at much
the same result and which are more in the spirit of the intent of programming in
Prolog?  I am not as interested in the solution to this particular problem as I
am in knowing whether or not I'm fully appreciating the power of the language