Page 1 of 1

Fun Easy Dumb Algorithm Puzzle

Posted: August 21st, 2019, 2:34 am
by chili
Here is a fun /dumb algorithm puzzle / pattern recognition puzzle I thought up last night in bed.

The following input vector:

{ 5,18,7,12,1,10,17,19,4,9,2,0,6, }

Is transformed into the following vector when the desired algorithm is applied:

{ 0,4,12,1,5,9,17,2,6,10,18,7,19, }

Using this info, determine what transformation algorithm is being applied and write some simple C++ code that will apply that same xform to any vector of non-negative integers. Hint: can be done simply with something from <algorithm>

Re: Fun Easy Dumb Algorithm Puzzle

Posted: August 21st, 2019, 2:41 am
by chili

Re: Fun Easy Dumb Algorithm Puzzle

Posted: August 21st, 2019, 3:24 am
by cyboryxmen

Code: Select all

void algorithm(std::vector<int>& io)
{
    constexpr auto output = std::array{0,4,12,1,5,9,17,2,6,10,18,7,19};
    
    std::copy(output.begin, output.end, io.begin);
}
git gud scrubs!

Re: Fun Easy Dumb Algorithm Puzzle

Posted: August 21st, 2019, 3:41 am
by chili
I need to add a facepalm emoji to this forum.

Re: Fun Easy Dumb Algorithm Puzzle

Posted: August 25th, 2019, 5:23 am
by chili
Solution

So the key to solving this one is the notice 2 things and make one leap of realization. First thing to notice is that the numbers in the output are just the numbers in the input, but reordered. Second thing to notice is that the numbers are ordered in groups, where the numbers in each group are ordered to increase in multiples of 4. The leap is to realize the groupings are by n % 4. What this means is that, all numbers for which n % 4 => 0 come first, followed by all numbers for which n % 4 => 1, etc.

The solution can be written in a number of ways, but since I had just done a video on std::sort, that was the method I had in mind.

Code: Select all

std::sort( v.begin(),v.end(),[]( int a,int b )
{
	if( a % 4 == b % 4 )
	{
		return a < b;
	}
	return a % 4 < b % 4;
} );
Order primarily by mod4 value, and if mod values are equal, order by raw value.

Re: Fun Easy Dumb Algorithm Puzzle

Posted: August 25th, 2019, 8:10 pm
by DEM0N194
Damn I gotta frequent the forum more often if you're gonna be posting more challenges/puzzles here ... Got here too late and now I got spoiled