Fun Easy Dumb Algorithm Puzzle

The Partridge Family were neither partridges nor a family. Discuss.
Post Reply
User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Fun Easy Dumb Algorithm Puzzle

Post by chili » August 21st, 2019, 2:34 am

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>
Chili

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Fun Easy Dumb Algorithm Puzzle

Post by chili » August 21st, 2019, 2:41 am

Chili

User avatar
cyboryxmen
Posts: 190
Joined: November 14th, 2014, 2:03 am

Re: Fun Easy Dumb Algorithm Puzzle

Post by cyboryxmen » August 21st, 2019, 3:24 am

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!
Zekilk

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Fun Easy Dumb Algorithm Puzzle

Post by chili » August 21st, 2019, 3:41 am

I need to add a facepalm emoji to this forum.
Chili

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Fun Easy Dumb Algorithm Puzzle

Post by chili » August 25th, 2019, 5:23 am

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

User avatar
DEM0N194
Posts: 28
Joined: April 15th, 2017, 4:14 pm
Location: Slovakia
Contact:

Re: Fun Easy Dumb Algorithm Puzzle

Post by DEM0N194 » August 25th, 2019, 8:10 pm

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

Post Reply