I’ve been doing the Weekly
Challenges. The
latest
involved Cartesian coordinates and a light sequence modification.
(Note that this ends today.)
Task 1: Straight Line
You are given a list of co-ordinates.
Write a script to find out if the given points make a straight line.
With the usual provisos about floating point errors… this is much
easier in a language in which a pair of numbers can be a hash element.
Crystal:
def straightline(a)
The order doesn't matter, but b is a list of the unique points.
b = a.to_set.to_a
Two unique points (or fewer, as in example 4) count as being in a
straight line.
if b.size < 3
return true
end
Build line equations: x = p + qn, y = r + sn, from the (arbitrary)
first two points.
p = b[0][0]
q = b[1][0] - b[0][0]
r = b[0][1]
s = b[1][1] - b[0][1]
Now check each of the other points:
b[2, b.size].each do |tpair|
If q is zero, x must be a constant, so just check that it equals
the base value.
if q == 0.0 && tpair[0] != b[0][0]
return false
end
Similarly with s and y.
if s == 0.0 && tpair[1] != b[0][1]
return false
end
Otherwise, use the equations above to solve for n with the given x
and y. If the two values are not equal, the point does not lie on
the line.
if q != 0.0 && s != 0.0
n1 = (tpair[0] - p) / q
n2 = (tpair[1] - r) / s
if n1 != n2
return false
end
end
end
true
end
Languages with non-hashable arrays need a bit more fiddle in the
preamble; as in Python, where each point is checked against the
preceding ones. (Yes, I know Python specifically has a way of fiddling
this. I couldn't be bothered to look it up, and I had to write the
algorithm for other languages anyway.) The first line of the above is
replaced by this:
def straightline(a):
Start with an empty list.
b = []
Look at each point. Assume we'll use it.
for xy in a:
u = True
Check each point we already have.
for bxy in b:
If both coordinates match, it's a duplicate, so flag it as not for
use.
if xy[0] == bxy[0] and xy[1] == bxy[1]:
u = False
break
If it's still flagged for use, append it to the list.
if u:
b.append(xy)
Task 2: Duplicate Zeros
You are given an array of integers.
Write a script to duplicate each occurrence of zero, shifting the
remaining elements to the right. The elements beyond the length of
the original array are not written.
Very straightforward: copy the list, append zeroes, stop when you have
enough. Lots of length testing. Perl:
sub duplicatezeros($a) {
my @b;
foreach my $n (@{$a}) {
push @b, $n;
if ($#{$a} ==$#b) {
last;
}
if ($n == 0) {
push @b, 0;
if ($#{$a} ==$#b) {
last;
}
}
}
\@b;
}
But I did rather like the PostScript approach.
/duplicatezeros {
Take the input list's length, and leave it at the bottom of the stack.
dup length exch
Start building an array.
[ exch
Iterate over the input values.
{
Drop the value on the stack, then add another zero if it was zero.
dup 0 eq {
0
} if
} forall
]
Now we need to trim this array for output; that's why we kept the
input length. Arrange the parameters into order and fire off the
getinterval built-in, which is a sub-array copier.
exch 0 exch getinterval
} bind def
Full code on
github.