DEV Community

Simon Green
Simon Green

Posted on

Earn with 3 digits

Weekly Challenge 303

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: 3-digits Even

Task

You are given a list (3 or more) of positive integers, @ints.

Write a script to return all even 3-digits integers that can be formed using the integers in the given list.

My solution

Thankfully both Perl and Python have a module that will compute all permutations of three digit integers from a list. I call that function, and remove values that start with a 0 or end in an odd number.

In Python I use a set to record unique integers. As Perl doesn't have sets, I use a hash to achieve the same functionality.

def three_digits_even(ints: list) -> list:
    solution = set()

    for p in permutations(ints, 3):
        if p[-1] % 2 == 1 or p[0] == 0:
            continue

        number = int(''.join(map(str, p)))
        solution.update([number])

    return sorted(solution)
Enter fullscreen mode Exit fullscreen mode

Examples

$ ./ch-1.py 2 1 3 0
[102, 120, 130, 132, 210, 230, 302, 310, 312, 320]

$ ./ch-1.py 2 2 8 8 2
[222, 228, 282, 288, 822, 828, 882]
Enter fullscreen mode Exit fullscreen mode

Task 2: Delete and Earn

Task

You are given an array of integers, @ints.

Write a script to return the maximum number of points you can earn by applying the following operation some number of times.

  • Pick any ints[i] and delete it to earn ints[i] points.
  • Afterwards, you must delete every element equal to ints[i] - 1 and every element equal to ints[i] + 1.

My solution

For this task, I convert the list of integers into a dict of frequencies of each integer. I then call the recursive function score to find the maximum score.

def delete_and_earn(ints: list) -> int:
    freq = Counter(ints)
    return score(freq)
Enter fullscreen mode Exit fullscreen mode

The score function takes the freq dictionary as input. It then iterates through each key (the integer from the original list). Each iteration follows the rules: removes values one less and one more than itself and reduces it's own index by one. If there is something left in the dict, the function is called again with the new freq dict.

I keep tabs of the max_points, and update this as required.

def score(freq: Counter) -> int:
    max_points = None

    for i in freq:
        points = i

        new_freq = freq.copy()
        if i - 1 in new_freq:
            del new_freq[i-1]
        if i + 1 in new_freq:
            del new_freq[i+1]

        new_freq[i] -= 1
        if new_freq[i] == 0:
            del new_freq[i]

        if new_freq:
            points += score(new_freq)

        if max_points is None or max_points < points:
            max_points = points

    return max_points
Enter fullscreen mode Exit fullscreen mode

Examples

$ ./ch-2.py 3 4 2
6

$ ./ch-2.py 2 2 3 3 3 4
9
Enter fullscreen mode Exit fullscreen mode

Top comments (0)