StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The question is incredibly difficult to understand.</p> <blockquote> <p>Is there a way to (conveniently) program the number of elements and their associated conditions based on an earlier computation?</p> </blockquote> <p>The problem is "program" is not really an understandable verb in this sentence, because a human programs a computer, or programs a VCR, but you can't "program a number". So I don't understand what you are trying to say here.</p> <p>But I can give you code review, and maybe through code review I can understand the question you are asking.</p> <h2>Unsolicited code review</h2> <p>It sounds like you are trying to solve a maze by eliminating dead ends, maybe.</p> <p>What your code actually does is:</p> <ol> <li><p>Generate a list of cells that are not dead ends or adjacent to dead ends, called <code>filtered</code></p></li> <li><p>Generate a sequence of adjacent cells from step 1, <code>sequences</code></p></li> <li><p>Concatenate four such adjacent sequences into a route.</p></li> </ol> <p><strong>Major</strong> problem: this only works if a correct route is exactly eight tiles long! Try to solve this maze:</p> <pre> [E]-[ ]-[ ]-[ ] | [ ]-[ ]-[ ]-[ ] | [ ]-[ ]-[ ]-[ ] | [ ]-[ ]-[ ]-[ ] | [ ]-[ ]-[ ]-[E] </pre> <p>So, working backwards from the code review, it sounds like your question is:</p> <blockquote> <p>How do I generate a list if I don't know how long it is beforehand?</p> </blockquote> <h2>Solutions</h2> <p>You can solve a maze with a search (DFS, BFS, A*).</p> <pre><code>import Control.Monad -- | Maze cells are identified by integers type Cell = Int -- | A maze is a map from cells to adjacent cells type Maze = Cell -> [Cell] maze :: Maze maze = ([[1], [0,2,5], [1,3], [2], [5], [4,6,1,9], [5,7], [6,11], [12], [5,13], [9], [7,15], [8,16], [14,9,17], [13,15], [14,11], [12,17], [13,16,18], [17,19], [18]] !!) -- | Find paths from the given start to the end solve :: Maze -> Cell -> Cell -> [[Cell]] solve maze start = solve' [] where solve' path end = let path' = end : path in if start == end then return path' else do neighbor <- maze end guard (neighbor `notElem` path) solve' path' neighbor </code></pre> <p>The function <code>solve</code> works by depth-first search. Rather than putting everything in a single list comprehension, it works recursively.</p> <ol> <li><p>In order to find a path from <code>start</code> to <code>end</code>, if <code>start /= end</code>,</p></li> <li><p>Look at all cells adjacent to the end, <code>neighbor <- maze end</code>,</p></li> <li><p>Make sure that we're not backtracking over a cell <code>guard (negihbor `notElem` path)</code>,</p></li> <li><p>Try to find a path from <code>start</code> to <code>neighbor</code>.</p></li> </ol> <p>Don't try to understand the whole function at once, just understand the bit about recursion.</p> <h2>Summary</h2> <p>If you want to find the route from cell 0 to cell 19, recurse: We know that cell 18 and 19 are connected (because they are directly connected), so we can instead try to solve the problem of finding a route from cell 0 to cell 18.</p> <p>This is recursion.</p> <h3>Footnotes</h3> <p>The guard,</p> <pre><code>someCondition a == True </code></pre> <p>Is equivalent to,</p> <pre><code>someCondition a </code></pre> <p>And therefore also equivalent to,</p> <pre><code>(someCondition a == True) == True </code></pre> <p>Or,</p> <pre><code>(someCondition a == (True == True)) == (True == (True == True)) </code></pre> <p>Or,</p> <pre><code>someCondition a == (someCondition a == someCondition a) </code></pre> <p>The first one, <code>someCondition a</code>, is fine.</p> <h3>Footnote about <code>do</code> notation</h3> <p>The <code>do</code> notation in the above example is equivalent to list comprehension,</p> <pre><code>do neighbor <- maze end guard (neighbor `notElem` path) solve' path' neighbor </code></pre> <p>The equivalent code in list comprehension syntax is,</p> <pre><code>[result | neighbor <- maze end, neighbor `notElem` path, result <- solve' path' neighbor] </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload