This content originally appeared on DEV Community and was authored by Bob Lied
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)
-
Input:
-
Example 2:
-
Input:
$path = "ULDR" -
Output:
true - U -> (0,1), L -> (-1,1), D -> (-1, 0), R -> (0,0)
-
Input:
-
Example 5:
-
Input:
$path = "RRUULLDDRRUU" -
Output:
true - RRUULLDD -> (0,0), RRUU -> (2,2)
-
Input:
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 agflag 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 thatm//will yield a list. Then taking thescalarof 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;
}
Notes:
-
use Math::Complex-- Yes, Perl does complex arithmetic. -
state $origin = (0 + 0*i)-- Set up a "constant" for the origin.statemakes a variable that is initialized only the first time the function is entered, and limits the scope to the function.Math::Complexmakes it possible to write complex constants in a natural way. -
state %move-- Set up "constants" for movements. Moving Right and Left affects the real part of the complex number; moving Up and Down affects the imaginary part. -
for ( split(...) )-- Take the path apart to process each move. I threw in anucto make sure we would only have uppercase input. -
$place += $move{$_}-- For each move, change$placein the complex plane.Math::Complexoverloads operators as expected. -
return true if $place == $origin-- Complex numbers can be compared, of course. - If we didn't find (0,0), then the answer is
false.
This content originally appeared on DEV Community and was authored by Bob Lied
Bob Lied | Sciencx (2025-11-26T03:32:52+00:00) PWC 349 More complex than it has to be. Retrieved from https://www.scien.cx/2025/11/26/pwc-349-more-complex-than-it-has-to-be/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.