Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

In the lab where I did my graduate work, there was a post doc who used to give the following problem to those prospective graduate students who were uncertain about their programming chops (and wanted some reassurance on whether they'd be able to handle the work).

Consider a 3-dimensional graph consisting of 27 vertices with coordinates (x, y, z), where each of x, y, and z belongs to the set {0, 1, 2}, and whose edges are the segments of length 1 between any two nodes along the coordinate axes (i.e. the coordinates of the endpoints of each edge differ by 1 at exactly one position). A "path" on this graph is defined as an ordered sequence of vertices such that adjacent vertices in the sequence are neighbors in the graph (i.e. the coordinates of two adjacent vertices in a path differ at exactly one position). A Hamltonian path (HP) on this graph is one that visits each of the 27 vertices exactly once.

The problem is to count exactly all the HPs on this graph.

One further detail had to do with the geometric symmetries of such cubic lattice. In the way the problem was usually posed, all the HPs that could be obtained from a given HP by a 3-D symmetry operation (e.g. flipping the lattice around one of its axes of symmetry, or reflecting through a plane of symmetry, etc.) counted as only one HP. (BTW, accounting for these symmetries is the trickiest aspect of the problem.) However, two HPs that could be obtained from each other by reversing the order of the nodes were to be counted as two different HPs.

the lowliest monk


In reply to Re: Simple but thought-provoking programming tasks [OT] by tlm
in thread Simple but thought-provoking programming tasks [OT] by Cody Pendant

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others drinking their drinks and smoking their pipes about the Monastery: (7)
    As of 2021-01-20 07:25 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      Notices?