<commit_before>package sudoku;

import common.ComboGen;
import common.Pair;
import common.graph.Graph;
import common.graph.BasicGraph;
import common.graph.WrapVertex;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Collector;
import java.util.stream.Collectors;

/**
 * <p>The color-chain technique exploits the fact that a Rule with 
 * only two connected Claims is analogous to a {@code xor} operation. 
 * A collection of interconnected two-Claim Rules, regardless of 
 * the size and shape of such a network, has only two possible 
 * solution-states.</p>
 * 
 * @author fiveham
 * 
 */
public class ColorChain extends Technique {
	
	private final ColorSource colorSource = new ColorSource();
	
	/**
	 * <p>Constructs a ColorChain that works to solve the 
	 * specified {@code target}.</p>
	 * @param target the Puzzle that this Technique works 
	 * to solve.
	 */
	public ColorChain(Sudoku puzzle) {
		super(puzzle);
	}
	
	/**
	 * <p>Imitates the slide structure of {@link Solver#solve() Solver.solve()}, 
	 * with subtechniques for {@link #visibleColorContradiction() color-contradiction} 
	 * and {@link #bridge() chain-chain interaction}. Subtechniques are applied 
	 * in sequence.</p>
	 * @return a SolutionEvent describing the changes made to the puzzle, or null 
	 * if no changes were made
	 */
	@Override
	protected SolutionEvent process(){
		List<Function<Collection<Graph<ColorClaim>>,SolutionEvent>> actions = new ArrayList<>(SUBTECHNIQUE_COUNT);
		Collections.addAll(actions, (graph)->visibleColorContradiction(graph), (graph)->bridge(graph));
		
		Collection<Graph<ColorClaim>> chains = generateChains();
		for(Function<Collection<Graph<ColorClaim>>,SolutionEvent> test : actions){
			SolutionEvent result = test.apply(chains);
			if(result != null){
				return result;
			}
		}
		
		return null;
	}
	
	public static final int SUBTECHNIQUE_COUNT = 2;
	
	/**
	 * <p>Checks pairs of xor-chains for bridge-based interactions that force 
	 * one of the chains to collapse.</p>
	 * 
	 * <p>If, given two chains, there exist two non-xor Rules that each contain 
	 * one Claim belonging to each of the two given chains, then one of the 
	 * chains may be completely collapseable. If the distance in one chain between 
	 * its claims belonging to the bridge Rules is odd and the distance in the 
	 * other chain between its claims belonging to the bridge Rules is even, then 
	 * the chain with the even distance can be collapsed, with the Claims having 
	 * the color of its Claims on the bridge all being false.</p>
	 * 
	 * @return a SolutionEvent describing the changes made to the puzzle, or 
	 * null if no changes were made
	 */
	//TODO create a graph where each xor-chain is a node, connected to each other chain-node with which the chain shares some rules
	private SolutionEvent bridge(Collection<Graph<ColorClaim>> chains){
		for(List<Graph<ColorClaim>> chainPair : new ComboGen<>(chains, CHAINS_FOR_BRIDGE, CHAINS_FOR_BRIDGE)){
			Pair<Graph<ColorClaim>,Integer> evenSideAndFalseColor = evenSideAndFalseColor(chainPair);
			if(evenSideAndFalseColor != null){
				Graph<ColorClaim> falseEvenSideChain = evenSideAndFalseColor.getA();
				return setChainFalseForColor(falseEvenSideChain, evenSideAndFalseColor.getB());
			}
		}
		
		return null;
	}
	
	public static final int CHAINS_FOR_BRIDGE = 2;
	
	/**
	 * <p>Any claims in the {@code target} that {@link Claim#visibleClaims() can see} 
	 * Claims with opposite colors from the same chain must be false, no matter 
	 * which color from that chain is true and which is false.</p>
	 * @return a SolutionEvent describing the changes made to the puzzle, or 
	 * null if no changes were made
	 */
	private SolutionEvent visibleColorContradiction(Collection<Graph<ColorClaim>> chains){
		for(Graph<ColorClaim> chain : chains){
			SolutionEvent result = visibleColorContradiction(chain);
			if( result != null ){
				return result;
			}
		}
		return null;
	}
	
	/**
	 * <p>Detects and {@link Claim#setFalse() sets false} Claims that 
	 * can see both of the colors in {@code concom}.</p>
	 * 
	 * <p>In a xor-chain, either all the positive-colored Claims are true 
	 * and all the negative-colored Claims are false or all the positive-
	 * colored Claims are false and all the negative-colored Claims are 
	 * true. </p>
	 * @param concom a xor-chain
	 * @return a SolutionEvent describing the changes made to the puzzle, or 
	 * null if no changes were made
	 */
	private SolutionEvent visibleColorContradiction(Graph<ColorClaim> concom){
		Set<Claim> visibleToPositives = concom.nodeStream()
				.filter((cc) -> cc.color > 0)
				.map((cc) -> cc.wrapped())
				.collect(CLAIMS_TO_VISIBLE_CLAIMS);
		Set<Claim> visibleToNegatives = concom.nodeStream()
				.filter((cc) -> cc.color < 0)
				.map((cc) -> cc.wrapped())
				.collect(CLAIMS_TO_VISIBLE_CLAIMS);
		
		Set<Claim> claimsToSetFalse = visibleToPositives;
		claimsToSetFalse.retainAll(visibleToNegatives);
		if(!claimsToSetFalse.isEmpty()){
			SolutionEvent result = new SolveEventColorChainVisibleContradiction(claimsToSetFalse);
			claimsToSetFalse.stream().forEach((c)->c.setFalse(result));
			return result;
		}
		
		return null;
	}
	
	public static final Collector<Claim,?,Set<Claim>> CLAIMS_TO_VISIBLE_CLAIMS = Collector.of(
			HashSet::new, 
			(r,t) -> r.addAll(t.visibleClaims()), 
			(r1,r2) -> {r1.addAll(r2); return r1;});
	
	/**
	 * <p>Isolates those Rules in the target that have two Claims, makes 
	 * a Graph of their Claims, where two Claims share an edge if they 
	 * share a Rule as an element, and returns a collection of that Graph's 
	 * connected components, each of which is a xor-chain with two possible 
	 * solution-states.</p>
	 * 
	 * @return a collection of the xor-chains that exist in the target 
	 * at the time when this method is called
	 */
	private Collection<Graph<ColorClaim>> generateChains(){
		return target.nodeStream()
				.filter((nodeSet)->(nodeSet.size()==Rule.SIZE_WHEN_XOR && nodeSet instanceof Rule))
				.map((nodeSet)->(Rule)nodeSet)
				.collect(Collector.of(
						HashSet::new,
						(Set<Rule> ruleSet, Rule rule) -> ruleSet.add(rule),
						(left,right) -> {left.addAll(right); return left;},
						(result) -> new BasicGraph<ColorClaim>(link(Sledgehammer.sideEffectUnion(result, false)))))
				.addContractEventListenerFactory(colorSource)
				.connectedComponents();
	}
	
	/**
	 * <p>Wraps the elements of {@code claims} in {@code ColorClaim}s and 
	 * adds bidirectional edges linking those ColorClaims if the Claims 
	 * wrapped by the ColorClaims linked by such an edge are 
	 * {@link Claim#visibleClaims() visible} to one another. Edge-linking 
	 * is done in {@code O(n)} time where {@code n = claims.size()}.</p>
	 * @param claims a set of Claims to be wrapped by ColorClaims and linked 
	 * by edges
	 * @return a list of connected ColorClaim each of which wraps a Claim 
	 * from {@code claims} and tags that Claim with a color
	 */
	private static List<ColorClaim> link(Set<Claim> claims){
		Map<Claim,ColorClaim> map = new HashMap<>();
		return claims.stream()
				.map(ColorClaim::new)
				.peek((colorClaim) -> map.put(colorClaim.wrapped(), colorClaim))
				.peek( (colorClaim) -> colorClaim.wrapped().visibleClaims().stream()
						.filter((visibleClaim) -> map.containsKey(visibleClaim))
						.filter((visClaimInChain) -> colorClaim.wrapped().stream() //TODO de-stream this stuff so that "chain claims connect through a binary Rule" is more clear
								.filter((fact)->visClaimInChain.contains(fact))
								.anyMatch(Fact.IS_XOR))
						.map((visClaimInChain) -> map.get(visClaimInChain))
						.forEach((colorVisClaim) -> {
							colorClaim.neighbors().add(colorVisClaim); 
						}) )
				.collect(Collectors.toList());
	}
	
	/**
	 * <p>Sets false all the Claims in this chain decorated with the specified 
	 * {@code color}.</p>
	 * @param time the contextual time node which needs to store a collection of 
	 * the Claims being set false by this method call 
	 * @param chain a xor-chain of connected two-Claim Rules 
	 * @param color the color of the Claims being set false
	 * @return {@code time}, after the Claims of the specified {@code color} from 
	 * the specified xor-{@code chain} are added to its pool of 
	 * {@link FalsifiedTime#falsified() falsified Claims}
	 */
	private SolutionEvent setChainFalseForColor(Graph<ColorClaim> chain, final int color){
		List<Claim> setFalse = chain.nodeStream()
				.filter((cc)->cc.color()==color)
				.map( (cc)->cc.wrapped() )
				.collect(Collectors.toList());
		SolutionEvent time = new SolveEventColorChainBridge(setFalse);
		setFalse.stream().filter(Claim.CLAIM_IS_BEING_SET_FALSE.negate()).forEach((c)->c.setFalse(time));<commit_msg>refactor ColorChain generation of edges between ColorClaims<commit_after>package sudoku;

import common.ComboGen;
import common.Pair;
import common.graph.Graph;
import common.graph.BasicGraph;
import common.graph.WrapVertex;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Collector;
import java.util.stream.Collectors;

/**
 * <p>The color-chain technique exploits the fact that a Rule with 
 * only two connected Claims is analogous to a {@code xor} operation. 
 * A collection of interconnected two-Claim Rules, regardless of 
 * the size and shape of such a network, has only two possible 
 * solution-states.</p>
 * 
 * @author fiveham
 * 
 */
public class ColorChain extends Technique {
	
	private final ColorSource colorSource = new ColorSource();
	
	/**
	 * <p>Constructs a ColorChain that works to solve the 
	 * specified {@code target}.</p>
	 * @param target the Puzzle that this Technique works 
	 * to solve.
	 */
	public ColorChain(Sudoku puzzle) {
		super(puzzle);
	}
	
	/**
	 * <p>Imitates the slide structure of {@link Solver#solve() Solver.solve()}, 
	 * with subtechniques for {@link #visibleColorContradiction() color-contradiction} 
	 * and {@link #bridge() chain-chain interaction}. Subtechniques are applied 
	 * in sequence.</p>
	 * @return a SolutionEvent describing the changes made to the puzzle, or null 
	 * if no changes were made
	 */
	@Override
	protected SolutionEvent process(){
		List<Function<Collection<Graph<ColorClaim>>,SolutionEvent>> actions = new ArrayList<>(SUBTECHNIQUE_COUNT);
		Collections.addAll(actions, (graph)->visibleColorContradiction(graph), (graph)->bridge(graph));
		
		Collection<Graph<ColorClaim>> chains = generateChains();
		for(Function<Collection<Graph<ColorClaim>>,SolutionEvent> test : actions){
			SolutionEvent result = test.apply(chains);
			if(result != null){
				return result;
			}
		}
		
		return null;
	}
	
	public static final int SUBTECHNIQUE_COUNT = 2;
	
	/**
	 * <p>Checks pairs of xor-chains for bridge-based interactions that force 
	 * one of the chains to collapse.</p>
	 * 
	 * <p>If, given two chains, there exist two non-xor Rules that each contain 
	 * one Claim belonging to each of the two given chains, then one of the 
	 * chains may be completely collapseable. If the distance in one chain between 
	 * its claims belonging to the bridge Rules is odd and the distance in the 
	 * other chain between its claims belonging to the bridge Rules is even, then 
	 * the chain with the even distance can be collapsed, with the Claims having 
	 * the color of its Claims on the bridge all being false.</p>
	 * 
	 * @return a SolutionEvent describing the changes made to the puzzle, or 
	 * null if no changes were made
	 */
	//TODO create a graph where each xor-chain is a node, connected to each other chain-node with which the chain shares some rules
	private SolutionEvent bridge(Collection<Graph<ColorClaim>> chains){
		for(List<Graph<ColorClaim>> chainPair : new ComboGen<>(chains, CHAINS_FOR_BRIDGE, CHAINS_FOR_BRIDGE)){
			Pair<Graph<ColorClaim>,Integer> evenSideAndFalseColor = evenSideAndFalseColor(chainPair);
			if(evenSideAndFalseColor != null){
				Graph<ColorClaim> falseEvenSideChain = evenSideAndFalseColor.getA();
				return setChainFalseForColor(falseEvenSideChain, evenSideAndFalseColor.getB());
			}
		}
		
		return null;
	}
	
	public static final int CHAINS_FOR_BRIDGE = 2;
	
	/**
	 * <p>Any claims in the {@code target} that {@link Claim#visibleClaims() can see} 
	 * Claims with opposite colors from the same chain must be false, no matter 
	 * which color from that chain is true and which is false.</p>
	 * @return a SolutionEvent describing the changes made to the puzzle, or 
	 * null if no changes were made
	 */
	private SolutionEvent visibleColorContradiction(Collection<Graph<ColorClaim>> chains){
		for(Graph<ColorClaim> chain : chains){
			SolutionEvent result = visibleColorContradiction(chain);
			if( result != null ){
				return result;
			}
		}
		return null;
	}
	
	/**
	 * <p>Detects and {@link Claim#setFalse() sets false} Claims that 
	 * can see both of the colors in {@code concom}.</p>
	 * 
	 * <p>In a xor-chain, either all the positive-colored Claims are true 
	 * and all the negative-colored Claims are false or all the positive-
	 * colored Claims are false and all the negative-colored Claims are 
	 * true. </p>
	 * @param concom a xor-chain
	 * @return a SolutionEvent describing the changes made to the puzzle, or 
	 * null if no changes were made
	 */
	private SolutionEvent visibleColorContradiction(Graph<ColorClaim> concom){
		Set<Claim> visibleToPositives = concom.nodeStream()
				.filter((cc) -> cc.color > 0)
				.map((cc) -> cc.wrapped())
				.collect(CLAIMS_TO_VISIBLE_CLAIMS);
		Set<Claim> visibleToNegatives = concom.nodeStream()
				.filter((cc) -> cc.color < 0)
				.map((cc) -> cc.wrapped())
				.collect(CLAIMS_TO_VISIBLE_CLAIMS);
		
		Set<Claim> claimsToSetFalse = visibleToPositives;
		claimsToSetFalse.retainAll(visibleToNegatives);
		if(!claimsToSetFalse.isEmpty()){
			SolutionEvent result = new SolveEventColorChainVisibleContradiction(claimsToSetFalse);
			claimsToSetFalse.stream().forEach((c)->c.setFalse(result));
			return result;
		}
		
		return null;
	}
	
	public static final Collector<Claim,?,Set<Claim>> CLAIMS_TO_VISIBLE_CLAIMS = Collector.of(
			HashSet::new, 
			(r,t) -> r.addAll(t.visibleClaims()), 
			(r1,r2) -> {r1.addAll(r2); return r1;});
	
	/**
	 * <p>Isolates those Rules in the target that have two Claims, makes 
	 * a Graph of their Claims, where two Claims share an edge if they 
	 * share a Rule as an element, and returns a collection of that Graph's 
	 * connected components, each of which is a xor-chain with two possible 
	 * solution-states.</p>
	 * 
	 * @return a collection of the xor-chains that exist in the target 
	 * at the time when this method is called
	 */
	private Collection<Graph<ColorClaim>> generateChains(){
		List<Rule> xorRules = target.nodeStream()
				.filter((nodeSet)->(nodeSet.size()==Rule.SIZE_WHEN_XOR && nodeSet instanceof Rule))
				.map((nodeSet)->(Rule)nodeSet)
				.collect(Collectors.toList());
		return new BasicGraph<ColorClaim>(link(xorRules))
				.addContractEventListenerFactory(colorSource)
				.connectedComponents();
	}
	
	/**
	 * <p>Wraps the Claims of the {@code xorRules} in {@code ColorClaim}s and 
	 * adds bidirectional edges linking those ColorClaims that wrap Claims that 
	 * are both connected to a common element of {@code xorRules}.</p>
	 * @param claims a set of Claims to be wrapped by ColorClaims and linked 
	 * by edges
	 * @return a list of connected ColorClaim each of which wraps a Claim 
	 * from {@code claims} and tags that Claim with a color
	 */
	private static List<ColorClaim> link(Collection<Rule> xorRules){
		Map<Claim,ColorClaim> map = new HashMap<>();
		List<ColorClaim> colorClaims = Sledgehammer.sideEffectUnion(xorRules, false).stream()
				.map(ColorClaim::new)
				.peek((colorClaim) -> map.put(colorClaim.wrapped(), colorClaim))
				.collect(Collectors.toList());
		
		xorRules.stream()
				.map((f) -> new ArrayList<>(f))
				.forEach((edge) -> {
					ColorClaim cc0 = map.get(edge.get(0));
					ColorClaim cc1 = map.get(edge.get(1));
					cc0.neighbors().add(cc1);
					cc1.neighbors().add(cc0);
				});
		
		return colorClaims;
	}
	
	/**
	 * <p>Sets false all the Claims in this chain decorated with the specified 
	 * {@code color}.</p>
	 * @param time the contextual time node which needs to store a collection of 
	 * the Claims being set false by this method call 
	 * @param chain a xor-chain of connected two-Claim Rules 
	 * @param color the color of the Claims being set false
	 * @return {@code time}, after the Claims of the specified {@code color} from 
	 * the specified xor-{@code chain} are added to its pool of 
	 * {@link FalsifiedTime#falsified() falsified Claims}
	 */
	private SolutionEvent setChainFalseForColor(Graph<ColorClaim> chain, final int color){
		List<Claim> setFalse = chain.nodeStream()
				.filter((cc)->cc.color()==color)
				.map( (cc)->cc.wrapped() )
				.collect(Collectors.toList());
		SolutionEvent time = new SolveEventColorChainBridge(setFalse);
		setFalse.stream().filter(Claim.CLAIM_IS_BEING_SET_FALSE.negate()).forEach((c)->c.setFalse(time));
{'fraction_non_alphanumeric': 0.10907638770038222, 'fraction_numerical': 0.001483256318101432, 'mean_word_length': 4.084106728538283, 'pattern_counts': {'":': 0, '<': 125, '<?xml version=': 0, '>': 166, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6407938', 'n_tokens_mistral': 5868, 'n_tokens_neox': 5018, 'n_words': 1716}