99 questions/Solutions/92 - Revision history
https://wiki.haskell.org/index.php?title=99_questions/Solutions/92&action=history
Revision history for this page on the wikienMediaWiki 1.19.14+dfsg-1Thu, 30 Mar 2017 00:49:39 GMTWizzup: categorize
https://wiki.haskell.org/index.php?title=99_questions/Solutions/92&diff=61396&oldid=prev
https://wiki.haskell.org/index.php?title=99_questions/Solutions/92&diff=61396&oldid=prev<p>categorize</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 03:45, 10 January 2017</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 26:</td>
<td colspan="2" class="diff-lineno">Line 26:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>This is a simple brute-force solver. This function will permute all assignments of the different node numbers and will then verify that all of the edge differences are different.  This code uses the List Monad.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>This is a simple brute-force solver. This function will permute all assignments of the different node numbers and will then verify that all of the edge differences are different.  This code uses the List Monad.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">[[Category:Programming exercise spoilers]]</ins></div></td></tr>
</table>Tue, 10 Jan 2017 03:45:57 GMTWizzuphttps://wiki.haskell.org/Talk:99_questions/Solutions/92Wapcaplet at 17:07, 15 July 2010
https://wiki.haskell.org/index.php?title=99_questions/Solutions/92&diff=36209&oldid=prev
https://wiki.haskell.org/index.php?title=99_questions/Solutions/92&diff=36209&oldid=prev<p></p>
<p><b>New page</b></p><div>(***) Von Koch's conjecture<br />
<br />
Several years ago I met a mathematician who was intrigued by a problem for which he didn't know a solution. His name was Von Koch, and I don't know whether the problem has been solved since.<br />
<br />
https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p92a.gif<br />
<br />
Anyway the puzzle goes like this: Given a tree with N nodes (and hence N-1 edges). Find a way to enumerate the nodes from 1 to N and, accordingly, the edges from 1 to N-1 in such a way, that for each edge K the difference of its node numbers equals to K. The conjecture is that this is always possible.<br />
<br />
For small trees the problem is easy to solve by hand. However, for larger trees, and 14 is already very large, it is extremely difficult to find a solution. And remember, we don't know for sure whether there is always a solution!<br />
<br />
Write a predicate that calculates a numbering scheme for a given tree. What is the solution for the larger tree pictured below?<br />
<br />
https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p92b.gif<br />
<br />
Solution:<br />
<br />
<haskell><br />
vonKoch edges = do<br />
let n = length edges + 1<br />
nodes <- permutations [1..n]<br />
let nodeArray = listArray (1,n) nodes<br />
let dists = sort $ map (\(x,y) -> abs (nodeArray ! x - nodeArray ! y)) edges<br />
guard $ and $ zipWith (/=) dists (tail dists)<br />
return nodes<br />
</haskell><br />
<br />
This is a simple brute-force solver. This function will permute all assignments of the different node numbers and will then verify that all of the edge differences are different. This code uses the List Monad.</div>Thu, 15 Jul 2010 17:07:01 GMTWapcaplethttps://wiki.haskell.org/Talk:99_questions/Solutions/92