verifying if a move position on an array is valid

Question

Can anyone help me ?

I need to implement a routine that tests an array if it's possible to move a position field please see the figure

the rules are:

1. the type F field can be in any position
2. the field of type X cannot be between the Start and End field
3. and between Start and End, cannot include another start-end

I would like you to give me ideas on how to implement this algorithm. if example code is needed, it can be in any language...

tanks!

Answer 1

The idea is simple. I would create a range array of indices to encode the (Start,End) positions. I assume that input is a valid formation that follows position related rules.

InputArray: [X1, F1, Start, F2, F3, End, F6, X2, Start, F4, End]
Encoding: [(2,5), (8,10)]

Now you can query the above encoding if the move should be allowed or not.

function query(currentPosition, targetPosition, Encoding):

    type = type of InputArray[currentPosition]

    if type == F:
        return True if targetPosition in bounds of InputArray

    if type == X:
        return True if binary search of the targetPosition doesn't overlap with any range in Encoding        
        
        #e.g. if targetPosition is 3 for above Encoding, then it overlaps with range (2,5). 

    if type == Start:
        index = Binary search for currentPosition in Encoding
        return targetPosition <= currentPosition and (index == 0 or targetPosition > Encoding[index-1].second)
        
        #e.g. if query(8, 6, Encoding) returns True
        #    index => 1
        #    Encoding[index-1].second => 5

    if type == End:
        index = Binary search for currentPosition in Encoding
        return targetPosition >= currentPosition and (index == len(Encoding)-1 or targetPosition < Encoding[index+1].first)

        #e.g. if query(5, 6, Encoding) returns True
        #    index => 0
        #    Encoding[index+1].first => 8

    return False

Time Complexity per query: O(log(n)). So, I think this is the most efficient solution.