PWC 349 More complex than it has to be

#perl #pwc #perlweeklychallenge

PWC 349 Task 2: Meeting Point

Musical Interlude

We're going deep cut from the classic Blood on the Tracks album by Bob Dylan, Meet Me in the Morning

The Task

You are given an instruction string made up of U (up), D (down), L (left) and R (right). Write a script to return true if following the instructions, you meet (0,0) at any point along the sequence.

Example 1:
- Input: $path = "ULD"
- Output: false
- U -> (0,1), L -> (-1,1), D -> (-1, 0)
Example 2:
- Input: $path = "ULDR"
- Output: true
- U -> (0,1), L -> (-1,1), D -> (-1, 0), R -> (0,0)
Example 5:
- Input: $path = "RRUULLDDRRUU"
- Output: true
- RRUULLDD -> (0,0), RRUU -> (2,2)

The Deliberation

The first thought is emulate the movement on the grid and see if we end up at (0,0).

A clever thought arises: to end up back where we began, every Up must be matched with a Down, and every Right must be matched with a Left. So all we really have to do is count moves, right?

But Example 5 throws a wrench. The path makes a big square and passes through (0,0), but doesn't end there. I guess I really do need to check every move in the path.

Second clever thought (this one might be worth keeping): moving around a grid can be like moving in the complex plane. A horizontal move is along the real axis, and a vertical move is along the imaginary axis. If we think of the location as a complex number, then a move is an increment of either the real or the imaginary part.

The Code

Nice try, no cigar

Let's dispense with what didn't work, because it looked good until we hit Example 5.

sub meet($path)
{
    my @m = map { scalar(()= $path =~ m/$_/g) } qw(U D L R);
    return $m[0] == $m[1]  && $m[2] == $m[3];
}

Notes:

We'll try to count the number of each direction and see if Ups cancel Downs and Rights cancel Lefts.
my @m = map {...} qw(U D L R) -- for each move, map to the number of occurrences of that move in $path
$path =~ m/$_/g -- $_ is one of (U,D,L,R). The regular expression match with a g flag can return a list of all the occurrences of that letter in $path.
scalar(()= ...) -- assigning the match to an empty list will create an array context, so that m// will yield a list. Then taking the scalar of that will give a count. This is a variant of the =()= Saturn secret operator
Now it only remains to check if the numbers align.

Moving on to something that works

sub meetComplex($path)
{
    use Math::Complex;

    state $origin = (0 + 0*i);
    state %move = ( R => (1 + 0*i), L => (-1 +  0*i),
                    U => (0 + 1*i), D => ( 0 + -1*i), );

    my $place = $origin;
    for ( split(//, uc $path) )
    {
        $place += $move{$_};
        return true if $place == $origin;
    }
    return false;
}