<div class="gmail_quote">On Tue, Jun 1, 2010 at 19:54, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:SeeWebsiteForEmail@erdani.org">SeeWebsiteForEmail@erdani.org</a>></span> wrote:<br><br>> I thought about this some more, and it's more difficult and more
interesting than I thought.<br><br>Yeah, that's why I proposed it as a challenge. You guys sure seem to like this :)<br>What's interesting, is that it may even be useful :)<br><br><br>It's ok to store positions in ulong objects. Most uses of infinite<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div class="h5"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
range combinations use only the first few elements; the computation<br>
will anyway take a very, very long time when any of the ranges<br>
overflows a ulong.<br></blockquote></blockquote></div></div></blockquote><div><br>Quite... <br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div><div class="h5">
<br></div></div>
I still haven't understood your explanation, but I think I figured a different way to reach the same solution. The idea is to crawl the space by adding layers on top of a hypercube of increasing side, starting from the origin corner.<br>
</blockquote><div><br>Like this?<br><br>01234<br>11234<br>22234<br>33334<br>44444<br><br>where you have layer #0, #1, ...<br><br>In fact, any method to iterate on a finite but growing space without going onto the already produced values is OK. You could iterate on an hypercube, then duplicate it to make it n times bigger and recurse:<br>
<br>01 22 3333<br>11 22 3333<br>22 22 3333<br>22 22 3333<br>3333<br>3333 ...<br>3333<br>3333<br><br>I think your solution is viable, because you always iterate on 'square' shapes, that's a good idea. Its only drawback is that the elements are produced in a less natural order, but really, who cares: you just want to take a finite part of an infinite range without closing any door while doing so. <br>
Going full diagonal is more difficult: you must find a way to peel of the slices.<br><br>I encountered this while reading some on Haskell and enumerating infinite ranges, but the only implentation I know of for diagonals is here:<br>
<a href="http://hackage.haskell.org/packages/archive/level-monad/0.3.1/doc/html/Control-Monad-Levels.html">http://hackage.haskell.org/packages/archive/level-monad/0.3.1/doc/html/Control-Monad-Levels.html</a><br><br>Related to this, I've something that takes 'hyperslices' from ranges of
ranges of ... (of whatever rank), but only<br>
'vertical' or 'horizontal' (perpendicular to the normal basis of ranges of ranges...)<br><br>I also have a n-dim generalization of take: take(rangeOfRanges, 2,3,4, ...) and for drop and slice.<br>I think it's doable to preduce something akin to your layers than way, or maybe my suggestion on blocks. A combination of takes and drops should produce<br>
finite cubic shapes that can then be iterated.<br><br><br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
This is an absolutely awesome problem. </blockquote><div><br>Man, don't you have some boring stuff to do instead?<br><br>I also found the (simple?) problem to enumerate a range of ranges to be more interesting than I thought.<br>
Given a range of ranges ... of ranges, of whatever rank, recursively enumerate it:<br><br>[[a,b,c],[d,e,f],[g,h,i]]<br><br>produce:<br><br>(a,0,0),(b,0,1), (c,0,2),(d,1,0), ...<br><br>the coordinates of each element, if you will. I have a working version now, but it sure taught me that my vision of recursion was flawed.<br>
<br><br><br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">I attach an implementation for two ranges. It's quite a bit more messy than I'd hope, so generalization to n ranges should be preceded by cleaning up the abstractions used. I think your solution already has said cleanups!<br>
</blockquote><div><br>It's good if you can make it to more than two ranges, but I think 2 is already quite useful.<br> <br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
The output of the program is:<br>
<br>
0 Tuple!(uint,uint)(0, 0)<br>
1 Tuple!(uint,uint)(0, 1)<br>
2 Tuple!(uint,uint)(1, 1)<br>
3 Tuple!(uint,uint)(1, 0)<br>
4 Tuple!(uint,uint)(0, 2)<br>
5 Tuple!(uint,uint)(1, 2)<br>
6 Tuple!(uint,uint)(2, 2)<br>
7 Tuple!(uint,uint)(2, 0)<br>
8 Tuple!(uint,uint)(2, 1)<br>
9 Tuple!(uint,uint)(0, 3)<br>
10 Tuple!(uint,uint)(1, 3)<br>
11 Tuple!(uint,uint)(2, 3)<br>
12 Tuple!(uint,uint)(0, 4)<br>
13 Tuple!(uint,uint)(1, 4)<br>
14 Tuple!(uint,uint)(2, 4)<br><font color="#888888">
<br>
<br>
</font></blockquote><div>Seems good to me. I see the layers, like in the Matrix.<br>If you ever put that in Phobos, make it a secondary function compared to a standard combination, or use a policy to let the user dicide to iterate along layers. Most of the time, you just want the standard 'digit-like' way to iterate on n ranges.<br>
<br>I'll have a look at your code.<br><br>Philippe<br><br></div></div>