Build convolution one loop at a time

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.11%22%0A%23%20dependencies%20%3D%20%5B%22marimo%3E%3D0.24.0%22%5D%0A%23%20%0A%23%20%5Btool.marimo.export%5D%0A%23%20lock_kind%20%3D%20%22resolved%22%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App(%0A%20%20%20%20width%3D%22medium%22%2C%0A%20%20%20%20app_title%3D%22Build%20convolution%20one%20loop%20at%20a%20time%22%2C%0A)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Build%20convolution%20one%20loop%20at%20a%20time%0A%0A%20%20%20%20This%20notebook%20begins%20with%20the%20multiplication%20table%20from%20Chapter%202.%20It%20deliberately%0A%20%20%20%20uses%20lists%2C%20loops%2C%20and%20accumulation.%20Change%20the%20values%3B%20every%20table%2C%20bucket%2C%20and%0A%20%20%20%20check%20below%20reacts%20immediately.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20left_0%20%3D%20mo.ui.number(-9%2C%209%2C%20value%3D2%2C%20label%3D%22a%E2%82%80%22)%0A%20%20%20%20left_1%20%3D%20mo.ui.number(-9%2C%209%2C%20value%3D-1%2C%20label%3D%22a%E2%82%81%22)%0A%20%20%20%20left_2%20%3D%20mo.ui.number(-9%2C%209%2C%20value%3D3%2C%20label%3D%22a%E2%82%82%22)%0A%20%20%20%20right_0%20%3D%20mo.ui.number(-9%2C%209%2C%20value%3D4%2C%20label%3D%22b%E2%82%80%22)%0A%20%20%20%20right_1%20%3D%20mo.ui.number(-9%2C%209%2C%20value%3D5%2C%20label%3D%22b%E2%82%81%22)%0A%20%20%20%20right_2%20%3D%20mo.ui.number(-9%2C%209%2C%20value%3D-2%2C%20label%3D%22b%E2%82%82%22)%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20mo.md(%22%23%23%201%20%C2%B7%20Choose%20two%20coefficient%20lists%22)%2C%0A%20%20%20%20%20%20%20%20mo.hstack(%5Bleft_0%2C%20left_1%2C%20left_2%5D)%2C%0A%20%20%20%20%20%20%20%20mo.hstack(%5Bright_0%2C%20right_1%2C%20right_2%5D)%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%20left_0%2C%20left_1%2C%20left_2%2C%20right_0%2C%20right_1%2C%20right_2%0A%0A%0A%40app.cell%0Adef%20_(left_0%2C%20left_1%2C%20left_2%2C%20right_0%2C%20right_1%2C%20right_2)%3A%0A%20%20%20%20left%20%3D%20%5Bleft_0.value%2C%20left_1.value%2C%20left_2.value%5D%0A%20%20%20%20right%20%3D%20%5Bright_0.value%2C%20right_1.value%2C%20right_2.value%5D%0A%20%20%20%20return%20left%2C%20right%0A%0A%0A%40app.cell%0Adef%20_(left%2C%20mo%2C%20right)%3A%0A%20%20%20%20_rows%20%3D%20%5B%5D%0A%20%20%20%20for%20_i%2C%20_left_value%20in%20enumerate(left)%3A%0A%20%20%20%20%20%20%20%20for%20_k%2C%20_right_value%20in%20enumerate(right)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_rows.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22left%20position%20i%22%3A%20_i%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22right%20position%20k%22%3A%20_k%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22destination%20i%2Bk%22%3A%20_i%20%2B%20_k%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22product%22%3A%20_left_value%20*%20_right_value%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D)%0A%20%20%20%20mo.vstack(%5Bmo.md(%22%23%23%202%20%C2%B7%20Make%20every%20pair%22)%2C%20mo.ui.table(_rows%2C%20selection%3DNone)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(left%2C%20right)%3A%0A%20%20%20%20output%20%3D%20%5B0%5D%20*%20(len(left)%20%2B%20len(right)%20-%201)%0A%20%20%20%20trace%20%3D%20%5B%5D%0A%20%20%20%20for%20_i%2C%20_left_value%20in%20enumerate(left)%3A%0A%20%20%20%20%20%20%20%20for%20_k%2C%20_right_value%20in%20enumerate(right)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_destination%20%3D%20_i%20%2B%20_k%0A%20%20%20%20%20%20%20%20%20%20%20%20_product%20%3D%20_left_value%20*%20_right_value%0A%20%20%20%20%20%20%20%20%20%20%20%20_before%20%3D%20output%5B_destination%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20output%5B_destination%5D%20%2B%3D%20_product%0A%20%20%20%20%20%20%20%20%20%20%20%20trace.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22bucket%20%7B_destination%7D%3A%20%7B_before%7D%20%2B%20(%7B_left_value%7D%C3%97%7B_right_value%7D)%20%3D%20%7Boutput%5B_destination%5D%7D%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20return%20output%2C%20trace%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20output%2C%20trace)%3A%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20mo.md(%22%23%23%203%20%C2%B7%20Accumulate%20pairs%20into%20output%20buckets%22)%2C%0A%20%20%20%20%20%20%20%20mo.callout(mo.md(f%22**convolution%20result%3A**%20%60%7Boutput%7D%60%22)%2C%20kind%3D%22success%22)%2C%0A%20%20%20%20%20%20%20%20mo.accordion(%7B%22Open%20the%20complete%20accumulation%20trace%22%3A%20mo.md(%22%5Cn%5Cn%22.join(f%22-%20%7Bline%7D%22%20for%20line%20in%20trace))%7D)%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(left%2C%20mo%2C%20right)%3A%0A%20%20%20%20size%20%3D%20len(left)%0A%20%20%20%20wrapped%20%3D%20%5B0%5D%20*%20size%0A%20%20%20%20wrapped_trace%20%3D%20%5B%5D%0A%20%20%20%20for%20_i%2C%20_left_value%20in%20enumerate(left)%3A%0A%20%20%20%20%20%20%20%20for%20_k%2C%20_right_value%20in%20enumerate(right)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_destination%20%3D%20_i%20%2B%20_k%0A%20%20%20%20%20%20%20%20%20%20%20%20_product%20%3D%20_left_value%20*%20_right_value%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_destination%20%3C%20size%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20wrapped%5B_destination%5D%20%2B%3D%20_product%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20wrapped_trace.append(f%22%7B_i%7D%2B%7B_k%7D%3D%7B_destination%7D%3A%20add%20%7B_product%7D%20directly%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20wrapped%5B_destination%20-%20size%5D%20-%3D%20_product%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20wrapped_trace.append(f%22%7B_i%7D%2B%7B_k%7D%3D%7B_destination%7D%3A%20wrap%20to%20%7B_destination-size%7D%20and%20subtract%20%7B_product%7D%22)%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20mo.md(%22%23%23%204%20%C2%B7%20Change%20only%20the%20boundary%20rule%22)%2C%0A%20%20%20%20%20%20%20%20mo.callout(mo.md(f%22**negacyclic%20result%3A**%20%60%7Bwrapped%7D%60%22)%2C%20kind%3D%22warn%22)%2C%0A%20%20%20%20%20%20%20%20mo.accordion(%7B%22Open%20the%20wrap%20trace%22%3A%20mo.md(%22%5Cn%5Cn%22.join(f%22-%20%7Bline%7D%22%20for%20line%20in%20wrapped_trace))%7D)%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20answer%20%3D%20mo.ui.radio(%0A%20%20%20%20%20%20%20%20options%3D%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%60output%5Bdestination%5D%20%3D%20product%60%22%3A%20%22replace%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%60output%5Bdestination%5D%20%2B%3D%20product%60%22%3A%20%22accumulate%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%60output%5Bi%5D%20%2B%3D%20right%5Bk%5D%60%22%3A%20%22mismatch%22%2C%0A%20%20%20%20%20%20%20%20%7D%2C%0A%20%20%20%20%20%20%20%20label%3D%22Which%20line%20preserves%20all%20products%20that%20share%20a%20bucket%3F%22%2C%0A%20%20%20%20)%0A%20%20%20%20answer%0A%20%20%20%20return%20(answer%2C)%0A%0A%0A%40app.cell%0Adef%20_(answer%2C%20mo)%3A%0A%20%20%20%20if%20answer.value%20%3D%3D%20%22accumulate%22%3A%0A%20%20%20%20%20%20%20%20_message%20%3D%20mo.callout(%22Correct.%20Several%20pairs%20may%20share%20one%20destination%2C%20so%20the%20bucket%20must%20accumulate.%22%2C%20kind%3D%22success%22)%0A%20%20%20%20elif%20answer.value%3A%0A%20%20%20%20%20%20%20%20_message%20%3D%20mo.callout(%22Try%20again.%20Follow%20two%20cells%20on%20the%20same%20diagonal%20into%20one%20bucket.%22%2C%20kind%3D%22danger%22)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_message%20%3D%20mo.md(%22Choose%20an%20answer%20after%20tracing%20one%20diagonal.%22)%0A%20%20%20%20_message%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A