roryokane/code.coffee

## code.coffee
# environment setup

# this is CoffeeScript (http://coffeescript.org/)
# and I'm using the Underscore.js library (http://underscorejs.org/)

log = console.log

testFunctionUsingTestCases = (fun, funName, testCases) ->
  for testCase in testCases
    expectedResult = _(testCase).first()
    callArguments = _(testCase).rest()
    actualResult = fun.apply(undefined, callArguments)

    if ! _.isEqual(actualResult, expectedResult)
      log("test failed for function "+funName+" - arguments, expected, and actual:", callArguments, expectedResult, actualResult)
      return
  log("all tests passed for function "+funName)


# defining evaluatePermutation

absOfDifference = (num1, num2) ->
  Math.abs(num1 - num2)

# Big O: O(n) for n = permutation size
evaluatePermutation = (permutation) ->
  current = _(permutation).first()
  for number in _(permutation).rest()
    current = absOfDifference(current, number)
  return current
evaluatePermutationTestCases = [
  [1, [1]]
  [1, [1, 2]]
  [2, [1, 2, 3]]
  [2, [2, 1, 3]]
  [0, [3, 1, 2]]
  [0, [3, 2, 1]]
  [2, [1, 2, 3, 4]]
  [4, [1, 3, 2, 4]]
  [2, [2, 1, 3, 4]]
]
testFunctionUsingTestCases(evaluatePermutation, "evaluatePermutation", evaluatePermutationTestCases)


permute = `function(input) {
    var permArr = [],
    usedChars = [];
    function main(input){
        var i, ch;
        for (i = 0; i < input.length; i++) {
            ch = input.splice(i, 1)[0];
            usedChars.push(ch);
            if (input.length == 0) {
                permArr.push(usedChars.slice());
            }
            main(input);
            input.splice(i, 0, ch);
            usedChars.pop();
        }
        return permArr
    }
    return main(input);
};` # from http://stackoverflow.com/a/11509565/578288

# Big O: O(n)
setWithSize = (size) ->
  [1..size]

# Big O: O(n!)
permutationsOfSetWithSize = (size) ->
  return _.compose(permute, setWithSize)(size)
permutationsOfSetWithSizeTestCases = [
  [[ [1] ], 1]
  [[ [1, 2],[2, 1] ], 2]
  [[ [1, 2, 3],[1, 3, 2],[2, 1, 3],[2, 3, 1],[3, 1, 2],[3, 2, 1] ], 3]
]
testFunctionUsingTestCases(permutationsOfSetWithSize, "permutationsOfSetWithSize", permutationsOfSetWithSizeTestCases)


# defining maximumValueForSetSize

# Big O: O(n*m) for n = num of permutations, m = permutation size
# evaluatePermutation is O(m)
# map is O(n)
# max is O(n)
maximumValueUsingPermutations = (permutations) ->
  return _.max( _(permutations).map(evaluatePermutation) )

# Big O: O(n!)
# maximumValueUsingPermutations is O(n^2)
# permutationsOfSetWithSize is O(n!)
maximumValueForSetSize = (size) ->
  return _.compose(maximumValueUsingPermutations, permutationsOfSetWithSize)(size)
maximumValueForSetSizeTestCases = [
  [1, 1]
  [1, 2]
  [2, 3]
]
testFunctionUsingTestCases(maximumValueForSetSize, "maximumValueForSetSize", maximumValueForSetSizeTestCases)


# defining maximumValuesForSetsUpTo

# Big O: O(n!)
maximumValuesForSetsUpTo = (maxSize) ->
  for size in [1..maxSize]
    maximumValueForSetSize(size)
maximumValuesForSetsUpToTestCases = [
  [[1, 1], 2]
  [[1, 1, 2], 3]
]
testFunctionUsingTestCases(maximumValuesForSetsUpTo, "maximumValuesForSetsUpTo", maximumValuesForSetsUpToTestCases)


# useful calculations

maxSize = 5
log("maximum values for sets of sizes up to #{maxSize}:", maximumValuesForSetsUpTo(maxSize) )

# this takes too long to run - estimated over a year
#idealSize = 2012
#log("maximum value for set of size #{idealSize}:",  maximumValueForSetSize(idealSize) )

## page_skeleton.html
<!DOCTYPE html>
<html>
<head>
<script src="http://documentcloud.github.com/underscore/underscore-min.js"></script>
  <meta name="description" content="program for solving Math puzzle on http://math.stackexchange.com/q/234792/33731" />
<meta charset=utf-8 />
  <title>Math puzzle assistant</title>
</head>
<body>
  Open the JavaScript and Console panes from the top. You can hide the other panes.
</body>
</html>
	# environment setup

	# this is CoffeeScript (http://coffeescript.org/)
	# and I'm using the Underscore.js library (http://underscorejs.org/)

	log = console.log

	testFunctionUsingTestCases = (fun, funName, testCases) ->
	for testCase in testCases
	expectedResult = _(testCase).first()
	callArguments = _(testCase).rest()
	actualResult = fun.apply(undefined, callArguments)

	if ! _.isEqual(actualResult, expectedResult)
	log("test failed for function "+funName+" - arguments, expected, and actual:", callArguments, expectedResult, actualResult)
	return
	log("all tests passed for function "+funName)


	# defining evaluatePermutation

	absOfDifference = (num1, num2) ->
	Math.abs(num1 - num2)

	# Big O: O(n) for n = permutation size
	evaluatePermutation = (permutation) ->
	current = _(permutation).first()
	for number in _(permutation).rest()
	current = absOfDifference(current, number)
	return current
	evaluatePermutationTestCases = [
	[1, [1]]
	[1, [1, 2]]
	[2, [1, 2, 3]]
	[2, [2, 1, 3]]
	[0, [3, 1, 2]]
	[0, [3, 2, 1]]
	[2, [1, 2, 3, 4]]
	[4, [1, 3, 2, 4]]
	[2, [2, 1, 3, 4]]
	]
	testFunctionUsingTestCases(evaluatePermutation, "evaluatePermutation", evaluatePermutationTestCases)


	permute = `function(input) {
	var permArr = [],
	usedChars = [];
	function main(input){
	var i, ch;
	for (i = 0; i < input.length; i++) {
	ch = input.splice(i, 1)[0];
	usedChars.push(ch);
	if (input.length == 0) {
	permArr.push(usedChars.slice());
	}
	main(input);
	input.splice(i, 0, ch);
	usedChars.pop();
	}
	return permArr
	}
	return main(input);
	};` # from http://stackoverflow.com/a/11509565/578288

	# Big O: O(n)
	setWithSize = (size) ->
	[1..size]

	# Big O: O(n!)
	permutationsOfSetWithSize = (size) ->
	return _.compose(permute, setWithSize)(size)
	permutationsOfSetWithSizeTestCases = [
	[[ [1] ], 1]
	[[ [1, 2],[2, 1] ], 2]
	[[ [1, 2, 3],[1, 3, 2],[2, 1, 3],[2, 3, 1],[3, 1, 2],[3, 2, 1] ], 3]
	]
	testFunctionUsingTestCases(permutationsOfSetWithSize, "permutationsOfSetWithSize", permutationsOfSetWithSizeTestCases)


	# defining maximumValueForSetSize

	# Big O: O(n*m) for n = num of permutations, m = permutation size
	# evaluatePermutation is O(m)
	# map is O(n)
	# max is O(n)
	maximumValueUsingPermutations = (permutations) ->
	return _.max( _(permutations).map(evaluatePermutation) )

	# Big O: O(n!)
	# maximumValueUsingPermutations is O(n^2)
	# permutationsOfSetWithSize is O(n!)
	maximumValueForSetSize = (size) ->
	return _.compose(maximumValueUsingPermutations, permutationsOfSetWithSize)(size)
	maximumValueForSetSizeTestCases = [
	[1, 1]
	[1, 2]
	[2, 3]
	]
	testFunctionUsingTestCases(maximumValueForSetSize, "maximumValueForSetSize", maximumValueForSetSizeTestCases)


	# defining maximumValuesForSetsUpTo

	# Big O: O(n!)
	maximumValuesForSetsUpTo = (maxSize) ->
	for size in [1..maxSize]
	maximumValueForSetSize(size)
	maximumValuesForSetsUpToTestCases = [
	[[1, 1], 2]
	[[1, 1, 2], 3]
	]
	testFunctionUsingTestCases(maximumValuesForSetsUpTo, "maximumValuesForSetsUpTo", maximumValuesForSetsUpToTestCases)


	# useful calculations

	maxSize = 5
	log("maximum values for sets of sizes up to #{maxSize}:", maximumValuesForSetsUpTo(maxSize) )

	# this takes too long to run - estimated over a year
	#idealSize = 2012
	#log("maximum value for set of size #{idealSize}:", maximumValueForSetSize(idealSize) )
	<!DOCTYPE html>
	<html>
	<head>
	<script src="http://documentcloud.github.com/underscore/underscore-min.js"></script>
	<meta name="description" content="program for solving Math puzzle on http://math.stackexchange.com/q/234792/33731" />
	<meta charset=utf-8 />
	<title>Math puzzle assistant</title>
	</head>
	<body>
	Open the JavaScript and Console panes from the top. You can hide the other panes.
	</body>
	</html>