CODEWITHSUNDEEP
algorithmperl
Dancrumb
Dancrumb

Reputation: 27589

Is there a name for this algorithm?

Apologies for the non-descriptive question; if you can think of a better one, I'm all ears.

I'm writing some Perl to implement an algorithm and the code I have smells fishy. Since I don't have a CS background, I don't have a lot of knowledge of standard algorithms in my back pocket, but this seems like something that it might be.

Let me describe what I'm doing by way of metaphor:

So, we have an algorithm for processing items in a list, if they meet some criteria, they should be added to a structure which, when it meets some other criteria, should be 'closed out'. Also, once the list has been processed, if there's an 'open' structure, it should be 'closed out' as well.

Naively, I assume that the algorithm consists of a loop acting over the list, with a conditional to see if the list element belongs in the structure and a conditional to see if the structure needs to be 'closed'. Outside the loop, there would be one more conditional to close any outstanding structures.

So, here are my questions:

  1. Is this a description of a well-known algorithm? If so, does it have a name?
  2. Is there an effective way to coalesce the 'closing out the box' activity into a single place, as opposed to once inside the loop and once outside of the loop?

I tagged this as 'Perl' because Perlish approaches are of interest, but I'd be interested to hear of any other languages that have neat solutions to this.

Upvotes: 20

Views: 621

Answers (5)

Travis J
Travis J

Reputation: 82357

When looking at algorithms, the mainstream CS ones tend to handle very complex situations, or employ very complex approaches (look up NP-Complete for example). Moreover, the algorithms tend to focus on optimization. How can this system be more efficient? How can I use less steps in this production schedule? What is the most amount of foos that I can fit in my bar? etc.

An example of a complex approach in my opinion is quick sort because the recursion is pretty genius. I know it is standard, but I really like it. If you like algorithms, then check out the Simplex Algorithm - it has been very influential.

An example of a complex situation would be if you had oranges that go in, get sorted into 5 orange piles, then went to 5 different places to be peeled, then all came back with another path of oranges to total 10 orange piles, then each orange was individually sliced, and boxed in groups of exactly 2 pounds.

Back to your example. Your example is a simplified version of a flow network. Instead of having so many side paths and options, there is only one path with a capacity of one orange at a time. Of the flow network algorithms, the Ford-Fulkerson algorithm is probably the most influential.

So, you can probably fit one of these algorithms into the example posed, but it would be through a simplification process. Basically there is not enough complexity here to need any optimization. And there is no risk of running at an inefficient time complexity so there is no need to be running the "perfect approach".

The approach you detailed is going to be fine here, and the accepted answer above does a good job suggesting an actual functional solution to the defined problem. I just wanted to add my 2 cents with regards to algorithms.

Upvotes: 0

The Archetypal Paul
The Archetypal Paul

Reputation: 41779

It's a nice fit with a functional approach - you're iterating over a stream of Oranges, testing, grouping and operating on them. In Scala, it would be something like:

 val oranges:Stream[Oranges] = ... // generate a stream of Oranges

 oranges.filter(_.isNotRotten).grouped(10).foreach{ o => {(new Box).fillBox(o)}}

(grouped does the right thing with the partial box at the end)

There's probably Perl equivalents.

Upvotes: 9

DVK
DVK

Reputation: 129569

Is there an effective way to coalesce the 'closing out the box' activity into a single place, as opposed to once inside the loop and once outside of the loop?

Yes. Simply add "... or there are no more oranges" to the "does the structure need to be closed" function. The easiest way of doing this is a do/while construct (technically speaking it's NOT a loop in Perl, though it looks like one):

my $current_container;
my $more_objects;
do {
    my $object = get_next_object();  # Easiest implementation returns undef if no more 
    $more_objects = more_objects($object) # Easiest to implement as "defined $object"
    if (!$more_objects || can_not_pack_more($current_container) { 
        close_container($current_container);
        $current_container = open_container() if $more_objects;
    }
    pack($object, $current_container) if $more_objects;
} while ($more_objects);

IMHO, this doesn't really win you anything if the close_container() is encapsulated into a method - there's no major technical or code quality cost to calling it both inside and outside the loop. Actually, I'm strongly of the opinion that a convoluted workaround like I presented above is WORSE code quality wise than a straightforward:

my $current_container;
while (my $more_objects = more_objects(my $object = get_next_object())) {
    if (can_not_pack_more($current_container)) { # false on undef
        close_container($current_container);
    }
    $current_container = open_container_if_closed($current_container); # if defined
    pack($object, $current_container);
}
close_container($current_container);

Upvotes: 5

Michael Carman
Michael Carman

Reputation: 30851

I don't think there's a name for this algorithm. For a straight-forward implementation you'll need two tests: one to detect a full box while in the processing loop and one after the loop to detect a partially full box. The "closing the box" logic can be made into a subroutine to avoid duplicating it. A functional approach could provide a way around that:

use List::MoreUtils qw(part natatime);

my ($good, $bad) = part { $_->is_rotten() } @oranges;

$_->dispose() foreach @$bad;

my $it = natatime 10, @$good;
while (my @batch = $it->()) {
    my $box = Box->new();
    $box->add(@batch);
    $box->close();
    $box->stack();
}

Upvotes: 1

Jerome WAGNER
Jerome WAGNER

Reputation: 22462

It seems like a bit over-complicated for the problem you are describing, but it sounds theoretically close to Petri Nets. check Petri Nets on wikipedia

A perl implementation can be found here

I hope this will help you,

Jerome Wagner

Upvotes: 3

Related Questions