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
	}

cGFja2FnZSBjb3VudGRvd25zb2x2ZXIKCglmdW4gbWFpbihhcmdzOiBBcnJheTxTdHJpbmc+KSB7CgkJc29sdmUobGlzdE9mKDEsIDMsIDcsIDYsIDgsIDMpLCAyNTApCgkJc29sdmUobGlzdE9mKDI1LCAxMDAsIDksIDcsIDMsIDcpLCA4ODEpCgkJc29sdmUobGlzdE9mKDYsIDc1LCAzLCAyNSwgNTAsIDEwMCksIDk1MikgICAgCgl9CgoJZnVuIHNvbHZlKGxzdDogTGlzdDxJbnQ+LCBzb2w6IEludCkgewoJCXZhbCBwZXJtcyA9IHBlcm11dGVMaXN0KGxzdCkKCQl2YWwgb3BzID0gb3BlcmF0b3JzKCkKCSAgICB2YXIgZXEgPSAiIgoJICAgIHZhciByZXMgPSAwCgoJICAgIGZvcihvcCBpbiBvcHMpIHsKCSAgICAJZm9yKHBlcm0gaW4gcGVybXMuZGlzdGluY3QoKS50b1R5cGVkQXJyYXkoKSkgewoJICAgIAkJZXEgPSBwZXJtWzBdLnRvU3RyaW5nKCkKCSAgICAJCXJlcyA9IHBlcm1bMF0KCSAgICAJCWZvcihpIGluIDEgdW50aWwgcGVybS5zaXplKSB7CgkgICAgCQkJZXEgPSBlcSArICIgIiArIG9wVG9TdHJpbmcob3BbaS0xXSkgKyAiICIgKyBwZXJtW2ldLnRvU3RyaW5nKCkKCSAgICAJCQlyZXMgPSBhcHBseU9wKG9wW2ktMV0sIHJlcywgcGVybVtpXSkKCSAgICAJCX0KCgkgICAgCQlpZihyZXMgPT0gc29sKSB7CgkgICAgCQkJcHJpbnRsbihlcSsiID0gIityZXMudG9TdHJpbmcoKSkJCgkgICAgCQl9CgkgICAgCX0KCSAgICB9Cgl9CgoJZnVuIHBlcm11dGVMaXN0KGxzdDogTGlzdDxJbnQ+KTogTGlzdDxMaXN0PEludD4+IHsKCSAgICBpZiAobHN0LnNpemUgPT0gMSkgcmV0dXJuIGxpc3RPZihsc3QpCgkgICAgdmFsIHBlcm1zID0gbXV0YWJsZUxpc3RPZjxMaXN0PEludD4+KCkKCSAgICB2YWwgdG9JbnNlcnQgPSBsc3RbMF0KCSAgICBmb3IocGVybSBpbiBwZXJtdXRlTGlzdChsc3QuZHJvcCgxKSkpIHsKCSAgICAgICAgZm9yKGkgaW4gMC4ucGVybS5zaXplKSB7CgkgICAgICAgICAgICB2YWwgbmV3UGVybSA9IHBlcm0udG9NdXRhYmxlTGlzdCgpCgkgICAgICAgICAgICBuZXdQZXJtLmFkZChpLCB0b0luc2VydCkKCSAgICAgICAgICAgIHBlcm1zLmFkZChuZXdQZXJtKQoJICAgICAgICB9CgkgICAgfQoJICAgIHJldHVybiBwZXJtcwoJfQoKCWZ1biBvcGVyYXRvcnMoKTogQXJyYXk8SW50QXJyYXk+IHsKCQl2YXIgcmVzID0gbXV0YWJsZUxpc3RPZihpbnRBcnJheU9mKDAsIDAsIDAsIDAsIDApKQoJCWZvcihpIGluIDAgdW50aWwgNCkgewoJCQlmb3IoaiBpbiAwIHVudGlsIDQpIHsgCgkJCQlmb3IoayBpbiAwIHVudGlsIDQpIHsKCQkJCQlmb3IobCBpbiAwIHVudGlsIDQpIHsKCQkJCQkJZm9yKG0gaW4gMCB1bnRpbCA0KSB7CgkJCQkJCQlyZXMuYWRkKGludEFycmF5T2YoaSwgaiwgaywgbCwgbSkpCgkJCQkJCX0KCQkJCQl9CgkJCQl9CgkJCX0KCQl9CgkJcmVzLnJlbW92ZUF0KDApCgkJcmV0dXJuIHJlcy50b1R5cGVkQXJyYXkoKQoJfQoKCWZ1biBvcFRvU3RyaW5nKHg6IEludCk6IFN0cmluZyA9IHdoZW4oeCkgewoJCTAgLT4gIisiCgkJMSAtPiAiLSIKCQkyIC0+ICIqIgoJCTMgLT4gIi8iCgkJZWxzZSAtPiAiIgoJfQoKCWZ1biBhcHBseU9wKG9wOiBJbnQsIHg6IEludCwgeTogSW50KTogSW50ID0gd2hlbihvcCkgewoJCTAgLT4geCArIHkKCQkxIC0+IHggLSB5CgkJMiAtPiB4ICogeQoJCTMgLT4geCAvIHkKCQllbHNlIC0+IHgKCX0=