Part One
各个阀门之间互通，设计最佳的流动路线，从而让流通的压力值最大。
Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Valve BB has flow rate=13; tunnels lead to valves CC, AA
…………
最短距离
为了尽量减少到达下一个阀门浪费的时间，需要计算两个阀门之间的最短距离。
WITH recursive origin AS (
SELECT substring(line, 7, 2) as valve,
substring(line, strpos(line, 'rate=') + 5, strpos(line, ';') - strpos(line, 'rate=') - 5) :: bigint as rate,
string_to_table(substring(substring(line, strpos(line, 'valve')), strpos(substring(line, strpos(line, 'valve')), ' ') + 1), ', ') as target
FROM lance_input
), valve_dist AS (
SELECT valve as _start, target as _end, '{}'::varchar[] || valve || target as path
FROM origin
WHERE rate > 0 OR valve = 'AA'
UNION ALL
SELECT x._start, y.target as _end, path || y.target
FROM valve_dist x
JOIN origin y
ON x._end = y.valve
WHERE NOT y.target = ANY(path)
)
SELECT *
FROM valve_dist
ORDER BY 1, 2
_start | _end | path
--------+------+---------------------------------
AA | BB | {AA,BB}
AA | BB | {AA,DD,CC,BB}
AA | CC | {AA,DD,CC}
AA | CC | {AA,BB,CC}
AA | DD | {AA,DD}
AA | DD | {AA,BB,CC,DD}
AA | EE | {AA,DD,EE}
AA | EE | {AA,BB,CC,DD,EE}
AA | FF | {AA,DD,EE,FF}
AA | FF | {AA,BB,CC,DD,EE,FF}
AA | GG | {AA,BB,CC,DD,EE,FF,GG}
仅保留两点之间的最短路径，而且终点需要是rate>0的valve
SELECT _start, _end, distance
FROM (
SELECT _start, _end, array_length(path, 1) - 1 as distance,
row_number() over (partition by _start, _end order by array_length(path, 1)) as rn
FROM valve_dist
) t
WHERE rn = 1
AND _end in (select valve from origin where rate > 0)
_start | _end | distance
--------+------+----------
AA | BB | 1
AA | CC | 2
AA | DD | 1
AA | EE | 2
AA | HH | 5
AA | JJ | 2
最佳顺序
不同的开启顺序，最终的总体压力值也会不同。总体思路肯定是优先开启流速大的valve，但是距离过长也会导致时间的浪费，因此还是穷举所有的可能路径，从而找出最大的压力值。
WITH recursive origin AS (
SELECT substring(line, 7, 2) as valve,
substring(line, strpos(line, 'rate=') + 5, strpos(line, ';') - strpos(line, 'rate=') - 5) :: bigint as rate,
string_to_table(substring(substring(line, strpos(line, 'valve')), strpos(substring(line, strpos(line, 'valve')), ' ') + 1), ', ') as target
FROM lance_input
), valve_path AS (
SELECT valve as _start, target as _end, '{}'::varchar[] || valve || target as path
FROM origin
WHERE rate > 0 OR valve = 'AA'
UNION ALL
SELECT x._start, y.target as _end, path || y.target
FROM valve_path x
JOIN origin y
ON x._end = y.valve
WHERE NOT y.target = ANY(path)
), valve_dist AS (
SELECT _start, _end, distance
FROM (
SELECT _start, _end, array_length(path, 1) - 1 as distance,
row_number() over (partition by _start, _end order by array_length(path, 1)) as rn
FROM valve_path
) t
WHERE rn = 1
AND _end in (select valve from origin where rate > 0)
), valve_seq AS (
SELECT _start, _end,
(30 - a.distance - 1) * b.rate as total,
30 - a.distance - 1 as left_minutes,
'{}'::varchar[] || _start || _end as path
FROM valve_dist a
JOIN (select distinct valve, rate from origin) b
ON a._end = b.valve
AND _start = 'AA'
UNION ALL
SELECT b._start, b._end,
total + (left_minutes - b.distance - 1) * c.rate as total,
left_minutes - b.distance - 1 as left_minutes,
path || b._end as path
FROM valve_seq a
JOIN valve_dist b
ON a._end = b._start
JOIN (select distinct valve, rate from origin) c
ON b._end = c.valve
WHERE NOT b._end = ANY(path)
AND left_minutes - b.distance - 1 > 0
)
SELECT path, total
FROM valve_seq
ORDER BY total desc limit 1
path | total
------------------------------+-------
{AA,JI,ZD,PL,HN,IY,LE,QY,YL} | 2265
Part Two
第二部分，增加了一头大象作为助手，同时出发去开启阀门
It would take you 4 minutes to teach an elephant how to open the right valves in the right order, leaving you with only 26 minutes to actually execute your plan.
分解阀门
基本的思路，就是将所有的阀门分拆为两部分，最终尽快开启所有的阀门后，这样可以保证总体流动的压力值最大。
valve_splits AS (
SELECT '{}'::varchar[] as man,
'AA' as man_valve,
'{}'::varchar[] as elephant,
'AA' as elephant_valve,
0 :: bigint as total,
26 :: bigint as man_minutes,
26 :: bigint as elephant_minutes
UNION ALL
SELECT case when c.id = 0 then man || b._end else man end as man,
case when c.id = 0 then b._end else man_valve end as man_valve,
case when c.id = 1 then elephant || b._end else elephant end as elephant,
case when c.id = 1 then b._end else elephant_valve end as elephant_valve,
total + (case when c.id = 0 then man_minutes else elephant_minutes end - b.distance - 1) * d.rate as total,
case when c.id = 0 then man_minutes - b.distance - 1 else man_minutes end as man_minutes,
case when c.id = 1 then elephant_minutes - b.distance - 1 else elephant_minutes end as elephant_minutes
FROM valve_splits a,
valve_dist b,
(select generate_series(0, 1)) as c(id),
(select distinct valve, rate from origin) d
WHERE case when c.id = 0 then man_valve else elephant_valve end = b._start
AND b._end = d.valve
AND NOT b._end = ANY(man)
AND NOT b._end = ANY(elephant)
AND case when c.id = 0 then man_minutes - b.distance - 1 else elephant_minutes - b.distance - 1 end > 0
)
SELECT man, elephant, total FROM valve_splits order by total desc limit 1;
man | elephant | total
------------+------------+-------
{JJ,BB,CC} | {DD,HH,EE} | 1707
(1 row)
但是在运行真实数据的时候，整体运行速度非常慢，还是因为产生了太多的重复记录
man | elephant | total
------------+------------+-------
{DD,HH,EE} | {JJ,BB,CC} | 1707
{DD,HH,EE} | {JJ,BB,CC} | 1707
{JJ,BB,CC} | {DD,HH,EE} | 1707
{JJ,BB,CC} | {DD,HH,EE} | 1707
{DD,HH,EE} | {JJ,BB,CC} | 1707
{JJ,BB,CC} | {DD,HH,EE} | 1707
{JJ,BB,CC} | {DD,HH,EE} | 1707
{DD,HH,EE} | {JJ,BB,CC} | 1707
{DD,HH,EE} | {JJ,BB,CC} | 1707
{JJ,BB,CC} | {DD,HH,EE} | 1707
(10 rows)
减少排列数量
上面的方法产生了太多的重复记录，因此要提升计算性能，需要尽可能地减少重复计算。比如{DD,HH,EE}与{DD,EE,HH}两个排列，产生的压力值是不同的，但是只保留最大压力值的排列就够了，另一个排列没有保留的必要了。
为了能够对数组进行去重，方便判断是否重合，需要转成int array
WITH mapping AS (
SELECT row_number() over () as rn,
valve
FROM (
SELECT substring(line, 7, 2) as valve FROM lance_input order by 1
) t
), origin AS (
SELECT y.rn as valve, x.rate, z.rn as target
FROM (
SELECT substring(line, 7, 2) as valve,
substring(line, strpos(line, 'rate=') + 5, strpos(line, ';') - strpos(line, 'rate=') - 5) :: bigint as rate,
string_to_table(substring(substring(line, strpos(line, 'valve')), strpos(substring(line, strpos(line, 'valve')), ' ') + 1), ', ') as target
FROM lance_input
) x
JOIN mapping y
ON x.valve = y.valve
JOIN mapping z
ON x.target = z.valve
)
SELECT * FROM origin
valve | rate | target
-------+------+--------
51 | 0 | 50
51 | 0 | 26
5 | 0 | 31
5 | 0 | 36
12 | 0 | 18
12 | 0 | 20
37 | 0 | 60
再计算出，每种排列组合的压力值，计算方式和第一段类似
valve_path AS (
SELECT valve as _start, target as _end, '{}'::integer[] || valve || target as path
FROM origin
WHERE rate > 0 OR valve = 1
UNION ALL
SELECT x._start, y.target as _end, path || y.target
FROM valve_path x
JOIN origin y
ON x._end = y.valve
WHERE NOT y.target = ANY(path)
), valve_dist AS (
SELECT _start :: integer, _end :: integer, distance :: integer
FROM (
SELECT _start, _end, array_length(path, 1) - 1 as distance,
row_number() over (partition by _start, _end order by array_length(path, 1)) as rn
FROM valve_path
) t
WHERE rn = 1
AND _end in (select valve from origin where rate > 0)
), valve_splits AS (
SELECT '{}'::integer[] as splits,
1 as valve,
0 :: bigint as total,
26 :: bigint as minutes,
0 as cnt
UNION ALL
SELECT splits || b._end as splits,
b._end as valve,
total + (minutes - b.distance - 1) * d.rate as total,
minutes - b.distance - 1 as minutes,
cnt + 1 as cnt
FROM valve_splits a,
valve_dist b,
(select distinct valve, rate from origin) d
WHERE a.valve = b._start
AND b._end = d.valve
AND NOT b._end = ANY(splits)
AND minutes - b.distance - 1 > 0
)
SELECT * FROM valve_splits
{31,18,59,35,56,60,33} | 33 | 1446 | 1 | 7
{31,18,59,26,56,60,35} | 35 | 1278 | 2 | 7
{31,18,59,35,26,60,56} | 56 | 1400 | 3 | 7
{30,18,59,35,26,60,56} | 56 | 927 | 1 | 7
{21,18,59,35,26,60,56} | 56 | 1323 | 1 | 7
{31,18,59,21,26,60,56} | 56 | 1288 | 1 | 7
{31,18,35,59,26,60,56} | 56 | 1322 | 1 | 7
{30,31,18,59,26,60,56} | 56 | 885 | 1 | 7
{22,31,18,59,26,60,56} | 56 | 1325 | 1 | 7
{31,30,18,59,26,60,56} | 56 | 958 | 1 | 7
{31,18,21,59,26,60,56} | 56 | 1329 | 1 | 7
{31,18,26,59,35,60,56} | 56 | 1254 | 1 | 7
{31,18,59,26,35,60,56} | 56 | 1317 | 2 | 7
(34230 rows)
一共有34230种组合，但是还可以继续去重，仅保留最大压力值的组合，从而减少后续计算量。去重后仅剩余3555条记录。
SELECT sort(splits),max(total) from valve_splits group by sort(splits);
{31,35,57,59,60} | 1145
{18,21,22,35,57,59} | 1519
{18,22,26,30,33,56} | 1034
{18,21,22,35,57} | 1517
{18,21,26,30,57} | 1174
{26,33,35,60} | 907
{21,30,56,57} | 861
{9,30,33} | 234
{22,30,31,56,60} | 1039
{26,33} | 246
{22,26,31,53,59} | 986
{9,21,35,56,59} | 1095
{9,26,31,56,59} | 770
(3555 rows)
最后一步，就是将组合两两配对，找出压力值最大的配对方式
SELECT *
FROM (select sort(splits) as splits, max(total) as total from valve_splits group by sort(splits)) x,
(select sort(splits) as splits, max(total) as total from valve_splits group by sort(splits)) y
WHERE NOT x.splits && y.splits
ORDER BY (x.total + y.total) desc limit 10;
splits | total | splits | total
---------------------+-------+---------------------+-------
{18,21,22,26,31,57} | 1686 | {33,35,53,56,59,60} | 1125
{33,35,53,56,59,60} | 1125 | {18,21,22,26,31,57} | 1686
{18,21,22,26,31,57} | 1686 | {9,33,35,56,59,60} | 1116
{9,33,35,56,59,60} | 1116 | {18,21,22,26,31,57} | 1686
{18,21,22,30,31,57} | 1666 | {33,35,53,56,59,60} | 1125
{33,35,53,56,59,60} | 1125 | {18,21,22,30,31,57} | 1666
{18,22,30,31,57,59} | 1543 | {21,26,33,35,56,60} | 1245
{21,26,33,35,56,60} | 1245 | {18,22,30,31,57,59} | 1543
{33,35,53,56,59,60} | 1125 | {18,21,22,31,57} | 1662
{18,21,22,31,57} | 1662 | {33,35,53,56,59,60} | 1125
(10 rows)
最终SQL
WITH recursive mapping AS (
SELECT row_number() over () as rn,
valve
FROM (
SELECT substring(line, 7, 2) as valve FROM lance_input order by 1
) t
), origin AS (
SELECT y.rn as valve, x.rate, z.rn as target
FROM (
SELECT substring(line, 7, 2) as valve,
substring(line, strpos(line, 'rate=') + 5, strpos(line, ';') - strpos(line, 'rate=') - 5) :: bigint as rate,
string_to_table(substring(substring(line, strpos(line, 'valve')), strpos(substring(line, strpos(line, 'valve')), ' ') + 1), ', ') as target
FROM lance_input
) x
JOIN mapping y
ON x.valve = y.valve
JOIN mapping z
ON x.target = z.valve
), valve_path AS (
SELECT valve as _start, target as _end, '{}'::integer[] || valve || target as path
FROM origin
WHERE rate > 0 OR valve = 1
UNION ALL
SELECT x._start, y.target as _end, path || y.target
FROM valve_path x
JOIN origin y
ON x._end = y.valve
WHERE NOT y.target = ANY(path)
), valve_dist AS (
SELECT _start :: integer, _end :: integer, distance :: integer
FROM (
SELECT _start, _end, array_length(path, 1) - 1 as distance,
row_number() over (partition by _start, _end order by array_length(path, 1)) as rn
FROM valve_path
) t
WHERE rn = 1
AND _end in (select valve from origin where rate > 0)
), valve_splits AS (
SELECT '{}'::integer[] as splits,
1 as valve,
0 :: bigint as total,
26 :: bigint as minutes,
0 as cnt
UNION ALL
SELECT splits || b._end as splits,
b._end as valve,
total + (minutes - b.distance - 1) * d.rate as total,
minutes - b.distance - 1 as minutes,
cnt + 1 as cnt
FROM valve_splits a,
valve_dist b,
(select distinct valve, rate from origin) d
WHERE a.valve = b._start
AND b._end = d.valve
AND NOT b._end = ANY(splits)
AND minutes - b.distance - 1 > 0
)
SELECT *
FROM (select sort(splits) as splits, max(total) as total from valve_splits group by sort(splits)) x,
(select sort(splits) as splits, max(total) as total from valve_splits group by sort(splits)) y
WHERE NOT x.splits && y.splits
ORDER BY (x.total + y.total) desc limit 10;