davecom / classiccomputerscienceproblemsinjava Goto Github PK

// CSP.java
// From Classic Computer Science Problems in Java Chapter 3
// Copyright 2020 David Kopec
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package chapter3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CSP<V, D> {
	private List<V> variables;
	private Map<V, List<D>> domains;
	private Map<V, List<Constraint<V, D>>> constraints = new HashMap<>();

	public CSP(List<V> variables, Map<V, List<D>> domains) {
		this.variables = variables;
		this.domains = domains;
		for (V variable : variables) {
			constraints.put(variable, new ArrayList<>());
			if (!domains.containsKey(variable)) {
				throw new IllegalArgumentException("Every variable should have a domain assigned to it.");
			}
		}
	}

	public void addConstraint(Constraint<V, D> constraint) {
		for (V variable : constraint.variables) {
			if (!variables.contains(variable)) {
				throw new IllegalArgumentException("Variable in constraint not in CSP");
			}
			constraints.get(variable).add(constraint);
		}
	}

	// Check if the value assignment is consistent by checking all constraints
	// for the given variable against it
	public boolean consistent(V variable, Map<V, D> assignment) {
		for (Constraint<V, D> constraint : constraints.get(variable)) {
			if (!constraint.satisfied(assignment)) {
				return false;
			}
		}
		return true;
	}

	public Map<V, D> backtrackingSearch(Map<V, D> assignment) {
		// assignment is complete if every variable is assigned (our base case)
		if (assignment.size() == variables.size()) {
			return assignment;
		}
		// get the first variable in the CSP but not in the assignment
		V unassigned = variables.stream().filter(v -> !assignment.containsKey(v)).findFirst().get();
		// get the every possible domain value of the first unassigned variable
		for (D value : domains.get(unassigned)) {
			// shallow copy of assignment that we can change
			Map<V, D> localAssignment = new HashMap<>(assignment);
			localAssignment.put(unassigned, value);
			// if we're still consistent, we recurse (continue)
			if (consistent(unassigned, localAssignment)) {
				Map<V, D> result = backtrackingSearch(localAssignment);
				// if we didn't find the result, we will end up backtracking
				if (result != null) {
					return result;
				}
			}
		}
		return null;
	}

	// helper for backtrackingSearch when nothing known yet
	public Map<V, D> backtrackingSearch() {
		return backtrackingSearch(new HashMap<>());
	}
}

// BUG: this code contains an error -- fails to read last three characters of string
for (int i = 0; i < geneStr.length() - 3; i += 3) {
    codons.add(new Codon(geneStr.substring(i, i + 3)));
}

// Here is an example of a corrected version:
final int len = geneStr.length();
final int partitionSize = 3;
for (int i = 0; i < len; i += partitionSize) {
    codons.add(new Codon(geneStr.substring(i, Math.min(len, i + partitionSize))));
}

// Test case that fails with original implementation
Codon ttt = new Codon("TTT");
System.out.println(myGene.linearContains(ttt)); // true
System.out.println(myGene.binaryContains(ttt)); // true

public CSP(List<V> variables, List<D> domain) {
     assert variables != null;
     assert domain != null;

     this.variables = variables;
     this.domains = new HashMap<>();

     for (V variable : variables) {
         domains.put(variable, domain);
         constraints.put(variable, new ArrayList<>());
     }
 }

final CSP<String, String> csp = new CSP<>(variables, List.of("red", "green", "blue"));