Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
This was my submission for the Dice.com coding contest initially posted at http://news.dice.com/2013/10/02/coding-challenge-046/ I came in 7th. Boo.
// Code submission for coding challenge "Prove Your Factorial Fluency"
// http://news.dice.com/2013/10/02/coding-challenge-046/
//
// Author: Richard R. Vasquez, II
// Website: http://tinymu.gs
//
// Notes: This was run in Release - Win32 - Visual Studio 2012
//
// Personal averages: ~0.5 seconds : 0.000000043 seconds to find correct solution.
// ~1.0 second : 0.000000034 seconds to find correct solution.
// ~5.0 seconds : 0.000000036 seconds to find correct solution.
// ~10.0 seconds : 0.000000035 seconds to find correct solution.
// ~25.0 seconds : 0.000000034 seconds to find correct solution.
// ~50.0 seconds : 0.000000034 seconds to find correct solution.
// I changed algorithm based on a bunch of papers I read over the past couple of weeks.
//
// Then I started banging on the resulting code by unrolling the main loop while
// throwing the inner loop into a series of switch case dropthroughs. Then add
// other tiny optimizations here and there with lookup tables and similar. It makes
// for *much* longer code, but it's about 3 orders of magnitude faster, which I'll
// consider an acceptable tradeoff.
#include <chrono>
#include <iostream>
#include <iomanip>
using namespace std;
void WriteOutput(char* answer, int iterations, double time);
// How many seconds minimum we want to run
const double seconds = 5.0;
// Which specific permutation we're looking for (1 based)
const int countTarget = 100000;
// Lookup tables for fast subtraction.
const int muls8[] = {0, -40320, -80640, -120960, -161280, -201600, -241920, -282240, -322560};
const int muls7[] = {0, -5040, -10080, -15120, -20160, -25200, -30240, -35280};
const int muls6[] = {0, -720, -1440, -2160, -2880, -3600, -4320};
const int muls5[] = {0, -120, -240, -360, -480, -600};
const int muls4[] = {0, -24, -48, -72, -96};
const int muls3[] = {0, -6, -12, -18};
const int muls2[] = {0, -2, -4};
const int muls1[] = {0, -1};
char letters[9] = {'9','8','7','6','5','4','3','2','1'};
int main()
{
// Initialization
std::chrono::steady_clock::time_point Start, End;
// Placeholder for the output
char s[10] = { '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0' };
// How many times we've calculated the answer.
int iterations = 0;
// Start ticking time.
Start = std::chrono::steady_clock::now();
End = std::chrono::steady_clock::now();
while(std::chrono::duration_cast<std::chrono::duration<double>>(End-Start).count() < seconds)
{
iterations++;
letters[0] = '9';
letters[1] = '8';
letters[2] = '7';
letters[3] = '6';
letters[4] = '5';
letters[5] = '4';
letters[6] = '3';
letters[7] = '2';
letters[8] = '1';
char c;
// We count with 0 based indexes
int zeroBase = countTarget - 1;
#pragma region Process 8! permutation value
int count = zeroBase / 40320;
c = letters[count];
switch(count)
{
case 8:
letters[8] = letters[7];
case 7:
letters[7] = letters[6];
case 6:
letters[6] = letters[5];
case 5:
letters[5] = letters[4];
case 4:
letters[4] = letters[3];
case 3:
letters[3] = letters[2];
case 2:
letters[2] = letters[1];
case 1:
letters[1] = letters[0];
letters[0] = c;
break;
default:
break;
}
zeroBase += muls8[count];
#pragma endregion
#pragma region Process 7! permutation value
count = zeroBase / 5040;
c = letters[count + 1];
switch(count)
{
case 7:
letters[8] = letters[7];
case 6:
letters[7] = letters[6];
case 5:
letters[6] = letters[5];
case 4:
letters[5] = letters[4];
case 3:
letters[4] = letters[3];
case 2:
letters[3] = letters[2];
case 1:
letters[2] = letters[1];
letters[1] = c;
break;
default:
break;
}
zeroBase += muls7[count];
#pragma endregion
#pragma region Process 6! permutation value
count = zeroBase / 720;
c = letters[count + 2];
switch(count)
{
case 6:
letters[8] = letters[7];
case 5:
letters[7] = letters[6];
case 4:
letters[6] = letters[5];
case 3:
letters[5] = letters[4];
case 2:
letters[4] = letters[3];
case 1:
letters[3] = letters[2];
letters[2] = c;
break;
default:
break;
}
zeroBase += muls6[count];
#pragma endregion
#pragma region Process 5! permutation value
count = zeroBase / 120;
c = letters[count + 3];
switch(count)
{
case 5:
letters[8] = letters[7];
case 4:
letters[7] = letters[6];
case 3:
letters[6] = letters[5];
case 2:
letters[5] = letters[4];
case 1:
letters[4] = letters[3];
letters[3] = c;
break;
default:
break;
}
zeroBase += muls5[count];
#pragma endregion
#pragma region Process 4! permutation value
count = zeroBase / 24;
c = letters[count + 4];
switch(count)
{
case 4:
letters[8] = letters[7];
case 3:
letters[7] = letters[6];
case 2:
letters[6] = letters[5];
case 1:
letters[5] = letters[4];
letters[4] = c;
break;
default:
break;
}
zeroBase += muls4[count];
#pragma endregion
#pragma region Process 3! permutation value
count = zeroBase / 6;
c = letters[count + 5];
switch(count)
{
case 3:
letters[8] = letters[7];
case 2:
letters[7] = letters[6];
case 1:
letters[6] = letters[5];
letters[5] = c;
break;
default:
break;
}
zeroBase += muls3[count];
#pragma endregion
#pragma region Process 2! permutation value
count = zeroBase / 2;
c = letters[count + 6];
switch(count)
{
case 2:
letters[8] = letters[7];
case 1:
letters[7] = letters[6];
letters[6] = c;
break;
default:
break;
}
zeroBase += muls2[count];
#pragma endregion
#pragma region Process 1! permutation value
count = zeroBase;
switch(count)
{
case 1:
swap(letters[7], letters[8]);
break;
default:
break;
}
#pragma endregion
End = std::chrono::steady_clock::now();
}
for(int i = 0; i < 9; i++)
{
s[ i ] = letters[ i ];
}
WriteOutput( s, iterations,
std::chrono::duration_cast<std::chrono::duration<double>>(End-Start).count()
);
//std::cin.get(); //uncomment to pause before ending.
return 0;
}
// Quick output of the answer, and the average time spent
// based on total time / number of iterations. Expanded out
// to nanoseconds since the speed of this algorithm on my
// machine initially only showed 1 microsecond.
void WriteOutput(char* answer, int iterations, double time)
{
double timePerIteration = time / (double) iterations;
int seconds = (int) timePerIteration;
int minutes = seconds / 60;
double partial = timePerIteration - seconds;
cout
<< answer << endl << endl << minutes
<< " minutes, " << fixed << setprecision( 9 )
<< partial << " seconds (" << iterations
<< " iterations in " << time
<< " seconds)" << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.