Sorting by threes

Weekly Challenge 245

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: Sort Language

Task

You are given two array of languages and its popularity.

Write a script to sort the language based on popularity.

My solution

This task is relatively straight forward. Split the input into two lists (arrays in Perl)

    half = len(inputs) // 2
    words = inputs[:half]
    # Convert input into integers
    places = [int(n) for n in inputs[half:]]

Then create a dict (hash in Perl) where the key is the popularity, and the value is the word.

rankings = { place: word for place, word in zip(places, words)}

And finally sort the dict by the popularity score, returning the language.

solution = [rankings[place] for place in sorted(rankings)]

Both solutions make use of the zip function. This is built-in in Python, and part of List::Util in Perl. Given two or more iterables, it will return a tuple of each pairing.

Examples

$ ./ch-1.py perl c python 2 1 3
c, perl, python

$ ./ch-1.py c++ haskell java 1 3 2
c++, java, haskell

Task 2: Largest of Three

Task

You are given an array of integers >= 0.

Write a script to return the largest number formed by concatenating some of the given integers in any order which is also multiple of 3. Return -1 if none found.

My solution

This solution is ugly and inefficient, but it works! (I hope)

Let's start with some number theory.

1. If the sum of the digits is devisable by 3, then the number is devisable by three. Looking at the first example 8 + 1 + 9 is 18, and that is devisable by three.
2. With the previous point, it stand to reason that the all permutations of the digits is also devisable by three.
3. While the examples all used single digit numbers, it is perfectly valid for some digits to be greater than nine.
4. If this was a real world exercise, I would put more effort into finding the largest number based on the digits. If we take, 60 and 3, the largest number is 603 (largest first). However with 60 and 9, the largest number is 960 (smallest first).

There are two main parts to my solution. The second part is to get the largest number for a given set of numbers. For this I work through all permutations to find this

def largest_number(numbers):
    largest = 0
    for i in permutations(map(lambda x: str(x), numbers)):
        n = int(''.join(i))
        if n > largest:
            largest = n

    return largest

The first part is to use a bit wise operator to work through all combinations of integers. Think of this as choosing or dropping an integer. Once I have selected the digits, I check the sum is divisible by three. If it is, I call the above function to get the largest number.

for bitwise in range(1, 2 ** len(ints)):
    numbers = [n for i, n in enumerate(ints) if bitwise & (2 ** i)]
    if sum(numbers) % 3 != 0:
        continue

Examples

$ ./ch-2.py 8 1 9
981

$ ./ch-2.py 8 6 7 1 0
8760

$ ./ch-2.py 1
-1