package countdownsolver

	fun main(args: Array<String>) {
		solve(listOf(1, 3, 7, 6, 8, 3), 250)
		solve(listOf(25, 100, 9, 7, 3, 7), 881)
		solve(listOf(6, 75, 3, 25, 50, 100), 952)    
	}

	fun solve(lst: List<Int>, sol: Int) {
		val perms = permuteList(lst)
		val ops = operators()
	    var eq = ""
	    var res = 0

	    for(op in ops) {
	    	for(perm in perms.distinct().toTypedArray()) {
	    		eq = perm[0].toString()
	    		res = perm[0]
	    		for(i in 1 until perm.size) {
	    			eq = eq + " " + opToString(op[i-1]) + " " + perm[i].toString()
	    			res = applyOp(op[i-1], res, perm[i])
	    		}

	    		if(res == sol) {
	    			println(eq+" = "+res.toString())	
	    		}
	    	}
	    }
	}

	fun permuteList(lst: List<Int>): List<List<Int>> {
	    if (lst.size == 1) return listOf(lst)
	    val perms = mutableListOf<List<Int>>()
	    val toInsert = lst[0]
	    for(perm in permuteList(lst.drop(1))) {
	        for(i in 0..perm.size) {
	            val newPerm = perm.toMutableList()
	            newPerm.add(i, toInsert)
	            perms.add(newPerm)
	        }
	    }
	    return perms
	}

	fun operators(): Array<IntArray> {
		var res = mutableListOf(intArrayOf(0, 0, 0, 0, 0))
		for(i in 0 until 4) {
			for(j in 0 until 4) { 
				for(k in 0 until 4) {
					for(l in 0 until 4) {
						for(m in 0 until 4) {
							res.add(intArrayOf(i, j, k, l, m))
						}
					}
				}
			}
		}
		res.removeAt(0)
		return res.toTypedArray()
	}

	fun opToString(x: Int): String = when(x) {
		0 -> "+"
		1 -> "-"
		2 -> "*"
		3 -> "/"
		else -> ""
	}

	fun applyOp(op: Int, x: Int, y: Int): Int = when(op) {
		0 -> x + y
		1 -> x - y
		2 -> x * y
		3 -> x / y
		else -> x
	}