fence-optimization.cpp

#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

/*
 * You are given n fence panels. There are n+1 posts installed in the ground (so n gaps).
 * The posts are fixed in position.
 *
 * You know:
 * 1) The length of each fence panel (in mm).
 * 2) The center-to-center distance between posts (in mm).
 *
 * The posts are 4" x 4" (so after sanding, about 3.5" x 3.5"). That will need to be taken into account.
 *
 * The task is to determine which is the optimal ordering from fence panels to gaps such that the difference
 * in length between fence panels and gaps is minimized.
 */

using namespace std;

ostream & operator<<( ostream & os, const vector<int> & v ) {
	os << "[";
	for(size_t i = 0; i < v.size(); i++) {
		os << v[i];
		if ( i < v.size() - 1 ) {
			os << ",";
		}
	}
	os << "]";
}

ostream & operator<<( ostream & os, const vector<float> & v ) {
	os << "[";
	for(size_t i = 0; i < v.size(); i++) {
		os << int( ::roundf( v[i] ) );
		if ( i < v.size() - 1 ) {
			os << ",";
		}
	}
	os << "]";
}

class Solution {
public:

	const vector<float> panels;
	const vector<float> gaps;
	vector<float> optimal_panels;
	vector<int> optimal_ordering;
	vector<float> optimal_err;
	float sq_error = FLT_MAX;

	Solution( const vector<float> &panels, const vector<float> &gaps )
	:
		panels( panels ),
		gaps( adjust_gaps_for_post_size( gaps ) ),
		optimal_panels(vector<float>(panels.size(), -1)),
		optimal_ordering( panels.size(), 0 ),
		optimal_err( panels.size(), 0 )
	{
		cout << "panels: " << panels << endl;
	}

	void callback(vector<int> &ordering) {
        // for each permutation, calculate the MSE of the difference between the gaps and the panels
		// If the MSE is less than the previously calculated one, then store the better results.
        // This is kind of a round-about way to do MMSE (which is typically done with overspecified
        // matrix math), but since we don't want to do matrix math atm with 40320-sized matrices, 
        // iteratively works too.
        
		vector<float> candidate_panels( ordering.size(), 0 );
		vector<float> candidate_err( ordering.size(), 0 );
		vector<float> candidate_sq_err( ordering.size(), 0 );

		for( size_t i = 0; i < ordering.size(); i++ ) {
			candidate_panels[ i ] = panels[ ordering[ i ] ];
		}

		for( size_t i = 0; i < ordering.size(); i++ ) {
			candidate_err[ i ] = gaps[ i ] - candidate_panels[ i ];
			candidate_sq_err[ i ] = ::powf( candidate_err[ i ], 2 );
		}

		float candidate_mean_sq_err = ::accumulate( candidate_sq_err.begin(), candidate_sq_err.end(), 0.0 / candidate_sq_err.size() );

		if ( candidate_mean_sq_err < sq_error ) {
			cout
				<< "order: " << ordering
				<< " error (mm): " << candidate_err
				<< " mse: " << candidate_mean_sq_err
				<< " rms: " << ::sqrtf(candidate_mean_sq_err) << " (mm)"
				<< endl;
			sq_error = candidate_mean_sq_err;
			copy( ordering.begin(), ordering.end(), optimal_ordering.begin() );
			optimal_err = candidate_err;
			copy( candidate_panels.begin(), candidate_panels.end(), optimal_panels.begin() );
		}
	}

	vector<int> find_optimal_ordering() {

		size_t n = panels.size();

		vector<int> r( n, 0 );

		// generates positions from 0 to n-1
		iota(r.begin(), r.end(), 0);

		// next, use an algorithm to generate all permutations and provide a callback for each
        // unique permutation
		heapPermutation(r, n);

		r = optimal_ordering;

		return r;
	}

	// Generating permutation using Heap Algorithm\
    // See https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/
	void heapPermutation(vector<int> &a, int size) {
	    // if size becomes 1 then prints the obtained permutation
	    if (size == 1) {
	        callback(a);
	        return;
	    }

	    for (int i=0; i<size; i++) {
	        heapPermutation(a,size-1);

	        // if size is odd, swap first and last element
	        if (size%2==1) {
	            swap(a[0], a[size-1]);
	        // If size is even, swap ith and last  element
	        } else {
	            swap(a[i], a[size-1]);
		}
	    }
	}

	static vector<float> adjust_gaps_for_post_size(const vector<float> &gaps) {
		const float post_width /* [mm] */ = 3.5 /* [in] */ * 25.4 /* [mm/in] */;

		cout << "c2c gaps: " << gaps << endl;

		vector<float> mgaps = gaps;
		for( auto & g: mgaps ) {
			g -= post_width;
		}

		cout << "    gaps: " << mgaps << endl;

		return mgaps;
	}
};

int main(int argc, char *argv[]) {
	const vector<float> panels = {
		2787.65,
		2292.35,
		2228.85,
		2235.2,
		2260.6,
		2260.6,
		2171.7,
		2209.8,
	};
	const vector<float> gaps = {
		2790.825,
		2349.5,
		2470.15,
		2317.75,
		2282.825,
		2317.75,
		2355.85,
		2133.6,
	};
	Solution soln(panels, gaps);
	vector<int> optimal_ordering = soln.find_optimal_ordering();
	cout << "gaps  : " << soln.gaps << endl;
	cout << "panels: " << soln.optimal_panels << endl;
	cout << "The optimal ordering is " << optimal_ordering << endl;
	cout << "The optimal error is " << soln.optimal_err << endl;
	return 0;
}

c2c gaps: [2791,2350,2470,2318,2283,2318,2356,2134]
    gaps: [2702,2261,2381,2229,2194,2229,2267,2045]
panels: [2788,2292,2229,2235,2261,2261,2172,2210]
order: [0,1,2,3,4,5,6,7] error (mm): [-86,-32,152,-6,-67,-32,95,-165] mse: 73407.1 rms: 270.937 (mm)
order: [0,2,1,3,4,5,6,7] error (mm): [-86,32,89,-6,-67,-32,95,-165] mse: 58084.6 rms: 241.007 (mm)
order: [0,3,1,2,4,5,6,7] error (mm): [-86,25,89,0,-67,-32,95,-165] mse: 57681.3 rms: 240.169 (mm)
order: [0,4,1,2,3,5,6,7] error (mm): [-86,0,89,0,-41,-32,95,-165] mse: 54294.2 rms: 233.011 (mm)
order: [0,4,1,3,2,5,6,7] error (mm): [-86,0,89,-6,-35,-32,95,-165] mse: 53850.7 rms: 232.058 (mm)
order: [0,6,1,2,3,4,5,7] error (mm): [-86,89,89,0,-41,-32,6,-165] mse: 53165.2 rms: 230.576 (mm)
order: [0,2,1,6,3,4,5,7] error (mm): [-86,32,89,57,-41,-32,6,-165] mse: 49536.2 rms: 222.567 (mm)
order: [0,3,1,6,2,4,5,7] error (mm): [-86,25,89,57,-35,-32,6,-165] mse: 48689.4 rms: 220.657 (mm)
order: [0,2,1,3,6,4,5,7] error (mm): [-86,32,89,-6,22,-32,6,-165] mse: 45100.7 rms: 212.369 (mm)
order: [0,3,1,2,6,4,5,7] error (mm): [-86,25,89,0,22,-32,6,-165] mse: 44697.5 rms: 211.418 (mm)
order: [0,4,1,3,6,2,5,7] error (mm): [-86,0,89,-6,22,0,6,-165] mse: 43084.5 rms: 207.568 (mm)
order: [0,7,1,2,3,4,5,6] error (mm): [-86,51,89,0,-41,-32,6,-127] mse: 36713.6 rms: 191.608 (mm)
order: [0,2,1,7,3,4,5,6] error (mm): [-86,32,89,19,-41,-32,6,-127] mse: 35503.9 rms: 188.425 (mm)
order: [0,3,1,7,2,4,5,6] error (mm): [-86,25,89,19,-35,-32,6,-127] mse: 34657.1 rms: 186.164 (mm)
order: [0,2,1,3,7,4,5,6] error (mm): [-86,32,89,-6,-16,-32,6,-127] mse: 33729.7 rms: 183.656 (mm)
order: [0,3,1,2,7,4,5,6] error (mm): [-86,25,89,0,-16,-32,6,-127] mse: 33326.5 rms: 182.555 (mm)
order: [0,4,1,3,2,7,5,6] error (mm): [-86,0,89,-6,-35,19,6,-127] mse: 33044.2 rms: 181.781 (mm)
order: [0,4,1,3,7,2,5,6] error (mm): [-86,0,89,-6,-16,0,6,-127] mse: 31713.6 rms: 178.083 (mm)
gaps  : [2702,2261,2381,2229,2194,2229,2267,2045]
panels: [2788,2261,2292,2235,2210,2229,2261,2172]
The optimal ordering is [0,4,1,3,7,2,5,6]
The optimal error is [-86,0,89,-6,-16,0,6,-127]