[Contest] Spy Game

[gugoXX]

Dai, metto la mia per il terzo quesito.
Alla fine e' un Dijkstra.
Dal nodo corrente provo a navigare su tutti i 9+9+9+9 = 36 numeri possibili.
Qualcuno apparterra' alla lista dei "primi ancora da visitare", gli altri invece vengono scartati.

 class Program
    {
        static void Main(string[] args)
        {

            Stopwatch sw = Stopwatch.StartNew();
            
            var path0 = PrimePathFinder.Instance.GetPath("1033", "8179");
            var path1 = PrimePathFinder.Instance.GetPath("1373", "8017");
            var path2 = PrimePathFinder.Instance.GetPath("5413", "4327");

            sw.Stop();
            Console.WriteLine("Time: {0}", sw.ElapsedMilliseconds);
            Console.ReadKey();
        }
    }

    public class PrimePathFinder
    {
        protected PrimePathFinder()
        {
        }

        public readonly static PrimePathFinder Instance = new PrimePathFinder();

        public ReadOnlyCollection<string> Primes = new ReadOnlyCollection<string> (new []{
            "1009","1013","1019","1021",.......,"9973"
        });           

        public List<string> GetPath(string first, string last)
        {         
            var tentativeDistance = Primes.ToDictionary(pr => pr, pr => int.MaxValue);

            if (!tentativeDistance.ContainsKey(first))
                return new List<string>();

            if (!tentativeDistance.ContainsKey(last))
                return new List<string>();

            if (first == last)
                return new List<string> { first };
                        
            var searchNeighbours = new Dictionary<string, int>(); 
            var comingFrom = new Dictionary<string, string>();

            var current = first;
            int nextWeigth = 0;
            do
            {
                nextWeigth++;

                foreach (var neighbour in ViciniPossibili(current))
                {
                    int distToPoint;
                    if (tentativeDistance.TryGetValue(neighbour, out distToPoint))
                    {
                        if (nextWeigth < distToPoint)
                        {
                            tentativeDistance[neighbour] = nextWeigth;
                            searchNeighbours[neighbour] = nextWeigth;
                            comingFrom[neighbour] = current;
                        }
                    }
                }
                tentativeDistance.Remove(current);
                searchNeighbours.Remove(current);

                if (!searchNeighbours.Any())
                    return new List<string>();

                var tdm = searchNeighbours.MinBy(v => v.Value);
                current = tdm.Key;
                nextWeigth = tdm.Value;                        
            } while (current != last);

            List<string> path = new List<string>();
            path.Add(current);

            do
            {
                var cf = comingFrom[current];
                path.Insert(0, cf);
                current = cf;
            }
            while (current != first);
            
            return path;
        }
       
        public IEnumerable<string> ViciniPossibili(string primo)
        {
            char[] ret = primo.ToCharArray();
            for (int t = 0; t < 4; t++)
            {
                var original = primo[t];                
                for (char v = '0'; v <= '9'; v++)
                {
                    ret[t] = v;
                    yield return new string(ret);
                }
                ret[t] = original;
            }
        }
       
    }

    public static class EnumerableExtensions
    {       
        public static T MinBy<T, TU>(this IEnumerable<T> domain, Func<T, TU> project)
            where TU : IComparable<TU>
        {
            var en = domain.GetEnumerator();
            en.MoveNext();
            T currentMin = en.Current;
            TU currentMinVal = project(currentMin);

            while(en.MoveNext())
            {
                var t = en.Current;
                var newProj = project(t);

                if (newProj.CompareTo(currentMinVal) < 0)
                {
                    currentMin = t;
                    currentMinVal = newProj;
                }
            }
           
            return currentMin;
        }      
    }

[rage88]

Posto allora anche il mio codice per il 3° problema che è il più interessante. Non ho usato Dijkstra essendo tutti gli archi a costo unitario, ma ho usato un algoritmo di attraversamento BFS. Il primo percorso trovato durante la navigazione del grafo è quello a costo minimo.
Il grafo ha ovviamente come nodi i numeri primi da 1000 a 9999 e un arco (u,v) è presente sse u e v differiscono per una sola cifra.

Di seguito il codice in C++.

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

bool isPrime(unsigned int i) {
	
	for(unsigned int d=2; d<= sqrt(i); d++){	
		if(i%d==0) {
			return false;
		
		}
	}
	return true;
}

void generatePrimeNumbers(vector<unsigned int> &v) {
	for(unsigned int i=1000; i<= 9999; i++) {
		if(isPrime(i)) {
			//cout << i << " is prime " << endl;
			v.push_back(i);
		}
	}
}

unsigned int numDiffDigits(unsigned int n, unsigned int m) {

	unsigned int nDD = 0;

	for(unsigned int i=10; i<=10000; i*=10) {
		if(!( (n%i) / (i/10) == (m%i) / (i/10) )) 
			nDD++;
	}
	return nDD;
}


void getNeighbourNodes(unsigned int n, vector<unsigned int> &dic, vector<unsigned int> &used, vector<unsigned int> &outNeighbours) {
	for(vector<unsigned int>::iterator it = dic.begin(); it != dic.end(); it++) {
		if(numDiffDigits(*it,n) == 1 && find(used.begin(), used.end(), *it) == used.end()) {
			/* Prime neighbour has not been used */
			outNeighbours.push_back(*it);
				
		}		
	}
}


unsigned int numSteps(unsigned int begin, unsigned int end, vector<unsigned int> &dictionary) {
	
	/* Coda dei percorsi da verificare. Il pair contiene il nodo e il costo ottenuto del
	percorso radice-nodo */
	deque< vector< pair<unsigned int, unsigned int> > > paths;
	
	/* Vettore dei nodi già percorsi */
	vector<unsigned int> used;


	vector< pair<unsigned int, unsigned int > > v;
	v.push_back(pair<unsigned int, unsigned int>(begin,0));

	/* Inizializzazione dei percorsi con il nodo di partenza */
	paths.push_back(v);
	
	used.push_back(begin);

	vector<unsigned int> neighbours;
	
	while(true) {
		if(paths.size() == 0) {
			cout << "No more paths to follow" << endl;
			return 0;
		}
		
		neighbours.clear();
		

		/* Current path to follow */ 
		vector< pair <unsigned int, unsigned int> > currentPath = paths.front();

		paths.pop_front();

		getNeighbourNodes( currentPath.at(currentPath.size()-1).first, dictionary, used, neighbours);
		
		
		for(vector<unsigned int>::iterator it = neighbours.begin(); it!= neighbours.end(); it++) {
			
			//cout << *it << " is neighbour of " << currentPath.at(currentPath.size()-1).first << endl;

			if(*it == end) {
	
				currentPath.push_back(pair<unsigned int,unsigned int>(*it, currentPath.at(currentPath.size()-1).second +1));
				
				cout << "## Found path!";
				for(vector< pair <unsigned int, unsigned int> >::iterator it = currentPath.begin() ; it!=currentPath.end(); it++) 
					cout << (*it).first << " " ;
				
				cout << endl;
				
				return currentPath.at(currentPath.size()-1).second;
			}	
			
			currentPath.push_back(pair<unsigned int,unsigned int>(*it, currentPath.at(currentPath.size()-1).second +1));
			paths.push_back(currentPath);
			

			used.push_back(*it);
			currentPath.pop_back(); 
		}
	}
}			


int main() {

	vector<unsigned int> primes;
	generatePrimeNumbers(primes);
	
	//for(vector<unsigned int>::iterator it = primes.begin(); it!= primes.end(); it++)
	//	cout << *it << endl;

	unsigned int begin = 1373;
	unsigned int end = 8017;
	
	unsigned int n = numSteps(begin,end,primes);
	
	begin = 5413;
	end = 4327;

	unsigned int m = numSteps(begin,end,primes);

	cout << n << ", " << m << endl;

}

Per il 4° problema ho usato un SQL injection mettendo nel campo username
maya' OR 1=1 --
con spazio dopo il -- altrimenti non lo considera come commento. Qualcuno ha fatto diversamente?

[banryu79]

Anche io per il 3° problema ho usato Dijkstra (da pigraccio quale sono, ho usato la libreria JGrapht).
Invece per il 4° problema la mia stringa per la sql injection è: "Maya' #".
Posto il codice scritto (in Java)
Inoltre ci ho messo un po' a capire perchè il secret calcolato sembrasse non funzionare...finchè non mi son chiesto perchè l'ultimo share fosse espresso in formato esadecimale.

package spycontest;

import java.util.List;
import org.jgrapht.Graph;
import org.jgrapht.alg.DijkstraShortestPath;

/**
 * Soluzioni del contest "Spy game"
 * http://www.hwupgrade.it/forum/showthread.php?t=2465013
 * 
 * @author francesco
 */
public class Solutions {
    
    public static void main(String[] args) {
        solutionForProblem1();
        solutionForProblem2();
        solutionForProblem3();
        solutionForProblem4();
        solutionForProblem5();
    }
    
//    Problem #1
//    ----------
//    Ciao Jim!
//    Come ben sai sto per imbarcarmi in una missione molto pericolosa per conto della M.A.D.T.
//    e non so quando ci rivedremo. Ho deciso di dividere un'informazione di vitale importanza
//    tra i miei amici più fidati.
//
//    Siccome sei sempre stato uno smanettone, credo che ti divertirai di più così...
//
//    La tua parte di segreto corrisponde al 1_000_001-esimo numero primo.
//
//    Saluti,
//    Dylan
    
    public static void solutionForProblem1() {
        System.out.println("- solution#1");
        int count = 2;
        int number = 3;
        while (count < 1000001) {
            number += 2;
            if (Utilities.isPrime(number)) count++;
        }
        System.out.println(number);
    }

//    Problem #2
//    ----------
//    Hey Richard!
//    Come ben sai sto per imbarcarmi in una missione molto pericolosa per conto della M.A.D.T.
//    e non so quando ci rivedremo. Ho deciso di dividere un'informazione di vitale importanza
//    tra i miei amici più fidati.
//
//    La tua parte di codice consiste nel calcolare il numero di zeri alla fine del fattoriale del  
//    1_000_001-esimo numero primo! :-)
//
//    Alla prossima,
//    Dylan
    
    public static void solutionForProblem2() {
        System.out.println("- solution#2");
        //Sia n il 1000001-esimo numero primo (ossia 15485867).
        //Sia k la massima potenza di cinque tale che 5^k <= n (k=10)
        //Allora il numero di zeri (in base 10) e' uguale alla sommatoria per i che va da 1 a k di INT(n/(5^i)), 
        //ossia 3871461 (a meno di errori grossolani (INT e' la funzione di troncamento)). 
        final int n = 15485867;
        final int k = 10;
        int sum = 0;
        for (int i=1; i<=k; i++) sum += n/(Math.pow(5, i));
        System.out.println(sum);
    }
    
//    Problem #3
//    ----------
//    Frank!
//    Come ben sai sto per imbarcarmi in una missione molto pericolosa per conto della M.A.D.T.
//    e non so quando ci rivedremo. Ho deciso di dividere un'informazione di vitale importanza
//    tra i miei amici più fidati.
//
//    Per la tua parte di segreto ho una storia da raccontarti.
//
//    Una volta, quando lavoravo per la Germania Est, ho avuto un incarico governativo presso
//    il Primo Ministro. Un giorno qualcuno decise che avremmo dovuto riorganizzare gli uffici,
//    cambiando tutti i numeri delle stanze.
//    Questo mandò su tutte le furie il Primo Ministro, che andava fiero della sua stanza 1373!
//    Essendo il Primo Ministro non poteva sopportare che il suo ufficio avesse un numero di 
//    stanza che non fosse un numero primo! E come biasimarlo!
//    Ma non solo, non poteva nemmeno sopportare che durante il cambio di numero qualcuno
//    attaccasse la cifra sbagliata rendendo temporaneamente il numero non primo!
//    Se avesse dovuto cambiare dalla stanza 1373 alla 8017 e qualcuno avesse cominciato 
//    attaccando un 8 alla prima cifra, il Primo Ministro sarebbe andato su tutte le furie
//    perché 8373 non è un numero primo!
//    Ogni cambio di cifra costò all'ufficio 1 Marco. Mi toccò sviluppare un programma che
//    calcolasse il costo minore passando da un numero primo all'altro passando solo attraverso
//    altri numeri primi! Ad esempio, cambiando da 1033 a 8179 costava 6 Marchi.
//    Un esempio di percorso più breve infatti è:
//
//    1033
//    1733     
//    3733     
//    3739     
//    3779
//    8779
//    8179      
//
//    La tua parte di codice è il prodotto dei costi minori tra 1373 -> 8017 e 5413 -> 4327.
//
//    Certo, potresti pure farlo a mano... ma saresti sicuro del risultato? E soprattutto, 
//    ti divertiresti? :-P
//
//    Saluti,
//    Dylan
    
    public static void solutionForProblem3() {
        System.out.println("- solution#3");
        Range range = Utilities.generatePrimesBetween(1009, 9973);
        Graph<Integer,Pair> g = Utilities.neighboursGraph(range);
        int cost1 = findShortestPathLength(g, 1373, 8017);
        int cost2 = findShortestPathLength(g, 5413, 4327);
        System.out.println(cost1*cost2);
    }
    
    static int findShortestPathLength(Graph<Integer,Pair> graph, int a, int b) {
        List<Pair> path = DijkstraShortestPath.findPathBetween(graph, a, b);
        return path.size();
    }
    
//    Problem #4
//    ----------
//    Carissima Maya,
//    sai bene della mia missione e non mi dilungherò su questo...
//
//    Per tutto quello che ci ha legati e per il fatto che non sei mai stata una smanettona, non
//    posso rifilarti un problema da risolvere per scoprire la tua parte di segreto.
//    L'ho semplicemente messa al sicuro al solito posto: http://bit.ly/HUYGVU
//
//    A presto,
//    Dylan
    
    public static void solutionForProblem4() {
        System.out.println("- solution#4");
        System.out.println("navigate to \"http://bit.ly/HUYGVU\" and in the user field input the string \"Maya\' #\"");
        System.out.println("Maya\'s code is 35D7F726");
    }
    
// Problem #5
// ----------
//    Complimenti!
//    Se siete arrivati fino a qui significa che avete tutti i pezzi per risolvere il
//    puzzle! :-)
//    Se invece non avete tutti i pezzi, beh... correte a risolvere gli altri
//    problemi!
//    Cosa ve ne fate di tutti questi numeri, direte voi? Beh l'idea è nata quando ho
//    scoperto di una cosa chiamata "secret sharing" (google vi sarà amico questa
//    volta :-P).
//    Vi lascio indovinare quale algoritmo ho usato per spezzare il segreto originale
//    in N parti! Divertitevi! Ma non scervellatevi troppo... non è complicato per
//    fortuna :-)
//
//    ps. 
//    Ah, quasi dimenticavo!
//    Vi chiederete:"E poi? Che ci facciamo con questo codice??". Beh, si da il caso
//    che stessi nascondendo un segreto piuttosto importante: http://bit.ly/J35owD
//
//    pps.
//    Scusate la macabra ironia: dato l'argomento del link qui sopra avrei dovuto
//    tenere un tono più serio, ma sapete che non ne sono capace!
//    
//    Maya's code: 35D7F726

    public static void solutionForProblem5() {
        System.out.println("- solution#5");
        // secret shares:
        // 15485867
        // 3871461
        // 42
        // 903345958 (35D7F726 hex)
        int r1 = 15485867;
        int r2 = 3871461;
        int r3 = 42;
        int r4 = 903345958;
        
        // trivial secret sharing
        int s = r4 ^ r3 ^ r2 ^ r1;
        System.out.println(Integer.toHexString(s));
    }
    
}

package spycontest;

import java.util.*;
import org.jgrapht.Graph;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.graph.SimpleGraph;

/**
 * Utility class
 * 
 * @author francesco
 */
public class Utilities {
    
    /**
     * Build the graph of all "neighbouring" relationship 
     * between the given range of prime numbers
     * @param range a range of prime numbers
     * @return the "neighbouring" graph
     */
    public static Graph<Integer,Pair> neighboursGraph(Range range) {
        UndirectedGraph<Integer,Pair> g = new SimpleGraph<>(Pair.class);
        for (int n : range) {
            g.addVertex(n);
        }
        for (int n : range) {
            Set<Integer> neighbours = Utilities.generatePrimeNeighboursOf(n);
            for (int m : neighbours) g.addEdge(n, m, Pair.of(n, m));
        }
        return g;
    }
    
    /**
     * Generate all prime numbers between first and last, inclusive.<p>
     * Precondition:<br> 
     * first and last must be prime;<br>
     * first must be smaller than last.<br>
     * @param first the smallest prime number.
     * @param last the greates prime number.
     * @return the selected range of primes.
     */
    public static Range generatePrimesBetween(int first, int last) {
        if (!isPrime(first)) {
            throw new IllegalArgumentException("Argument 'first' should be prime");
        }
        if (!isPrime(last)) {
            throw new IllegalArgumentException("Argument 'last' should be prime");
        }
        if (first > last) {
            throw new IllegalArgumentException("Argument 'first' should be lesser than 'last'");
        }
        List<Integer> list = new LinkedList<>();
        list.add(first);
        for (int n = first+2; n<last; n+=2) if (isPrime(n)) {
            list.add(n);
        }
        list.add(last);
        return new Range(list);
    }
    
    /**
     * Generate all primes that are "neighbours" of num.
     * To be a neighbour of num, a prime should differ from num by only one digit.<p>
     * Preconditions:<br>
     * num should be prime.<br>
     * @param num the prime number
     * @return the set of primes that are neigbours of num
     */
    public static SortedSet<Integer> generatePrimeNeighboursOf(int num) {
        if (!isPrime(num)) {
            throw new IllegalArgumentException("Argument 'num' should be prime.");
        }
        SortedSet<Integer> set = new TreeSet<>();
        int[] digits = splitDigits(num);
        for (int i=0; i<digits.length; i++) {
            List<Integer> neighbours = neighboursForDigit(digits, i);
            for (int neighbour : neighbours) if (isPrime(neighbour)) {
                set.add(neighbour);
            }
        }
        return set;
    }
    
    /* 
     * Naive primality test
     * test for all odd integers from 3 to sqrt(n) (inclusive)
     */
    public static boolean isPrime(int n) {
        if (n%2 == 0) return false;
        int limit = (int) Math.sqrt(n);
        for (int div=3; div<=limit; div+=2) if (n%div == 0) {
            return false;
        }
        return true;
    }
    
    /*
     * Get the array of digits of a positive integer number.<p>
     * Preconditions:<br>
     * number must be positive (i.e. greater than zero).<br>
     * @param number the positive integer
     * @return the digits of number
     */
    private static int[] splitDigits(int number) {
        if (number <= 0) {
            throw new IllegalArgumentException("Argument 'number' should be greater than zero.");
        }
        char[] array = Integer.toString(number).toCharArray();
        int[] digits = new int[array.length];
        for (int i=0; i<array.length; i++) digits[i] = array[i] - 48;
        return digits;
    }
    
    /**
     * Get the positive integer number denoted by an array of digits.<p>
     * Preconditions:<br>
     * all elements of digits should not be negative numbers.<br>
     * @param digits the integer number's digits
     * @return the integer number
     */
    private static int collapseDigits(int[] digits) {
        for (int digit : digits) if (digit < 0) {
            throw new IllegalArgumentException("Argument 'digits' should only contains positve values.");            
        }
        int factor = 1;
        int number = 0;
        for (int i=digits.length-1; i>=0; i--) {
            number += digits[i] * factor;
            factor *= 10;
        }
        return number;
    }
    
    private static final int[] decimalsWithoutZero = {1,2,3,4,5,6,7,8,9};
    private static final int[] decimalsWithZero = {0,1,2,3,4,5,6,7,8,9};
    
    /**
     * Compute all the primes that are neighbours of the
     * given one (digits). A prime to be a neighbour of 
     * another must differ from him of exactley one digit
     * @param idx
     * @param digits
     * @return 
     */
    private static List<Integer> neighboursForDigit(int[] digits, int idx) {
        int[] decimals = (idx == 0) ? decimalsWithoutZero : decimalsWithZero;
        List<Integer> list = new LinkedList<>();
        for (int d : decimals) {
            if (d == digits[idx]) continue;
            int[] neighbour = Arrays.copyOf(digits, digits.length);
            neighbour[idx] = d;
            int number = collapseDigits(neighbour);
            list.add(number);
        }
        return list;
    }
    
//
// Tests ---------------
//
    
    public static void main(String[] args) {
        testGeneratePrimesBetween(11, 97);
        testGeneratePrimesBetween(101, 997);
        testGeneratePrimesBetween(1009, 9973);
        testSplitDigits(1234567890);
        testSplitDigits(1011110010);
        testSplitDigits(Integer.MAX_VALUE);
        int[] arr1 = {1,2,3,4};
        testCollapseDigits(arr1);
        int[] arr2 = {0,3,9,5,2,0};
        testCollapseDigits(arr2);
        int index = 3;
        int[] digits = {1,0,0,9};
        testNeighboursOfDigit(digits, index);
    }

    private static void testSplitDigits(int number) {
        int[] digits = splitDigits(number);
        System.out.println("- testSplitDigits(" + number + ")");
        System.out.println("output = " + Arrays.toString(digits));
    }

    private static void testCollapseDigits(int[] digits) {
        int number = collapseDigits(digits);
        System.out.println("- testCollapseDigits(" + Arrays.toString(digits) + ")");
        System.out.println("output = " + number);
    }

    private static void testNeighboursOfDigit(int[] digits, int index) {
        List<Integer> neighbours = neighboursForDigit(digits, index);
        System.out.println("- testNeighboursOfDigit(" + index + ", " + Arrays.toString(digits) + ")");
        System.out.println("output = " + neighbours);
    }

    private static void testGeneratePrimesBetween(int first, int last) {
        Range range = generatePrimesBetween(first, last);
        System.out.println("- testGeneratePrimesBetween(" + first + ", " + last + ")");
        System.out.println("output: " + range.toLongString());
    }
}

package spycontest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

/**
 * Holds a range of sorted integer numbers.
 * Immutable.
 * 
 * @author francesco
 */
public class Range implements Iterable<Integer> {
    
    public final int first;
    public final int last;
    public final int size;
    
    private final List<Integer> primes;
    private String asString;
    private String asLongString;
    
    public Range(Integer... items) {
        first = items[0];
        last = items[items.length-1];
        size = items.length;
        primes = Arrays.asList(items);
    }
    
    public Range(int... items) {
        first = items[0];
        last = items[items.length-1];
        size = items.length;
        primes = new ArrayList<>(size);
        for (int n : items) primes.add(n);
    }
    
    public Range(List<Integer> list) {
        first = list.get(0);
        last = list.get(list.size() - 1);
        size = list.size();
        primes = list;
    }
    
    @Override
    public Iterator<Integer> iterator() {
        return primes.iterator();
    }
    
    @Override
    public String toString() {
        if (asString == null) {
            asString = "Range(" + first + ".." + last + ", of size " + size +")";
        }
        return asString;
    }
    
    public String toLongString() {
        if (asLongString == null) {
            StringBuilder buffer = new StringBuilder()
                .append(this.toString()).append(":\n")
                .append("[");
            for (int n : primes) buffer.append(n).append(",");
            buffer.replace(buffer.length() - 1, buffer.length(), "]");
            asLongString = buffer.toString();
        }
        return asLongString;
    }
}

package spycontest;

/**
 * An immutable tuple of two integer numbers
 * @author francesco
 */
public final class Pair {
    
    public static Pair of(int a, int b) {
        return new Pair(a, b);
    }
    
    public final int a, b;
    
    private Pair(int a, int b) {
        this.a = a;
        this.b = b;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (obj == this) return true;
        if (!(obj instanceof Pair)) return false;
        Pair other = (Pair) obj;
        return this.a == other.a && this.b == other.b;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 17 * hash + this.a;
        hash = 31 * hash + this.b;
        return hash;
    }
    
    @Override
    public String toString() {
        return "{" + a + "," + b + "}";
    }
}