TSP + Excalidraw Whiteboard

import%20marimo%0A%0A__generated_with%20%3D%20%220.23.13%22%0Aapp%20%3D%20marimo.App(width%3D%22full%22%2C%20app_title%3D%22TSP%20%2B%20Excalidraw%20Whiteboard%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20from%20wigglystuff%20import%20Excalidraw%0A%0A%20%20%20%20return%20Excalidraw%2C%20mo%2C%20np%2C%20plt%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(np)%3A%0A%20%20%20%20np.random.seed(42)%0A%20%20%20%20n_cities%20%3D%2012%0A%20%20%20%20cities%20%3D%20np.random.rand(n_cities%2C%202)%20*%20100%0A%20%20%20%20return%20cities%2C%20n_cities%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(cities%2C%20np)%3A%0A%20%20%20%20def%20_dist(city1%2C%20city2)%3A%0A%20%20%20%20%20%20%20%20return%20np.sqrt((city1%5B0%5D%20-%20city2%5B0%5D)**2%20%2B%20(city1%5B1%5D%20-%20city2%5B1%5D)**2)%0A%0A%20%20%20%20def%20_solve_tsp(cities)%3A%0A%20%20%20%20%20%20%20%20n%20%3D%20len(cities)%0A%20%20%20%20%20%20%20%20unvisited%20%3D%20set(range(1%2C%20n))%0A%20%20%20%20%20%20%20%20path%20%3D%20%5B0%5D%0A%20%20%20%20%20%20%20%20current%20%3D%200%0A%20%20%20%20%20%20%20%20while%20unvisited%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20nearest%20%3D%20min(unvisited%2C%20key%3Dlambda%20i%3A%20_dist(cities%5Bcurrent%5D%2C%20cities%5Bi%5D))%0A%20%20%20%20%20%20%20%20%20%20%20%20path.append(nearest)%0A%20%20%20%20%20%20%20%20%20%20%20%20unvisited.remove(nearest)%0A%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20nearest%0A%20%20%20%20%20%20%20%20path.append(0)%0A%20%20%20%20%20%20%20%20return%20path%0A%0A%20%20%20%20tsp_path%20%3D%20_solve_tsp(cities)%0A%20%20%20%20return%20(tsp_path%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20n_cities)%3A%0A%20%20%20%20slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D0%2C%0A%20%20%20%20%20%20%20%20stop%3Dn_cities%20%2B%201%2C%0A%20%20%20%20%20%20%20%20value%3D0%2C%0A%20%20%20%20%20%20%20%20step%3D1%2C%0A%20%20%20%20%20%20%20%20label%3D%22City%20Index%22%2C%0A%20%20%20%20%20%20%20%20full_width%3DTrue%0A%20%20%20%20)%0A%20%20%20%20play_button%20%3D%20mo.ui.button(label%3D%22%E2%96%B6%20Auto%20Play%22%2C%20kind%3D%22primary%22)%0A%20%20%20%20reset_button%20%3D%20mo.ui.button(label%3D%22%E2%86%BA%20Reset%22)%0A%20%20%20%20return%20play_button%2C%20reset_button%2C%20slider%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(Excalidraw%2C%20mo)%3A%0A%20%20%20%20draw%20%3D%20mo.ui.anywidget(Excalidraw(height%3D620%2C%20theme%3D%22dark%22))%0A%20%20%20%20return%20(draw%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(cities%2C%20np%2C%20plt%2C%20slider%2C%20tsp_path)%3A%0A%20%20%20%20path_coords%20%3D%20np.array(%5Bcities%5Bi%5D%20for%20i%20in%20tsp_path%5D)%0A%20%20%20%20total_cities%20%3D%20len(path_coords)%0A%20%20%20%20_current_pos%20%3D%20slider.value%0A%0A%20%20%20%20fig%2C%20ax%20%3D%20plt.subplots(figsize%3D(8%2C%208))%0A%20%20%20%20ax.set_xlim(-10%2C%20110)%0A%20%20%20%20ax.set_ylim(-10%2C%20110)%0A%20%20%20%20ax.set_aspect('equal')%0A%20%20%20%20ax.set_facecolor('%230a0a0f')%0A%20%20%20%20fig.patch.set_facecolor('%230a0a0f')%0A%0A%20%20%20%20ax.scatter(cities%5B%3A%2C%200%5D%2C%20cities%5B%3A%2C%201%5D%2C%20c%3D'%2300d4ff'%2C%20s%3D300%2C%20alpha%3D0.6%2C%20zorder%3D5)%0A%20%20%20%20for%20idx%2C%20(x%2C%20y)%20in%20enumerate(cities)%3A%0A%20%20%20%20%20%20%20%20ax.text(x%2C%20y%20%2B%203%2C%20str(idx)%2C%20ha%3D'center'%2C%20va%3D'bottom'%2C%20color%3D'white'%2C%20fontsize%3D10%2C%20fontweight%3D'bold')%0A%0A%20%20%20%20ax.plot(path_coords%5B%3A%2C%200%5D%2C%20path_coords%5B%3A%2C%201%5D%2C%20'c--'%2C%20alpha%3D0.2%2C%20linewidth%3D2)%0A%0A%20%20%20%20if%20_current_pos%20%3E%200%3A%0A%20%20%20%20%20%20%20%20active_path%20%3D%20path_coords%5B%3A_current_pos%20%2B%201%5D%0A%20%20%20%20%20%20%20%20ax.plot(active_path%5B%3A%2C%200%5D%2C%20active_path%5B%3A%2C%201%5D%2C%20'c-'%2C%20linewidth%3D3%2C%20alpha%3D0.8)%0A%0A%20%20%20%20if%20_current_pos%20%3C%20total_cities%3A%0A%20%20%20%20%20%20%20%20current_city%20%3D%20path_coords%5B_current_pos%5D%0A%20%20%20%20%20%20%20%20ax.scatter(current_city%5B0%5D%2C%20current_city%5B1%5D%2C%20c%3D'%23ff6b35'%2C%20s%3D500%2C%20zorder%3D10%2C%20edgecolors%3D'white'%2C%20linewidths%3D2)%0A%0A%20%20%20%20ax.set_title('Nearest-Neighbor%20TSP%20Solution'%2C%20color%3D'white'%2C%20fontsize%3D13%2C%20pad%3D15)%0A%20%20%20%20info_text%20%3D%20f%22Step%20%7B_current_pos%7D%2F%7Btotal_cities%20-%201%7D%20%7C%20%7B'%20%E2%86%92%20'.join(map(str%2C%20tsp_path%5B%3A_current_pos%20%2B%201%5D))%7D%22%0A%20%20%20%20ax.text(50%2C%20-5%2C%20info_text%2C%20ha%3D'center'%2C%20va%3D'top'%2C%20color%3D'%2300d4ff'%2C%20fontsize%3D9%2C%20fontweight%3D'bold')%0A%0A%20%20%20%20ax.tick_params(colors%3D'white')%0A%20%20%20%20for%20spine%20in%20ax.spines.values()%3A%0A%20%20%20%20%20%20%20%20spine.set_color('white')%0A%20%20%20%20plt.tight_layout()%0A%20%20%20%20plt%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(cities%2C%20mo%2C%20np%2C%20slider%2C%20tsp_path)%3A%0A%20%20%20%20_total_distance%20%3D%200%0A%20%20%20%20for%20_idx%20in%20range(len(tsp_path)%20-%201)%3A%0A%20%20%20%20%20%20%20%20dx%20%3D%20cities%5Btsp_path%5B_idx%20%2B%201%5D%5D%5B0%5D%20-%20cities%5Btsp_path%5B_idx%5D%5D%5B0%5D%0A%20%20%20%20%20%20%20%20dy%20%3D%20cities%5Btsp_path%5B_idx%20%2B%201%5D%5D%5B1%5D%20-%20cities%5Btsp_path%5B_idx%5D%5D%5B1%5D%0A%20%20%20%20%20%20%20%20_total_distance%20%2B%3D%20np.sqrt(dx**2%20%2B%20dy**2)%0A%0A%20%20%20%20_current_pos%20%3D%20slider.value%0A%20%20%20%20_current_distance%20%3D%200%0A%20%20%20%20for%20_idx%20in%20range(_current_pos)%3A%0A%20%20%20%20%20%20%20%20if%20_idx%20%2B%201%20%3C%20len(tsp_path)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20dx%20%3D%20cities%5Btsp_path%5B_idx%20%2B%201%5D%5D%5B0%5D%20-%20cities%5Btsp_path%5B_idx%5D%5D%5B0%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20dy%20%3D%20cities%5Btsp_path%5B_idx%20%2B%201%5D%5D%5B1%5D%20-%20cities%5Btsp_path%5B_idx%5D%5D%5B1%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_current_distance%20%2B%3D%20np.sqrt(dx**2%20%2B%20dy**2)%0A%0A%20%20%20%20stats_text%20%3D%20f%22%22%22%0A%20%20%20%20%23%23%23%20Path%20Statistics%0A%20%20%20%20-%20**Total%20distance%3A**%20%7B_total_distance%3A.1f%7D%20units%0A%20%20%20%20-%20**Current%20distance%3A**%20%7B_current_distance%3A.1f%7D%20units%0A%20%20%20%20-%20**Progress%3A**%20%7B_current_pos%7D%2F%7Blen(tsp_path)%20-%201%7D%20cities%20visited%0A%20%20%20%20-%20**Path%3A**%20%7B'%20%E2%86%92%20'.join(map(str%2C%20tsp_path))%7D%0A%20%20%20%20%22%22%22%0A%20%20%20%20mo.md(stats_text)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20play_button%2C%20reset_button%2C%20slider)%3A%0A%20%20%20%20mo.hstack(%5Bplay_button%2C%20reset_button%2C%20slider%5D%2C%20justify%3D%22space-between%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20%23%23%20%F0%9F%8E%A8%20Sketch%20Your%20Own%20Route%0A%0A%20%20%20%20The%20**Excalidraw%20whiteboard**%20below%20lets%20you%20annotate%2C%20sketch%20alternative%20routes%2C%0A%20%20%20%20or%20draw%20freehand.%20Export%20your%20drawing%20via%20the%20Excalidraw%20menu%20(top-left).%0A%0A%20%20%20%20**Try%20it%3A**%0A%20%20%20%201.%20Drag%20the%20slider%20to%20watch%20the%20computed%20path%20build%0A%20%20%20%202.%20Sketch%20your%20own%20path%20guess%20on%20the%20whiteboard%0A%20%20%20%203.%20Compare%20%E2%80%94%20is%20your%20intuition%20better%20than%20nearest-neighbor%3F%0A%0A%20%20%20%20*Built%20with%20%5Bwigglystuff%5D(https%3A%2F%2Fgithub.com%2Fkoaning%2Fwigglystuff)%20%2B%20%5Bmarimo%5D(https%3A%2F%2Fmarimo.io)*%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.hstack(%5B%0A%20%20%20%20%20%20%20%20mo.md(%22%23%23%23%20%E2%9C%8F%EF%B8%8F%20Excalidraw%20Whiteboard%22)%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(draw)%3A%0A%20%20%20%20draw%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%23%20How%20It%20Works%0A%0A%20%20%20%20This%20notebook%20combines%20**reactive%20computation**%20with%20a%20**freeform%20whiteboard**%3A%0A%0A%20%20%20%201.%20**Left**%3A%20The%20nearest-neighbor%20TSP%20algorithm%20runs%20reactively%20%E2%80%94%20drag%20the%20slider%2C%20the%20path%20updates%20instantly%0A%20%20%20%202.%20**Right**%3A%20An%20embedded%20Excalidraw%20canvas%20for%20sketching%2C%20annotation%2C%20and%20freeform%20exploration%0A%20%20%20%203.%20**Export**%3A%20Use%20Excalidraw's%20built-in%20export%20(top-left%20menu%20%E2%86%92%20%22Export%20to%20image%22)%20to%20save%20your%20sketches%0A%0A%20%20%20%20The%20Excalidraw%20widget%20syncs%20its%20state%20back%20to%20Python%20via%20the%20%60scene%60%20traitlet%2C%0A%20%20%20%20so%20you%20can%20programmatically%20access%20every%20element%20you%20draw.%0A%0A%20%20%20%20%23python%20%23engineering%20%23travelingsalesman%20%23excalidraw%20%23opensource%0A%20%20%20%20%22%22%22)%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