Fun Easy Dumb Algorithm Puzzle

The Partridge Family were neither partridges nor a family. Discuss.
chili
Posts: 3892
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Fun Easy Dumb Algorithm Puzzle

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

chili
Posts: 3892
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Fun Easy Dumb Algorithm Puzzle

Chili

cyboryxmen
Posts: 180
Joined: November 14th, 2014, 2:03 am

Re: Fun Easy Dumb Algorithm Puzzle

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

chili
Posts: 3892
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Fun Easy Dumb Algorithm Puzzle

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

chili
Posts: 3892
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Fun Easy Dumb Algorithm Puzzle

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

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

Re: Fun Easy Dumb Algorithm Puzzle

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