MuhammadSawalhy · July 30, 2021 10:51 · Jul 30, 2021 · Jul 30, 2021
diff --git a/unique-square--lowest-cost.py b/unique-square--lowest-cost.py
@@ -1,8 +1,5 @@
 #!/bin/python3
 
-# This is a HakerRank misunderstood question, that made it a difficult one not medium.
-# https://www.hackerrank.com/challenges/magic-square-forming/problem
-
 import math
 import os
 import random
@@ -33,7 +30,6 @@ def formingMagicSquare(s):
         for ii in range(i+1, 9):
             if current == s[ii]:
                 nums[current].append(ii)
-                break
 
     # ---------- replacements -------------
 
@@ -155,6 +151,8 @@ def reduce_once():
     for i in range(3):
         s.extend(map(int, sys.argv[i+1].rstrip().split()))
 
-    result = formingMagicSquare(s)
+    total_cost = formingMagicSquare(s)
 
-    print(result)
+    print("-"*15)
+    print("total cost:", total_cost)
+    print("-"*15)
diff --git a/unique-square--lowest-cost.py b/unique-square--lowest-cost.py
@@ -0,0 +1,160 @@
+#!/bin/python3
+
+# This is a HakerRank misunderstood question, that made it a difficult one not medium.
+# https://www.hackerrank.com/challenges/magic-square-forming/problem
+
+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)
+                break
+
+    # ---------- 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()))
+
+    result = formingMagicSquare(s)
+
+    print(result)