Stats: 3,186,948 members, 7,931,294 topics. Date: Sunday, 25 August 2024 at 09:32 PM |
Nairaland Forum / Science/Technology / Programming / Simple Code Challenge: C#, Java, C, C++ (19186 Views)
Please Help With This Simple Code / Programming FUN With Code Snippets!! -C++,C#, Java,php,python Or Any Language!! / Code Challenge [1]: Pseudo-code, C#, JAVA (apply Object Oriented Principles) (2) (3) (4)
(1) (2) (3) (4) (5) (Reply) (Go Down)
Re: Simple Code Challenge: C#, Java, C, C++ by mikkytrio(m): 6:26am On May 27, 2011 |
no ish bruv, just sleep easy man and then I could later repaste my new codes. I am loving the challenge!! |
Re: Simple Code Challenge: C#, Java, C, C++ by mikkytrio(m): 6:34am On May 27, 2011 |
@omo_to_dun thanks alot bruv never looked at that in my tests I just wanted to be sure I was on the same page with him(beef) unto the search and sort algorithm he is talking about would settle the indices later. So, what's the deal. Is he going to paste it as a later date or time?. |
Re: Simple Code Challenge: C#, Java, C, C++ by Nobody: 6:36am On May 27, 2011 |
^ I honestly have no clue; but I suspect he is waiting for more people to turn in their answers. I wish we had more threads like this in the programming section! |
Re: Simple Code Challenge: C#, Java, C, C++ by whoelse(m): 8:27am On May 27, 2011 |
@Beaf Sorry man. didnt even realize they were different arrays unto i saw your response. I guess thats what u and @omo_to_dun were talking about when u both talked about circular arrays. Dont worry, i'll be back wit the answer soon enough. Till then, nothing from u pls. |
Re: Simple Code Challenge: C#, Java, C, C++ by whoelse(m): 8:51am On May 27, 2011 |
I'm back class ArraySearch { static void Main(string[] args) { int[] searchArray = new int[] { 1, 3, 0, 0, 8 }; int[] array1 = { 0, 8, 1, 0, 0, 0, 8, 6, 7, 8, 9, 5, 2, 6, 3, 0, 7, 4, 1, 1, 0, 0, 7, 0, 0, 8, 6, 7, 8, 9, 5, 9, 1, 1, 3, 0 }; int[] array2 = { 1, 0, 0, 0, 8, 6, 7, 8, 9, 1, 3, 0, 0, 8, 5, 2, 6, 3, 0, 7, 4, 1, 1, 0, 0, 7, 0, 0, 8, 6, 7, 8, 9, 5, 9, 1 }; int[] array3 = { 1, 0, 5, 2, 6, 3, 0, 7, 4, 1, 1, 0, 0, 7, 0, 0, 8, 6, 7, 8, 9, 5, 0, 0, 8, 6, 7, 8, 9, 1, 3, 0, 0, 8, 9, 1 }; DisplayResult(ArraySearch.Check(searchArray, array1)); DisplayResult(ArraySearch.Check(searchArray, array2)); DisplayResult(ArraySearch.Check(searchArray, array3)); Console.Read(); } private static void DisplayResult(int result) { if (result == -1) { Console.WriteLine("Search array was not found." ![]() } else { Console.WriteLine("Array found and starts at index {0}", result); } } /// <summary> /// Searches an array for another array. /// </summary> /// <param name="searchArray">The array to be searched for.</param> /// <param name="fullArray">The array to search in.</param> /// <returns>If -1, then the array doesn't exist, else returns the start index of the first item.</returns> public static int Check(int[] searchArray, int[] fullArray) { int invalid = -1; //Check for empty arrays. if(fullArray == null || fullArray.Length == 0) { return invalid; } //And here too. if (searchArray == null || searchArray.Length == 0) { return invalid; } //Check that the length of the full array can contain the searchArray. if (searchArray.Length > fullArray.Length) { return invalid; } int currentIndex = 0; int fullArrayIndex =0; //To solve the circular reference thing, just loop twice, for (int i = 0; i < fullArray.Length * 2; i++, currentIndex++) { fullArrayIndex = i; if (i >= fullArray.Length) { fullArrayIndex = i - fullArray.Length; } if (fullArray[fullArrayIndex] == searchArray[currentIndex]) { //Check if all the items in the array have been searched for. if (searchArray.Length == currentIndex +1) { return i + (currentIndex * -1); } } else { //Rewind back to the last known stop. i += (currentIndex * -1); currentIndex = -1; } } return invalid; } } |
Re: Simple Code Challenge: C#, Java, C, C++ by Otuabaroku: 11:31am On May 27, 2011 |
The linear solution to the code challenge is : class PatternSearch { public static void main(String args[]) { int pattern[] = new int[]{1,3,0,0,8}; int searchedArray1[] = new int[] {0,8,1,0,0,0,8,6,7,8,9,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,9,1,1,3,0}; int searchedArray2[] = new int[]{1,0,0,0,8,6,7,8,9,1,3,0,0,8,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,9,1}; int searchedArray3[] = new int[]{1,0,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,0,0,8,6,7,8,9,1,3,0,0,8,9,1}; searchPattern(pattern, searchedArray1,"first" ![]() searchPattern(pattern, searchedArray2,"second" ![]() searchPattern(pattern, searchedArray3,"third" ![]() } public static void searchPattern(int pattern[],int searchedArray[], String name) { int NoMatch=-1; for(int i=0; i<searchedArray.length;i++) { if(pattern[0]==searchedArray[i] && searchedArray.length-1 >= pattern.length) { boolean Matched = true; int j,k; for( j=0,k=i;j<pattern.length && Matched== true; j++,k++) { if(k>=searchedArray.length|| pattern[j]!=searchedArray[k]) { Matched=false; break; } } if(Matched) { NoMatch=i; System.out.println("Pattern found in " +name+" Array at index "+NoMatch); i=k; } } } if(NoMatch== -1) System.out.println("No pattern found in " +name+" Array" ![]() } } |
Re: Simple Code Challenge: C#, Java, C, C++ by mikkytrio(m): 1:33pm On May 27, 2011 |
@Otuabaroku Nice work and I feel you man as a java brother, but we have gone past the linear search and stuff. Go back through the thread you should get an idea of what I am saying, if you go a page backward. @omo_to_dun yea I too wish for more of such, at least it makes you want to shake off dust from those feathers. So, meanwhile anymore solutions or ideas from you cause seems no one else has been able to produce something new apart from the code reproduction(s). |
Re: Simple Code Challenge: C#, Java, C, C++ by ektbear: 4:08pm On May 27, 2011 |
My solution (written in Matlab/Octave): http://pastebin.com/hLs62DE9 And here is the result: ![]() The four test vectors look like:
We find the location of the correct starting "1" for V1, V2 and V3 (namely, entries 34, 10, and 30), and the code returns a -1 when it cannot find the pattern in V4. At least, I think this is the correct solution if I've understood the problem properly |
Re: Simple Code Challenge: C#, Java, C, C++ by Beaf: 4:13pm On May 27, 2011 |
@Otuabaroku You have nested loops, so your solution fails. |
Re: Simple Code Challenge: C#, Java, C, C++ by Beaf: 4:16pm On May 27, 2011 |
@whoelse Your solution is very similar to one of mine and with less code too! So, tentatively we give it to. . . Hehe!!! ![]() I'm gonna check your output to see that I've not missed out anything (no coding tools on this laptop). |
Re: Simple Code Challenge: C#, Java, C, C++ by ektbear: 4:30pm On May 27, 2011 |
I think the key conceptual thing to recognize is that if you are searching for the pattern:
In the arrays
Well, in arrays like the first one that don't wrap around, it is dead easy. . . . you do a single loop (of length N) and look for the first index where:
By a simple small trick, you can treat the second type of array like the first one. You'll invent some appropriately chosen function F(idx,N), and then instead just search for the first index where:
That way you can deal with wraparounds like "2BCA1" easily. |
Re: Simple Code Challenge: C#, Java, C, C++ by Beaf: 4:44pm On May 27, 2011 |
ekt_bear: I don't see any definition for your shift function; using functions which arent yours is cheating really, so your entry fails. |
Re: Simple Code Challenge: C#, Java, C, C++ by ektbear: 4:48pm On May 27, 2011 |
^-- On line 14:
|
Re: Simple Code Challenge: C#, Java, C, C++ by Beaf: 5:08pm On May 27, 2011 |
^ Lol! My bad, I'm not used to Matlab/Octave and just assumed you used the shift() in Octave. Good solution! I'll lean a bit toward whoelse at this time tho, cos his solution is more robust (array isn't unrolled, which means it'll work for patterns of arbitrary length). Nice. |
Re: Simple Code Challenge: C#, Java, C, C++ by ektbear: 5:52pm On May 27, 2011 |
I think his solution is better if the search array is big. If we use N to denote the size of the original array and M the search array, his algorithm is still only of complexity 2N (he effectively just repeats the original array twice then does a search.) Otoh, mine has complexity NM, since if M is of arbitrarily length, since at each iteration I do M comparisons (you can imagine me having an additional loop inside the first to do comparisons. . . though of course as you stated the original problem, you don't want an additional loop. Though I should probably point out that there are ways to "cheat" and get effectively two [or three, or four, etc] loops out of one, circumventing this condition you placed ![]() So I think my algorithm is only useful if M is much smaller than N. . . say searching for 5 in 1000. His is probably better (at least theoretically) for 500 in 1000. |
Re: Simple Code Challenge: C#, Java, C, C++ by Beaf: 6:09pm On May 27, 2011 |
^ My solution is similar to whoelse's, but much more efficient. He just needs a couple of optimisations to remove the need to repeat the loop. Both of you have offered solutions which are useful, but have weaknesses; his is more robust, only because the pattern array can be a random size. That said, I still haven't tested whoelse's entry for any gotcha's. . . .and talking about ways of cheating and getting around the no nested loop requirement? Lol! Someone already attempted that with recursion! In fact, I'm going to edit the article to clarify that there must be no recursion or tricks like labels and gotos. |
Re: Simple Code Challenge: C#, Java, C, C++ by ektbear: 6:25pm On May 27, 2011 |
Beaf:Are you able to do it in N steps rather than the 2N he uses? This is the only other substantial area of improvement. But I don't think it is possible to do it in N steps. . . you sort of have to double the original array one way or another (something akin to what he did.) If you (or anyone else) can do it in N steps, I'd want to see that.
You could always manufacture a nested loop from a single one, just using the ceil function and the modulo function:
|
Re: Simple Code Challenge: C#, Java, C, C++ by whoelse(m): 8:16pm On May 27, 2011 |
Not yet giving it to me? ![]() My solution is similar to whoelse's, but much more efficient. He just needs a couple of optimisations to remove the need to repeat the loop. Thought making it a lil bit clearer wouldn't be a bad idea.
Funny, just as i was about trying it out, I got an even better response from someone else I showed the question. public static int Check(int[] searchArray, int[] fullArray) BTW Beaf, a very cool thread for the programming section. The fact that peeps post in different languages might just encourage some of us to pick up another language. |
Re: Simple Code Challenge: C#, Java, C, C++ by Beaf: 8:35pm On May 27, 2011 |
^ Wow! Nice terse solution! The solution is to see the array as a wheel that can be turned in one revolution or more by resetting the loops current index. The above solution is basically what I've got, though I'm more verbose. I believe my solution will work for multiple occurences of the pattern in a single array as well (not tested tho), and random pattern and search array sizes. Here goes (feel free to burst my bubble ![]()
Call it so: PatternSearch(patternArray, searchArray3); PatternSearch(patternArray, searchArray1); PatternSearch(patternArray, searchArray2); //Print out for console for (int i = 0; i < foundPosCollection.Count; i++) { Console.WriteLine("Found at " + foundPosCollection[i].ToString() + " " ![]() } Console.ReadLine(); //Print out for web for (int i = 0; i < foundPosCollection.Count; i++) { Response.Write("Found at " + foundPosCollection[i].ToString() + " " ![]() } |
Re: Simple Code Challenge: C#, Java, C, C++ by Beaf: 8:47pm On May 27, 2011 |
ekt_bear: I think my solution is N and a lil over. You really can't get it in N without foreknowledge of the pattern length, if you know that then your method comes tops. The most performant implementation would be taking your method, unrolling the array to be tested and looping the pattern array instead; that will get us preety close to the metal (5 revs instead of 36 and no bound checks). ekt_bear: Gaddem! Thats some morafcking ugly code. Its a hack thats as ugly as it would perform too. Quite innovative tho. |
Re: Simple Code Challenge: C#, Java, C, C++ by Beaf: 9:22pm On May 27, 2011 |
[size=33pt]Winning entry from whoelse!!![/size] So short and sexy, it shows a lil bit of panties. ![]()
[img]http://adam1cor.files./2010/09/champagne.jpg[/img] |
Re: Simple Code Challenge: C#, Java, C, C++ by Nobody: 10:21pm On May 27, 2011 |
i bow down to u guys.i was at home trying to solve it.almost jumped off my balcony outta frustration.Nairaland get Gurus. |
Re: Simple Code Challenge: C#, Java, C, C++ by naijaswag1: 10:58pm On May 27, 2011 |
Submitting my solution at the close of submission (I said yesterday or so that I will) .I am getting interested in algorithm programming nowadays so racking my brain for this is a step further in the right direction. import java.util.ArrayList; public class Nairaland { public static void main(String[] args){ int[] pattern = {1,3,0,0,8}; int[] search1 = {0,8,1,0,0,0,8,6,7,8,9,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,9,1,1,3,0}; int[] search2 = {1,0,0,0,8,6,7,8,9,1,3,0,0,8,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,9,1}; int[] search3 = {1,0,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,0,0,8,6,7,8,9,1,3,0,0,8,9,1}; searchEngine(search1,pattern); searchEngine(search2,pattern); searchEngine(search3,pattern); } static void searchEngine(int[] searchArray,int[] pattern){ ArrayList<Integer> found = null; ArrayList<Integer> foundIndex = null; for(int i=0;i<searchArray.length-1;i++){ if(i == ((searchArray.length-1) - 4)) break; if(searchArray[i] == pattern[0]){ found = new ArrayList<Integer>(); found.add(searchArray[i]); foundIndex = new ArrayList<Integer>(); foundIndex.add(i); int q = 1; int h = i+4; INNER_LOOP: for(int j=i+1;j<=h;j++){ if(searchArray[j] == pattern[q++]){ found.add(searchArray[j]); foundIndex.add(j); continue INNER_LOOP; }else break INNER_LOOP; } printIndices(found,foundIndex); } } } static void printIndices(ArrayList<Integer> found,ArrayList<Integer> foundIndex){ if(found.size() == 5){ System.out.println("Hurray we found a pattern" ![]() for(int i=0;i<found.size();i++){ System.out.println(found.get(i) + " index location " + foundIndex.get(i)); } } } } |
Re: Simple Code Challenge: C#, Java, C, C++ by Beaf: 11:27pm On May 27, 2011 |
^ Submissions surely aint closed. ![]() I strongly doubt that whoelses entry can be beaten for beauty and precision, but if that happens we'll simply sieze the crown from him and award it to the new winner! LOLZZZ!! . . .You've got a nested loop, so your entry fails. |
Re: Simple Code Challenge: C#, Java, C, C++ by naijaswag1: 11:36pm On May 27, 2011 |
@beaf you wanted this done without a nested for loop? If thats the case,I will try but wanted to get it to work first.It gave me real headache to come up with this.But its good for the brain for it to work faster. |
Re: Simple Code Challenge: C#, Java, C, C++ by ektbear: 12:50am On May 28, 2011 |
@whoelses: Yeah, I like what you wrote just now the best. Good job. |
Re: Simple Code Challenge: C#, Java, C, C++ by ektbear: 1:00am On May 28, 2011 |
I'm kind of annoyed with myself that I didn't think of something like that first. . . . in hindsight it is obvious. N iterations (rather than 2N or NM), short and simple. I was too focused on just solving the case in the OP w/o making it more general. Bleh. . . I should have been less lazy and more creative |
Re: Simple Code Challenge: C#, Java, C, C++ by Otuabaroku: 1:24am On May 28, 2011 |
whoelse:^^^ I think the code is clean but it is not fit for the purpose. The search function is meant to print or return the position or index of all the occurrences of the pattern in the array and not the total number of occurrences in the array. |
Re: Simple Code Challenge: C#, Java, C, C++ by Nobody: 1:54am On May 28, 2011 |
^ I believe that you are mistaken. I tested and ran the winning code and it returns the index---not the total occurrence---of the first pattern in the search array. The code is indeed clean, but beaf overlooked the fact that it is not a complete program like the rest of us submitted. Also, not having comments helped drastically reduce the size of the winner's code. Beaf did not state whether or not all occurrences of the pattern must be searched, so I think returning the index of the first occurrence suffices as a solution. It is an awesome code. Congrats whoelse. @Beaf On your next problem, can you, please, include a benchmark program to test for the time analysis of different input? You don't have to do it for all programs; I can help out with C, C++, or Java. |
Re: Simple Code Challenge: C#, Java, C, C++ by Nobody: 2:02am On May 28, 2011 |
ekt_bear: If you peruse the code carefully, you'll see that the loop does not necessarily run N times, since i is not incremented in every iteration. If the pattern in the array occurs in a wrap around fashion, as in the first array that beaf posted, then the loop will necessarily iterate more than N-times. Matter of fact, time analysis for the loop is O(N + M - 1)) = O(N + M) for the worst case; |
Re: Simple Code Challenge: C#, Java, C, C++ by Otuabaroku: 2:06am On May 28, 2011 |
Beaf:^^^ You failed in the condition you set. you said that nested for loop should not be used, but you ended up using it when you want to print the position of the occurrence of the pattern in the array. For now I think there is no way you can implement this function correctly to solve this problem witout using 2 for loop either directly or indirectly. |
Re: Simple Code Challenge: C#, Java, C, C++ by Beaf: 2:07am On May 28, 2011 |
^ Damn! ![]() Dude, there is no nested loop involved in that solution. I simply decided to loop through the results after they'd been returned, which is not nesting. Otuabaroku: I actually ran it on my PC and it worked. Being the killjoy that I am tho, I went and upped the test to include several instances of the search pattern in each test array (two in each), at random positions. ![]() The new arrays are: 0, 8, 1, 0, 0, 0, 8, 6, 7, 1, 3, 0, 0, 8, 3, 0, 7, 4, 1, 1, 0, 0, 7, 0, 0, 8, 6, 7, 8, 9, 5, 9, 1, 1, 3, 0 1, 0, 0, 0, 8, 6, 7, 8, 9, 1, 3, 0, 0, 8, 5, 2, 6, 3, 0, 7, 4, 1, 1, 0, 0, 7, 0, 0, 1, 3, 0, 0, 8, 5, 9, 1 1, 0, 5, 2, 6, 3, 0, 7, 4, 1, 1, 0, 0, 7, 0, 0, 8, 1, 3, 0, 0, 8, 0, 0, 8, 6, 7, 8, 9, 1, 3, 0, 0, 8, 9, 1 All entries failed the test. . . Except the one from here; https://www.nairaland.com/nigeria/topic-675768.32.html#msg8406195 It very correctly reported: Found at 9 Found at 33 Found at 9 Found at 28 Found at 17 Found at 29 ![]() LOL!! I therefore shamelessly award the babe below to my humble self (strictly for the cure of a manly "itch" ![]() ![]() |
Nigerian Ethical Hackers In Here ---> / Programming Challenge For Beginners N20000 / C++ Tutorial For Beginners... Part 1...
(Go Up)
Sections: politics (1) business autos (1) jobs (1) career education (1) romance computers phones travel sports fashion health religion celebs tv-movies music-radio literature webmasters programming techmarket Links: (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) Nairaland - Copyright © 2005 - 2024 Oluwaseun Osewa. All rights reserved. See How To Advertise. 140 |