Part One
通过三种module的传递，计算出传递的low / high信号次数。有些模块需要存储，根据上一次信号类型，才能决定下一次的信号类型。
broadcaster -> a, b, c
%a -> b
%b -> c
%c -> inv
&inv -> a
状态存储
通过一张state表来存储状态，并创建两个函数来进行状态判断
CREATE OR REPLACE FUNCTION flip(_module VARCHAR)
RETURNS VARCHAR AS $$
DECLARE
pulse VARCHAR;
BEGIN
UPDATE state SET status = CASE WHEN status = 'ON' THEN 'OFF' ELSE 'ON' END WHERE module = _module RETURNING status INTO pulse;
IF pulse = 'OFF' THEN
return 'low';
ELSE
return 'high';
END IF;
END;
$$ LANGUAGE plpgsql;
CREATE OR REPLACE FUNCTION conjunction(_module VARCHAR, _pre_module VARCHAR, _pulse VARCHAR)
RETURNS VARCHAR AS $$
DECLARE
pulse VARCHAR;
BEGIN
UPDATE state
SET status = replace(replace(status,
_pre_module || ':low',
_pre_module || ':' || _pulse
),
_pre_module || ':high',
_pre_module || ':' || _pulse
)
WHERE module = _module RETURNING status INTO pulse;
IF pulse like '%low%' THEN
return 'high';
ELSE
return 'low';
END IF;
END;
$$ LANGUAGE plpgsql;
状态需要初始化
WITH RECURSIVE origin AS (
SELECT _row, CASE WHEN substring(module,1,1) IN ('%', '&') THEN substring(module, 2) ELSE module END as module_name,
CASE WHEN substring(module,1,1) = '%' THEN 'flip-flop'
WHEN substring(module,1,1) = '&' THEN 'conjunction'
WHEN module = 'broadcaster' THEN 'broadcaster'
ELSE 'untyped'
END as module_type,
destination
FROM (
SELECT row_number() over () as _row, split_part(line, ' -> ', 1) as module, split_part(line, ' -> ', 2) as destination
FROM lance_input
) t
),states AS (
SELECT module_name, module_type, 'OFF' as status
FROM origin
WHERE module_type = 'flip-flop'
UNION ALL
SELECT a.module_name, a.module_type, string_agg(b.module_name || ':low', ',') as status
FROM origin a, origin b
WHERE a.module_type = 'conjunction'
AND b.destination || ',' like '%' || a.module_name || ',%'
GROUP BY a.module_name, a.module_type
) select module_name, status from states;
1000次发送
每当一次发送后，所有的状态都处理完毕后，需要进行下一次按钮发送。通过not exists的条件来进行判断，每当无后续信号时，则重新发送一次按钮。
SELECT 'button' as current_module, 'low' as pulse, 'broadcaster' as next_module, b.button_seq + 1 as button_seq
FROM (select 1) a, (select button_seq from signals_inner limit 1) b
WHERE not exists (
SELECT 1
FROM signals_inner a
JOIN origin b
ON a.next_module = b.module_name
AND a.pulse is not null
)
AND b.button_seq < 1000
完整SQL
WITH RECURSIVE origin AS (
SELECT _row, CASE WHEN substring(module,1,1) IN ('%', '&') THEN substring(module, 2) ELSE module END as module_name,
CASE WHEN substring(module,1,1) = '%' THEN 'flip-flop'
WHEN substring(module,1,1) = '&' THEN 'conjunction'
WHEN module = 'broadcaster' THEN 'broadcaster'
ELSE 'untyped'
END as module_type,
destination
FROM (
SELECT row_number() over () as _row, split_part(line, ' -> ', 1) as module, split_part(line, ' -> ', 2) as destination
FROM lance_input
) t
),
signals AS (
SELECT 'button' as current_module, 'low' as pulse, 'broadcaster' as next_module, 1 as button_seq
UNION ALL
SELECT *
FROM (
WITH signals_inner AS (
SELECT * FROM signals
)
SELECT current_module, pulse, unnest(regexp_split_to_array(destination, ', ')) as next_module, button_seq
FROM (
SELECT b.module_name as current_module,
CASE WHEN b.module_type = 'broadcaster' THEN a.pulse
WHEN b.module_type = 'flip-flop' AND a.pulse = 'low' THEN flip(b.module_name)
WHEN b.module_type = 'conjunction' THEN conjunction(b.module_name, a.current_module, a.pulse)
END as pulse,
b.destination,
button_seq
FROM signals_inner a JOIN origin b
ON a.next_module = b.module_name
AND a.pulse is not null
) t
UNION ALL
SELECT 'button' as current_module, 'low' as pulse, 'broadcaster' as next_module, b.button_seq + 1 as button_seq
FROM (select 1) a, (select button_seq from signals_inner limit 1) b
WHERE not exists (
SELECT 1
FROM signals_inner a
JOIN origin b
ON a.next_module = b.module_name
AND a.pulse is not null
)
AND b.button_seq < 1000
) t
)
SELECT pulse,count(*) from signals group by pulse;
Part Two
查找发送low信号到rx的最小按键次数
&mr -> qb
&rz -> qb
&kv -> qb
&jg -> qb
&qb -> rx
10000次的观察
qb发送low到rx，由于qb是conjunction类型，需要mr/rz/kv/jb四个module发送high到qb。
运行10000次后，看下四个module发送high信号的次数分布情况
postgres=# select * From lance_test where current_module = 'mr' and next_module = 'qb' and pulse = 'high';
current_module | pulse | next_module | button_seq
----------------+-------+-------------+------------
mr | high | qb | 8006
mr | high | qb | 4003
(2 rows)
postgres=# select * From lance_test where current_module = 'rz' and next_module = 'qb' and pulse = 'high';
current_module | pulse | next_module | button_seq
----------------+-------+-------------+------------
rz | high | qb | 4073
rz | high | qb | 8146
(2 rows)
postgres=# select * From lance_test where current_module = 'kv' and next_module = 'qb' and pulse = 'high';
current_module | pulse | next_module | button_seq
----------------+-------+-------------+------------
kv | high | qb | 7478
kv | high | qb | 3739
(2 rows)
postgres=# select * From lance_test where current_module = 'jg' and next_module = 'qb' and pulse = 'high';
current_module | pulse | next_module | button_seq
----------------+-------+-------------+------------
jg | high | qb | 3911
jg | high | qb | 7822
(2 rows)
则计算四个数字的最小公倍数即可。
次数的背后
网上找到了这篇文章，比较有意思，原来这个次数背后是有一定规则的。
以kv这个module为例，根据规则顺序画了具体的依赖图，发送信号到qz以红线标注
具体用二进制表示，就是1110 1001 1011，对应的十进制就是3739，正好是kv的按键次数。
因为flip模块交替发送high low信号，而遇到high信号不处理，因此越往后需要的次数就越多。比如这里lx需要2次，nt需要8次。