AdventOfCode 2024 Day 24

Part One

输入x,y,经过一系列的运算后得出z的值

已知x,y的值,后续会陆续得出更多的已知值,因此需要每一轮迭代的输出要带上所有的已知值。终止条件就是所有的值都已找出,没有后续的未知值了。

with recursive origin AS (
    SELECT row_number() over () as rn, line
    FROM lance_input
), input AS (
    SELECT split_part(line, ': ', 1) as key, split_part(line, ': ', 2) :: INTEGER as value
    FROM origin
    WHERE rn < (select rn from origin where line is null)
), gate AS (
    SELECT split_part(line, ' ', 1) as l, 
           split_part(line, ' ', 2) as op,
           split_part(line, ' ', 3) as r,
           split_part(line, ' ', 5) as output
    FROM origin
    WHERE rn > (select rn from origin where line is null)
), gate_output AS (
    SELECT key, value
    FROM input

    UNION ALL

    SELECT key, value
    FROM (
        WITH inner_gate AS (select * from gate_output),
        new_output as (
            SELECT key, value from inner_gate

            UNION ALL

            SELECT output as key,
                   CASE WHEN op = 'AND' THEN b.value & c.value
                        WHEN op = 'OR' THEN b.value | c.value
                        WHEN op = 'XOR' THEN b.value # c.value
                    END as value
            FROM gate a
            JOIN inner_gate b
            ON a.l = b.key
            JOIN inner_gate c
            ON a.r = c.key
            LEFT JOIN inner_gate d
            ON a.output = d.key
            WHERE d.value is null
        )
        SELECT key, value
        FROM new_output
        WHERE exists (
            SELECT 1 
            FROM gate 
            LEFT JOIN inner_gate 
            ON gate.output = inner_gate.key 
            WHERE inner_gate.value is null
        )
    ) t
)
SELECT sum(value * power(2, substring(key, 2) :: integer)) 
FROM (
    select distinct key, value
    from gate_output 
    where key like 'z%'
) t;

Part Two

这道题的实际目的是为了计算两个二进制数的求和,00,01,02代表着对应bit位的值。最终结果是不正确的,因此有几对运算结果错误,需要调换下,找出这几对的运算结果。

这道题很巧妙,需要理解二进制进行加法运算的规律。

00位加法运算

         x00
+        y00
--------------
         z00

z00 = x00 XOR y00

z00的值其实就是x00与y00的XOR,题面也是这么设计的

y10 AND x10 -> wrk
x00 XOR y00 -> z00
qfp XOR vhf -> z17

如果x00与y00均为1值,要往前进一位,因此就是x00 AND y00的值

x28 XOR y28 -> scd
y00 AND x00 -> mgk
fgn OR cpm -> qfp

01位加法运算

       mgk  
       x01  x00
+      y01  y00
-----------------
       z01  z00

z01 = (x01 XOR y01) XOR mgk

z01的值,其实是x01,y01,mgk三个值的xor

y34 AND x34 -> qmr
x01 XOR y01 -> rkf
djs AND chf -> pwv

cdf OR npv -> jbg
rkf XOR mgk -> z01
y44 XOR x44 -> pvc

现在比较复杂的就是计算出01位是否往前进位,根据加法运算,三个数中至少2个1就可以往前进位。

x01与y01的xor为1,代表0|1,如果上个bit位的进位值为1,则取AND就是本bit位的进位值

       1        1                   
       0        1
+      1        0        
----------------------
       0        0

(x01 XOR y01) AND (x00 AND y00)

y34 AND x34 -> qmr
x01 XOR y01 -> rkf
djs AND chf -> pwv

x26 XOR y26 -> pjf
rkf AND mgk -> kmj
pvk XOR kdf -> z10

还有一种情况,x01与y01都为1,那么肯定要往前进位

       0        1                   
       1        1
+      1        1        
----------------------
       0        1

x01 AND y01

tsw AND mvj -> nwd
x01 AND y01 -> nfw
gkw XOR mhv -> z21

那么两种情况都有可能往前进位,因此求OR即可

y17 AND x17 -> vmq
nfw OR kmj -> rwp
dkm OR hgm -> shr

rwp,即01位运算后往前的进位

最后一位结果

最后一位,无需加法运算,直接就是前一位的进位值即可

qfj AND rcg -> bck
vrk OR nhn -> z45
x28 AND y28 -> bwk

计算每一位的取值及进位

接下来就按照这个规则,递归地求出每一位的取值以及进位,如果在某一位计算中断,则肯定是某一项计算不正确导致。

with recursive origin AS (
    SELECT row_number() over () as rn, line
    FROM lance_input
), input AS (
    SELECT split_part(line, ': ', 1) as key, split_part(line, ': ', 2) :: INTEGER as value
    FROM origin
    WHERE rn < (select rn from origin where line is null)
), gate AS (
    SELECT split_part(line, ' ', 1) as l, 
           split_part(line, ' ', 2) as op,
           split_part(line, ' ', 3) as r,
           split_part(line, ' ', 5) as output
    FROM origin
    WHERE rn > (select rn from origin where line is null)
), bit_calc AS (
    SELECT 0 as bit_seq, 
           max(case when op = 'XOR' then output end) as bit_val,
           max(case when op = 'AND' then output end) as bit_carry
    FROM gate
    WHERE least(l, r) = 'x00' and greatest(l, r) = 'y00'

    UNION ALL

    SELECT bit_seq, bit_val, bit_carry
    FROM (
        WITH inner_bit AS (select * From bit_calc)
        SELECT a.bit_seq, c.output as bit_val, e.output as bit_carry
        FROM (
            SELECT b.bit_seq + 1 as bit_seq,
                   max(case when op = 'XOR' then output end) as bit_xor,
                   max(case when op = 'AND' then output end) as bit_and
            FROM gate a
            JOIN inner_bit b
            ON least(l, r) = 'x' || lpad((b.bit_seq + 1)::text, 2, '0') and greatest(l, r) = 'y' || lpad((b.bit_seq + 1)::text, 2, '0')
            GROUP BY b.bit_seq
        ) a
        JOIN inner_bit b
        ON a.bit_seq = b.bit_seq + 1
        JOIN gate c
        ON ((c.l = a.bit_xor and c.r = b.bit_carry) OR (c.l = b.bit_carry and c.r = a.bit_xor))
        AND c.op = 'XOR'
        LEFT JOIN gate d
        ON ((d.l = a.bit_xor and d.r = b.bit_carry) OR (d.l = b.bit_carry and d.r = a.bit_xor))
        AND d.op = 'AND'
        LEFT JOIN gate e
        ON ((e.l = a.bit_and and e.r = d.output) OR (e.l = d.output and e.r = a.bit_and))
        AND e.op = 'OR'
    ) t
)
select * from bit_calc;

比如,最一开始,计算至z08时,结果中断,则说明mvb的计算不正确,应该与z08调换。

postgres-# select * from bit_calc;
 bit_seq | bit_val | bit_carry 
---------+---------+-----------
       0 | z00     | mgk
       1 | z01     | rwp
       2 | z02     | fmj
       3 | z03     | ncp
       4 | z04     | qfj
       5 | z05     | hjm
       6 | z06     | tnr
       7 | z07     | sjd
       8 | mvb     | 
(9 rows)

找出4对不正确之后,则最终可以计算到最后一位

      31 | z31     | shr
      32 | z32     | mqb
      33 | z33     | smq
      34 | z34     | prv
      35 | z35     | vvt
      36 | z36     | jrs
      37 | z37     | chf
      38 | z38     | wch
      39 | z39     | sfr
      40 | z40     | rmb
      41 | z41     | vcr
      42 | z42     | mvj
      43 | z43     | sgh
      44 | z44     | z45
(45 rows)

发表评论