Last active
January 19, 2021 13:20
-
-
Save pankgeorg/e3f0ea302fa4fa081034451ba68fde8a to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html lang="en"> | |
| <head> | |
| <meta name="viewport" content="width=device-width" /> | |
| <title>⚡ Pluto.jl ⚡</title> | |
| <meta charset="utf-8" /> | |
| <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/fonsp/Pluto.jl@0.12.18/frontend/editor.css" type="text/css" /> | |
| <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/fonsp/Pluto.jl@0.12.18/frontend/treeview.css" type="text/css" /> | |
| <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/fonsp/Pluto.jl@0.12.18/frontend/hide-ui.css" type="text/css" /> | |
| <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/codemirror@5.58.1/lib/codemirror.min.css" type="text/css" /> | |
| <script src="https://cdn.jsdelivr.net/npm/codemirror@5.59.0/lib/codemirror.min.js" defer></script> | |
| <script src="https://cdn.jsdelivr.net/npm/codemirror@5.58.1/mode/julia/julia.min.js" defer></script> | |
| <style id="MJX-SVG-styles"> | |
| mjx-container[jax="SVG"] { | |
| direction: ltr; | |
| } | |
| mjx-container[jax="SVG"] > svg { | |
| overflow: visible; | |
| } | |
| mjx-container[jax="SVG"] > svg a { | |
| fill: blue; | |
| stroke: blue; | |
| } | |
| mjx-assistive-mml { | |
| position: absolute !important; | |
| top: 0px; | |
| left: 0px; | |
| clip: rect(1px, 1px, 1px, 1px); | |
| padding: 1px 0px 0px 0px !important; | |
| border: 0px !important; | |
| display: block !important; | |
| width: auto !important; | |
| overflow: hidden !important; | |
| -webkit-touch-callout: none; | |
| -webkit-user-select: none; | |
| -khtml-user-select: none; | |
| -moz-user-select: none; | |
| -ms-user-select: none; | |
| user-select: none; | |
| } | |
| mjx-assistive-mml[display="block"] { | |
| width: 100% !important; | |
| } | |
| mjx-container[jax="SVG"][display="true"] { | |
| display: block; | |
| text-align: center; | |
| margin: 1em 0; | |
| } | |
| mjx-container[jax="SVG"][display="true"][width="full"] { | |
| display: flex; | |
| } | |
| mjx-container[jax="SVG"][justify="left"] { | |
| text-align: left; | |
| } | |
| mjx-container[jax="SVG"][justify="right"] { | |
| text-align: right; | |
| } | |
| g[data-mml-node="merror"] > g { | |
| fill: red; | |
| stroke: red; | |
| } | |
| g[data-mml-node="merror"] > rect[data-background] { | |
| fill: yellow; | |
| stroke: none; | |
| } | |
| g[data-mml-node="mtable"] > line[data-line] { | |
| stroke-width: 70px; | |
| fill: none; | |
| } | |
| g[data-mml-node="mtable"] > rect[data-frame] { | |
| stroke-width: 70px; | |
| fill: none; | |
| } | |
| g[data-mml-node="mtable"] > .mjx-dashed { | |
| stroke-dasharray: 140; | |
| } | |
| g[data-mml-node="mtable"] > .mjx-dotted { | |
| stroke-linecap: round; | |
| stroke-dasharray: 0,140; | |
| } | |
| g[data-mml-node="mtable"] > g > svg { | |
| overflow: visible; | |
| } | |
| [jax="SVG"] mjx-tool { | |
| display: inline-block; | |
| position: relative; | |
| width: 0; | |
| height: 0; | |
| } | |
| [jax="SVG"] mjx-tool > mjx-tip { | |
| position: absolute; | |
| top: 0; | |
| left: 0; | |
| } | |
| mjx-tool > mjx-tip { | |
| display: inline-block; | |
| padding: .2em; | |
| border: 1px solid #888; | |
| font-size: 70%; | |
| background-color: #F8F8F8; | |
| color: black; | |
| box-shadow: 2px 2px 5px #AAAAAA; | |
| } | |
| g[data-mml-node="maction"][data-toggle] { | |
| cursor: pointer; | |
| } | |
| mjx-status { | |
| display: block; | |
| position: fixed; | |
| left: 1em; | |
| bottom: 1em; | |
| min-width: 25%; | |
| padding: .2em .4em; | |
| border: 1px solid #888; | |
| font-size: 90%; | |
| background-color: #F8F8F8; | |
| color: black; | |
| } | |
| foreignObject[data-mjx-xml] { | |
| font-family: initial; | |
| line-height: normal; | |
| overflow: visible; | |
| } | |
| .MathJax path { | |
| stroke-width: 3; | |
| } | |
| </style> | |
| </head> | |
| <body> | |
| <main><preamble><button class="runallchanged" title="Save and run all changed cells"><span></span></button></preamble><pluto-notebook id="a837e842-5a58-11eb-2239-d5ba50a5f4b6"><pluto-cell class="code_folded " id="5b2ee40e-a2b8-11ea-0fef-c35fe6918860"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><h1>The tower of Hanoi</h1> | |
| <p>The tower of hanoi is a famous puzzle.</p> | |
| <p><img src="https://upload.wikimedia.org/wikipedia/commons/0/07/Tower_of_Hanoi.jpeg" alt="setup of the tower of a hanoi"></p> | |
| <p>The game consists of three rods with disks stacked on top of them. The puzzle will start with all disks in a stack on one of the rods (like in the picture). The goal is to move all the discs to a single stack on different rod.</p> | |
| <p>To move the disks, you have to follow the following rules:</p> | |
| <ul> | |
| <li><p>You can move only one disk at a time.</p> | |
| </li> | |
| <li><p>For each move, you have to take the upper disk from one of the stacks, and place it on top of another stack or empty rod.</p> | |
| </li> | |
| <li><p>You cannot place a larger disk on top of a smaller disk.</p> | |
| </li> | |
| </ul> | |
| <p>This notebook will define a Julia implementation of the puzzle. It's up to you to write an algorithm that solves it.</p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">6.6 ms</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="95fbd0d2-a2b9-11ea-0682-fdf783251797"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><h2>Setting up the game pieces</h2> | |
| <p>What does a Julia implementation look like? We're not really interested in writing code that will manipulate physical disks. Our final goal is a function that will give us a <em>recipe</em> to solve the tower of hanoi, which is just a list of moves to make. Because of that, we can use a lot of abstraction in our implementation, and keep the data structures as simple as possible.</p> | |
| <p>To start, we have to define some representation of the disks and the stacks. The disks have one important property, which is that they are ordered. We can use integers to represent them.</p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">4.9 ms</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="620d6834-a2ba-11ea-150a-2132bb54e4b3"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="scroll_y " mime="text/plain"><assignee>num_disks</assignee><div><pre><code>8</code></pre></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">num_disks = 8</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">200 ns</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="35ada214-a32c-11ea-0da3-d5d494b28467"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><p>(Side note: the number of disks is arbitrary. When testing your function, you may want to set it to 1 or 2 to start.)</p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">7.2 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="7243cc8e-a2ba-11ea-3f29-99356f0cdcf4"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="scroll_y " mime="text/plain"><assignee>all_disks</assignee><div><pre><code>1:8</code></pre></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">all_disks = 1:num_disks</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">100 ns</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="7e1ba2ac-a2ba-11ea-0134-2f61ed75be18"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><p>A single stack can be represented as an array with all the disks in it. We will list them from top to bottom.</p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">5.5 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="43781a52-a339-11ea-3803-e56e2d08aa83"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="" mime="application/vnd.pluto.tree+object"><assignee>first_stack</assignee><div><jltree class="collapsed">Int64<jlarray class="Array"><r><k>1</k><v><pre>1</pre></v></r><r><k>2</k><v><pre>2</pre></v></r><r><k>3</k><v><pre>3</pre></v></r><r><k>4</k><v><pre>4</pre></v></r><r><k>5</k><v><pre>5</pre></v></r><r><k>6</k><v><pre>6</pre></v></r><r><k>7</k><v><pre>7</pre></v></r><r><k>8</k><v><pre>8</pre></v></r></jlarray></jltree></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">first_stack = collect(all_disks)</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">2.6 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="b648ab70-a2ba-11ea-2dcc-55b630e44325"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><p>Now we have to make three of those. </p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">7.9 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="32f26f80-a2bb-11ea-0f2a-3fc631ada63d"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="" mime="application/vnd.pluto.tree+object"><assignee>starting_stacks</assignee><div><jltree class="collapsed">Array{Any,1}<jlarray class="Array"><r><k>1</k><v><jltree class="collapsed">Any<jlarray class="Array"><r><k>1</k><v><pre>1</pre></v></r><r><k>2</k><v><pre>2</pre></v></r><r><k>3</k><v><pre>3</pre></v></r><r><k>4</k><v><pre>4</pre></v></r><r><k>5</k><v><pre>5</pre></v></r><r><k>6</k><v><pre>6</pre></v></r><r><k>7</k><v><pre>7</pre></v></r><r><k>8</k><v><pre>8</pre></v></r></jlarray></jltree></v></r><r><k>2</k><v><jltree class="collapsed">Any<jlarray class="Array"></jlarray></jltree></v></r><r><k>3</k><v><jltree class="collapsed">Any<jlarray class="Array"></jlarray></jltree></v></r></jlarray></jltree></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">starting_stacks = [first_stack, [], []]</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">59.8 ms</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="e347f1de-a2bb-11ea-06e7-87cca6f2a240"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><h2>Defining the rules</h2> | |
| <p>Now that we have our "game board", we can implement the rules.</p> | |
| <p>To start, we make two functions for states. A state of the game is just an array of stacks.</p> | |
| <p>We will define a function that checks if a state is okay according to the rules. To be legal, all the stacks should be in the correct order, so no larger disks on top of smaller disks. </p> | |
| <p>Another good thing to check: no disks should have appeared or disappeared since we started!</p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">14.2 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="512fa6d2-a2bd-11ea-3dbe-b935b536967b"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="scroll_y " mime="text/plain"><assignee></assignee><div><pre><code>islegal (generic function with 1 method)</code></pre></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">function islegal(stacks) | |
| order_correct = all(issorted, stacks) | |
| #check if we use the same disk set that we started with | |
| disks_in_state = sort([disk for stack in stacks for disk in stack]) | |
| disks_complete = disks_in_state == all_disks | |
| order_correct && disks_complete | |
| end</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">74.5 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="c56a5858-a2bd-11ea-1d96-77eaf5e74925"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><p>Another function for states: check if we are done! We can assume that we already checked if the state was legal. So we know that all the disks are there and they are ordered correctly. To check if we are finished, we just need to check if the last stack contains all the disks.</p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">6.1 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="d5cc41e8-a2bd-11ea-39c7-b7df8de6ae3e"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="scroll_y " mime="text/plain"><assignee></assignee><div><pre><code>iscomplete (generic function with 1 method)</code></pre></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">function iscomplete(stacks) | |
| last(stacks) == all_disks | |
| end</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">18.8 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="53374f0e-a2c0-11ea-0c91-97474780721e"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><p>Now the only rules left to implement are the rules for moving disks. </p> | |
| <p>We could implement this as another check on states, but it's easier to just write a legal <code>move</code> function. Your solution will specify moves for the <code>move</code> function, so this will be the only way that the stacks are actually manipulated. That way, we are sure that nothing fishy is happening.</p> | |
| <p>We will make our <code>move</code> function so that its input consists of a state of the game, and instructions for what to do. Its output will be the new state of the game.</p> | |
| <p>So what should those instructions look like? It may seem intuitive to give a <em>disk</em> that should be moved, but that's more than we need. After all, we are only allowed to take the top disk from one stack, and move it to the top of another. So we only have to say which <em>stacks</em> we are moving between.</p> | |
| <p>(Note that the <code>move</code> function is okay with moving a larger disk on top of a smaller disk. We already implemented that restriction in <code>islegal</code>.)</p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">16.4 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="e915394e-a2c0-11ea-0cd9-1df6fd3c7adf"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="scroll_y " mime="text/plain"><assignee></assignee><div><pre><code>move (generic function with 1 method)</code></pre></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">function move(stacks, source::Int, target::Int) | |
| #check if the from stack if not empty | |
| if isempty(stacks[source]) | |
| error("Error: attempted to move disk from empty stack") | |
| end | |
| new_stacks = deepcopy(stacks) | |
| disk = popfirst!(new_stacks[source]) #take disk | |
| pushfirst!(new_stacks[target], disk) #put on new stack | |
| return new_stacks | |
| end</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">54.6 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="87b2d164-a2c4-11ea-3095-916628943879"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><h2>Solving the problem</h2> | |
| <p>We have implemented the game pieces and the rules, so you can start working on your solution.</p> | |
| <p>To do this, you can fill in the <code>solve(stacks)</code> function. This function should give a solution for the given <code>stacks</code>, by moving all the disks from stack 1 to stack 3.</p> | |
| <p>As output, <code>solve</code> should give a recipe, that tells us what to do. This recipe should be an array of moves. Each moves is a <code>(source, target)</code> tuple, specifying from which stack to which stack you should move.</p> | |
| <p>For example, it might look like this:</p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">19.4 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="29b410cc-a329-11ea-202a-795b31ce5ad5"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="scroll_y " mime="text/plain"><assignee></assignee><div><pre><code>wrong_solution (generic function with 1 method)</code></pre></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">function wrong_solution(stacks)::Array{Tuple{Int, Int}} | |
| return [(1,2), (2,3), (2,1), (1,3)] | |
| end</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">25.3 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="ea24e778-a32e-11ea-3f11-dbe9d36b1011"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><p>Now you can work on building an actual solution. Some tips:</p> | |
| <ul> | |
| <li><p><code>solve(stacks)</code> can keep track of the board if you want, but it doesn't have to.</p> | |
| </li> | |
| <li><p>The section below will actually run your moves, which is very useful for checking them.</p> | |
| </li> | |
| <li><p>If you want, you can change <code>num_disks</code> to 1 or 2. That can be a good starting point.</p> | |
| </li> | |
| </ul> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">14.9 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="010dbdbc-a2c5-11ea-34c3-837eae17416f"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="scroll_y " mime="text/plain"><assignee></assignee><div><pre><code>solve (generic function with 1 method)</code></pre></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">function solve(stacks)::Array{Tuple{Int, Int}} | |
| #what to do? | |
| return [] | |
| end</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">23.2 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="3eb3c4c0-a2c5-11ea-0bcc-c9b52094f660"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><h2>Checking solutions</h2> | |
| <p>This is where we can check a solution. We start with a function that takes our recipe and runs it.</p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">13.0 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="4709db36-a327-11ea-13a3-bbfb18da84ce"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="scroll_y " mime="text/plain"><assignee></assignee><div><pre><code>run_solution (generic function with 2 methods)</code></pre></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">function run_solution(solver::Function, start = starting_stacks) | |
| moves = solver(deepcopy(start)) #apply the solver | |
| all_states = Array{Any,1}(undef, length(moves) + 1) | |
| all_states[1] = starting_stacks | |
| for (i, m) in enumerate(moves) | |
| try | |
| all_states[i + 1] = move(all_states[i], m[1], m[2]) | |
| catch | |
| all_states[i + 1] = missing | |
| end | |
| end | |
| return all_states | |
| end</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">51.7 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="372824b4-a330-11ea-2f26-7b9a1ad018f1"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><p>You can use this function to see what your solution does.</p> | |
| <p>If <code>run_solution</code> tries to make an impossible move, it will give <code>missing</code> from that point onwards. Look at what happens in the <code>wrong_solution</code> version and compare it to the moves in <code>wrong_solution</code>.</p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">10.1 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="d2227b40-a329-11ea-105c-b585d5fcf970"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="" mime="application/vnd.pluto.tree+object"><assignee></assignee><div><jltree class="collapsed">Any<jlarray class="Array"><r><k>1</k><v><jltree class="collapsed">Array{Any,1}<jlarray class="Array"><r><k>1</k><v><jltree class="collapsed">Any<jlarray class="Array"><r><k>1</k><v><pre>1</pre></v></r><r><k>2</k><v><pre>2</pre></v></r><r><k>3</k><v><pre>3</pre></v></r><r><k>4</k><v><pre>4</pre></v></r><r><k>5</k><v><pre>5</pre></v></r><r><k>6</k><v><pre>6</pre></v></r><r><k>7</k><v><pre>7</pre></v></r><r><k>8</k><v><pre>8</pre></v></r></jlarray></jltree></v></r><r><k>2</k><v><jltree class="collapsed">Any<jlarray class="Array"></jlarray></jltree></v></r><r><k>3</k><v><jltree class="collapsed">Any<jlarray class="Array"></jlarray></jltree></v></r></jlarray></jltree></v></r><r><k>2</k><v><jltree class="collapsed">Array{Any,1}<jlarray class="Array"><r><k>1</k><v><jltree class="collapsed">Any<jlarray class="Array"><r><k>1</k><v><pre>2</pre></v></r><r><k>2</k><v><pre>3</pre></v></r><r><k>3</k><v><pre>4</pre></v></r><r><k>4</k><v><pre>5</pre></v></r><r><k>5</k><v><pre>6</pre></v></r><r><k>6</k><v><pre>7</pre></v></r><r><k>7</k><v><pre>8</pre></v></r></jlarray></jltree></v></r><r><k>2</k><v><jltree class="collapsed">Any<jlarray class="Array"><r><k>1</k><v><pre>1</pre></v></r></jlarray></jltree></v></r><r><k>3</k><v><jltree class="collapsed">Any<jlarray class="Array"></jlarray></jltree></v></r></jlarray></jltree></v></r><r><k>3</k><v><jltree class="collapsed">Array{Any,1}<jlarray class="Array"><r><k>1</k><v><jltree class="collapsed">Any<jlarray class="Array"><r><k>1</k><v><pre>2</pre></v></r><r><k>2</k><v><pre>3</pre></v></r><r><k>3</k><v><pre>4</pre></v></r><r><k>4</k><v><pre>5</pre></v></r><r><k>5</k><v><pre>6</pre></v></r><r><k>6</k><v><pre>7</pre></v></r><r><k>7</k><v><pre>8</pre></v></r></jlarray></jltree></v></r><r><k>2</k><v><jltree class="collapsed">Any<jlarray class="Array"></jlarray></jltree></v></r><r><k>3</k><v><jltree class="collapsed">Any<jlarray class="Array"><r><k>1</k><v><pre>1</pre></v></r></jlarray></jltree></v></r></jlarray></jltree></v></r><r><k>4</k><v><pre>missing</pre></v></r><r><k>5</k><v><pre>missing</pre></v></r></jlarray></jltree></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">run_solution(wrong_solution)</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">89.4 ms</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="9173b174-a327-11ea-3a69-9f7525f2e7b4"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="" mime="application/vnd.pluto.tree+object"><assignee></assignee><div><jltree class="collapsed">Any<jlarray class="Array"><r><k>1</k><v><jltree class="collapsed">Array{Any,1}<jlarray class="Array"><r><k>1</k><v><jltree class="collapsed">Any<jlarray class="Array"><r><k>1</k><v><pre>1</pre></v></r><r><k>2</k><v><pre>2</pre></v></r><r><k>3</k><v><pre>3</pre></v></r><r><k>4</k><v><pre>4</pre></v></r><r><k>5</k><v><pre>5</pre></v></r><r><k>6</k><v><pre>6</pre></v></r><r><k>7</k><v><pre>7</pre></v></r><r><k>8</k><v><pre>8</pre></v></r></jlarray></jltree></v></r><r><k>2</k><v><jltree class="collapsed">Any<jlarray class="Array"></jlarray></jltree></v></r><r><k>3</k><v><jltree class="collapsed">Any<jlarray class="Array"></jlarray></jltree></v></r></jlarray></jltree></v></r></jlarray></jltree></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">run_solution(solve)</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">83.2 ms</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="bb5088ec-a330-11ea-2c41-6b8b92724b3b"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><p>Now that we have way to run a recipe, we can check if its output is correct. We will check if all the intermediate states are legal and the final state is the finished puzzle.</p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">5.3 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="10fb1c56-a2c5-11ea-2a06-0d8c36bfa138"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="scroll_y " mime="text/plain"><assignee></assignee><div><pre><code>check_solution (generic function with 2 methods)</code></pre></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">function check_solution(solver::Function, start = starting_stacks) | |
| try | |
| #run the solution | |
| all_states = run_solution(solver, start) | |
| #check if each state is legal | |
| all_legal = all(islegal, all_states) | |
| #check if the final state is is the completed puzzle | |
| complete = (iscomplete ∘ last)(all_states) | |
| all_legal && complete | |
| catch | |
| #return false if we encountered an error | |
| return false | |
| end | |
| end</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">66.0 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="" id="8ea7f944-a329-11ea-22cc-4dbd11ec0610"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="scroll_y " mime="text/plain"><assignee></assignee><div><pre><code>false</code></pre></div></pluto-output><pluto-input><button class="delete_cell" title="Delete cell"><span></span></button><textarea style="display: none;"></textarea><textarea class="init-cm">check_solution(solve)</textarea></pluto-input><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">210 ms</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell><pluto-cell class="code_folded " id="e54add0a-a330-11ea-2eeb-1d42f552ba38"><pluto-shoulder draggable="true" title="Drag to move cell"><button class="foldcode" title="Show/hide code"><span></span></button></pluto-shoulder><pluto-trafficlight></pluto-trafficlight><button class="add_cell before" title="Add cell"><span></span></button><pluto-output class="rich_output " mime="text/html"><assignee></assignee><div><div class="markdown"><p>The <code>solve</code> function doesn't work yet. Keep working on it!</p> | |
| </div></div></pluto-output><pluto-runarea><button class="runcell" title="Run"><span></span></button><span class="runtime">57.5 μs</span></pluto-runarea><button class="add_cell after" title="Add cell"><span></span></button></pluto-cell></pluto-notebook><dropruler></dropruler></main> | |
| <svg id="MJX-SVG-global-cache" style="display: none;"><defs></defs></svg> | |
| </body> | |
| <script> | |
| const cmOptions = { | |
| lineNumbers: true, | |
| mode: "julia", | |
| lineWrapping: true, | |
| viewportMargin: Infinity, | |
| placeholder: "Enter cell code...", | |
| indentWithTabs: true, | |
| indentUnit: 4, | |
| readOnly: "nocursor", | |
| } | |
| document.addEventListener("DOMContentLoaded", () => | |
| document.querySelectorAll(".init-cm").forEach(textArea => { | |
| CodeMirror.fromTextArea(textArea, cmOptions) | |
| }) | |
| ) | |
| </script> | |
| </html> | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment