# September 2019 Archives

## Intersection of Straight Lines

Write a script to find the intersection of two straight lines. The coordinates of the two lines should be provided as command line parameter.

I vaguely remember we did the general form of the equation of a straight line at secondary school. The formula itself is pretty simple:

`Ax + By + C = 0`

Now, clearly, if we have two straight lines `A1, B1, C1` and `A2, B2, C2`, their intersection are the `x` and `y` such that `A1x + B1y + C = A2x + B2y + C2`. From the general formula we know that

`x = (-B1y - C1) / A1`

It takes a bit of pen and paper work to find out that

`y = (A2C1 - C2A1) / (A1B2 - A2B1)`

## Stones and Jewels

Create a script that accepts two strings, let’s call them “stones” and “jewels”. It should print the count of “letters” from the string “stones” found in the string “jewels”. For example, if your stones is “chancellor” and “jewels” is “chocolate”, then the script should print 8. To keep it simple, only A-Z, a-z characters are acceptable. Also, make the comparison case sensitive.

The most important thing is to realise that we only want to consider unique characters in the “stones”. My initial idea was for each character of the “stones” to count how many times it appears in the “jewels”. Remember that the global matching operator `m//g` returns the number of matches in list context.

Let’s call the subroutine with two names parameters, stones and jewels, each of them containing a string.

``````use List::Util qw{ uniq };

sub count1 {
my %args = @_;
my \$count = 0;
\$count += () = \$args{jewels} =~ /\$_/g
for uniq(split //, \$args{stones});
return \$count
}``````

## The longest sequence

Generate a longest sequence of the following “English Pokemon” names where each name starts with the last letter of previous name.

I’m not sure whether the term “sequence” has a unique and generally accepted definition. For example, does it have to contain each element just once? If not, the longest sequence might be

``girafarig girafarig girafarig girafarig girafarig girafarig girafarig girafarig...``

If we want each element to appear just once in the sequence, we are in the graph theory and we search for the longest simple path. For a general graph, this is an NP-hard problem, but fortunately, our input is small enough to be solved in reasonable time.

We can implement a brute-force search (i.e. trying all the possible sequences) recursively. The recursive steps takes the sequence constructed so far and tries to extend it by all the possible next steps, calling itself to extend each of them further.