Multidimensional Possibilities

Discussion in 'Ruby' started by Phrogz, Dec 18, 2007.

  1. Phrogz

    Phrogz Guest

    I recently had to solve a one-off problem for work, and the solution I
    came up with was about as non-DRY as you can imagine. I couldn't
    figure out how to make it simple, however. In order to expand my
    knowledge, I'm hoping to get some ideas (or even related problem
    domains) to solve this generically.

    The problem was this:

    This website has a menu of industries, a menu of categories, and a
    menu of products.
    If a single industry is selected, highlight the categories and
    products are available for that industry.
    If a single category is selected, highlight the industries and
    products are available for that category.
    If a single product is selected, highlight the industries and
    categories available for that industry.
    If a pair of items is selected (for example, one industry and one
    product) show all the related items that match the intersection (for
    example, all the categories that apply to the intersection of those
    two choices).

    I solved it by storing the data as a series of nested hashes, dictated
    an order in which axes were specified, and hard-coded it for the 3
    axes above, and repeated almost the same code for all 6 possible axis
    queries (axis1, axis2, axis3, axis1+axis2, axis1+axis3, axis2+axis3).
    It was huge and bloated and menial.

    SO...this is like a data cube (in this particular set of 3
    dimensions). I'm looking for a solution that is generic to n
    dimensions. Doing that will simultaneously make the code simpler and
    more generally useful.

    Here's Ruby code and plenty of test cases to exactly describe what I'm
    looking for. It's echoed at http://pastie.caboo.se/130061 for easier
    reading and preventing unintended line-wrapping.

    My preemptive thanks to all who provide some ideas (or working code)
    towards the solution.

    # BOYv NUM>| one | two | three |
    # ----------+-----------+-----------+----------+
    # jim | alpha | | beta |
    # jam | beta | alpha | |
    # jem | delta | | delta |
    # jom |beta, alpha| omega | delta |


    AXES = [ :boy, :num, :greek ]

    COMBOS = {
    :jim => {
    :eek:ne => [ :alpha ],
    :three => [ :beta ]
    },
    :jam => {
    :eek:ne => [ :beta ],
    :two => [ :alpha ]
    },
    :jem => {
    :eek:ne => [ :delta ],
    :three => [ :delta ]
    },
    :jom => {
    :eek:ne => [ :beta, :alpha ],
    :two => [ :eek:mega ],
    :three => [ :delta ]
    }
    }

    def make_database( axes, nested_hash )
    # Parse however you like to create
    # your own data structure.
    end

    def fetch_options( database, axes_values = {} )
    # Return all valid possibilities based on the supplied values
    end

    require 'test/unit'
    class TestMultiDimensionalDB < Test::Unit::TestCase
    def setup
    $db = make_database( AXES, COMBOS )
    end
    def test_one_axis
    opts = fetch_options( $db, :greek=>:eek:mega )
    assert( opts[:boy] == [:jom],
    "The only boy with greek:eek:mega is jom." )
    assert( opts[:num] == [:two],
    "The only num with greek:eek:mega is two." )



    opts = fetch_options( $db, :greek=>:alpha )
    assert( opts[:boy].length == 3,
    "There are 3 boys with greek:alpha." )
    assert( opts[:boy].include?:)jim),
    "One of the 3 boys with greek:alpha is jim." )
    assert( opts[:boy].include?:)jam),
    "One of the 3 boys with greek:alpha is jam." )
    assert( opts[:boy].include?:)jom),
    "One of the 3 boys with greek:alpha is jom." )

    assert( opts[:num].length == 2,
    "There are 2 nums with greek:alpha." )
    assert( opts[:num].include?:)one) && opts[:num].include?:)two),
    "The nums with greek:alpha are one and two." )



    opts = fetch_options( $db, :boy=>:jem )
    assert( opts[:num].length == 2,
    "There are 2 nums with the boy:jem." )
    assert( opts[:num].include?:)one) && opts[:num].include?:)three),
    "The nums with the boy:jem are one and three." )

    assert( opts[:greek] == [:delta]
    "The only greek with the boy:jem is delta" )



    opts = fetch_options( $db, :num=>:eek:ne )
    assert( opts[:boy].length == 4,
    "There are 4 boys with num:eek:ne." )
    assert( opts[:boy].include?:)jim),
    "One of the 4 boys with num:eek:ne is jim." )
    assert( opts[:boy].include?:)jam),
    "One of the 4 boys with num:eek:ne is jam." )
    assert( opts[:boy].include?:)jem),
    "One of the 4 boys with num:eek:ne is jem." )
    assert( opts[:boy].include?:)jom),
    "One of the 4 boys with num:eek:ne is jom." )

    assert( opts[:greek].length == 3,
    "There are 3 greek with num:eek:ne." )
    assert( opts[:greek].include?:)alpha),
    "One of the 3 greeks with num:eek:ne is alpha." )
    assert( opts[:greek].include?:)beta),
    "One of the 3 greeks with num:eek:ne is beta." )
    assert( opts[:greek].include?:)delta),
    "One of the 3 greeks with num:eek:ne is delta." )
    end

    def test_two_axes
    opts = fetch_options( $db, :greek=>:alpha, :num=>:eek:ne )
    assert( opts[:boy].length == 2,
    "There are 2 boys with greek:alpha and num:eek:ne." )
    assert( opts[:boy].include?:)jim) && opts[:boy].include?:)jom),
    "The boys with greek:alpha and num:eek:ne are jim and jom." )



    opts = fetch_options( $db, :greek=>:alpha, :num=>:two )
    assert( opts[:boy] == [:jam],
    "The only boy with greek:alpha and num:two is jam." )



    opts = fetch_options( $db, :boy=>:jom, :num=>:eek:ne )
    assert( opts[:greek].length == 2,
    "There are 2 greeks with the boy:jom and num:eek:ne." )
    assert( opts[:greek].include?:)alpha) && opts[:greek].include?
    :)beta),
    "The greeks with the boy:jom and num:eek:ne are alpha and beta." )



    opts = fetch_options( $db, :boy=>:jam, :greek=>:eek:mega )
    assert( opts[:num].length == 0,
    "There are no nums with the boy:jam and greek:eek:mega." )



    opts = fetch_options( $db, :boy=>:jem, :greek=>:delta )
    assert( opts[:num].length == 2,
    "There are 2 nums with the boy:jem and greek:delta." )
    assert( opts[:num].include?:)one) && opts[:num].include?:)three),
    "The nums with the boy:jem and greek:delta are one and three." )
    end
    end
     
    Phrogz, Dec 18, 2007
    #1
    1. Advertising

  2. On Dec 18, 2007 11:00 PM, Phrogz <> wrote:
    >
    > This website has a menu of industries, a menu of categories, and a
    > menu of products.
    > If a single industry is selected, highlight the categories and
    > products are available for that industry.
    > If a single category is selected, highlight the industries and
    > products are available for that category.
    > If a single product is selected, highlight the industries and
    > categories available for that industry.
    > If a pair of items is selected (for example, one industry and one
    > product) show all the related items that match the intersection (for
    > example, all the categories that apply to the intersection of those
    > two choices).


    Use a database - they're written to solve this exact problem!

    martin
     
    Martin DeMello, Dec 18, 2007
    #2
    1. Advertising

  3. Okay, a bit less of a copout:

    Store the data in a linear array of records. Also, have a hash of
    {[axis, value] => bitvector}, where the bitvector is 1 for every
    record containing that value on that axis (e.g. {[boy, jim] =>
    1100000} means that of the seven records, the first two have boy:jim)

    Then you simply and together the bitvectors for all your criteria and
    traverse the resultant bitvector, picking out array indices.

    Add/delete a record: for every axis in your new record, hash[axis,
    value].bitvector.toggle(record.index)

    Note that deletion leaves gaps you cannot compact, though you can
    maintain a subsidiary datastructure pointing to deleted records so
    they can be reclaimed one by one

    martin
     
    Martin DeMello, Dec 18, 2007
    #3
  4. Phrogz

    Phrogz Guest

    On Dec 18, 10:45 am, Martin DeMello <> wrote:
    > On Dec 18, 2007 11:00 PM, Phrogz <> wrote:
    >
    >
    >
    > > This website has a menu of industries, a menu of categories, and a
    > > menu of products.
    > > If a single industry is selected, highlight the categories and
    > > products are available for that industry.
    > > If a single category is selected, highlight the industries and
    > > products are available for that category.
    > > If a single product is selected, highlight the industries and
    > > categories available for that industry.
    > > If a pair of items is selected (for example, one industry and one
    > > product) show all the related items that match the intersection (for
    > > example, all the categories that apply to the intersection of those
    > > two choices).

    >
    > Use a database - they're written to solve this exact problem!


    What does that look like? Given n tables of entries, you have a single
    extra table with n columns, where each row enumerates a given possible
    combination? And then you just query that table to get a flat list of
    all possible combinations, and then spin through the rows and build up
    your arrays of possibilities?

    Not a bad suggestion, and so simple.
     
    Phrogz, Dec 18, 2007
    #4
  5. On Dec 19, 2007 12:40 AM, Phrogz <> wrote:
    > >
    > > Use a database - they're written to solve this exact problem!

    >
    > What does that look like? Given n tables of entries, you have a single
    > extra table with n columns, where each row enumerates a given possible
    > combination? And then you just query that table to get a flat list of
    > all possible combinations, and then spin through the rows and build up
    > your arrays of possibilities?
    >
    > Not a bad suggestion, and so simple.


    Why do you even need the n tables of entries? Since your data is
    simply a set of points in a multidimensional space, you could have a
    single table where the columns correspond to the axes and the rows are
    the coordinates of the point on each axis. Searching is simply a
    matter of synthesising sql statements to select subsets.

    martin
     
    Martin DeMello, Dec 18, 2007
    #5
  6. Phrogz

    Todd Benson Guest

    On Dec 18, 2007 11:30 AM, Phrogz <> wrote:
    > I recently had to solve a one-off problem for work, and the solution I
    > came up with was about as non-DRY as you can imagine. I couldn't
    > figure out how to make it simple, however. In order to expand my
    > knowledge, I'm hoping to get some ideas (or even related problem
    > domains) to solve this generically.
    >
    > The problem was this:
    >
    > This website has a menu of industries, a menu of categories, and a
    > menu of products.
    > If a single industry is selected, highlight the categories and
    > products are available for that industry.
    > If a single category is selected, highlight the industries and
    > products are available for that category.
    > If a single product is selected, highlight the industries and
    > categories available for that industry.
    > If a pair of items is selected (for example, one industry and one
    > product) show all the related items that match the intersection (for
    > example, all the categories that apply to the intersection of those
    > two choices).


    I'll have a look at your code later, but this looks to me solvable
    using queries to the database; that is, if you have a database. If
    not, then you are trying to create one, which task I wouldn't wish on
    anybody (that's a way of saying I wish you well :). The problem
    domain, though, seems confined to be tackled solely in Ruby and still
    be maintainable, the solution unstable. I think it would be an
    awesome Ruby Quiz!

    If you have a database, using SQL (fill in the blanks)...

    select <columns that you want> from industries, categories, products
    where <condition>

    I know, db guys/gals like to use caps for key words, but I tend to be
    lazy on lists.

    I'm pretty certain you were well aware of this, but I thought I'd
    throw the SQL info in for other newbies (like myself, not you) that
    struggle with this kind of situation.

    From there, it would depend on the tool a person would use to access
    the db, you know, all the ones people keep bringing up on the list.

    Todd
     
    Todd Benson, Dec 18, 2007
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. noe
    Replies:
    25
    Views:
    658
    Leor Zolman
    May 28, 2004
  2. Sridhar R

    distutils possibilities

    Sridhar R, Feb 14, 2004, in forum: Python
    Replies:
    1
    Views:
    237
    Jorgen Grahn
    Feb 14, 2004
  3. Skip Montanaro
    Replies:
    1
    Views:
    338
    Torsten Mohr
    Jun 7, 2004
  4. Daniel Hilgarth
    Replies:
    1
    Views:
    564
    Martin Honnen
    Nov 25, 2006
  5. Christopher Benson-Manica

    Preprocessor possibilities

    Christopher Benson-Manica, Dec 13, 2005, in forum: C Programming
    Replies:
    15
    Views:
    464
    Robert Gamble
    Dec 13, 2005
Loading...

Share This Page