Logic problem

[Cringer]

I hope I'm ok with putting this in General Chat. It's not so much a Progress issue as just a problem I have understanding some logic. It could be in any language you like - I just happen to be working in Progress for this.

I need to work out a way of doing something. I'm translating the actual problem into apples and conveyor belts so it's more relevant for you!

A conveyor belt has n apples on it. When they get to the end they fall off into one of 2 bags. This is of course totally random. One bag is on the left (L) the other is on the right (R). I need to map out all the different possibilities there are for the apples to fall. Obviously there are 2^n possible results. I'll include a couple of examples.

1 apple
L R

2 apples
LR RL LL RR

3 apples
LLL LLR LRL RLL RRL RLR LRR RRR

I hope that makes sense. How would you go about working out these different combinations?

 

[joey.jeremiah]

one way of doing that dynamically with a variable number of "apples" is using cross-joins or joins without any join conditions

well, its basically whats called a cartesian product or all possible combinations


define a temp-table and fill it with all the possible values, in this case, left and right

dynamically create buffers for every "apple" and a dynamic query that "each's" every buffer without join conditions or cross-join


if the number of possiblities is much, much bigger i would go with static nested loops. something like this -

do i1 = 1 to 3:
 do i2 = 1 to 3:
  ...
   do in = 1 to 3:
  end.
 end.
end.

but the problem you'll run into is that progress is an interpreted language and isn't very suitable for this type of low level operations, performance wise.

if someone was using it for brute force and not counting apples, imo, if it was dealing with numbers and chars both upper and lower case running all possible combinations would be ridiculously long.

 

[Cringer]

Thanks for getting back to me. I'll see what I can work out. Thankfully performance is not as issue at this stage. I want to take the concept of this and add it to the solution for a slightly bigger problem. Maybe once I've solved it in Progress (my main language) I can investigate how to solve it in another, more efficient language for this sort of thing. But for now all I need is the solution. Let the playing begin!

 

[joey.jeremiah]

ridiculousy long could come to a substantial part of someones lifetime

since its not counting apples, what is it ?

it might not be the best approach to solving the problem

 

[Cringer]

This is the idea of the excercise really. Need to find any solution - no matter how greedy, then evaluate it and work out how to improve it.

It's part of an excercise we've been set at work to encourage us to think about how inefficient code can be without thought and then to look at how to improve it.

It's a variation on the knapsack problem basically.

 

[joey.jeremiah]

i completely agree. think what would be the best approach before starting. though in many cases it takes alot of experience and deep understanding to know what that is.

maybe another thing you could do is actively encourage studying or specializing in one thing or another. like, database admin, web design, graphics etc.

it'll get them thinking, see other solutions and technologies, and it also has a substantial added value.

i don't know how one would go about doing that or what companies doing something similar do ? maybe gift certificates for buying books from amazon.com, personal project etc.

 

[Cringer]

The way it's being done here is that we are given an hour a week of company time to work on challenges and projects as well as a forum where we sit together in smaller groups of developers with diverse skills and experience to work on a group problem. The idea is that we can all challenge each other to improve ourselves.

By the way - I've got my solution to this problem done now. I did nested loops in the end for the Cartesian Product. Used Progress to write a .p on the fly and run it in the end for ease of understanding from my part. Next week's job will be to reinvent the wheel more efficiently.

Thanks for your pointers.