Resistor Network Generator

This is used to generate connected resistor networks to work with the Circuit Solver script. The whole point of generating these networks was to solve the problem posed in the xkcd comic, Nerd Sniping:

My hypothesis was that if I found the resistance for larger and larger networks, that the values would eventually converge, or at the very least, there would be some kind of pattern to the values.

On a Friday afternoon, just before I went home, I ran 15 iterations, starting from a 3×2 network and increasing each dimension by 2 each time. I was initially running on my own workstation, but Cygwin was limiting me to ~400MB of RAM per Perl process. Then I realized that I had access to a server with 32GB of RAM, and some number of processors. Since it was a Friday afternoon, very little work was being done on it, and nobody would be looking at it all weekend. The first few iterations ran pretty quickly, but the 5th iteration took 20 minutes, and the 6th iteration had been running for 30 minutes when I decided to go home.

It turns out my hypothesis was right! The final value that I got was ~0.774 ohms before I started to run out of memory. (It seems the Matrix library that I used is horribly inefficient…) I graphed the outputs and it was clear that they were converging to something very close to 0.774 ohms.

At this point, I decided to see if anyone else had solved the problem. (I was purposely not looking for this before so that I wouldn’t give up on solving it.) I did in fact find someone who solved it, and they were nice enough to show their work! It turns out you can use Fourier transforms to get a crazy double-integral which, when you solve it, tells you that the actual value of the equivalent resistance is (8-pi)/(2*pi) ohms, which equals 0.773239545 ohms. I came pretty close!

Use

Run the script like so:

perl netmaker.pl <width> <height> [dot-mode]
  • Width should be 3 or greater.
  • Height should be 2 or greater.
  • Any third value will put the script into dot-mode.

Dot-Mode

To verify that the proper connections were being made, I made the script output dot code to produce a graph of the network:

Each node in the graph is a node in the network, and each edge is a resistor. The edge label indicates the resistor's value in ohms.

You might notice the swapping of node 0 and some other node. This is due to a restriction of the circuit solving method I used, which requires that node 0 be ground. Since I was solving for the resistance between two points, I put a voltage source across them, and then measure the current. To do this correctly, I need to move the ground node around.

Non-Dot-Mode

In non-Dot-mode, the output of the program is similar to SPICE syntax. The output is usually piped into the Circuit Solver.

V1 5 0 5
R1 5 1 1
R2 1 2 1
R3 3 4 1
R4 3 5 1
R5 4 0 1
R6 4 1 1
R7 0 2 1

Code

#!/usr/bin/perl -s
use strict;
use warnings;
use POSIX qw(floor);
use vars qw($d $dot);
 
# This is used to generate connected resistor networks.
# They are used to iteratively solve the "Nerd Sniping" puzzle from xkcd.
# http://xkcd.com/356/
 
# TODO: Make a proper error message if these values aren't given.
my $width = $ARGV[0];
my $height = $ARGV[1];
 
# Giving the option -d or -dot will put us into dot-mode.
my $dot_mode = $d || $dot;
 
# Just used so that each node has a unique index.
my $index = 0;
 
# Used to get the correct nodes for the xkcd Nerd Sniping puzzle.
my $plus = floor($width*$height/2 - ($width/2)-1);
my $neg = $plus+2+$width;
if ($plus == 0) { $plus = $neg; }
 
if ($dot_mode)
{
    print "graph G {\n";
}
else
{
    # We need to connect a voltage source so that a current flow through the network.
    # To get the resistance, we use abs((voltage source's voltage)/(current leaving voltage source))
    printf("V1 %d %d %d\n",$plus,0,5);
}
 
# Makes a connected network of resistors.
for (my $y = 0; $y < $height; ++$y)
{
    for (my $x = 0; $x < $width-1; ++$x)
    {
    my $nx = $y*$width+$x;
 
    # Connect the current node to the one next to it horizontally.
    print_connection(++$index,correct_node($nx),correct_node($nx+1),1);
 
    if ($y > 0)
    {
        # Connect the current node to the one next to it vertically, if there is one.
        print_connection(++$index,correct_node($nx),  correct_node($nx-$width),  1);
 
        # If we're at the edge of the network, connect the horizontally-adjacent node to the one above it,
        # since that node isn't going to get an iteration for itself.
        print_connection(++$index,correct_node($nx+1),correct_node($nx-$width+1),1) if ($x == $width-2);
    }
    }
}
 
if ($dot_mode)
{
    align_nodes();
    print "}\n";
}
 
# The matrix math requires that node 0 be grounded, so we need to do some swapping
# in order to have the 0th node be one of the nodes mentioned in the puzzle.
# $neg holds the index of the node where 0 is supposed to be.
sub correct_node
{
    my $val = shift;
    if ($val == 0) { return $neg; }
    if ($val == $neg) { return 0; }
    return $val;
}
 
# Prints a node connection. If we're in dot mode, also print the resistor value as an edge label.
sub print_connection
{
    my ($index, $current_node, $connected_node, $value) = @_;
 
    if ($dot_mode)
    {
    print "edge [label=$value];\n";
    print "$current_node -- $connected_node;\n";
    }
    else
    {
    printf("R%d %d %d %d\n",$index,$current_node,$connected_node,$value);
    }
}
 
# Used in dot mode to align horizontally adjacent nodes to make nice networks.
sub align_nodes
{
    for (my $y = 0; $y < $height; ++$y)
    {
    print "{rank = same; ";
    for (my $x = 0; $x < $width; ++$x)
    {
        print correct_node($y*$width+$x),"; ";
    }
    print "};\n"
    }
}
 
resistor_network_generator.txt · Last modified: 2010/03/13 05:00 by Ryan Fox
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki