3x3 2D Array that contains numbers from range(1,10). The goal is to make each number unrepeated, appears only one time, with the lowest total value changes (lowest cost).

unique-square--lowest-cost.py

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'formingMagicSquare' function below.
#
# The function is expected to return an INTEGER.
# The function accepts 2D_INTEGER_ARRAY s as parameter.
#


def formingMagicSquare(s):
    cost = 0
    changes = []

    # ---------- get num of appearences of each num -------------

    nums = {}
    for i in range(9):
        current = s[i]
        skip = nums.get(current)
        if skip:
            continue
        nums[current] = [i]
        for ii in range(i+1, 9):
            if current == s[ii]:
                nums[current].append(ii)

    # ---------- replacements -------------

    class CostsMore(Exception):
        pass

    class NoCost(Exception):
        pass

    def get_change_with_cost(index,
                             freq=None, cost=1, make_sub_changes=True,
                             sub_changes_to_not_changed_nor_new=True):
        """[summary]

        Args:
            index (int): the index
            freq (list, optional): array of indeces that the num appeared at.. Defaults to the value in `nums`
            cost (int, optional): Defaults to 1.
            make_sub_changes (bool, optional): get `next` value from absents only. Defaults to True.
            sub_changes_to_not_changed_nor_new (bool, optional): Defaults to True.

        Raises:
            CostsMore: When it costs more than `cost`

        Returns:
            Change: a change dict {index, current, next, change}
        """
        my_cost = 0
        cur = s[index]  # current
        freq = freq if freq else nums[cur]
        for d in range(1, max([9 - cur, cur - 1])):
            change = d
            replacement = cur + d
            is_present = nums.get(replacement)
            if is_present:
                change = -d
                replacement = cur - d
                is_present = nums.get(replacement)
            if not is_present:
                my_cost = d
                break
        if my_cost == 0:
            return
        if make_sub_changes and my_cost > cost:
            for sub_cost in range(1, cost):
                new_cost = cost - sub_cost
                for i in range(9):
                    is_changed_or_new = len(
                        [*filter(lambda c: c.get("index") == i, changes)]) > 0
                    is_present = nums.get(i)
                    if i in freq or \
                            sub_changes_to_not_changed_nor_new and is_changed_or_new:
                        continue
                    try:
                        ch = get_change_with_cost(i, cost=sub_cost)
                        # ch will go to `ch.next`, I will take its state `ch.current`
                        if not ch: continue
                        proposed_cost = abs(ch.get("current") - cur)
                        if proposed_cost <= new_cost:
                            my_cost = proposed_cost
                            replacement = ch.get("current")
                            change = replacement - cur
                            break
                    except CostsMore:
                        pass

        if my_cost > cost:
            raise CostsMore("`my_cost` can't be <= `cost`")
        return {
            "index": index,
            "current": cur, "next": replacement,
            "change": change, "cost": cost}

    def apply_change(ch):
        print("applying a change:")
        print(ch)
        nonlocal cost
        i = ch.get("index")
        val = ch.get("next")
        cur = ch.get("current")
        ch_cost = ch.get("cost")
        s[i] = val
        nums[val] = [i]
        del nums[cur][0]
        cost += ch_cost

    def reduce_once():
        for num in nums:
            freq = nums[num]  # frequency
            i = freq[0]
            cur = s[i]  # current
            if len(freq) == 1:
                continue
            for c in range(1, 9):
                try:
                    ch = get_change_with_cost(i, freq=freq, cost=c)
                    if not ch: continue
                    changes.append(ch)
                    apply_change(ch)
                    return
                except CostsMore:
                    pass
            raise NoCost("no cost is available")

    done = False # TODO: optimize
    while not done:
        changes_len_before = len(changes)
        reduce_once()
        changes_len_after = len(changes)
        done = changes_len_after == changes_len_before

    return cost


if __name__ == '__main__':

    s = []

    for i in range(3):
        s.extend(map(int, sys.argv[i+1].rstrip().split()))

    total_cost = formingMagicSquare(s)

    print("-"*15)
    print("total cost:", total_cost)
    print("-"*15)

> unique-square \
"1 2 3" \
"5 5 5" \
"6 6 9"

Output

applying a change:
{'index': 3, 'current': 5, 'next': 4, 'change': -1, 'cost': 1}
applying a change:
{'index': 4, 'current': 5, 'next': 7, 'change': 2, 'cost': 2}
applying a change:
{'index': 6, 'current': 6, 'next': 8, 'change': 2, 'cost': 2}
---------------
total cost: 5
---------------

Sub change doesn't make the total cost smaller

This if-statement shouldn't be there

https://gist.github.com/MuhammadSawalhy/e49bda0c6aa36dbac2ee66d39f69f0e2#file-unique-square-lowest-cost-py-L76

Now we can change the repeated num to the nearest absent number, and this should have been an easy question.