RabbitFarm
2022-05-22
The Weekly Challenge 165 (Prolog Solutions)
The examples used here are from the weekly challenge problem statement and demonstrate the working solution.
Part 1
Plot lines and points in SVG format.
Solution
svg-->svg_begin, svg_body, svg_end.
svg_body-->[].
svg_body-->svg_line(_, _, _, _), svg_body.
svg_body-->svg_point(_, _), svg_body.
svg_begin-->['<?xml version="1.0" encoding="UTF-8" standalone="yes"?><!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd"><svg height="100%" width="100%" xmlns="http://www.w3.org/2000/svg" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">'].
svg_point(X, Y)-->['<circle cx="', X,'" cy="', Y, '" r="1" />'].
svg_line(X1, Y1, X2, Y2)-->['<line x1="', X1, '" x2="', X2, '" y1="', Y1, '" y2="', Y2, '" style="stroke:#006600;" />'].
svg_end-->[''].
plot([], SVGAccum, SVG):-
phrase(svg_begin, Begin),
flatten([Begin|SVGAccum], SVG).
plot([H|T], SVGAccum, SVG):-
length(H, 2),
[X, Y] = H,
phrase(svg_point(X, Y), Point),
plot(T, [Point|SVGAccum], SVG).
plot([H|T], SVGAccum, SVG):-
length(H, 4),
[X1, Y1, X2, Y2] = H,
phrase(svg_line(X1, Y1, X2, Y2), Line),
plot(T, [Line|SVGAccum], SVG).
plot(Lines, SVG):-
phrase(svg_end, End),
plot(Lines, [End], SVG).
main:-
plot([[53,10], [53, 10, 23, 30], [23, 30]], SVG),
maplist(write, SVG), nl,
halt.
Sample Run
$ gprolog --consult-file prolog/ch-1.p
<?xml version="1.0" encoding="UTF-8" standalone="yes"?><!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd"><svg height="100%" width="100%" xmlns="http://www.w3.org/2000/svg" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"><circle cx="23" cy="30" r="1" /><line x1="53" x2="23" y1="10" y2="30" /><circle cx="53" cy="10" r="1" /></svg>
Notes
SVG is an XML based format, and so the use of a DCG like this may be unexpected. After all, the "grammar" is really dictated by a known XML schema. Still, the DCG is helpful in that we can describe the sequence and formatting of the statements we expect. From this we can generate the required SVG and even do some basic validation.
Part 2
Given a list of numbers, generate the skip summations.
Solution
avg_difference(Avg, V, Difference):-
Difference is V - Avg.
square(X, XSquared):-
XSquared is X * X.
xy(X, Y, XY):-
XY is X * Y.
linear_regression(Points, RegressionLineEndpoints):-
length(Points, NumberPoints),
% 1. Calculate average of your X variable.
maplist(nth(1), Points, Xs),
msort(Xs, XSorted),
nth(NumberPoints, XSorted, XMax),
sum_list(Xs, XSum),
XAvg is XSum / NumberPoints,
% 2. Calculate the difference between each X and the average X.
maplist(avg_difference(XAvg), Xs, XDifferences),
% 3. Square the differences and add it all up. This is Sx.
maplist(square, XDifferences, XDifferencesSquared),
sum_list(XDifferencesSquared, Sx),
% 4. Calculate average of your Y variable.
maplist(nth(2), Points, Ys),
sum_list(Ys, YSum),
YAvg is YSum / NumberPoints,
% 5. Multiply the differences (of X and Y from their respective averages) and add them all together. This is Sxy.
maplist(avg_difference(YAvg), Ys, YDifferences),
maplist(xy, XDifferences, YDifferences, XY),
sum_list(XY, Sxy),
% 6. Using Sx and Sxy, you calculate the intercept by subtracting Sx / Sxy * AVG(X) from AVG(Y).
M is Sxy / Sx,
B is YAvg - (Sxy / Sx * XAvg),
EndX is XMax + 10,
EndY is M * EndX + B,
RegressionLineEndpoints = [0, B, EndX, EndY].
main:-
Points = [[333,129], [39, 189], [140, 156], [292, 134], [393, 52], [160, 166], [362, 122], [13, 193], [341, 104], [320, 113], [109, 177], [203, 152], [343, 100], [225, 110], [23, 186], [282, 102], [284, 98], [205, 133], [297, 114], [292, 126], [339, 112], [327, 79], [253, 136], [61, 169], [128, 176], [346, 72], [316, 103], [124, 162], [65, 181], [159, 137], [212, 116], [337, 86], [215, 136], [153, 137], [390, 104], [100, 180], [76, 188], [77, 181], [69, 195], [92, 186], [275, 96], [250, 147], [34, 174], [213, 134], [186, 129], [189, 154], [361, 82], [363, 89]],
linear_regression(Points, RegressionLine),
write(RegressionLine), nl.
Sample Run
$ gprolog --consult-file prolog/ch-1.p --consult-file prolog/ch-2.p
| ?- Points = [[333,129], [39, 189], [140, 156], [292, 134], [393, 52], [160, 166], [362, 122], [13, 193], [341, 104], [320, 113], [109, 177], [203, 152], [343, 100], [225, 110], [23, 186], [282, 102], [284, 98], [205, 133], [297, 114], [292, 126], [339, 112], [327, 79], [253, 136], [61, 169], [128, 176], [346, 72], [316, 103], [124, 162], [65, 181], [159, 137], [212, 116], [337, 86], [215, 136], [153, 137], [390, 104], [100, 180], [76, 188], [77, 181], [69, 195], [92, 186], [275, 96], [250, 147], [34, 174], [213, 134], [186, 129], [189, 154], [361, 82], [363, 89]],
linear_regression(Points, RegressionLine), append(Points, [RegressionLine], PointsLine), plot(PointsLine, SVG), maplist(write, SVG), nl.
<?xml version="1.0" encoding="UTF-8" standalone="yes"?><!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd"><svg height="100%" width="100%" xmlns="http://www.w3.org/2000/svg" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"><line x1="0" x2="403" y1="200.13227253558171" y2="79.249802930305563" style="stroke:#006600;" /><circle cx="363" cy="89" r="1" /><circle cx="361" cy="82" r="1" /><circle cx="189" cy="154" r="1" /><circle cx="186" cy="129" r="1" /><circle cx="213" cy="134" r="1" /><circle cx="34" cy="174" r="1" /><circle cx="250" cy="147" r="1" /><circle cx="275" cy="96" r="1" /><circle cx="92" cy="186" r="1" /><circle cx="69" cy="195" r="1" /><circle cx="77" cy="181" r="1" /><circle cx="76" cy="188" r="1" /><circle cx="100" cy="180" r="1" /><circle cx="390" cy="104" r="1" /><circle cx="153" cy="137" r="1" /><circle cx="215" cy="136" r="1" /><circle cx="337" cy="86" r="1" /><circle cx="212" cy="116" r="1" /><circle cx="159" cy="137" r="1" /><circle cx="65" cy="181" r="1" /><circle cx="124" cy="162" r="1" /><circle cx="316" cy="103" r="1" /><circle cx="346" cy="72" r="1" /><circle cx="128" cy="176" r="1" /><circle cx="61" cy="169" r="1" /><circle cx="253" cy="136" r="1" /><circle cx="327" cy="79" r="1" /><circle cx="339" cy="112" r="1" /><circle cx="292" cy="126" r="1" /><circle cx="297" cy="114" r="1" /><circle cx="205" cy="133" r="1" /><circle cx="284" cy="98" r="1" /><circle cx="282" cy="102" r="1" /><circle cx="23" cy="186" r="1" /><circle cx="225" cy="110" r="1" /><circle cx="343" cy="100" r="1" /><circle cx="203" cy="152" r="1" /><circle cx="109" cy="177" r="1" /><circle cx="320" cy="113" r="1" /><circle cx="341" cy="104" r="1" /><circle cx="13" cy="193" r="1" /><circle cx="362" cy="122" r="1" /><circle cx="160" cy="166" r="1" /><circle cx="393" cy="52" r="1" /><circle cx="292" cy="134" r="1" /><circle cx="140" cy="156" r="1" /><circle cx="39" cy="189" r="1" /><circle cx="333" cy="129" r="1" /></svg>
Notes
This is mainly an implementation of the same linear regression procedure as used in the Perl solution to the same problem. By consulting the solution to the first problem we can then re-use the same plotting code.
References
posted at: 23:28 by: Adam Russell | path: /prolog | permanent link to this entry
SVG Plots of Points and Lines
The examples used here are from the weekly challenge problem statement and demonstrate the working solution.
Part 1
Plot lines and points in SVG format.
Solution
use strict;
use warnings;
sub svg_begin{
return <<BEGIN;
<?xml version="1.0" encoding="UTF-8" standalone="yes"?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd"> <svg height="100%" width="100%" xmlns="http://www.w3.org/2000/svg" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
BEGIN
}
sub svg_end{
return "";
}
sub svg_point{
my($x, $y) = @_;
return "<circle cx=\"$x\" cy=\"$y\" r=\"1\" />";
}
sub svg_line{
my($x0, $y0, $x1, $y1) = @_;
return "<line x1=\"$x0\" x2=\"$x1\" y1=\"$y0\" y2=\"$y1\" style=\"stroke:#006600;\" />";
}
sub svg{
my @lines = @_;
my $svg = svg_begin;
for my $line (@_){
$svg .= svg_point(@{$line}) if @{$line} == 2;
$svg .= svg_line(@{$line}) if @{$line} == 4;
}
return $svg . svg_end;
}
MAIN:{
my @lines;
while(){
chomp;
push @lines, [split(/,/, $_)];
}
print svg(@lines);
}
__DATA__
53,10
53,10,23,30
23,30
Sample Run
$ perl perl/ch-1.pl
<?xml version="1.0" encoding="UTF-8" standalone="yes"?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd"> <svg height="100%" width="100%" xmlns="http://www.w3.org/2000/svg" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
<circle cx="53" cy="10" r="1" /><line x1="53" x2="23" y1="10" y2="30" /><circle cx="23" cy="30" r="1" /></svg>
Notes
Doing the SVG formatting from scratch is not so bad, especially when sticking only to points and lines. The boiler plate XML is taken from a known good SVG example and used as a template.
Part 2
Compute a linear regression and output an SVG plot of the points and regression line.
Solution
use strict;
use warnings;
sub svg_begin{
return <<BEGIN;
<?xml version="1.0" encoding="UTF-8" standalone="yes"?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd"> <svg height="100%" width="100%" xmlns="http://www.w3.org/2000/svg" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
BEGIN
}
sub svg_end{
return "";
}
sub svg_point{
my($x, $y) = @_;
return "<circle cx=\"$x\" cy=\"$y\" r=\"1\" />";
}
sub svg_line{
my($x0, $y0, $x1, $y1) = @_;
return "<line x1=\"$x0\" x2=\"$x1\" y1=\"$y0\" y2=\"$y1\" style=\"stroke:#006600;\" />";
}
sub svg{
my @lines = @_;
my $svg = svg_begin;
for my $line (@_){
$svg .= svg_point(@{$line}) if @{$line} == 2;
$svg .= svg_line(@{$line}) if @{$line} == 4;
}
return $svg . svg_end;
}
sub linear_regression{
my(@points) = @_;
# 1. Calculate average of your X variable.
my $sum = 0;
my $x_avg;
map{$sum += $_->[0]} @points;
$x_avg = $sum / @points;
# 2. Calculate the difference between each X and the average X.
my @x_differences = map{$_->[0] - $x_avg} @points;
# 3. Square the differences and add it all up. This is Sx.
my $sx = 0;
my @squares = map{$_ * $_} @x_differences;
map{$sx += $_} @squares;
# 4. Calculate average of your Y variable.
$sum = 0;
my $y_avg;
map{$sum += $_->[1]} @points;
$y_avg = $sum / @points;
my @y_differences = map{$_->[1] - $y_avg} @points;
# 5. Multiply the differences (of X and Y from their respective averages) and add them all together. This is Sxy.
my $sxy = 0;
@squares = map {$y_differences[$_] * $x_differences[$_]} 0 .. @points - 1;
map {$sxy += $_} @squares;
# 6. Using Sx and Sxy, you calculate the intercept by subtracting Sx / Sxy * AVG(X) from AVG(Y).
my $m = $sxy / $sx;
my $y_intercept = $y_avg - ($sxy / $sx * $x_avg);
my @sorted = sort {$a->[0] <=> $b->[0]} @points;
my $max_x = $sorted[@points - 1]->[0];
return [0, $y_intercept, $max_x + 10, $m * ($max_x + 10) + $y_intercept];
}
MAIN:{
my @points;
while(){
chomp;
push @points, [split(/,/, $_)];
}
push @points, linear_regression(@points);
print svg(@points);
}
__DATA__
333,129
39,189
140,156
292,134
393,52
160,166
362,122
13,193
341,104
320,113
109,177
203,152
343,100
225,110
23,186
282,102
284,98
205,133
297,114
292,126
339,112
327,79
253,136
61,169
128,176
346,72
316,103
124,162
65,181
159,137
212,116
337,86
215,136
153,137
390,104
100,180
76,188
77,181
69,195
92,186
275,96
250,147
34,174
213,134
186,129
189,154
361,82
363,89
Sample Run
$ perl perl/ch-2.pl
<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
<svg height="100%" width="100%" xmlns="http://www.w3.org/2000/svg" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
<circle cx="333" cy="129" r="1" /><circle cx="39" cy="189" r="1" /><circle cx="140" cy="156" r="1" /><circle cx="292" cy="134" r="1" /><circle cx="393" cy="52" r="1" /><circle cx="160" cy="166" r="1" /><circle cx="362" cy="122" r="1" /><circle cx="13" cy="193" r="1" /><circle cx="341" cy="104" r="1" /><circle cx="320" cy="113" r="1" /><circle cx="109" cy="177" r="1" /><circle cx="203" cy="152" r="1" /><circle cx="343" cy="100" r="1" /><circle cx="225" cy="110" r="1" /><circle cx="23" cy="186" r="1" /><circle cx="282" cy="102" r="1" /><circle cx="284" cy="98" r="1" /><circle cx="205" cy="133" r="1" /><circle cx="297" cy="114" r="1" /><circle cx="292" cy="126" r="1" /><circle cx="339" cy="112" r="1" /><circle cx="327" cy="79" r="1" /><circle cx="253" cy="136" r="1" /><circle cx="61" cy="169" r="1" /><circle cx="128" cy="176" r="1" /><circle cx="346" cy="72" r="1" /><circle cx="316" cy="103" r="1" /><circle cx="124" cy="162" r="1" /><circle cx="65" cy="181" r="1" /><circle cx="159" cy="137" r="1" /><circle cx="212" cy="116" r="1" /><circle cx="337" cy="86" r="1" /><circle cx="215" cy="136" r="1" /><circle cx="153" cy="137" r="1" /><circle cx="390" cy="104" r="1" /><circle cx="100" cy="180" r="1" /><circle cx="76" cy="188" r="1" /><circle cx="77" cy="181" r="1" /><circle cx="69" cy="195" r="1" /><circle cx="92" cy="186" r="1" /><circle cx="275" cy="96" r="1" /><circle cx="250" cy="147" r="1" /><circle cx="34" cy="174" r="1" /><circle cx="213" cy="134" r="1" /><circle cx="186" cy="129" r="1" /><circle cx="189" cy="154" r="1" /><circle cx="361" cy="82" r="1" /><circle cx="363" cy="89" r="1" /><line x1="0" x2="403" y1="200.132272535582" y2="79.2498029303056" /></svg>
Notes
I re-use the SVG code from Part 1 and add in the linear regression calculation. Continuing
a small habit from the past few weeks of these challenges I am making much use of map to
keep the code as small, and yet still readable, as possible. The linear regression
calculation is fairly straightforward, as much as I hate having a terse writeup on this
I am not sure I have much more to say!
References
posted at: 23:16 by: Adam Russell | path: /perl | permanent link to this entry