Icosahedron Implementation
Icosahedron Implementation[from NumberOfKeystrokes, talking about whether "most of the work" is in finding solutions for problems or in implementing those found solutions]
Let's use the GeographyExample. I attacked it with code first and ran into several dead ends. I stepped back, drew some pictures, did some math, drew some more pictures and finally found a solution to the problem. Typing in the solution took much less effort than solving the problem.
-- EH
To answer this challenge, I reread the GeographyExample. I must admit I didn't check the word "equilateral" at the first time I read it (English is not my native tongue) - I checked it now and was very surprised, because I know that for this problem, the only sensible numbers of equilateral triangles you can stick together are 5 or 6. So, the only sensible way of laying out the triangles is to make a kind-of stretched-out icosahedron, which is the shape formed by 5-triangles-a-corner. All this thinking was instantaneous for me, but maybe I'm good at math / geometry.
Now, the relations between the triangles within a side of the icosahedron are relatively regular, whereas the relations between the sides of the icosahedron are both quite hard to express algorithmically and relatively few. So I (again quite instantly) arrived at the conclusion that the relations between the sides are worth writing out in a database / data structure explicitly.
Now begins the bulk of coding, which in my experience takes most of the time, and that has little to do with solving the geometrical problem. Which representation to choose for the objects? How to manipulate them? What API should they provide? How to find shortest paths efficiently in this (highly plane-like) environment?
Not surprisingly, most of the GeographyExample page is talk about this. And that's the phase of implementation for me.
So, you have it your way, I seem to have it mine.
The problem I needed to solve was how to generate that data structure. I could have typed in all of the elements and their relationships for a single map of a given size (which would have required a great number of keystrokes for any reasonably sized map), but instead I worked out an algorithm to produce the elements and their relationships for any map size (which required considerably fewer keystrokes but more mental effort.) -- EH
I don't think you could beat the encoding of an icosahedron by a table with an algorithm. Please note that I, too, ended up doing algorithmically the movements within a side of the icosahedron; please show me your code, here is the encoding of an icosahedron as data (every side is represented by a tuple of adjacent side numbers (sorry, the indexing starts at 1)):
ico_rel = [(2,5,6), (1,3,8), (2,4,10), (3,5,12), (4,1,14),
(1,7,15), (6,8,16), (2,7,9), (8,10,17), (3,9,11),
(10,12,18), (4,11,13), (12,14,19), (5,13,15), (6,14,20),
(7,17,20), (9,16,18), (11,17,19), (13,18,20), (15,16,19)]
Please note that my solution, too, works for any scale by changing the number of triangles within a side of the icosahedron. I took the problem literally and modeled an icosahedron with 100 triangles on every side (in rows of 1, 3, 5, ..., 19 triangles), but you could put in any number of rows, so my solution is level with yours in that way. Please also note that I'm not putting the adjacency information for the triangles within a side in a database at all - it's not feasible, because those relations are very regular and fast to calculate.
I wrote the code above while modeling an icosahedron in my head. I could have done the same on paper, but the work would have been the same, and I would have had to put that into code separately, which I now didn't have to do.
But please, let me see your code! -- PK
I emailed it to you. -- EH
It took me a while to figure out what the data above means. I need a map that my game units can interact with. The code solution I have contains several classes: a Map that contains 20 Sides, where each Side is a Triangle that contains smaller Triangles (the cells), each Triangle has 3 Edges, etc. My algorithm generates the neighbor relationships for every cell, so a unit can be given a movement command and ask its current cell where that movement should take it. How do you do the adjancency calculations between cells on different Sides? That was the big problem I needed to solve. -- EH
Ta-ta, you seem to have generated an OO solution even though the problem explicitly stated that the design should be procedural or database-driven. (Of course, it's stupid to have requirements like that.) Well, anyway, here is the routine that finds the adjacent cells for any given cell. Each cell is represented by a (side, row, column) triple, which are all indexed from 1. For the solution to work, I had to rearrange the icosahedron data so that the edges of a side are always enumerated clockwise (looking from outside the icosahedron), so I put the new data here also:
ico_rel = [(0, 0, 0),
(5, 2, 6), (1, 3, 8), (2, 4, 10), (3, 5, 12), (4, 1, 14),
(1, 7, 15), (6, 8, 16), (2, 9, 7), (8, 10, 17), (3, 11, 9),
(10, 12, 18), (4, 13, 11), (12, 14, 19), (5, 15, 13), (14, 6, 20),
(7, 17, 20), (9, 18, 16), (11, 19, 17), (13, 20, 18), (15, 16, 19)]
def adjacent_tricells( rows, tri ):
side, row, col = tri
if not col % 2:
return ( (side, row - 1, col - 1),
(side, row, col - 1),
(side, row, col + 1) )
else:
return ( crosscheck( rows, side, row + 1, col + 1 ),
crosscheck( rows, side, row, col + 1 ),
crosscheck( rows, side, row, col - 1 ) )
def crosscheck( rows, side, row, col ):
if col < 1:
nside = ico_rel[side][0]
nrow, ncol = tri_over( rows, edgeof( side, nside ),
rows - row + 1 )
elif col >= row * 2:
nside = ico_rel[side][1]
nrow, ncol = tri_over( rows, edgeof( side, nside ), row )
elif row > rows:
nside = ico_rel[side][2]
crosspt = (rows * 2 - col + 2) / 2
nrow, ncol = tri_over( rows, edgeof( side, nside ), crosspt )
else:
return (side, row, col)
return (nside, nrow, ncol)
def edgeof( srcside, dstside ):
if ico_rel[dstside][0] == srcside: return 0
elif ico_rel[dstside][1] == srcside: return 1
elif ico_rel[dstside][2] == srcside: return 2
else: assert False
def tri_over( rows, edge, crosspt ):
counterpt = rows - crosspt + 1
return [ (crosspt, 1),
(counterpt, counterpt * 2 - 1),
(rows, crosspt * 2 - 1) ][edge]
[outdated comment:]
By the way, your reluctance to show your code leaves me suspecting about whether you have actually written any code. Maybe you skipped the hard work, the implementation? My fellow programmer was like that. He wouldn't actually implement anything, "because I already know I could do that". But if you try measuring the time programming takes, implementation almost always takes the most time. I happened to have a clock handy when writing down this code: it took approximately 45 minutes. How about you? Could you please show me your code?
Ah, the GeographyExample page was a challenge to TopMind. My solution (of course) used an OO implementation. Not only do I have code, I have unit tests. The source is too big to put on a wiki page. I'll upload it to my web site tonight and leave a link. My source is in Java. What is yours in? -- EricHodges
Ah okay, I didn't know about the historical details :) funnily, because I made this in a procedural way, it still hasn't anything to do with tables...
My solution is in Python. I coded a unit test, because I guessed that would be the next thing to ask. It's actually a unit test of the icosahedron data, not the routines; I'll make a separate unit test for that. Here's the code:
from ico import * def nextside( refside, prevside ): return ico_rel[refside][(edgeof( prevside, refside ) + 1) % 3] def test_symmetry( side ): for nbr in ico_rel[side]: assert side in ico_rel[nbr] def test_circ( side ): for d in range( 3 ): curside = side nside = ico_rel[side][d] for i in range( 5 ): curside, nside = nside, nextside( nside, curside ) assert curside == side def test(): for side in range( 1, 21 ): test_symmetry( side ) test_circ( side ) if __name__ == '__main__': test()This code took approx. 25 minutes to write.
Yes, I am very interested in your solution! Please leave the link on this page when you're done. -- PanuKalliokoski
Cool, but you're still only dealing with the 20 sides (if I understand your code). I need to be able to move game units from one cell to another, sometimes within a side, sometimes from one side to another. -- EH
No, you must have misunderstood the code. See this excerpt of using the code:
[atehwa@humma ~/proj/icosa]$ python Python 2.3.2 (#2, Oct 6 2003, 08:02:06) [GCC 3.3.2 20030908 (Debian prerelease)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> from ico import * >>> adjacent_tricells( rows=3, tri=(1, 1, 1) ) ((1, 2, 2), (2, 1, 1), (5, 1, 1)) >>> adjacent_tricells( rows=3, tri=(1, 2, 2) ) ((1, 1, 1), (1, 2, 1), (1, 2, 3)) >>> adjacent_tricells( rows=3, tri=(1, 2, 3) ) ((1, 3, 4), (2, 2, 1), (1, 2, 2)) >>> adjacent_tricells( rows=3, tri=(2, 2, 1) ) ((2, 3, 2), (2, 2, 2), (1, 2, 3)) >>> adjacent_tricells( rows=3, tri=(2, 3, 2) ) ((2, 2, 1), (2, 3, 1), (2, 3, 3)) >>> adjacent_tricells( rows=3, tri=(2, 3, 1) ) ((8, 3, 1), (2, 3, 2), (1, 3, 5)) >>> adjacent_tricells( rows=3, tri=(8, 3, 1) ) ((7, 1, 1), (8, 3, 2), (2, 3, 1)) >>> adjacent_tricells( rows=3, tri=(7, 1, 1) ) ((7, 2, 2), (8, 3, 1), (6, 1, 1))As you can see, moving into adjacent cells sometimes changes the side (the first number of the tricell triple) sometimes doesn't. I chose the value 3 for rows, because that doesn't make it too cumbersome to move over a side triangle by triangle. The normal movement within a side is handled directly in adjacent_tricells (in the if: block) and in crosscheck (in the else: block). The rest of the code is for crossing the icosahedron edges.
By the way, here is the unit test for the routines (namely adjacent_tricells); it took exactly 13 minutes to code:
from ico import *
def test_tricell( rows, tri ):
side, row, col = tri
assert side > 0 and side <= 20
assert row > 0
assert col > 0
assert row <= rows
assert col < rows * 2
def test_neighbours( rows, tri ):
for nbr in adjacent_tricells( rows, tri ):
assert tri in adjacent_tricells( rows, nbr )
test_tricell( rows, nbr )
def test():
for tri in [ (1, 1, 1), (1, 2, 2), (1, 2, 1), (5, 3, 3),
(14, 1, 1), (14, 4, 7), (11, 3, 5),
(11, 3, 4), (20, 5, 1) ]:
for rows in range( tri[1], 6 ):
test_tricell( rows, tri )
test_neighbours( rows, tri )
if __name__ == '__main__': test()
The reason I count the times it takes to implement various things is that I am testing the hypothesis that amount of work corresponds roughly to the amount of keystrokes. I also contrast this with the time it took me to come up with a "solution", which was approximately one and a half minutes, including the time to check the word "equilateral" in the dictionary. -- PanuKalliokoski
But if you try measuring the time programming takes, implementation almost always takes the most time.
Again, our experiences differ. Implementation is the bottleneck only when I'm implementing something very similar to something I've implemented before, which is blessedly rare. I spend most of my time thinking about how to solve the problem. This time may be interleaved with implementation. I may write a line of code, then think a bit, then write another line. Perhaps this has something to do with my typing speed, also. 22 years of chat room arguments have left me with prodigious typing skills. -- EricHodges
Well, now I've looked at your implementation. The main differences between our implementations are:
In your comment above, you seem to be drawing back your distinction between "finding a solution" and "design". "Finding a solution" is, in my book, something that you cannot interleave with implementation, because before you've found a solution, you don't know just what you're trying to implement. Design, however, is a continuous process that goes hand in hand with the implementation. Liquid thinking plays a major part in "finding a solution", whereas crystallised thinking plays a major part in "design".
Anyway, whatever these be called, I think only the former task (the thinking before which you don't know what you're implementing) is not related to the NumberOfKeystrokes, and the latter task (the thinking in which you put the concepts and details of the implementation in their place) is very much proportional to the NumberOfKeystrokes. Because this has already been discussed between us a lot, I'm content with the result that our experiences differ. However, you must be very lucky if you mostly tackle novel problems. This problem, for instance, was not new to me at all: even though I've never implemented an icosahedron-shaped world before, I have implemented worlds that consist of planes (of square cells) knit together.
The directional movement comes from the unit tests. The unit tests come from the requirements. This map is going to be used in a game/simulation. Game units (armies, workers, messages, etc.) will be moved by the user.
Class definition overhead isn't really overhead anymore. I use Eclipse. It creates class definitions for me once I click a few menus and type in a name.
I must be a very bad problem solver. I spent several hours over 3 days playing with pen and paper to solve the fundamental problem of how to move between map cells. Once I understood the geometry, implementing the solution took much less time.
In my book, solutions are often found in stages. I may find part of a solution, implement that, find another part in the context of the previous part, implement that, etc., through several iterations.
-- EricHodges
PassiveCodeGeneration is a design smell. But I'm sorry about what I said about bad problem solving, it was quite irrelevant. Otherwise, I think most of our points have been made. -- PK
No offense taken. I may be spectacularly bad at solving this sort of problem. I don't consider letting the IDE create class definitions for me to be a design smell at all, though. It's a labor saving device. -- EH
EditText of this page
(last edited December 17, 2003)
or FindPage with title or text search