Sorting by threes
Tags: perl, python, theweeklychallenge
Published: 2023-12-03 10:56:35

## Weekly Challenge 245

Each week Mohammad S. Anwar sends out [The Weekly Challenge](https://theweeklychallenge.org/), 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](https://theweeklychallenge.org/blog/perl-weekly-challenge-245/), [My solutions](https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-245/sgreen)

## 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)

```python
    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.

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

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

```python
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

```bash
$ ./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.
1. With the previous point, it stand to reason that the all permutations of the digits is also devisable by three.
1. While the examples all used single digit numbers, it is perfectly valid for some digits to be greater than nine.
1. 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

```python
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.

```python
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

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

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

$ ./ch-2.py 1
-1
```