Weekly Challenge: The one about arrays

Weekly Challenge 344

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Array Form Compute

Task

You are given an array of integers, @ints and an integer, $x.

Write a script to add $x to the integer in the array-form.

The array form of an integer is a digit-by-digit representation stored as an array, where the most significant digit is at the 0th index.

My solution

The easiest solution would be to turn the ints array into an integer, add the value and then turn it back into an array. However, I don't think this is what this challenge is about.

So it's back to doing things like we did in primary school math classes. For input from the command line, I take the last argument as x and the rest of the arguments as ints (a list in Python, array in Perl).

I start by making sure that ints only contains a single digit and x is a non-negative integer.

def array_form_compute(ints: list[int], x: int) -> list[int]:
    if any(not isinstance(n, int) or n < 0 or n > 9 for n in ints):
        raise ValueError("All elements in the list must be single digit integers (0-9).")

    if x < 0:
        raise ValueError("The integer x must be a non-negative integer.")

The next step is to handle all but the most significant (first) digit. Working backwards (last digit first), I set the pos variable to determine the position of the digit I am working on. I set i to the value of the integer at the position.

I take the x value and split it using the divmod function. The remainder is the remainder of diving x by 10 (i.e. the last digit), and x is now the integer division which is used in the next iteration.

    for pos in range(len(ints) -1, 0, -1):
        i = ints[pos]
        x, remainder = divmod(x, 10)

This is where primary school math comes into play. If i + remainder is more than one digit (i.e. greater than 9), then the last digit of the sum becomes the new i and the other digits are added to the integer before it. In this case, it is added to the x value.

        add_x, add_i = divmod(i + remainder, 10)
        ints[pos] = add_i
        x += add_x

Lastly I need to handle the most significant digit slightly differently. In this case, where ints[0] + x is greater than or equal to 10, I need to split the digits of the new number to a list of individual digits.

    ints[0] += x
    if ints[0] >= 10:
        digits = map(int, str(ints[0]))
        ints = list(digits) + ints[1:]

Finally, I return the new list, or print the array in Perl.

    return ints

The Perl solution follows the same logic. It doesn't have a built in divmod function, so I created one.

sub divmod($a, $b) {
    my $div = int($a / $b);
    my $mod = $a % $b;
    return ($div, $mod);
}

Examples

$ ./ch-1.py 1 2 3 4 12
[1, 2, 4, 6]

$ ./ch-1.py 2 7 4 181
[4, 5, 5]

$ ./ch-1.py 9 9 9 1
[1, 0, 0, 0]

$ ./ch-1.py 1 0 0 0 0 9999
[1, 9, 9, 9, 9]

$ ./ch-1.py 0 1000
[1, 0, 0, 0]

Task 2: Array Formation

Task

You are given two list: @source and @target.

Write a script to see if you can build the exact @target by putting these smaller lists from @source together in some order. You cannot break apart or change the order inside any of the smaller lists in @source.

My solution

For input from the command line, I take a JSON string from the first argument and convert that to the source variable. The remaining arguments make up the target value.

This is one challenge that is a lot easier to complete in Python than in Perl. I explain the Python solution.

I start by seeing if a solution is indeed possible. This is done by counting the frequency of all digits in both the source and target lists and seeing if they are the same. If they are not the same, I return False.

def array_formation(source: list[list[int]], target: list[int]) -> bool:
    # Check that a solution is possible
    if Counter(chain.from_iterable(source)) != Counter(target):
        return False

There are a few inbuilt features in the above.

• itertools.chain.from_iterable is a function that will flatten a list of lists in to a single list.
• collections.Counter will turn an iterable (in this case a list) and turn it into a dictionary with the value as the key and the frequency as the value.
• In Python, comparing two dictionaries for equality will compare to see if the key and value are the same. The order of the keys does not matter.

From here, there are two possible approaches to take. One would be to call a recursive function to try all valid starting numbers recursively until we found the one that works. Given the examples (where there is only a few lists in the source value), this seems like an unneeded optimization.

So I took the brute force approach and compute all permutations of the source list. If I find the right one, I return True. If I exhaust all permutations, I return False.

Python has the permutations function from the itertools module. In Perl, the Algorithm::Combinatorics function does the same.

    for perm in permutations(source):
        combined = list(chain.from_iterable(perm))
        if combined == target:
            return True

    return False

The Perl solution follows the same logic. It does not have an inbuilt way to flatten so I wrote my own.

sub flatten_array($list) {
    return map { @$_ } @$list;
}

It also cannot compare an array for equality, so I faked it by joining the lists with spaces and then tested if the two strings are equal.

sub compare_array ( $list1, $list2 ) {
    return join( ' ', @$list1 ) eq join( ' ', @$list2 );
}

To check that a solution is possible, I numerically sort the source and target values to check if they are equal.

sub array_formation( $source, $target ) {
    if (
        not compare_array(
            [ sort { $a <=> $b } flatten_array($source) ],
            [ sort { $a <=> $b } @$target ]
        )
      )
    {
        return 'false';
    }

    my $iter = permutations($source);
    while ( my $perm = $iter->next ) {
        if ( compare_array( [ flatten_array($perm) ], $target ) ) {
            return 'true';
        }
    }

    return 'false';
}

Examples

$ ./ch-2.py "[[2,3], [1], [4]]" 1 2 3 4
True

$ ./ch-2.py "[[1,3], [2,4]]" 1 2 3 4
False

$ ./ch-2.py "[[9,1], [5,8], [2]]" 5 8 2 9 1
True

$ ./ch-2.py "[[1], [3]]" 1 2 3
False

$ ./ch-2.py "[[7,4,6]]" 7 4 6
True