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
👋 While you are here

Reinvent your career. Join DEV.

It takes one minute and is worth it for your career.

Get started

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay