Perl Weekly Challenge: The Ultimate Test of Cerebral Fitness

Posted on by

This week, both tasks are chess-based, so I’m just linking you to the original concept album for the musical Chess, knowing full well most of you will only know the big single, One Night in Bangkok.

So let’s move on to the ultimate test of cerebral fitness: Perl Weekly Challenge 281!

Task 1: Check Color

You are given coordinates, a string that represents the coordinates of a square of the chessboard as shown below:

Week_281_Task_1

Write a script to return true if the square is light, and false if the square is dark.

Example 1

Input: $coordinates = "d3"
Output: true

Example 2

Input: $coordinates = "g5"
Output: false

Example 3

Input: $coordinates = "e6"
Output: true

Approach

Ok, this one feels fairly straightforward: if the letter of the coordinate is a, c, e, or g and the number is even, or the letter is b, d, f, or h and the number is odd, then the square is light.

Raku

I’m sure I could get this to be more terse, but I’m going for readability and ease of comprehension, not lowest golf score.

sub isLight($coordinates) {
  my ($letter, $num) = $coordinates.comb;
  return (
    $letter.match(/<[aceg]>/) && ($num %% 2)
    ||
    $letter.match(/<[bdfh]>/) && !($num %% 2)
  ) ?? 'true' !! 'false';
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $coordinates = "d3"
Output: true

Example 2:
Input: $coordinates = "g5"
Output: false

Example 3:
Input: $coordinates = "e6"
Output: true

Perl

sub isLight($coordinates) {
  my ($letter, $num) = split //, $coordinates;
  return (
    ( ($letter =~ /[aceg]/) && ($num % 2 == 0) )
    ||
    ( ($letter =~ /[bdfh]/) && ($num % 2 == 1) )
  ) ? 'true' : 'false';
}

View the entire Perl script for this task on GitHub.

Python

In Python, it’s easy to just test to see if a string exists in another string, so we don’t have to resort to a regular expression.

def isLight(coordinates):
  letter = coordinates[0:1]
  num = int(coordinates[1:])
  return (
     ( (letter in "aceg") and (num % 2 == 0) )
     or
     ( (letter in "bdfh") and (num % 2 == 1) )
  )

View the entire Python script for this task on GitHub.

Elixir

Functions I wound up using:

At first, I got the error (UndefinedFunctionError) function Integer.is_odd/1 is undefined or private. However, there is a macro with the same name and arity. Be sure to require Integer if you intend to invoke this macro. However, once I added line 4, the error went away. Looking into why, I discovered that because Integer.is_even/1 and Integer.is_odd/1 are defined as macros so they can be used as guards, we have to require the module before we can use the functions.

  require Integer

  def isLight(coordinates) do
    letter = String.first(coordinates)
    {num, _} = Integer.parse(String.last(coordinates))
    cond do
      String.contains?("aceg", letter)
        and Integer.is_even(num) -> "true"
      String.contains?("bdfh", letter)
        and Integer.is_odd(num)  -> "true"
      true -> "false"
    end
  end

View the entire Elixir script for this task on GitHub.

Task 2: Knight’s Move

A Knight in chess can move from its current position to any square two rows or columns plus one column or row away. So in the diagram below, if it starts a S, it can move to any of the squares marked E.

Write a script which takes a starting position and an ending position and calculates the least number of moves required.

Week_281_Task_2

Example 1

Input: $start = 'g2', $end = 'a8'
Ouput: 4

g2 -> e3 -> d5 -> c7 -> a8

Example 2

Input: $start = 'g2', $end = 'h2'
Ouput: 3

g2 -> e3 -> f1 -> h2

Approach

There’s graph theory about how knights move around a chessboard, and we can think about the moves to get from a starting point on the board to an ending point on the board as a graph. This lets us do a breadth-first search of all the nodes to find a solution with the fewest number of moves.

First, we need a function to generate all the possible moves from a given starting point. Then we use hashes to keep track of where we’ve been on the board already (so we don’t get into endless loops) and how we got there. We put our starting point into a queue and note that we’ve been to that starting point and it took us 0 moves to get there. Then we pull that point out of the queue and generate all the possible points we can get to from there. We loop over those points, updating the hash to indicate the path we took to get there and the number of moves we needed. If one of these points is our destination, we bail out of the search; otherwise we push the point onto the end of the queue and shift the next point off the queue.

Raku

my @knightMoveList = (
  (-2, -1), (-2, +1), (-1, -2), (-1, +2),
  (+2, -1), (+2, +1), (+1, -2), (+1, +2),
);

sub knightMoves($coordinates) {
  my ($letter, $num) = $coordinates.comb;
  my @endpoints;
  for @knightMoveList -> @colRow {
    my ($col, $row) = @colRow;
    my $newcol = ($letter.ord + $col).chr;
    next unless $newcol ge "a" && $newcol le "h";
    my $newrow = $num + $row;
    next unless 1 <= $newrow <= 8;
    @endpoints.push($newcol ~ $newrow);
  }
  return @endpoints;
}

sub leastMoves($start is copy, $end) {
  # trivial case: we're already at the end point
  return ( 0, $end ) if $start eq $end;

  # Ok, we're going to need to search for a solution.

  # Keep track of how many moves it takes to get to
  # a particular position, starting at $start
  my %moves = ( $start => 0 );

  # also keep track of the path to get there
  my %path_to = ( $start => $start );

  # make a queue of starting points
  my @queue = ( $start );

  while ( @queue ) {
    $start = @queue.shift;

    # figure out the valid moves that we haven't been to yet
    my @endpoints = knightMoves($start).grep({
      %path_to{$_}:!exists
    });

    for @endpoints -> $next {
      # build the path to the next endpoint
      %path_to{$next} = %path_to{$start} ~ " -> $next";

      # increment the number of moves it takes to get there
      %moves{$next} = %moves{$start} + 1;

      # have we arrived at our destination
      return ( %moves{$next}, %path_to{$next} ) if $next eq $end;

      # no? then push this space onto our processing queue
      @queue.push: $next;
    }
  }

  # we can't get there from here!
  # (only possible when the chessboard is an odd size)
  return ( -1, "no path found" );
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku | less
Example 1:
Input: $start = 'g2', $end = 'a8'
Output: 4

g2 -> e3 -> c4 -> b6 -> a8


Example 2:
Input: $start = 'g2', $end = 'h2'
Output: 3

g2 -> e1 -> f3 -> h2


Example 3:
Input: $start = 'a1', $end = 'h8'
Output: 6

a1 -> c2 -> a3 -> c4 -> e5 -> g6 -> h8

Perl

my @knightMoveList = (
  [-2, -1], [-2, +1], [-1, -2], [-1, +2],
  [+2, -1], [+2, +1], [+1, -2], [+1, +2],
);

sub knightMoves($coordinates) {
  my ($letter, $num) = split //, $coordinates;
  my @endpoints;
  foreach my $colRow ( @knightMoveList ) {
    my ($col, $row) = @$colRow;
    my $newcol = chr(ord($letter) + $col);
    next unless $newcol ge "a" && $newcol le "h";
    my $newrow = $num + $row;
    next unless 1 <= $newrow <= 8;
    push @endpoints, ($newcol . $newrow);
  }
  return @endpoints;
}

sub leastMoves($start, $end) {
  # trivial case: we're already at the end point
  return ( 0, $end ) if $start eq $end;

  # Ok, we're going to need to search for a solution.

  # Keep track of how many moves it takes to get to
  # a particular position, starting at $start
  my %moves = ( $start => 0 );

  # also keep track of the path to get there
  my %path_to = ( $start => $start );

  # make a queue of starting points
  my @queue = ( $start );

  while ( @queue ) {
    $start = shift @queue;

    # figure out the valid moves that we haven't been to yet
    my @endpoints = grep {
      ! exists $path_to{$_}
    } knightMoves($start);

    foreach my $next ( @endpoints ) {
      # build the path to the next endpoint
      $path_to{$next} = $path_to{$start} . " -> $next";

      # increment the number of moves it takes to get there
      $moves{$next} = $moves{$start} + 1;

      # have we arrived at our destination
      return ( $moves{$next}, $path_to{$next} ) if $next eq $end;

      # no? then push this space onto our processing queue
      push @queue, $next;
    }
  }

  # we can't get there from here!
  # (only possible when the chessboard is an odd size)
  return ( -1, "no path found" );
}

View the entire Perl script for this task on GitHub.

Python

knightMoveList = [
  [-2, -1], [-2, +1], [-1, -2], [-1, +2],
  [+2, -1], [+2, +1], [+1, -2], [+1, +2],
]

def knightMoves(coordinates):
  letter = coordinates[0:1]
  num = int(coordinates[1:])
  endpoints = []
  for colRow in knightMoveList:
    col, row = colRow
    newcol = chr(ord(letter) + col)
    if "a" <= newcol <= "h":
      newrow = num + row
      if 1 <= newrow <= 8:
        endpoints.append(newcol + str(newrow))
  return endpoints


def leastMoves(start, end):
  # trivial case: we're already at the end point
  if start == end:
      return ( 0, end )

  # Ok, we're going to need to search for a solution.

  # Keep track of how many moves it takes to get to
  # a particular position, starting at $start
  moves = { start: 0 }

  # also keep track of the path to get there
  path_to = { start: start }

  # make a queue of starting points
  queue = [ start ]

  while ( queue ):
    start = queue.pop(0)

    # figure out the valid moves that we haven't been to yet
    endpoints = [
      m for m in knightMoves(start) if m not in path_to
    ]

    for next in endpoints:
      # build the path to the next endpoint
      path_to[next] = f'{path_to[start]} -> {next}'

      # increment the number of moves it takes to get there
      moves[next] = moves[start] + 1

      # have we arrived at our destination
      if next == end:
        return ( moves[next], path_to[next] )

      # no? then push this space onto our processing queue
      queue.append(next)

  # we can't get there from here!
  # (only possible when the chessboard is an odd size)
  return ( -1, "no path found" )

View the entire Python script for this task on GitHub.

Elixir

Wow, this is twice as big as the Raku, Perl, or Python solutions. I’m going to break it down. First, the knightMoves function:

  defp letterAdd(letter, add) do
    <<val::utf8>> = letter
    List.to_string([val + add])
  end

  def onBoard(c,r) do
    "a" <= c and c <= "h" and 1 <= r and r <= 8
  end
  
  defp knightMoveList(), do: [
    {-2, -1}, {-2, +1}, {-1, -2}, {-1, +2},
    {+2, -1}, {+2, +1}, {+1, -2}, {+1, +2},
  ]

  def knightMoves([], _, _, endpoints), do: endpoints

  def knightMoves([next | rest], letter, num, endpoints) do
    {col, row} = next
    newcol = letterAdd(letter, col)
    newrow = num + row
    endpoints = if onBoard(newcol,newrow) do
      # add to list being returned
      endpoints ++ [ newcol <> to_string(newrow) ]
    else
      endpoints
    end
    knightMoves(rest, letter, num, endpoints)
  end

  def knightMoves(coordinates) do
    letter = String.first(coordinates)
    {num, _} = Integer.parse(String.last(coordinates))
    knightMoves(knightMoveList(), letter, num, [])
  end

Adding or subtracting from the ASCII value of a character isn’t so easy in Elixir (“easy” being something like chr(ord(letter) + col)), so I decided to abstract it out into a letterAdd/2 function. Also, since I like to keep the lines in my PWC solutions under 65 characters (because of how my blog is formatted), I decided to abstract out a onBoard/2 function to determine if a column/row set was on the board. Then I thought about adding knightMovesList as a module attribute, but reading through the section on using module attributes as compile-time constants, they recommend using private functions as constants instead.

The knightMoves/4 functions themselves use recursion to process knightMovesList; this is the recommended method of looping in Elixir (that is, when you’re not looping over an enumerable and returning a modified version of that enumerable, like you do in Enum.map/2). I also provided a knightMoves/1 function that parsed the coordinates into its letter and number and then called knightMoves/4 with the list of move offsets, the letter and number, and an empty result list. 

  def processEndpoints(
    next, params = %{
      moves_to: moves_to,
      path_to:  path_to,
      startPos: startPos,
      endPos:   endPos,
      queue:    queue
    }
  ) do
    # update the move count map
    moves_to = Map.put(moves_to, next, moves_to[startPos] + 1)

    # update the path to current space map
    path_to = Map.put(path_to, next,
      "#{path_to[startPos]} -> #{next}"
    )

    if next == endPos do
      # we found the shortest path, update the return
      # values which will stop the loop
      %{ moves: moves_to[next], path: path_to[next] }
    else
      # update params for next iteration
      params |> Map.put(:moves_to, moves_to)
             |> Map.put(:path_to,  path_to)
             |> Map.put(:queue,    queue ++ [ next ])
    end
  end

  def processEndpoints(_, params = %{moves: moves})
    when not is_nil(moves), do: params

Because there’s a bunch of states I need to keep track of (the queue of spaces to consider, the starting position, the ending position, the map of move counts, and the map of paths to get to each space, I’m bundling them all together in a Map so I can pass them to the next recursive call (and return the values from those calls) in a single labelled data structure. But because I want to be able to easily access those values within the function, I use pattern matching to extract them as individual labels so I can access them easily within the function.

I initially implemented this as a recursive function, but then I realized I could use Enum.reduce/3 to call the function with each endpoint and pass in my params map as the “accumulator”:

params = Enum.reduce(endpoints, params, &processEndpoints/2)

But that left me with the problem of bailing out of the loop once we identified the shortest path. I was able to use a Guard in one of my processEndpoints/2 definitions (TBH, the definition I had initially written as the stopping case for the recursion) to check whether the :moves key in my params map had been defined, and if so, just return the params map without further processing. We still wind up calling processEndpoints/2 once for each item in endpoints, but once we find the shortest path, the rest of those calls are no-ops.

  # we've exhausted the queue
  # (only possible when the chessboard is an odd size)
  def processQueue([], _), do: %{
    moves: -1, path: "no path found"
  }

  def processQueue(_, params = %{moves: moves})
    when not is_nil(moves), do: params

  def processQueue([startPos | queue], params = %{
    path_to: path_to
  }) do
    # put the current starting position and the current queue
    # into the params
    params = params |> Map.put(:queue,    queue)
                    |> Map.put(:startPos, startPos)

    # figure out the valid moves that we haven't been to yet
    endpoints = knightMoves(startPos)
    |> Enum.filter(fn m -> !Map.has_key?(path_to, m) end)

    # call processEndpoints/2 for each of the endpoints
    params = Enum.reduce(endpoints, params, &processEndpoints/2)

    # recursively call to process the rest of the queue
    processQueue(params[:queue], params)
  end

I couldn’t do the same Enum.reduce/3 trick for processQueue/2, though, because we need to be able to add items to the queue from inside the function (well, really from within processEndpoints/2), and Enum.reduce/3 takes the list being processed as its first parameter. That’s not really a big deal though; this function still winds up being fairly succinct. It stuffs the current queue and starting position into the params map, gets the list of possible moves from this starting point, filters out the places we’ve already visited, and then makes the Enum.reduce/3 call to processEndpoints/2. I did add a stopping case that tested whether or not the :moves key in my params map had been defined, and if so, just return the params map without further processing.

  # trivial case: we're already at the end point
  def leastMoves(startPos, endPos) when startPos == endPos, do:
    { 0, endPos }

  def leastMoves(startPos, endPos) do
    params = processQueue([ startPos ], %{
      endPos:   endPos,
      moves_to: %{ startPos => 0 },
      path_to:  %{ startPos => startPos },
      moves:    nil,
      path:     nil
    })
    { params[:moves], params[:path] }
  end

Finally, I get to the function I call from my solution function. Really, besides handling the trivial case, all this does is set up the values being passed around in the params map, make the initial call to processQueue/2, and then unpack the :moves and :path keys in the returned params map and pass them back to the caller as a tuple.

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-281/packy-anderson