#
# Create by Hua on 8/6/22
#

"""
You are given a 0-indexed integer array nums containing distinct numbers, an integer start, and an integer goal. There is an integer x that is initially set to start, and you want to perform operations on x such that it is converted to goal. You can perform the following operation repeatedly on the number x:

If 0 <= x <= 1000, then for any index i in the array (0 <= i < nums.length), you can set x to any of the following:

x + nums[i]
x - nums[i]
x ^ nums[i] (bitwise-XOR)
Note that you can use each nums[i] any number of times in any order. Operations that set x to be out of the range 0 <= x <= 1000 are valid, but no more operations can be done afterward.

Return the minimum number of operations needed to convert x = start into goal, and -1 if it is not possible.



Example 1:

Input: nums = [2,4,12], start = 2, goal = 12
Output: 2
Explanation: We can go from 2 → 14 → 12 with the following 2 operations.
- 2 + 12 = 14
- 14 - 2 = 12
Example 2:

Input: nums = [3,5,7], start = 0, goal = -4
Output: 2
Explanation: We can go from 0 → 3 → -4 with the following 2 operations.
- 0 + 3 = 3
- 3 - 7 = -4
Note that the last operation sets x out of the range 0 <= x <= 1000, which is valid.
Example 3:

Input: nums = [2,8,16], start = 0, goal = 1
Output: -1
Explanation: There is no way to convert 0 into 1.


Constraints:

1 <= nums.length <= 1000
-109 <= nums[i], goal <= 109
0 <= start <= 1000
start != goal
All the integers in nums are distinct.

"""


class Solution(object):
    def minimumOperations(self, nums, start, goal):
        """
        :type nums: List[int]
        :type start: int
        :type goal: int
        :rtype: int

        thought: BFS to try all possibilities, and find the min, if not return -1.
        08/06/2022 11:25	Accepted	1662 ms	13.6 MB	python
        08/06/2022 11:29	Accepted	2033 ms	13.6 MB	python  with simplified code of loops (n+m,n-m,n^m)
        medium
        BFS
        20-30min.
        """

        lt = [start]
        visited = set([start])
        ret = 1
        while lt:
            next_round = set()
            for n in lt:
                for m in nums:
                    for t in (n+m, n-m, n^m):
                        if t == goal:
                            return ret
                        if 0 <= t <= 1000 and t not in visited:
                            next_round.add(t)
                            visited.add(t)

            lt = list(next_round)
            ret += 1
        return -1
