numbers.groovy

@groovy.transform.Canonical
class Candidate {
	def result
	def invalids = []
}

def brute(def list, def ok, def okInOrder, def candidates) {
	def newCandidates = []

	candidates.findResults { candidate ->
		(0..<(list.size) as List).subsequences()
			.findAll { it.size == ok }
			.each { indexesToCheck ->
			(indexesToCheck.subsequences().findAll { it.size == okInOrder } ?: [[]])
			.each { inOrder ->
				def res = candidate.result
				def inv = candidate.invalids
				// Other, non-null value already selected for some in-order index
				if (inOrder.any { res[it] != null && res[it] != list[it] }) return

				def outOfOrder = indexesToCheck.findAll { !(it in inOrder) }
				def restOrigIndexes = (0..<(list.size)).findAll { !(it in inOrder) }
				
				(restOrigIndexes.subsequences()
					.findAll { it.size == outOfOrder.size }
					.collectMany { it.permutations() } ?: [[]])
				.each { potentialMap ->
					def keyPairs = [outOfOrder, potentialMap].transpose()
					// Out-of-order index mapped to same index, or
					// Other, non-null value already selected for some out-of-order index
					if (keyPairs.any { it[0] == it[1] || (res[it[0]] != null && res[it[0]] != list[it[1]]) }) return
					// Constrain regarding invalid values from previous iterations
					if (inOrder.any { list[it] in inv } || keyPairs.any { list[it[1]] in inv }) return

					def copy = res + []
					inOrder.each { copy[it] = list[it] }
					keyPairs.each { copy[it[0]] = list[it[1]] }

					def newInv = (0..<(list.size))
						.findAll { !(it in (inOrder + keyPairs.collect { it[1] })) }
						.collect { list[it] }
					if (copy.any { it in newInv }) return

					newCandidates << new Candidate(copy, (inv + newInv).unique())
				}
			}
		}
	}
	return newCandidates.unique { it.result }
}

def solve = { constraintList ->
	// Assume all examples are of same size
	def empty = (1..(constraintList[0][0].size)).collect { null }

	println constraintList
		.inject([new Candidate(empty)]) { res, con -> brute(con[0], con[1], con[2], res) }
		.collect { it.result }
}

// List of constraints: [example, #ok, #ok in order]
solve([[[5,8,1,6], 2, 1],
       [[3,8,2,6], 2, 0],
       [[1,9,8,3], 2, 0],
       [[1,4,2,7], 1, 1]])  // --> [[5, 4, 3, 8]]

solve([[[2,7,5,3], 2, 1],
       [[9,7,6,3], 2, 0],
       [[4,5,7,9], 2, 0],
       [[4,1,6,8], 1, 1]])  // --> [3, 9, 5, 8], [2, 1, 9, 7]]

transpose is like zip in functional languages, and
inject is like fold