How to get first 1's index and last 1's index in a or-tools 1-D bool array? (or-tools)

user_13863269 0
Viewed 140

I want to find out a first 1's index and last 1's index in a or-tools 1-D bool array , it look like this: if the array=[0,0,1,0,1,0,1,0] , I wish to get first_one_index = 2 and last_one_index=6,what should I do？

from ortools.sat.python import cp_model
model = cp_model.CpModel()
solver = cp_model.CpSolver()


work={}

for i in range(8):
    work[i]=model.NewBoolVar("work(%i)" % (i))

model.Add(work[0]==0)
model.Add(work[1]==0)
model.Add(work[2]==1)
model.Add(work[3]==0)
model.Add(work[4]==1)
model.Add(work[5]==0)
model.Add(work[6]==1)
model.Add(work[7]==0)


first_one_index = model.NewIntVar(0, 7, "")
las_one_index = model.NewIntVar(0, 7, "")

    
# how to find first 1 and last 1 index   

#####################################

status = solver.Solve(model)
print("status:",status)  

print("first_one_index:",solver.Value(first_one_index))
print("las_one_index:",solver.Value(las_one_index))
or-tools python
1 Answers

Adapted from Laurent's answer here

for each day d, create two variables v1[d] = d * working_var[d], and v2[d] = horizon + working_var * (d - horizon). Then model.AddMinEquality(first_day_worked, v2), model.AddMaxEquality(last_day_worked, v1)

from ortools.sat.python import cp_model

if __name__ == "__main__":
    model = cp_model.CpModel()
    solver = cp_model.CpSolver()

    work = {}
    days = 8
    horizon = 7
    for i in range(days):
        work[i] = model.NewBoolVar("work(%i)" % (i))

    model.Add(work[0] == 0)
    model.Add(work[1] == 0)
    model.Add(work[2] == 1)
    model.Add(work[3] == 0)
    model.Add(work[4] == 1)
    model.Add(work[5] == 0)
    model.Add(work[6] == 1)
    model.Add(work[7] == 0)

    first_one_index = model.NewIntVar(0, 7, "")
    las_one_index = model.NewIntVar(0, 7, "")

    v1 = [model.NewIntVar(0, horizon, "") for _ in range(days)]
    v2 = [model.NewIntVar(0, horizon, "") for _ in range(days)]
    for d in range(days):
        model.Add(v1[d] == d * work[d])
        model.Add(v2[d] == horizon + work[d] * (d - horizon))
    model.AddMinEquality(first_one_index, v2)
    model.AddMaxEquality(las_one_index, v1)

    status = solver.Solve(model)
    print("status:", status)

    print("first_one_index:", solver.Value(first_one_index))
    print("las_one_index:", solver.Value(las_one_index))
user_78107770
Related