Perl Weekly Challenge: Merge the Target Index Items

For some reason, my brain conflated “index” with “reflex”, so this week’s musical theme is The Reflex by Duran Duran. Yeah, I remember when that was on the radio.

Onward to Perl Weekly Challenge 263!

Task 1: Target Index

You are given an array of integers, @ints and a target element $k.

Write a script to return the list of indices in the sorted array where the element is same as the given target element.

Example 1

Input: @ints = (1, 5, 3, 2, 4, 2), $k = 2
Output: (1, 2)

Sorted array: (1, 2, 2, 3, 4, 5)
Target indices: (1, 2) as $ints[1] = 2 and $ints[2] = 2

Example 2

Input: @ints = (1, 2, 4, 3, 5), $k = 6
Output: ()

No element in the given array matching the given target.

Example 3

Input: @ints = (5, 3, 2, 4, 2, 1), $k = 4
Output: (4)

Sorted array: (1, 2, 2, 3, 4, 5)
Target index: (4) as $ints[4] = 4

Approach

The approach here is pretty straightforward: sort the list, then scan for entries where the value matches the target. There’s probably a clever way to do it, but it’s not coming to me, and I’ve always stressed ease of implementation and comprehension over cleverness in my solutions.

Raku

In Raku, we can use the kv routine on lists to loop over the sorted list of ints and have both the index and the value at that index.

sub targetIndex($k, @ints) {
  my @sorted = @ints.sort;
  my $explain = 'Sorted array: (' ~ @sorted.join(', ') ~ ")\n";

  my @output;
  for @sorted.kv -> $i, $v {
    next unless $v == $k;
    @output.push($i);
  }
  if (@output == 0) {
    $explain ~= 'No element in the given array matching '
             ~  'the given target.';
  }
  else {
    $explain ~= 'Target indices: (' ~ @output.join(', ')
             ~  ') as ';
    my @explain_indices = @output.map({ "\$ints[$_] = $k"});
    $explain ~= @explain_indices.join(' and ');
  }
  return $explain, @output;
}
$ raku/ch-1.raku
Example 1:
Input: @ints = (1, 5, 3, 2, 4, 2), $k = 2
Output: (1 2)

Sorted array: (1, 2, 2, 3, 4, 5)
Target indices: (1, 2) as $ints[1] = 2 and $ints[2] = 2

Example 2:
Input: @ints = (1, 2, 4, 3, 5), $k = 6
Output: ()

Sorted array: (1, 2, 3, 4, 5)
No element in the given array matching the given target.

Example 3:
Input: @ints = (5, 3, 2, 4, 2, 1), $k = 4
Output: (4)

Sorted array: (1, 2, 2, 3, 4, 5)
Target indices: (4) as $ints[4] = 4

View the entire Raku script for this task on GitHub.

Perl

In Perl, however, we just loop over the indices as $i and use $sorted[$i] to access the values at those indices.

sub targetIndex($k, @ints) {
  my @sorted = sort @ints;
  my $explain = 'Sorted array: (' . join(', ', @sorted) . ")\n";

  my @output;
  foreach my $i (0 .. $#sorted) {
    next unless $sorted[$i] == $k;
    push @output, $i;
  }
  if (@output == 0) {
    $explain .= 'No element in the given array matching '
             .  'the given target.';
  }
  else {
    $explain .= 'Target indices: (' . join(', ', @output)
             .  ') as ';
    my @explain_indices = map { "\$ints[$_] = $k"} @output;
    $explain .= join(' and ', @explain_indices);
  }
  return $explain, @output;
}

View the entire Perl script for this task on GitHub.

Python

In Python, we get to use the enumerate function I last used back in PWC251.

def comma_join(arr):
    return ', '.join(map(lambda i: str(i), arr))

def targetIndex(k, ints):
  sortedArray = sorted(ints)
  explain = f'Sorted array: ({comma_join(sortedArray)})\n'

  output = []
  for i, v in enumerate(sortedArray):
    if v == k:
      output.append(i)
  
  if len(output) == 0:
    explain += 'No element in the given array matching '
    explain += 'the given target.'
  else:
    explain += f'Target indices: ({comma_join(output)}) as '
    explain_indices = [ f'$ints[{i}] = {k}' for i in output ]
    explain += ' and '.join(
       map(lambda i: str(i), explain_indices)
    )
  return explain, output

View the entire Python script for this task on GitHub.


Task 2: Merge Items

You are given two 2-D array of positive integers, $items1 and $items2 where element is pair of (item_id, item_quantity).

Write a script to return the merged items.

Example 1

Input: $items1 = [ [1,1], [2,1], [3,2] ]
       $items2 = [ [2,2], [1,3] ]
Output: [ [1,4], [2,3], [3,2] ]

Item id (1) appears 2 times: [1,1] and [1,3]. Merged item now (1,4)
Item id (2) appears 2 times: [2,1] and [2,2]. Merged item now (2,3)
Item id (3) appears 1 time: [3,2]

Example 2

Input: $items1 = [ [1,2], [2,3], [1,3], [3,2] ]
       $items2 = [ [3,1], [1,3] ]
Output: [ [1,8], [2,3], [3,3] ]

Example 3

Input: $items1 = [ [1,1], [2,2], [3,3] ]
       $items2 = [ [2,3], [2,4] ]
Output: [ [1,1], [2,9], [3,3] ]

Approach

This feels like a wonderful thing to use a hash for: as we loop through the pairs and use the item_id as the hash key and just add item_quantity to the hash value.

Raku

sub mergeItems(@items1, @items2) {
  my %merged;
  # loop over the items and add item_quantities (element 1)
  # to the count for each item_id (element 0)
  for (slip(@items1), slip(@items2)) -> @i {
    %merged{@i[0]} += @i[1];
  }
  # re-render the hash as a 2D array
  return %merged.keys.sort.map({ [ $_, %merged{$_} ] });
}
$ raku/ch-2.raku
Example 1:
Input: $items1 = [ [1,1], [2,1], [3,2] ]
       $items2 = [ [2,2], [1,3] ]
Output: [ [1,4], [2,3], [3,2] ]

Example 2:
Input: $items1 = [ [1,2], [2,3], [1,3], [3,2] ]
       $items2 = [ [3,1], [1,3] ]
Output: [ [1,8], [2,3], [3,3] ]

Example 3:
Input: $items1 = [ [1,1], [2,2], [3,3] ]
       $items2 = [ [2,3], [2,4] ]
Output: [ [1,1], [2,9], [3,3] ]

View the entire Raku script for this task on GitHub.

Perl

sub mergeItems($items1, $items2) {
  my %merged;
  # loop over the items and add item_quantities (element 1)
  # to the count for each item_id (element 0)
  foreach my $i (@$items1, @$items2) {
    $merged{$i->[0]} += $i->[1];
  }
  # re-render the hash as a 2D array
  return [ map { [ $_, $merged{$_} ] } sort keys %merged ];
}

View the entire Perl script for this task on GitHub.

Python

As always, when I’m counting things in Python, I use the Counter type in the collections module. I also found that the chain function in itertools:

Make an iterator that returns elements from the first iterable until it is exhausted, then proceeds to the next iterable, until all of the iterables are exhausted. Used for treating consecutive sequences as a single sequence. 

def mergeItems(items1, items2):
  merged = Counter()
  # loop over the items and add item_quantities (element 1)
  # to the count for each item_id (element 0)
  for i in chain(items1, items2):
    merged[ i[0] ] += i[1]

  # re-render the hash as a 2D array
  return [ [i, v] for i, v in merged.items() ]

View the entire Python script for this task on GitHub.


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