In the continuation of the previous challenge, we reach the question table as the normalized table, in the rest of the algorithm the below step should be done. Step 3: Cover all zeros in the matrix (question table) using a minimum number of horizontal and vertical lines. Step 4: Test for Optimality: If the minimum number of covering lines is 4, we reach the result and go to step 6, else go to step 5. Step 5: Determine the smallest entry not covered by any line (shown by green). Subtract this entry from each uncovered value (shown by yellow and green), and then add it to the intersection of lines (shown by blue). Return to step 3. Step 6. Select the 0 in the matrix with one zero selected in each row and column. the results of the steps are provided above.
📌 Challenge Details and Links
Challenge Number: 50
Challenge Difficulty: ⭐⭐⭐⭐⭐
📥Download Sample File
📥Link to the solutions on LinkedIn
Solving the challenge of Assignment Problem (Part 2)! with Power Query
Power Query solution 1 for Assignment Problem (Part 2)!, proposed by Omid Motamedisedeh:
let
Source = Excel.CurrentWorkbook(){[Name="Table1"]}[Content],
Cost = Table.RemoveColumns(Source,{"Column1"}),
n=Table.RowCount(Source),
S = List.Repeat({0},n),
X = List.Transform(List.Positions(S),each List.ReplaceRange(S,_,1,{1})),
T = Table.FromColumns(List.Repeat({{X}},n)),
N=Table.ColumnNames(T),
AllCombination = List.Accumulate(N,T, (x,y)=>Table.ExpandListColumn(x, y)),
Merged_C = Table.CombineColumns(AllCombination,N,each _,"M"),
Feasibility = Table.AddColumn(Merged_C, "Non_Feasibility", each List.Contains(List.Transform(List.Zip([M]),List.Sum),0)),
Filtered = Table.SelectRows(Feasibility, each ([Non_Feasibility] = false)),
Convert = Table.TransformColumns(Filtered,{"M", each List.Transform(_,(x)=>List.PositionOf(x,1))}),
Cost_Calculation = Table.AddColumn(Convert, "Cost", each List.Sum(List.Transform(List.Positions([M]), (x)=>Table.Column(Cost,Table.ColumnNames(Cost){x}){[M]{x}}))),
Power Query solution 2 for Assignment Problem (Part 2)!, proposed by Omid Motamedisedeh:
let
Source = Excel.CurrentWorkbook(){[Name = "Table1"]}[Content],
Cost = Table.RemoveColumns(Source, {"Column1"}),
n = Table.RowCount(Source),
T = Table.FromColumns(List.Repeat({{{0 .. n - 1}}}, n)),
N = Table.ColumnNames(T),
Comb = List.Accumulate(N, T, (x, y) => Table.ExpandListColumn(x, y)),
Filtered = Table.SelectRows(Table.CombineColumns(Comb, N, each _, "M"), each List.IsDistinct([M])),
Cost_Calculation = Table.AddColumn(
Filtered,
"Cost",
each List.Sum(
List.Transform(
List.Positions([M]),
(x) => Table.Column(Cost, Table.ColumnNames(Cost){x}){[M]{x}}
)
)
),
Filtered_Rows = Table.SelectRows(
Cost_Calculation,
each ([Cost] = List.Min(Cost_Calculation[Cost]))
),
M = Table.FromColumns(
{Source[Column1]}
& List.Transform(Filtered_Rows{0}[M], each List.InsertRange(List.Repeat({0}, n - 1), _, {1})),
Table.ColumnNames(Source)
)
in
MSolving the challenge of Assignment Problem (Part 2)! with Excel
Excel solution 1 for Assignment Problem (Part 2)!, proposed by Bo Rydobon 🇹🇭:
=LET(L,LAMBDA(L,c,LET(n,ROWS(c),s,SEQUENCE(n),
z,N(c=0),lin,MAKEARRAY(n,n,LAMBDA(r,c,IF(INDEX(z,r,c),SIGN(SUM(INDEX(z,r,))-SUM(INDEX(z,,c)))))),
y,BYROW(lin,LAMBDA(x,OR(x={0;1})))+(BYCOL(lin,MIN)<0),d,IF(y,c,c-MIN(IF(y-1,c))),
IF(AND(c=d),
{"Taks","Person"}&SORT(DROP(REDUCE({0,0},s,LAMBDA(a,w,
LET(ar,ISNUMBER(XMATCH(s,DROP(a,,1))),
e,d+ar+ISNUMBER(XMATCH(TOROW(s),TAKE(a,,1))),
p,IFNA(XMATCH(1,BYROW(N(e=0),SUM),1),XMATCH(FALSE,ar)),tk,XMATCH(0,INDEX(e,p,),1),VSTACK(a,HSTACK(tk,p))))),1)),L(L,d)))),
L(L,C3:F6))Excel solution 2 for Assignment Problem (Part 2)!, proposed by Bo Rydobon 🇹🇭:
=LET(
z,
C3:F6,
s,
SEQUENCE(
ROWS(
z
)
),
m,
MID(
REDUCE(
,
s,
LAMBDA(
a,
v,
TOROW(
REPLACE(
a,
SEQUENCE(
v
),
,
v
)
)
)
),
s,
1
), HSTACK(
TOCOL(
C2:F2
),
INDEX(
B3:B6,
XLOOKUP(
0,
BYCOL(
INDEX(
z,
m,
s
),
SUM
),
m,
,
1
)
)
)
)Excel solution 4 for Assignment Problem (Part 2)!, proposed by Kris Jaganah:
=LET(a,
B3:B6,
b,
C2:F2,
c,
C3:F6,
d,
IF(
c=MIN(
c
),
1,
0
),
e,
SEQUENCE(
,
COLUMNS(
d
)
),
f,
BYCOL(
d,
MAX
)*e,
g,
IFERROR(
CHOOSECOLS(
c,
FILTER(
f,
f
)
),
0
),
h,
MIN(
FILTER(
c,
f=0,
0
)
),
i,
IF(IFNA((g<>c),
TRUE)=TRUE,
c-h,
c),
j,
BYROW(
i,
MIN
),
k,
TEXTSPLIT(
ARRAYTOTEXT(
TOCOL(
a&"-"&b&"-"&i&"-"&j
)
),
"-",
", "
),
l,
FILTER(
TAKE(
k,
,
2
),
CHOOSECOLS(
k,
3
)=TAKE(
k,
,
-1
)
),
m,
TAKE(
l,
,
-1
),
n,
MAP(m,
LAMBDA(x,
SUM(--(m=x)))),
REDUCE(
{"Tasks",
"Person"},
SORT(
UNIQUE(
m
)
),
LAMBDA(
v,
w,
VSTACK(
v,
LET(
r,
FILTER(
HSTACK(
TAKE(
l,
,
1
),
n
),
m=w
),
HSTACK(
w,
CHOOSEROWS(
TAKE(
r,
,
1
),
TAKE(
r,
-1,
-1
)
)
)
)
)
)
))Excel solution 5 for Assignment Problem (Part 2)!, proposed by John Jairo Vergara Domínguez:
=LET(
s,
SEQUENCE(
,
ROWS(
C3:F6
)
),
p,
MID(
REDUCE(
"",
s,
LAMBDA(
a,
v,
TOCOL(
IFS(
ISERR(
FIND(
s,
a
)
),
a&s
),
2
)
)
),
s,
1
),
i,
BYROW(
INDEX(
C3:F6,
p,
s
),
SUM
),
TRANSPOSE(
VSTACK(
C2:F2,
INDEX(
B3:B6,
FILTER(
p,
i=MIN(
i
)
)
)
)
)
)Excel solution 6 for Assignment Problem (Part 2)!, proposed by Diarmuid Early:
=LET(combs,
1-MID(
BASE(
SEQUENCE(
2^8,
,
0
),
2,
8
),
SEQUENCE(
,
8
),
1
), combsSrt,
SORTBY(
combs,
BYROW(
combs,
SUM
)
), uncan,
LAMBDA(
rng,
comb,
SUM(
N(
rng+TAKE(
comb,
,
4
)+TOCOL(
TAKE(
comb,
,
-4
)
)=0
)
)
), step6,
REDUCE(
C3:F6,
SEQUENCE(
3
),
LAMBDA(
arr,
itNum,
LET(
uncancelled,
BYROW(
combsSrt,
LAMBDA(
rw,
uncan(
arr,
rw
)
)
),
cancels,
XLOOKUP(
0,
uncancelled,
combsSrt
),
mask,
TAKE(
cancels,
,
4
)+TOCOL(
TAKE(
cancels,
,
-4
)
)=0,
IF(
SUM(
cancels
)=4,
arr,
arr-IF(
mask,
MIN(
IF(
mask,
arr,
""
)
)
)
)
)
)
), step7,
REDUCE(EXPAND(
step6,
,
5,
""
),
SEQUENCE(
4
),
LAMBDA(arr,
itNum, LET(mainArr,
TAKE(
arr,
,
4
),
rwDrops,
TAKE(
arr,
,
-1
), HSTACK(mainArr,
IF(rwDrops<>"",
rwDrops,
TOCOL(BYCOL(IF(
ISNUMBER(
XMATCH(
{1;2;3;4},
rwDrops
)
),
1,
mainArr
),
LAMBDA(cl,
IF(SUM(--(cl=0))=1,
XMATCH(
0,
cl
),
""))))))))), HSTACK(
"Task "&SEQUENCE(
4
),
"Person "&TAKE(
step7,
,
-1
)
))Excel solution 7 for Assignment Problem (Part 2)!, proposed by LEONARD OCHEA 🇷🇴:
=LET(
d,
C3:F6,
h,
C2:F2,
v,
B3:B6,
s,
SEQUENCE(
ROWS(
d
)
),
r,
REDUCE(
1,
DROP(
s,
1
),
LAMBDA(
x,
y,
LET(
p,
FACT(
y-1
),
m,
HSTACK(
SEQUENCE(
p
)^0,
x+1
),
REDUCE(
m,
SEQUENCE(
y-1
),
LAMBDA(
a,
b,
LET(
c,
TAKE(
a,
-p
),
VSTACK(
TAKE(
a,
-p*b
),
IF(
c=b,
b+1,
IF(
c=b+1,
b,
c
)
)
)
)
)
)
)
)
),
t,
MMULT(
INDEX(
d,
r,
TOROW(
s
)
),
s^0
),
TRANSPOSE(
VSTACK(
h,
INDEX(
v,
FILTER(
r,
t=MIN(
t
)
)
)
)
)
)Excel solution 8 for Assignment Problem (Part 2)!, proposed by Rayan Saud:
=LET( tn,
B2:E2, pn,
A3:A6, max,
MAX(
COUNTA(
tn
)
), seq,
SEQUENCE(
REPT(
max,
max
),
,
REPT(
1,
max
)
), f,
FILTER(
seq,
MAP(
seq,
LAMBDA(
x,
LET(
s,
MID(
x,
SEQUENCE(
LEN(
x
)
),
1
) + 0,
COUNTA(
UNIQUE(
FILTER(
s,
s > 0
)
)
) = LEN(
x
)
)
)
)
), c,
CONCAT(
f
), Comb,
MID(
c,
SEQUENCE(
LEN(
c
)
),
1
), Plist,
INDEX(
pn,
ROUNDUP(
SEQUENCE(
max * max
) / max,
0
)
), Tlist,
TOCOL(
IFNA(
EXPAND(
tn,
max
),
tn
)
), Nlist,
TOCOL(
B3:E6
), p,
INDEX(
pn,
Comb
), t,
TOCOL(
IFNA(
EXPAND(
tn,
COUNTA(
Comb
) / max
),
tn
)
), Cost,
IFERROR( BYCOL(
WRAPCOLS(
XLOOKUP(
p & t,
Plist & Tlist,
Nlist,
0,
0
),
max
),
SUM
),
"/"
), m,
MATCH(
MIN(
Cost
),
Cost,
0
), HSTACK(
CHOOSECOLS(
WRAPCOLS(
t,
max
),
m
),
CHOOSECOLS(
WRAPCOLS(
p,
max
),
m
)
))Excel solution 9 for Assignment Problem (Part 2)!, proposed by Rayan Saud:
=LET(
Comb,
{1,
2,
3,
4,
1,
2,
4,
3,
1,
3,
2,
4,
1,
3,
4,
2,
1,
4,
2,
3,
1,
4,
3,
2,
2,
1,
3,
4,
2,
1,
4,
3,
2,
3,
1,
4,
2,
3,
4,
1,
2,
4,
1,
3,
2,
4,
3,
1,
3,
1,
2,
4,
3,
1,
4,
2,
3,
2,
1,
4,
3,
2,
4,
1,
3,
4,
1,
2,
3,
4,
2,
1,
4,
1,
2,
3,
4,
1,
3,
2,
4,
2,
1,
3,
4,
2,
3,
1,
4,
3,
1,
2,
4,
3,
2,
1}, Plist,
INDEX(
A3:A6,
ROUNDUP(
SEQUENCE(
16
) / 4,
0
)
), Tlist,
TOCOL(
IFNA(
EXPAND(
B2:E2,
4
),
B2:E2
)
),
Nlist,
TOCOL(
B3:E6
), p,
TRANSPOSE(
INDEX(
A3:A6,
Comb
)
), t,
TOCOL(
IFNA(
EXPAND(
B2:E2,
COUNTA(
Comb
) / 4
),
B2:E2
)
), Cost,
BYCOL(
WRAPCOLS(
XLOOKUP(
p & t,
Plist & Tlist,
Nlist,
0,
0
),
4
),
SUM
),
m,
MATCH(
MIN(
Cost
),
Cost,
0
), HSTACK(
CHOOSECOLS(
WRAPCOLS(
t,
4
),
m
),
CHOOSECOLS(
WRAPCOLS(
p,
4
),
m
)
)
)Solving the challenge of Assignment Problem (Part 2)! with Python
Python solution 1 for Assignment Problem (Part 2)!, proposed by Rayan Saud:
import pandas as pd
df = pd.read_csv(r'c:\Excel\CH-050.csv')
# Load algorithm
from scipy.optimize import linear_sum_assignment
# Data Cleaning
df.dropna(inplace=True)
cost_matrix = df.iloc[:, 1:]
df.iloc[:, 1:] = None
# Apply the algorithm
row_ind, col_ind = linear_sum_assignment(cost_matrix)
for agent, task in zip(row_ind, col_ind):
task_name = cost_matrix.columns[task]
df.at[df.index[agent], task_name] = task_name
unpivot = pd.melt(df, id_vars=['Unnamed: 0'], value_name='Value')
Drop = unpivot.drop('variable', axis=1)
df = Drop.dropna(subset=['Value'])Solving the challenge of Assignment Problem (Part 2)! with R
R solution 1 for Assignment Problem (Part 2)!, proposed by Konrad Gryczan, PhD:
library(clue)
M = matrix(c(13, 4, 7, 6, 1, 11, 5, 4, 6, 7, 2, 8, 1, 3, 5, 9), nrow=4, byrow=TRUE)
result = solve_LSAP(M)
result
Optimal assignment:
1 => 2, 2 => 4, 3 => 3, 4 => 1
# it is Task => Person