Problem 1. splits.pl
This problem reprises splits.hs from assignment 2. In Prolog it is to be a predicate splits(+List,-Split) that unifies Split with each "split" of List in turn. Example:
?- splits([1,2,3],S).
S = [1]/[2, 3] ;
S = [1, 2]/[3] ;
false.
Note that Split is not an atom. It is a structure with the functor /. Observe:
?- splits([1,2,3], A/B).
A = [1],
B = [2, 3] ;
A = [1, 2],
B = [3] ;
false.
Here are additional examples. Note that splitting a list with less than two elements fails.
?- splits([],S).
false.
?- splits([1],S).
false.
?- splits([1,2],S).
S = [1]/[2] ;
false.
?- atom_chars('splits',Chars), splits(Chars,S).
Chars = [s, p, l, i, t, s],
S = [s]/[p, l, i, t, s] ;
Chars = [s, p, l, i, t, s],
S = [s, p]/[l, i, t, s] ;
Chars = [s, p, l, i, t, s],
S = [s, p, l]/[i, t, s] ;
Chars = [s, p, l, i, t, s],
S = [s, p, l, i]/[t, s] ;
Chars = [s, p, l, i, t, s],
S = [s, p, l, i, t]/[s] ;
false.
My solution uses only two predicates: append and \==
Problem 2. repl.pl
Write a predicate repl(?E, +N, ?R) that unifies R with a list that is N replications of E. If N is less
than 0, repl fails.
?- repl(x,5,L).
L = [x, x, x, x, x].
?- repl(1,3,[1,1,1]).
true.
?- repl(X,2,L), X=7.
X = 7,
L = [7, 7].
?- repl(a,0,X).
X = [].
?- repl(a,-1,X).
false.
Problem 3. pick.pl
Write a predicate pick(+From, +Positions, -Picked) that unifies Picked with an atom consisting of the characters in From at the zero-based, non-negative positions in Positions.
?- pick('testing', [0,6], S).
S = tg.
?- pick('testing', [1,1,1], S).
S = eee.
?- pick('testing', [10,2,4], S).
S = si.
?- between(0,6,P), P2 is P+1, pick('testing', [P,P2], S),
writeln(S), fail.
te
es
st
ti
in
ng
g
false.
?- pick('testing', [], S).
S = ''.
If a position is out of bounds, it is silently ignored. My solution uses atom_chars, findall,
member, and nth0.
Problem 4. polyperim.pl
Write a predicate polyperim(+Vertices,-Perim) that unifies Perim with the perimeter of the
polygon described by the sequence of Cartesian points in Vertices, a list of pt structures.
?- polyperim([pt(0,0),pt(3,4),pt(0,4),pt(0,0)],Perim).
Perim = 12.0.
?- polyperim([pt(0,0),pt(0,1),pt(1,1),pt(1,0),pt(0,0)],Perim).
Perim = 4.0.
?- polyperim([pt(0,0),pt(1,1),pt(0,1),pt(1,0),pt(0,0)],Perim).
Perim = 4.82842712474619.
The polygon is assumed to be closed explicitly, i.e., assume that the first point specified is the same as the
last point specified.
There is no upper bound on the number of points but at least four points are required, so that the minimal path describes a triangle. (Think of it as ABCA, with the final A "closing" the path.) If less than four points are specified, a message is produced:
?- polyperim([pt(0,0),pt(3,4),pt(0,4)],Perim).
At least a four-point path is required.
false.
This is not a course on geometric algorithms so keep things simple! Calculate the perimeter by simply summing the lengths of all the sides; don't worry about intersecting sides, coincident vertices, etc.
Be sure that polyperim produces only one result.
Problem 5. (18 points) switched.pl
This problem is a reprise of switched.rb from assignment 5. a8/births.pl has a subset of the baby name data, represented as facts. Here are the first five lines:
% head -5 a8/births.pl
births(1950,'Linda',f,80437).
births(1950,'Mary',f,65461).
births(1950,'Patricia',f,47942).
births(1950,'Barbara',f,41560).
births(1950,'Susan',f,38024).
births.pl only holds data for 1950-1959. Names with less than 70 births are not included.
Your task is to write a predicate switched(+First,+Last) that prints a table much like that produced by the Ruby version. To save a little typing, switched assumes that the years specified are in the 20th century.
?- switched(51,58).
1951 1952 1953 1954 1955 1956 1957 1958
Dana 1.19 1.20 1.26 1.29 1.00 0.79 0.67 0.64
Jackie 1.40 1.29 1.14 1.13 1.11 0.94 0.72 0.57
Kelly 4.23 2.74 3.73 2.10 2.32 1.77 0.98 0.51
Kim 2.58 1.82 1.47 1.08 0.61 0.30 0.17 0.12
Rene 1.43 1.32 1.15 1.24 1.13 0.88 0.87 0.89
Stacy 1.06 0.81 0.62 0.47 0.44 0.36 0.29 0.21
Tracy 1.51 1.14 1.02 0.73 0.56 0.55 0.59 0.59
true.
If no names are found, switched isn't very smart; it goes ahead and prints the header row:
?- switched(52,53).
1952 1953
true.
If you want to make your switched smarter, that's fine-I won't test with any spans that produce no names. Also, I'll only test with spans where the first year is less than the last year.
Names are left-justified in a ten-wide field. Below is a format call that does that. Note that the dollar sign is included only to clearly show the end of the output.
?- format("~w~t~10|tiny_mce_markerquot;, 'testing').
testing $
true.
Outputting the ratios is a little more complicated. I'll spare you the long story but I use sformat, like this:
?- sformat(Out, '~t~2f~6|', 2.32754), write(Out).
Problem 6. (18 points) iz.pl
In this problem you are to write a predicate iz/2 that evaluates expressions involving atoms and a set of operators and functions. Let's start with some examples:
?- S iz abc+xyz. % + concatenates two atoms
S = abcxyz.
?- S iz (ab + cd)*2. % *N produces N replications of the atom.
S = abcdabcd.
?- S iz -cat*3. % - is a unary operator that produces a reversed copy of the atom.
S = tactactac.
?- S iz -cat+dog.
S = tacdog.
?- S iz abcde / 2. % / N produces the first N characters of the atom.
S = ab.
?- S iz abcde / -3. % If N is negative, / produces last N characters
S = cde.
?- N is 3-5, S iz (-testing)/N.
N = -2,
S = et.
The functions len and wrap are also supported. len(E) evaluates to an atom (not a number!) that represents the length of E.
?- N iz len(abc*15).
N = '45'.
?- N iz len(len(abc*15)).
N = '2'.
wrap adds characters to both ends of its argument. If wrap is called with a two arguments, the second argument is concatenated on both ends of the string:
?- S iz wrap(abc, ==).
S = '==abc=='.
?- S iz wrap(wrap(abc, ==), '*' * 3).
S = '***==abc==***'.
If wrap is called with three arguments, the second and third arguments are concatenated to the left and right ends of the string, respectively:
?- S iz wrap(abc, '(', ')').
S = '(abc)'.
?- S iz wrap(abc, '>' * 2, '<' * 3).
S = '>>abc<<<'.
It is important to understand that len(xy), wrap(abc, ==), and wrap(abc, '(', ')') are simply structures. If iz encounters a two-term structure whose functor is wrap (like wrap(abc, ==)) its value is the concatenation of the second term, the first term, and the second term. iz evaluates len and wrap like is evaluates random and sqrt.
The atoms comma, dollar, dot, and space do not evaluate to themselves with iz but instead evaluate to the atoms ',', ', '.', and ' ', respectively. (They are similar to e and pi in arithmetic expressions evaluated with is/2.) In the following examples note that swipl (not me!) is adding some additional wrapping on the comma and the dollar sign that stand alone. That adornment disappears when
those characters are used in combination with others.
?- S iz comma.
S = (',').
?- S iz dollar.
S = ($).
?- S iz dot.
S = '.'.
?- S iz space.
S = ' '.
?- S iz comma+dollar*2+space+dot*3.
S = ',$ ...'.
?- S iz wrap(wrap(space+comma+space,dot),dollar).
S = '$. , .
?- S iz dollarcommadotspace.
S = dollarcommadotspace.
The final example above demonstrates that these four special atoms don't have special meaning if they appear in a larger atom.
Here is a summary for iz/2:
-Atom iz +Expr unifies Atom with the result of evaluating Expr, a structure representing a calculation involving atoms. The operators (functors) are as follows:
E1+E2 Concatenates the atoms produced by evaluating E1 and E2 with iz.
E*N Concatenates E (evaluated with iz) with itself N times. (Just like Ruby.) N is a term that can be evaluated with is/2 (repeat, is/2). Assume N >= 0.
E/N Produces the first (last) N characters of E if N is greater than (less than) 0.
If N is zero, an empty atom is produced. (An empty atom is shown as two single quotes with nothing between them.) N is a term that can be evaluated with is/2. The behavior is undefined if abs(N) is greater than the length of E.
-E Produces reversed E.
len(E) Produces an atom, not a number, that represents the length of E. wrap(E1,E2) Produces E2+E1+E2.
wrap(E1,E2,E3) Produces E2+E1+E3.
The behavior of iz is undefined for all cases not covered by the above. Things like 1+2, abc*xyz, etc., simply won't be tested.
Here are some cases that demonstrate that the right-hand operand of * and / can be an arithmetic expression:
?- X = 2, Y= 3, S iz 'ab' * (X+Y*3).
X = 2,
Y = 3,
S = ababababababababababab .
?- S = '0123456789', R iz S + -S, End iz R / -(2+3).
S = '0123456789',
R = '01234567899876543210',
End = '43210' .
Problem 7. observations.txt
Submit a plain text file named observations.txt with...
(a) An estimate of how long it took you to complete this assignment. To facilitate programmatic extraction of the hours from all submissions have an estimate of hours on a line by itself, more or less like one of the following three examples:
Hours: 6
Hours: 3-4.5
Hours: ~8
If you want the one-point bonus, be sure to report your hours on a line that starts with "Hours:". Some students are including per-problems times, too. That's useful and interesting data-keep it coming!-but observations.txt should have only one line that starts with Hours:. If you care to report perproblem times, impress me with a good way to show that data. Other comments about the assignment are welcome, too. Was it too long, too hard, too detailed? Speak up!
I appreciate all feedback, favorable or not.
(b) Cite an interesting course-related observation (or observations) that you made while working on the assignment. The observation should have at least a little bit of depth. Think of me saying "Good!" as one point, "Excellent!" as two points, and "Wow!" as three points. I'm looking for quality, not quantity.