October 2009 Programming Challenge

[Rabid Dog]

October 6th, 2009, 1:34 am

Ok so finally I have a new one for everyone. It is relatively simple but I think the challenge is to do it in the least amount of code as possible. This is open to any language.

The problem:
You have a combination lock with 3 sets running from 0-9 (Like the kind you find on briefcases).

So in other words
Set 1 [0-9]
Set 2 [0-9]
Set 3 [0-9]

Your challenge:
This is a two phase challenge

Phase 1:
To find all possible combinations available in the combination lock. This would require you printing them out to a console or some other media. This should be smart enough to handle combination locks with more or less than 3 sets. You might even want to take it to the extent where you can also pass in how many numbers each set contains.

Phase 2:
Given all combinations provide a code and find it in the combination set. This means that your method should be able to find a combination set inside the possible combinations. This is a brute force mechanism.

Your method signature might be something to the effect of

Code: [ Download ] [ Select ]

public void FindCombinations(int sets, int setLength, int[] combinationToSearchFor){

}

1. public void FindCombinations(int sets, int setLength, int[] combinationToSearchFor){
3. }

Submission Format & Rules
Since this could probably be wrapped up in a single method/function, post your solutions in this topic. Once someone has posted a solution in a specific language you may not repost the same algorithim in that language. If it is a variation on the algorithm it is fine

In closing
It isn't that hard but it is cool when you get it right! Think mathematically and you should be able to come up with a rather elegant solution.

[mk27]

October 6th, 2009, 9:07 am

Rabid Dog wrote:

Phase 2:
Given all combinations provide a code and find it in the combination set. This means that your method should be able to find a combination set inside the possible combinations.

I think you should explain what you mean by this (at least to me). "Having all combinations" is as simple as declaring a 3D array, or some kind of parallel data structure. Of course, then any and all combinations will be inside that. So what would "find a combination set inside the possible combinations" refer to?

Rabid Dog wrote:

Your challenge:
This is a three phase challenge

Actually I count 2 in the OP.

Maybe you could post a pseudo-code version of what you mean, or just a function prototype (required inputs, required outputs) because for the life of me, I do not see such a possibility here...

Code: [ Download ] [ Select ]

int main(void) {
int triple_matrix[10][10][10];
return 0;
}

1. int main(void) {
2. int triple_matrix[10][10][10];
3. return 0;
4. }

Wow, just the subscripted index to the matrix will contain all the combinations. You don't even have to assign them. Check "where it is"? Okay, combination 3-0-7 is in triple_matrix[3][0][7]. No offence, but either I totally don't understand you, or this is a "no-programming" contest.

If what you mean is crack a 3 digit code, then does getting one number correct count (then proceed to the next one), or do you need to get all three correct simultaneously? Either way, it is just a "brute-force" set of iterative loops, but the second one will take longer.

[UPSGuy]

October 6th, 2009, 9:10 am

I'm a little hazy here as well. I'm a bit lost on the same basis - I get that we're after permutations, but that's about it.

[Rabid Dog]

October 6th, 2009, 9:30 am

Sorry guys I don't know how else to actually explain it. mk27 is on the right track in terms of filling the arrays with combinations but the idea is to actually figure it out based on the parameters I have supplied in the method signature above so you don't really know what the number of sets is in the method only that it is provided (I have updated above to reflect that). Please reread above and let me know if it makes sense otherwise I am gonna have to come up with another idea. I think getting a set right individually is good enough. It is effectively a brute force type method, I thought listing all possible combinations would be a challenge in it's own intially for those that are starting out

[mk27]

October 7th, 2009, 12:10 pm

Rabid Dog wrote:

Please reread above and let me know if it makes sense otherwise I am gonna have to come up with another idea. I think getting a set right individually is good enough. It is effectively a brute force type method, I thought listing all possible combinations would be a challenge in it's own intially for those that are starting out

I kind of think you should (come up with another idea). "Given all combinations provide a code and find it in the combination set" -- it just does not make sense, Rabid Dog. Or rather, it makes sense, but I do not see "a problem" (like, "Given the spectrum, find the color of the sky").

Since the set size, etc, are not known, I suppose it would be a challenge for "those that are starting out" to deal with how to dynamically structure some data, but I really think there need to be more meat on these bones, since once the data is structured, the combination is there -- you do not need to "find it", you just need to do the brute force iteration (unless there is a none brute force method, which I would be surprised, but hey).

I was just googling around and I found this page:
http://www.codinghorror.com/blog/archives/000951.html
I've spent a whole lot of time at cprogramming.com (like, 3500 posts in 15 months) and so I get to see a lot of what the CS students are getting asked to do in their first few years. Of the problems listed on the above page, I have seen AT LEAST 5-10 threads on every single one of them except for "Two Generals" which I've never heard of. I've never myself taken time to solve any of them*, mind you, but they do look kind of interesting. The "dining philosophers" is not so appropriate since it is really a multi-process/threading problem, but for sure the "Eight Queens" or "Towers of Hanoi" are good; so maybe is the "Traveling Salesman" but it needs fleshing out. I think they are all to greater and lesser degrees about permutations. If they seem too involved (I think they would take most people at least an afternoon) there are tons of problems at "Sphere online judge":
http://www.spoj.pl/
altho the SPOJ interface itself is gimpy and you have to register to browse the challanges, but they range from dead simple stuff on up.

Anyway, sad that I am not myself more creative, but there's some suggestions. Maybe someone could come up with a complication on the original idea from the OP (you need a complication), sometimes stuff like that falls out of the sky and manages to land in my head...just not so far

* I have enough programming problems as is but I do promise to do this one.

[Rabid Dog]

October 7th, 2009, 12:27 pm

Ok well if the general consensus is that this ain't gonna work, I will see if I can come up with another one.

The challenging part is finding something that everyone can work on.

October 16th, 2009, 9:08 am

Sounds interesting

[Bogey]

November 9th, 2009, 8:31 pm

Is the November Challenge coming? I can't believe I missed this... I too though, can't really understand the challange.

You want us to find all possible combinations in a given amount of sets whose numbers could be anywhere between 0 and 9? If so, I think I got it.