4 ms·

Fascinating and depressing at the same time. Posts like this make me think I'm in the wrong job as if asked to write a similar program, I'd have no idea where t

by Hates_ 17y ago

Fascinating and depressing at the same time. Posts like this make me think I'm in the wrong job as if asked to write a similar program, I'd have no idea where to start. JGC labels this as a "small program", like it was knocked up on a whim :(

jgrahamc 17y ago
It was knocked up on a whim, and it is small, but don't be depressed: it wasn't easy... I had to bang my head against the trigonometry to get it all correct. Although I know the rules of trig, I always have a hard time applying them in the real world because I have a hard time imagining the shapes involved. Ended up drawing little pictures of what was doing on.
- torpor 17y ago
  I think it would be quite interesting to know more about how you approached this problem for solution, than the solutions presented by the program itself .. I didn't really get much of the details about how you'd sorted through this from your post .. perhaps a followup topic? Its really great, btw .. I play with this toy with my son on a regular basis, and found myself just a few days ago wondering what is the maximum number of shapes we can build with the set .. okay, this got a bit screwed up by the addition of another mini-set gifted to my son by a friend, so there is room for improvement in my thinking now that I've learned what you have discovered. Nice job!
  - jgrahamc 17y ago
    I tried to explain how it works in the comments in the code. Probably worth reading them in detail as they do explain the algorithm used. My thought process was something like this (over a number of days grabbing time when I could): Emulate a human selecting pieces and clicking them together. Model pieces as straight lines of the right length. There are two important things: how long the line is and how much it modifies the angle at which the next piece will join. Thus all I need is to keep track of the position of the end of the last piece added and the angle. Spend a while figuring out the trigonometry and getting that code working correctly. To generate the permutations I realized that the process could be split into three parts: 1. Always place the bridge. Since there's one just add it at the end. 2. Separate the straights and curves. Generate all the permutations of clockwise and anticlockwise curved pieces. To do that I used the trick of all 12-bit binary numbers between 0 and 2^12-1. 3. Then insert the straight pieces between the curved pieces in all places possible. Feed each possible track layout into code that builds the track and check that the end pieces match up. Add code to eliminate end pieces that join impossibly (come from the wrong angle), add code to remove duplicates caused by rotation and reflection. Once I got that working I then wrote code in Processing to draw a pretty picture.
    - fhars 17y ago
      You might be able to speed it up considerably by adding 2a. Continue with next iteration unless the turning number of the sequence of curves is a whole number. You add 1/8 to the turning number for each clockwise curve and subtract 1/8 for each CCW (for numerical stability you would rather add of subtract 1 and check for multiples of 8).
dschobel 17y ago
HN is a good place to feel inferior, nothing has ever made me feel more so than: http://news.ycombinator.com/item?id=639976 http://news.ycombinator.com/item?id=639976
Tichy 17y ago
I am genuinely interested: how could you have no idea how to start? Isn't it obvious to check all possible permutations of the 9 pieces (and orientations I suppose, also accounting for duplicate pieces)? I suppose that is what you would be doing even if you didn't have a computer? That shouldn't be too hard. A little harder perhaps to then determine if a given permutation is a closed loop or not, but essentially it should be basic geometry (didn't look at the code). Even if that naive approach would not work, it would at least be a way to start. The remaining sub problems should be less scary to tackle.
anthonyb 17y ago
I did a similar thing with our kids' LILLABO set. Except that rather than build from zero, my algorithm was to start with the smallest possible loop (8 curves - a circle) and add similar parts to both sides until the set was used up. The main criteria for the additions was that they had to translate but not rotate, ie. AC or SS and B, although more complex ones are possible, like BCA vs. SCAS. It doesn't seem to make any difference as long as they translate to the same thing. You should be able to generate all possible loops relatively cheaply, since you're just moving characters around. You might need a separate character for the original circle/curve parts though, to make it possible to find the originals. I never got around to implementing this - it was just an observation while building interesting tracks for my children, but I might have a go...

by Hates_ 17y ago

jgrahamc 17y ago

It was knocked up on a whim, and it is small, but don't be depressed: it wasn't easy... I had to bang my head against the trigonometry to get it all correct. Although I know the rules of trig, I always have a hard time applying them in the real world because I have a hard time imagining the shapes involved. Ended up drawing little pictures of what was doing on.

torpor 17y ago
I think it would be quite interesting to know more about how you approached this problem for solution, than the solutions presented by the program itself .. I didn't really get much of the details about how you'd sorted through this from your post .. perhaps a followup topic? Its really great, btw .. I play with this toy with my son on a regular basis, and found myself just a few days ago wondering what is the maximum number of shapes we can build with the set .. okay, this got a bit screwed up by the addition of another mini-set gifted to my son by a friend, so there is room for improvement in my thinking now that I've learned what you have discovered. Nice job!
- jgrahamc 17y ago
  I tried to explain how it works in the comments in the code. Probably worth reading them in detail as they do explain the algorithm used. My thought process was something like this (over a number of days grabbing time when I could): Emulate a human selecting pieces and clicking them together. Model pieces as straight lines of the right length. There are two important things: how long the line is and how much it modifies the angle at which the next piece will join. Thus all I need is to keep track of the position of the end of the last piece added and the angle. Spend a while figuring out the trigonometry and getting that code working correctly. To generate the permutations I realized that the process could be split into three parts: 1. Always place the bridge. Since there's one just add it at the end. 2. Separate the straights and curves. Generate all the permutations of clockwise and anticlockwise curved pieces. To do that I used the trick of all 12-bit binary numbers between 0 and 2^12-1. 3. Then insert the straight pieces between the curved pieces in all places possible. Feed each possible track layout into code that builds the track and check that the end pieces match up. Add code to eliminate end pieces that join impossibly (come from the wrong angle), add code to remove duplicates caused by rotation and reflection. Once I got that working I then wrote code in Processing to draw a pretty picture.
  - fhars 17y ago
    You might be able to speed it up considerably by adding 2a. Continue with next iteration unless the turning number of the sequence of curves is a whole number. You add 1/8 to the turning number for each clockwise curve and subtract 1/8 for each CCW (for numerical stability you would rather add of subtract 1 and check for multiples of 8).

dschobel 17y ago

HN is a good place to feel inferior, nothing has ever made me feel more so than: http://news.ycombinator.com/item?id=639976 http://news.ycombinator.com/item?id=639976

Tichy 17y ago

I am genuinely interested: how could you have no idea how to start? Isn't it obvious to check all possible permutations of the 9 pieces (and orientations I suppose, also accounting for duplicate pieces)? I suppose that is what you would be doing even if you didn't have a computer? That shouldn't be too hard. A little harder perhaps to then determine if a given permutation is a closed loop or not, but essentially it should be basic geometry (didn't look at the code). Even if that naive approach would not work, it would at least be a way to start. The remaining sub problems should be less scary to tackle.

anthonyb 17y ago

I did a similar thing with our kids' LILLABO set. Except that rather than build from zero, my algorithm was to start with the smallest possible loop (8 curves - a circle) and add similar parts to both sides until the set was used up. The main criteria for the additions was that they had to translate but not rotate, ie. AC or SS and B, although more complex ones are possible, like BCA vs. SCAS. It doesn't seem to make any difference as long as they translate to the same thing. You should be able to generate all possible loops relatively cheaply, since you're just moving characters around. You might need a separate character for the original circle/curve parts though, to make it possible to find the originals. I never got around to implementing this - it was just an observation while building interesting tracks for my children, but I might have a go...