পাইথনে মুদ্রা আربیট্রেজ বা সুযোগ যাচাই

একটি N×N মুদ্রা বিনিময় দরের টেবিল দেওয়া আছে। যাচাই করতে হবে কিছু লেনদেন সিকোয়েন্স দিয়ে আربیট্রেজ (সুবিধা) সম্ভব কিনা। অর্থাৎ কিছু মুদ্রা থেকে শুরু করে ফিরে আসলে বেশি পরিমাণ পাওয়া যায় কিনা।

উদাহরণ ম্যাট্রিক্স: 1, 1.28, 0.82 0.78, 1, 0.65 1.21, 1.55, 1 আউটপুট True।

সমাধানের ধাপসমূহ

• ম্যাট্রিক্সের প্রতিটি উপাদানকে -log2(value) এ রূপান্তর করুন
• ফ্লয়েড-ওয়ার্শ্যাল অ্যালগরিদম চালিয়ে সব জোড়ার ন্যূনতম পথ বের করুন
• যদি কোনো ডায়াগোনাল উপাদান নেগেটিভ হয় তবে আربیট্রেজ আছে, True ফেরত দিন

উদাহরণ কোড

import math
class Solution:
    def solve(self, matrix):
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                matrix[i][j] = -math.log(matrix[i][j], 2)
        v = len(matrix)
        for k in range(v):
            for i in range(v):
                for j in range(v):
                    matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
        return any(matrix[i][i] < 0 for i in range(len(matrix)))

ob = Solution()
matrix = [
    [1, 1.28, 0.82],
    [0.78, 1, 0.65],
    [1.21, 1.55, 1]
]
print(ob.solve(matrix))

ইনপুট

matrix = [[1, 1.28, 0.82], [0.78, 1, 0.65], [1.21, 1.55, 1]]

আউটপুট

True