Ćwiczenie z wariacją

Ten filmik (budzi podziw :)) zainspirował mnie do wykonania pewnego ćwiczenia. Polegało ono na odgadnięciu tego samego, ale przy pomocy komputera – zadanie jak z pierwszego roku studiów, ale potrafi przynieść satysfakcje.
W poniższej implementacji została użyta brutalna siła :). Generowane są zbiory możliwych kombinacji działań matematycznych (wariacja z powtórzeniami) i każdy z nich jest sprawdzany we wszystkich konfiguracjach danych liczb 😉 (wariacja bez powtórzeń). Po przeliczeniu, ponad 2 milionów przypadków, otrzymałem 8 sposobów na dojście do tej liczby (tak na prawdę były 2, reszta wynikała z przemienności mnożenia). Jeden ze sposobów, inny niż na filmie, to:
(3 + 100) = 103,
(103 * 6) = 618,
(618 * 75) = 46350,
(46350 / 50) = 927,
(927 + 25) = 952


Kod realizujący to sprowadzał się do:

		BigDecimal expected = new BigDecimal(952);
		
		String[] allowedOperations = {Value.ADD, Value.MULTIPLY, Value.SUBTRACT, Value.DIVIDE, Value.DIVIDE2};
		Integer[] givenValues = {25,50,75,100,3,6};
		
		long operationCount = 1;
		long expectedCount = 0;
		for (String[] operations : Permutation.variationWithRepetition(5, allowedOperations)) {
			for (Integer[] values : Permutation.variationWithoutRepetition(6, givenValues)) {
				// wykonanie dzialania
				Value value = Value.value(values[0]);
				for (int j = 0, k = 1; j < operations.length; j++,k++) {
					value = value.compute(operations[j], values[k]);
				}
				// drukuj jesli oczekiwana
				if (expected.equals(value.value)){
					expectedCount++;
					System.out.println(value.computation);
					System.out.println(operationCount);
				}
				operationCount++;
			}
		}

		System.out.println(operationCount);
		System.out.println(expectedCount);

Gdzie klasa Value pozwalająca na zapisywanie działań w taki sposób:

Value value = value(5).compute(MULTIPLY,5).compute(SUBTRACT, 5).compute(DIVIDE, 2);

Wygląda tak:

public class Value {
	
	public static final String DIVIDE = "divide";
	public static final String DIVIDE2 = "divide2";
	public static final String MULTIPLY = "multiply";
	public static final String SUBTRACT = "subtract";
	public static final String ADD = "add";

	public final BigDecimal value;
	public final String computation;
	
	private Value(BigDecimal value, String computation) {
		this.value = value;
		this.computation = computation;
	}
	
	public static Value value(int value){
		return new Value(new BigDecimal(value),""+value);
	}

	public static void main(String[] args) {
		System.out.println("Test: "+Value.class.getSimpleName());
		
		Value value = value(5).compute(MULTIPLY,5).compute(SUBTRACT, 5).compute(DIVIDE, 2);
		
		System.out.println(value.computation);
		System.out.println(value.value);
	}

	public Value compute(String operation, int i) {
		if (this.value == null){
			// nie mozna wyknywac operacj, poprostu zwroc orginal
			// pozwala na unikniecie NPE w trakcie przetwarzania łańcucha
			return this;
		}
		BigDecimal eval = null; 
		BigDecimal value2 = new BigDecimal(i);
		String evalStrin = "";
		
		if (ADD.equals(operation)){
			
			eval = this.value.add(value2);
			evalStrin = evalStrin(this.value, "+" ,value2);
			
		} else if (SUBTRACT.equals(operation)){
			
			eval = this.value.subtract(value2);
			evalStrin = evalStrin(this.value, "-" ,value2);
			
		} else if (MULTIPLY.equals(operation)){
			
			eval = this.value.multiply(value2);
			evalStrin = evalStrin(this.value, "*" ,value2);
			
		} else if (DIVIDE.equals(operation)){
			if(BigDecimal.ZERO.compareTo(value2) != 0){
				eval = this.value.divide(value2, MathContext.DECIMAL32);
			} 
			evalStrin = evalStrin(this.value, "/" ,value2);
			
		} else if (DIVIDE2.equals(operation)){
			if(BigDecimal.ZERO.compareTo(this.value) != 0){
				eval =  value2.divide(this.value, MathContext.DECIMAL32);
			} 
			evalStrin = evalStrin(value2, "/" ,this.value); // odwrocenie
			
		}
		String computation = this.computation + "; "+ evalStrin + " = " + eval;
		Value v = new Value(eval, computation);
		return v;
	}
	
	private static String evalStrin(BigDecimal v1,String operation, BigDecimal v2){
		return "( "+v1 + " "+operation+" " + v2+" )";
	}
	
}

Klasa Permutation, generująca zbiory, została zamieszczona na końcu.

Wnioski z tej zabawy
Fajnie jest czasem pomyśleć nad innymi problemami niż te z którymi ma się zwyczajowo styczność.

Kawałek kodu do generowania możliwych zbiorów pewnie kiedyś się jeszcze przyda. Pierwsze co przychodzi do głowy to generowanie haseł :), ale pewnie są bardziej życiowe przykłady. Chociaż trochę dziwne że nie można czegoś takiego dla javy łatwo znaleźć (może w jakichś matematycznych bibliotekach), dla pythona od razu znalazłem przykład.

Ciekawym pomysłem byłoby aby w generatorze zbiorów dać możliwość sterowania kolejnością zwracanych rezultatów. Tak aby zbiory z wieloma powtórzeniami (*,*,*,*,*) były zwracane na końcu, podczas gdy zróżnicowane w miarę na początku (+,*,*,-,/). Jakoś powinno da się ustawić pożądaną kolejność zwracania zbiorów dla danej klasy problemu, ten facet z filmiku pewnie musi tak robić :).

Można stracić dużo czasu na cyzelowanie implementacji. Zwłaszcza było tak w przypadku Permutation. Kod dający rozwiązanie powstał w jakieś 4 godzin, a zabawa z nim aby go poprawić (przyspieszyć i zrobić bardziej czytelnym) odwlekła się w czasie o jakiś miesiąc ;). I tak nie jest to piękne, ale najgorszy bałagan jest na samym dole. Ciekawe czy tak praca zwróci się w postaci łatwego zrozumienia o co tu biega, jak za jakiś czas wrócę do tego kod.

public class Permutation {

	public static void main(String[] args) {
		int count = 1;
		long start = System.currentTimeMillis();
		for (Integer[] intSet : variationWithoutRepetition(6, new Integer[] { 25, 50, 75, 100, 3, 6 })) {
			System.out.println(Arrays.toString(intSet) + " - " + (count++));
		}
		System.out.println("Czas = " + (System.currentTimeMillis() - start));
	}

	public static <E> Iterable<E[]> variationWithoutRepetition(final int wordLength, final E ... values) {
		return new Iterable<E[]>() {
			public Iterator<E[]> iterator() {
				return new Variation<E>(
						new UpdateContextWithoutRepetition(values.length, wordLength) 
						, values);
			}
		};
	}
	public static <E> Iterable<E[]> variationWithRepetition(final int wordLength, final E ... values) {
		return new Iterable<E[]>() {
			public Iterator<E[]> iterator() {
				return new Variation<E>(
						new UpdateContextWithRepetition(values.length, wordLength)
						, values);
			}
		};
	}
	
	private static class Variation<E> implements Iterator<E[]>  {
		E[] dictionery = null;
		UpdateContext conetxt;
		
		private Variation(UpdateContext conetxt, E ... dict) {
			this.dictionery = dict;
			this.conetxt = conetxt;
		}

		@Override
		public void remove() {
		}
		
		@Override
		public boolean hasNext() {
			return  conetxt.hasNext();
		}

		@Override
		public E[] next() {
			return remapToDictionery(conetxt.nextWord());
		}

		private E[] remapToDictionery(int[] currentIndex) {
			E[] nextWord = create(currentIndex.length);
			for (int i = 0; i < currentIndex.length; i++) {
				nextWord[i] = dictionery[currentIndex[i]];
			}
			return nextWord;
		}

		private E[] create(int length) {
			Class<?> componentType = this.dictionery[0].getClass();
			@SuppressWarnings("unchecked")
			E[] newInstance = (E[])java.lang.reflect.Array.newInstance(componentType, length);
			return newInstance;
		}
		
	}
	
	abstract static class UpdateContext {
		int dictioneryLength;
	    int[] currentIndexWord;
		long finishCount;
		long count = 0;
		int startFromLastIndex;
		private int currentIndex;
		
		public UpdateContext(int dictioneryLength, int wordLength) {
			this.dictioneryLength = dictioneryLength;
			
			this.finishCount = this.finishCount(wordLength);
			this.startFromLastIndex = wordLength - 1;
		}
		
		public boolean hasNext() {
			return (finishCount != count);
		}
		
		public int[] nextWord() {
			if (this.currentIndexWord == null){ // start
				this.currentIndexWord = this.createStartIndexWord();
			} else {
				updateIndex(startFromLastIndex);
			}
			count++;
			return this.currentIndexWord;
		}
		
		private void updateIndex(int lastLetterInWordToChangeIndex) {
			updateCurrentIndex(lastLetterInWordToChangeIndex);
			if (isLastPosibleWord()) {
				// ostatni mozliwy index
				// ustaw na poczatek i zwieksze w poprzedzajacym
				if (lastLetterInWordToChangeIndex > 0) {
					updateIndex(lastLetterInWordToChangeIndex - 1);
				}
				// po powrocie z rekurencyjnego wywolania uaktualnij kontekst
				updateCurrentIndex(lastLetterInWordToChangeIndex);
				setLettet(getFirstPosibleLetter());
			} else {
				setLettet(getNextPosibleLetter());
			}
		}
		
		public void updateCurrentIndex(int currentIndexValue){
			currentIndex = currentIndexValue;
			update(currentIndex);
		}
		public boolean isLastPosibleWord() {
			return currentIndexWord[currentIndex] == getLastPosibleLetterInWord();
		}
		public int getNextPosibleLetter(){
			return getNextPosibleLetterForGivenIndex(currentIndex);
		}
		public int getFirstPosibleLetter() {
			return firstPosibleLetter();
		}
		public void setLettet(int letter){
			currentIndexWord[currentIndex] = letter;
		}
		
		protected abstract int firstPosibleLetter();

		protected abstract int[] createStartIndexWord();

		protected abstract int getNextPosibleLetterForGivenIndex(int lastWordToChangeIndex);

		protected abstract void update(int lastWordToChangeIndex);

		protected abstract long finishCount(int dictLength);
		
		protected abstract int getLastPosibleLetterInWord();
	}
	
	private static class UpdateContextWithoutRepetition extends UpdateContext {
		
		int[] letterThatCanBeUsed;

		public UpdateContextWithoutRepetition(int dictioneryLength, int wordLength) {
			super(dictioneryLength, wordLength);
		}
		@Override
		public int firstPosibleLetter(){
			return letterThatCanBeUsed[0];
		}
		@Override
		public int getLastPosibleLetterInWord(){
			return letterThatCanBeUsed[letterThatCanBeUsed.length - 1];
		}
		@Override
		public int getNextPosibleLetterForGivenIndex(int lastWordToChangeIndex){
			int letterIndexInPosibleWords = findItPositionInArray(this.currentIndexWord[lastWordToChangeIndex], letterThatCanBeUsed);
			return letterThatCanBeUsed[letterIndexInPosibleWords+1];
		}
		
		private static int findItPositionInArray(int it, int[] array){
			for (int i = 0; i < array.length; i++) {
				if(array[i] == it){
					return i;
				}
			}
			return -1;
		} 
		
		@Override
		protected void update(int lastWordToChangeIndex) {
			this.letterThatCanBeUsed = getLetterThatCanBeUsed(lastWordToChangeIndex, currentIndexWord);
		}
		
		@Override
		public int[] createStartIndexWord() {
			return createRange(0, dictioneryLength);
		}
		
		private static int[] createRange(int start, int to){
			int[] range = new int[to - start];
			for (int i = 0; i < range.length; i++) {
				range[i] = i+start;
			}
			return range;
		}
		
		private int[] getLetterThatCanBeUsed(int lastWordToChangeIndex, int[] indexWord) {
			int[] arrayCopyFristValuesToGivenIndex = copyToGivenIndex(indexWord,lastWordToChangeIndex);
			int[] letterThatCanBeUsed = subtractFromRange(arrayCopyFristValuesToGivenIndex);
			return letterThatCanBeUsed;
		}
		
		private static int[] copyToGivenIndex(int[] remove, int toIndex) {
			int[] dest = new int[toIndex];
			System.arraycopy(remove, 0, dest, 0, dest.length);
			return dest;
		}
		
		private int[] subtractFromRange(int[] toRemove) {
			int[] range  = createRange(0, dictioneryLength);
			int resultSize = range.length - toRemove.length;
			if (resultSize == 0) {
				return range;
			}
			int[] result = new int[resultSize];
			
			int signeAsToRemove = -1; // value not in range
			for (int asIndexInRaneg : toRemove) {
				range[asIndexInRaneg] = signeAsToRemove; 
			}
			
			int index = 0;
			for (int valueFromRange : range) {
				if (valueFromRange != signeAsToRemove){
					result[index++] = valueFromRange;
				}
			}
			
			return result;
		}
		
		@Override
		public long finishCount(int dictLength){
			return factorial(dictioneryLength) / factorial(dictioneryLength - dictLength);
		}
		
		private static long factorial(int value) {
			long accumulator = 1L;
			for (long counter = value; ! (counter == 0); counter--) {
				accumulator = (counter * accumulator);
			}
			return accumulator;
		}
		
	}
	
	private static class UpdateContextWithRepetition extends UpdateContext {
		public UpdateContextWithRepetition(int dictioneryLength, int wordLength) {
			super(dictioneryLength, wordLength);
		}
		@Override
		public int firstPosibleLetter() {
			return 0;
		}
		@Override
		public int getLastPosibleLetterInWord() {
			return dictioneryLength - 1;
		}
		@Override
		public int getNextPosibleLetterForGivenIndex(int lastWordToChangeIndex) {
			return this.currentIndexWord[lastWordToChangeIndex] + 1;
		}
		@Override
		protected void update(int lastWordToChangeIndex) {
			// nic nie trzeba robic
		}
		@Override
		public long finishCount(int dictLength){
			return (long)Math.pow(dictioneryLength, dictLength);
		}
		@Override
		public int[] createStartIndexWord() {
			int[] startWord = new int[dictioneryLength];
			for (int i = 0; i < startWord.length; i++) {
				startWord[i] = 0;
			}
			return startWord;
		}
		
	}
	
}