₦airaland Forum

. . .Takes Schumi at last! Simply brilliant from Lewis.

Lewis! Lewis! Lewis! Lewis! Lewis! Lewis! Lewis! Lewis! What can I say?!
Dude is driving that car like its a bicycle!

Lol!!

The man is a bloody disgrace to Isoko's, we reject him. I wonder if his bedmate, Alao Akala will do the same?
Nigeria belongs to the common man, not the group of thugs that have foisted themselves on us in every party and at every level. Thank God for GEJ.

[size=14pt]24 Hours to Handover: OGD in Dramatic Flight to London[/size]
28 May 2011

https://serving.thisdaylive.com/0bef99d6-acf5-4e2c-9779-8fa02ba3fcd4/assets/1602F16.Gbenga-Daniel.jpg?maxwidth=400&maxheight=540
Out-going Ogun State Governor, Otunba Gbenga Daniel

By Idowu Sowunmi

Barely 24 hours to the inauguration of Senator Ibikunle Amosun as the new governor of Ogun State, out-going governor, Otunba Gbenga Daniel Friday night travelled to London, fuelling speculation that he may have fled to avert arrest for alleged corruption.
Daniel left aboard a British Airways flight to London. A British Airways official confirmed to THISDAY that Daniel was aboard the flight to the United Kingdom last night.

The trip, coming less than 24 hours to the swearing in of his successor is rather curious, given the controversy that has been trailing his administration, particularly as regard alleged corruption.
Daniel left when he still enjoys immunity from arrest as an incumbent governor. He loses the immunity by May 29 when his tenure expires.

A few days ago, he admitted that he left behind a debt of N49 billion.
In a move targeted at Daniel, some of the top officials that worked with him particularly the Director-General of the Bureau of Lands & Survey, Gbenga Ogunnoiki, had been under investigation for some time now by the Economic and Financial Crimes Commission.
Although EFCC officials declined comments Friday night on Daniel’s curious trip, they, however, admitted they had been discreetly investigating Daniel.
Daniel had lamented that despite his efforts at taking the state to a greater height, he was constrained to leave behind N49, 232,597,163.67 debts.

He stated this while receiving a compendium of financial statements of the state from 2003 to 2010 as well as the government’s cash flow from January to March 31, 2011, from the state Accountant-General (AG), Mr. Seye Senfuye.
The ceremony was a valedictory State Executive Council (SEC) meeting held at the Governor’s Office, Abeokuta Friday.
According to him, his administration had done what was expected of it in terms of infrastructural and human capital development.
The financial statements showed that the state government owed N49, 232,597,163.67 as at March 31, 2011, including cash-based liabilities of N26, 453,260,717.13 and contingent liabilities at N22, 779,336,446.54.
Daniel, who said his administration had done its best, lamented that his efforts were thwarted by what he described as insensitivity and un-cooperative attitude of some members of the state House of Assembly. The Assembly members, according to Daniel, failed to approve his moves to access bond from the capital market.

Daniel commended the AG and his team for working tirelessly to publish the state’s statements of accounts and challenged them to distribute the public document to all agencies and parastatals including EFCC and the Independent Corrupt Practices and Other Related Offences Commission (ICPC) and several others.

http://www.thisdaylive.com/articles/24-hours-to-handover-ogd-in-dramatic-flight-to-london/92186/

Perez's crash ruined what would have been an really exciting pole shootout. Sad.
Even sadder, there'll be no rain tomorrow. But as always, we can expect crashes in Monaco, uncertainty and for once, safety car periods. . . at long last!

whoelse:
^^^I'm so envying Beaf too. At least i could have enjoyed that prize while it lasted, Dammnnn.

@omo_to_dun
The funny thing is i actually considered that but as Beaf stated in his question, he just requested for the array as a single unit so its safe to say my assumptions are correct. I still consider myself as part-winner.

@ekt_bear
Seen your posts in other sections. Didnt think programming was your tin. Thumbs up on your analysis.

@Beaf
Where's my share of the prize

Kai!!
I've woken up rather spent this morning, after a night of deep mystery, packed with intense gymnastic pleasures. . . Sensual thrills. . . Ecstasy. lol! But bruv, you are the overall winner na!
Your code is so sexy I keep going back to stare; its some high IQ stuff that gave you choice fireworks and champagne. Congrats!
No vex me o! Wetin you wan tek woman do wen you get champagne?

@topic
Please can somebody help out with a test to see which of the best entries is most performant, and award a worthy trophy? I'm damn tired after waking too early to watch F1 quallies. The three to test are ekt_bear's, whoelse's and Beaf's. If you take up the task, please dump your test code/methodology on omo_to_dun's specially created thread here: https://www.nairaland.com/nigeria/topic-677281.0.html
I would have cheated with a hyper performant entry based on a total rejig of ekt_bear's entry, but I can't find the strength to boot up a PC with a dev environment. I desperately need sleep. Ekt_bear, can you do it, we already discussed switching the looped array briefly (to the one with just 5 elements)?

^
Thanks.

Otuabaroku: ^^^^ Brilliant! If you agree with me that the function needs to return a list/array, that means in order to get the result printed out, you need to iterate the list /array there by using for(or any other ) loop to accomplish the task;hence using 2 loops indirectly. The same can be said about beaf code.

The loop was simply for convenience, printing out the output is a bonus. That said, I could have done:

Console.WriteLine(foundPosCollection.ToString(",");

or

Response.Write(String.Join(foundPosCollection, "
"); //web

or

Console.WriteLine(String.Join(foundPosCollection, Environment.NewLine)); //console

Look ma, no loop!! . . .Guy, E be like say you de jealous my babe trophy!

^
Thanks dude. Its great that we can now have some agreed standards. Nice one.

Otuabaroku:
^^^ are you kidding me or is it the more I look the less I see. Please can one tell me how this function:


public static int Check(int[] searchArray, int[] fullArray)
{
int j = 0;
int result = -1;
for (int i = 0; i < fullArray.Length; )
{
int x = i + j;
if (x >= fullArray.Length) x -= fullArray.Length;
if (fullArray[x] == searchArray[j])
{
j++;
}
else
{
j = 0;
i++;
}
if (j >= searchArray.Length)
{
result = i;
break;
}
}

return result;
}



will return the individual index of occurrences of a pattern in array that has assuming 5 patterns in it without looping through it to get your answer.

It does work. I think you are missing the way the loop is declared, the bits marked "//@@@@@" in the code below are very important to its functioning (I think thats where your confusion lies).
While loops are usually declared in this manner, for (int i = 0; i < fullArray.Length; i++), it is also perfectly legal to do the following:

for (int i = 0; i < fullArray.Length; ). Note that i++ is missing. The winning code increments i elswhere under tight conditions.

Constructs like for ( ;  ; ) are also legal, in this case its an infinite loop equivalent to while(true).

Check the code below with this new understanding, it is incredibly beautiful. Test it also and you'll find it works nicely.

 public static int Check(int[] searchArray, int[] fullArray)
       {
           int j = 0;
           int result = -1;
           for (int i = 0; i < fullArray.Length; )//@@@@@
           {
               int x = i + j;
               if (x >= fullArray.Length) x -= fullArray.Length;
               if (fullArray[x] == searchArray[j])
               {
                   j++;
               }
               else
               {
                   j = 0;
                   i++;//@@@@@
               }
               if (j >= searchArray.Length)
               {
                   result = i;
                   break;
               }
           }

           return result;
       }

^
Take the honours then and open it.

[quote author=omo_to_dun link=topic=675768.msg8407557#msg8407557 date=1306544060]@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. [/font][/size][/quote]I think this is quite a good idea. Maybe we should actually open a thread to dump such programmes. What d'you think?

[quote author=omo_to_dun link=topic=675768.msg8407609#msg8407609 date=1306545277]^
Beaf, that is the problem; you should have stated that you wanted all occurrences; you are just confusing everyone. Completely state your goals next time, and don't keep people guessing. Anyway, I dash you one GBOSA for letting folks use their brains, rather than complaining about the dullness of the programming section.[/quote]No, the real test is over, we are now in jara stage. Tomorrow, I'm going to test for the most perfomant solution as well, lets spread the goodies!

^
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 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.

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

https://prestigeroulette.com/takeittothemax/New-Year-Fireworks-Animation-01.gif

LOL!! I therefore shamelessly award the babe below to my humble self (strictly for the cure of a manly "itch"!

https://akorra.com/wp-content/uploads/2010/10/l_6126fd2ca74c42f6841cf41c5677f74a.jpg

jmaine:
With kpaco ( stick) or with guns and cutlasses . . if it's the later then we are looking for trouble . . .

Nigeria's biggest bunkerers are evil men like Atiku and IBB. These sort will not hesitate to spill anyone spying on their activities in the name of "youth patrols."
If we see injuries or even deaths, the next line of action would be to arm the youth, or at the very least, make them a part of an armed paramilitary structure.

I don't get what you mean by "we are looking for trouble" tho, cos we've got to stop oil bunkerers at some point if we are serious about siezing the future of the country and harnessing resources for development. We need to confront and tear down the powers that be and rip their structures apart; it is high time the youth were armed. Let it be fire for fire.

The next logical step is to arm them.

^
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.

Jealousy.

[size=33pt]Winning entry from whoelse!!![/size]
So short and sexy, it shows a lil bit of panties.

https://www.bunspace.com/static/photobucket/7735/birthdays/animatedFireworks.gif

 public static int Check(int[] searchArray, int[] fullArray)
       {
           int j = 0;
           int result = -1;
           for (int i = 0; i < fullArray.Length; )
           {
               int x = i + j;
               if (x >= fullArray.Length) x -= fullArray.Length;
               if (fullArray[x] == searchArray[j])
               {
                   j++;
               }
               else
               {
                   j = 0;
                   i++;
               }
               if (j >= searchArray.Length)
               {
                   result = i;
                   break;
               }
           }

           return result;
       }

[img]http://adam1cor.files./2010/09/champagne.jpg[/img]

[quote author=ekt_bear link=topic=675768.msg8405567#msg8405567 date=1306517105]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.[/quote]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).

[quote author=ekt_bear link=topic=675768.msg8405567#msg8405567 date=1306517105]You could always manufacture a nested loop from a single one, just using the ceil function and the modulo function:

% Getting a double loop
N=3;

for i=1:N^2 
  j = ceil(i/N);
  k = mod(i-1, N)+1;
  [j,k]
  % Call some function f(j,k) here that does whatever I wanted to do
end

for j=1:N,
  for k=1:N
    [j,k] % Same as above
  end
end

[/quote]Gaddem! Thats some morafcking ugly code. Its a hack thats as ugly as it would perform too. Quite innovative tho.

^
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 ):

private Collection<int> foundPosCollection = new Collection<int>();

private void PatternSearch(int[] patternArray, int[] searchArray)
    {
        int foundPos = -1;
        int foundPosExtendedMode = -1;
        int currSearchElementPos = 0;//current index of searchArray being tested
        int currExtendedModeSearchElementPos = 0;//current index of searchArray being tested in extended mode
        int maxExtendedCycles = 0;
        int patternArrayLength = patternArray.Length;
        bool isLoopInExtendedMode = false;

        for (int i = 0; i < searchArray.Length; i++)
        {
            if (patternArray[0] == searchArray[i])
            {
                //get the number of elements by which our pattern must spill over the upper bound of the
                //array we are searching for a match to be found.
                int spillover = ((i + patternArrayLength) - searchArray.Length);
                if (spillover > 0)
                {
                    foundPosExtendedMode = i;
                    isLoopInExtendedMode = true;
                }
                else
                {
                    isLoopInExtendedMode = false;
                    currExtendedModeSearchElementPos = 0;
                }

                foundPos = i;
                currSearchElementPos++;
                continue;
            }

            //perform overlapping mode specific search
            if (isLoopInExtendedMode)
            {
                currExtendedModeSearchElementPos++;//set index of next element to be tested
                if (i == (searchArray.Length - 1))
                {
                    //get number of elements left to match
                    maxExtendedCycles = (patternArrayLength - 1) - currExtendedModeSearchElementPos;
                    i = -1;//reset the loop and start over (we use -1, cos i is going to be incremented in the loop declaration
                    continue;
                }

                if (currExtendedModeSearchElementPos == (patternArrayLength - 1))
                {
                    foundPosCollection.Add(foundPosExtendedMode);//add to found positions
                }
                if (i == (maxExtendedCycles - 1))
                {
                    //reset and break
                    foundPos = -1;
                    currSearchElementPos = 0;//current index of searchArray being tested
                    currExtendedModeSearchElementPos = 0;//current index of searchArray being tested in extended mode
                    maxExtendedCycles = 0;
                    patternArrayLength = patternArray.Length;
                    isLoopInExtendedMode = false;
                    break;
                }
            }

            //perform regular specific search
            if (currSearchElementPos > 0)
            {
                if (patternArray[currSearchElementPos] == searchArray[i])
                {
                    if (i + 1 == searchArray.Length)
                    {
                    }
                    //report a find if we have successfully tested to the last element
                    if (currSearchElementPos == (patternArrayLength - 1))
                    {
                        foundPosCollection.Add(foundPos);//add to found positions
                        currSearchElementPos = 0;
                        continue;//you can break here, if you are sure there's only a single occurrence of the pattern
                    }

                    currSearchElementPos++;
                }
                else
                {
                    //set to zero if there is no match
                    foundPos = -1;
                    currSearchElementPos = 0;
                }
            }
        }
    }

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() + "
";
}

^
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.

^
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.

[quote author=ekt_bear link=topic=675768.msg8404611#msg8404611 date=1306508908]My solution (written in Matlab/Octave):

http://pastebin.com/hLs62DE9

And here is the result:

https://i54.tinypic.com/11ay9o6.png

The four test vectors look like:

%%%%%%%%%%%%
V1 = [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];
V2 = [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];
V3 = [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];
V4 = [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]; % An additional vector that doesn't contain the pattern

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[/quote]I don't see any definition for your shift function; using functions which arent yours is cheating really, so your entry fails.

@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).

@Otuabaroku
You have nested loops, so your solution fails.

^
Lol! I should have said no recursion!
I really can't look at your code properly now, tho. I'm just chilling after a day of real donkey loads, bros no vex, I go look ya latest code later. It looks promising tho.

Alj harem, do you have a Nigerian passport? Abi you just ran away from Chad like that?!
They are looking for you, I'm telling you.

@mikkytrio

I'm quite tired from a hard slug all day, so I've not been able to look at your code without seeing double. lol!
However, I can tell that it fails to find the pattern in the first array.

@whoelse
You cannot merge the three arrays into one. Dat na ojoro! Nice try, but no dice.

usisky:
@Beaf,

oga Beaf, maybe d problem has to do with your question. cos when i read it, i thot exactly in the same line as the first
person who replied. so u need to rephrase it better. which ever way, it looks so so easy. but why d no use of char, only int. say i must use char for a reason, why not. int takes more memory space where char would have been enough. pls rephrase. make it complete

Nah, my question is fine. In my replies so far, I've given out some pretty hefty hints to the solution. omo_to_dun had the kernel, but didn't try hard enough.
The reason I ruled out chars and other data types is to force us to create original solutions.
I've just finished coding up the answer, but I wanna see how others approach it (I have two solutions, one is slightly dubious ).

Seun:
Why can't I use Python?

Someone already attempted in PHP, so lets see your python solution.

[quote author=Kilode?!]^^HAHA you have no idea Beaf, I'm not Lagos Royalty, I'm Odua Tokan Tokan though, but my "midwest"(SS) credentials/ties are very very substantial.

Bros, I might actually have the authority to banish or even excise you from the South South o, I will check back with the elders   

Thank you though, SS citizenship accepted!

@Isale, The thread is on the Homepage already??  I'll post more of my ancestors when I get a minute,

Edit.[/quote]
Oghene biko o! You wan invoke spirit? How can you barnish the root and foundation? My paddy wan know wetin mek ogoro jump!!
I'm quite interested, where are your SS roots? Edo or Delta?