Weekend Programming Challenge – Week #25 Solutions


Image

Indeed this one was not easy problem, we got only 4 solutions.  I like the output examples in solution 2.

I will admit I’m trying to make Eagle ULP script which to route DDR memory with equal paths and wanted to see with what algorithm / strategy others will come with🙂 as for the moment I try brute force starting from the path which seems with longest distance, then route others stretching them to become with same length like the first one.

The solutions as usual are at GitHub

3 Comments (+add yours?)

  1. mickesprag
    Sep 24, 2013 @ 17:39:52

    Please share your ULP script with the rest of us when you are finished!

    Reply

  2. Dylan
    Sep 25, 2013 @ 18:58:51

    The alternative is to guess how long the longest path will be, then do an A* for your middle/shortest data lines (I’ll call them 15 and 16), then have a step which adds ‘squiggles’ to increase the length as far as possible from obstructions (using some sort of metric of local density of already occupied nodes). Then repeat for 14 and 17, etc, so that the area of board covered is minimised/optimised.

    Of course, if transfers are 32 (or 128, or whatever) bits wide, you could also use Hall’s Marriage Theorem (every bit on CPU matches a bit on the DDR, but they need not have the same number) and the fact you have two or more layers to the board to create a couple of vias for a short (2 node jump) crossover on the other side of the PCB. This adds three units of area to the other side of the board per line in exchange for one “bridge/tunnel” space.

    Reply

  3. ultimateohm
    Sep 28, 2013 @ 19:36:47

    My code (Ohmohm) may not suitable for wiring PCB because it may walk to block that is passed. Fortunately, passed blocks can be added to list in comment “#append point that passed as want” in order to not use passed blocks.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: