Find all possible routes from City1 to various other cities.
📌 Challenge Details and Links
ExcelBI Power Query Challenge Number: 269
Challenge Difficulty: ⭐️⭐️⭐️⭐️
📥Download Sample File
📥Link to the solutions on LinkedIn
Solving the challenge of Find all possible routes from with Power Query
Power Query solution 1 for Find all possible routes from, proposed by Luan Rodrigues:
let
Fonte = Table.SelectRows(Tabela1, each Number.From(Text.Select([From City],{"0".."9"})) < Number.From(Text.Select([To City],{"0".."9"})) ),
tab = hashtag#table({"Chave", "Valor"}, {}),
res = List.Accumulate(
Table.ToRows(Fonte),tab, (s,c)=>
let
chave = c{1},
valor = try Table.SelectRows(s, each [Chave] = c{0})[Valor]{0} otherwise c{0},
novoValor = Text.Combine({valor,c{1}},"-"),
tabela = hashtag#table({"Chave","Valor"},{{chave,novoValor}}),
conc = Table.Combine({s,tabela})
in
conc )
in
res
Power Query solution 2 for Find all possible routes from, proposed by Eric Laforce:
let
Source = Excel.CurrentWorkbook(){[Name="tData269"]}[Content],
Acc = List.Accumulate(List.Distinct(Source[From City]), {}, (s,c)=>let
_NewFromTo = Table.SelectRows(Source, each ([From City]=c))
in if List.IsEmpty(s)
then List.Transform(Table.ToRows(_NewFromTo), each Text.Combine(_,"->"))
else List.Combine(
List.Transform(s, (t)=>let
_ToAdd = if (List.Last(Text.Split(t, "->"))<>c) then {}
else List.Accumulate(_NewFromTo[To City], {}, (s,c)=>s & (if Text.Contains(t,c) then {} else {t&"->"&c}))
in {t} & _ToAdd
))
),
Result = Table.FromColumns({Acc}, {"Result"})
in
Result
NB : sort order also not being exactly the same as expected.
Power Query solution 3 for Find all possible routes from, proposed by Seokho MOON:
let
Source = Excel.CurrentWorkbook(){[Name = "Table1"]}[Content],
Rec = List.Accumulate(
List.Select(
Table.ToRows(Source),
each Number.From(Text.Range(_{0}, 4)) < Number.From(Text.Range(_{1}, 4))
),
[],
(a, v) =>
[
A = if Record.HasFields(a, v{1}) then v{0} & v{1} else v{1},
B = Record.FieldOrDefault(a, v{0}, v{0}) & "-" & v{1},
C = Record.AddField(a, A, B)
][C]
),
Res = Table.FromList(Record.ToList(Rec), each {_}, {"Result"})
in
ResSolving the challenge of Find all possible routes from with Excel
Excel solution 1 for Find all possible routes from, proposed by Bo Rydobon 🇹🇭:
=DROP(
REDUCE(
A2,
B2:B15,
LAMBDA(
a,
v,
UNIQUE(
VSTACK(
a,
a&REPT(
"-"&v,
REGEXTEST(
a,
@+v:A15&"$"
)*NOT(
REGEXTEST(
a,
v
)
)
)
)
)
)
),
1
)Excel solution 2 for Find all possible routes from, proposed by Kris Jaganah:
=LET(a,
A2:A15&"-"&B2:B15,
b,
"City1",
c,
SCAN(
b,
SEQUENCE(
6
),
LAMBDA(
x,
y,
TEXTJOIN(
"#",
1,
MAP(
TEXTSPLIT(
x,
,
"#",
1
),
LAMBDA(
z,
TEXTJOIN(
"#",
,
IFERROR(
z&"-"&TEXTAFTER(
FILTER(
a,
TEXTBEFORE(
a,
"-"
)=TEXTAFTER(
z,
"-",
-1,
,
,
z
)
),
"-"
),
""
)
)
)
)
)
)
),
d,
TEXTSPLIT(
CONCAT(
c&"#"
),
,
"#",
1
),
FILTER(d,
MAP(
d,
LAMBDA(
u,
ROWS(
UNIQUE(
TEXTSPLIT(
u,
,
"-"
)
)
)
)
)=(LEN(
d
)-LEN(
SUBSTITUTE(
d,
"-",
""
)
)+1)))Excel solution 3 for Find all possible routes from, proposed by Pieter de B.:
=LET(L,
LAMBDA(x,
x&FILTER("-"&B2:B15,
(A2:A15=TEXTAFTER(
"-"&x,
"-",
-1
))*ISNA(
XMATCH(
"*"&B2:B15&"-*",
x,
2
)
),
"")),
REDUCE(
L(
A2
),
A3:A15,
LAMBDA(
a,
_,
UNIQUE(
VSTACK(
a,
REDUCE(
a,
a,
LAMBDA(
b,
c,
VSTACK(
b,
L(
c
)
)
)
)
)
)
)
))Solving the challenge of Find all possible routes from with Python
Python solution 1 for Find all possible routes from, proposed by Konrad Gryczan, PhD:
import pandas as pd
path = "PQ_Challenge_269.xlsx"
input = pd.read_excel(path, usecols="A:B", nrows=15)
test = pd.read_excel(path, usecols="D", nrows=12).sort_values(by="Result").reset_index(drop=True)
G = nx.from_pandas_edgelist(input, source='From City', target='To City', create_using=nx.DiGraph())
all_paths = ['-'.join(path) for target in G.nodes if target != 'City1' for path in nx.all_simple_paths(G, source='City1', target=target)]
df_paths = pd.DataFrame(all_paths, columns=['Path']).sort_values(by='Path').reset_index(drop=True)
print(df_paths['Path'].equals(test['Result'])) # True
Python solution 2 for Find all possible routes from, proposed by Luan Rodrigues:
import pandas as pd
from functools import reduce
file = r"PQ_Challenge_269.xlsx"
df = pd.read_excel(file,usecols="A:B")
df = df[
df['From City'].str.replace(r'[^0-9]','',regex=True ).astype('int') <
df['To City'].str.replace(r'[^0-9]','',regex=True ).astype('int')
]
lista = df.to_dict(orient="records")
tab = pd.DataFrame([],columns=['Chave','Valor'])
def acumular(s, c):
chave = c['To City']
valor = s.loc[s['Chave'] == c['From City'], 'Valor'].values[0] if not s.loc[s['Chave'] == c['From City']].empty else c['From City']
novo_valor = f"{valor}-{c['To City']}"
nova_linha = pd.DataFrame({'Chave': [chave], 'Valor': [novo_valor]})
return pd.concat([s, nova_linha], ignore_index=True)
resultado = reduce(acumular, lista, tab)
print(resultado)
Solving the challenge of Find all possible routes from with Python in Excel
Python in Excel solution 1 for Find all possible routes from, proposed by Alejandro Campos:
df = xl("A1:B15", headers=True)
graph = df.groupby("From City")["To City"].apply(list).to_dict()
def find_routes(g, start):
r, d = [], lambda c, p: (r.append("-".join(p+[c])) if p else None) or
[d(n, p+[c]) for n in g.get(c, []) if n not in p]
d(start, [])
return pd.DataFrame(r, columns=["Route"])
find_routes(graph, "City1")
Python in Excel solution 2 for Find all possible routes from, proposed by Aditya Kumar Darak 🇮🇳:
df = xl("A1:B15", True)
G = nx.DiGraph()
for fc, tc in zip(df["From City"], df["To City"]):
G.add_edge(fc, tc)
result = []
for t in G.nodes:
if t != "City1":
for p in nx.all_simple_paths(G, source="City1", target=t):
result.append("-".join(p))
result = pd.DataFrame({"Result": result})
Solving the challenge of Find all possible routes from with R
R solution 1 for Find all possible routes from, proposed by Konrad Gryczan, PhD:
library(tidyverse)
library(readxl)
library(igraph)
path = "Power Query/PQ_Challenge_269.xlsx"
input = read_excel(path, range = "A1:B15")
test = read_excel(path, range = "D1:D13") %>% arrange(Result)
g = graph_from_data_frame(input, directed = TRUE)
all_paths = all_simple_paths(g, from = "City1", to = V(g))
all_paths_df = map_df(all_paths, ~{
path = .x
path_str = paste(V(g)[path]$name, collapse = "-")
data.frame(path = path_str)
}) %>%
arrange(path)
all.equal(all_paths_df$path, test$Result) # TRUE
&&&