[Contest] Spy Game

[shinya]

Buongiorno!

Ho ricevuto un dispaccio che non riesco a comprendere e ho pensato di condividerlo con voi
che siete più intelligenti di me.

I servizi hanno scoperto una serie di mail tra un certo Dylan e qualche suo conoscente.
Dylan pare lavori per un'associazione sovversiva che si fa chiamare Mutually Assured
Destruction Theorists, anche conosciuta come M.A.D.T., ed è sparito dalla circolazione recentemente.

Pare che le mail contengano parti di un codice segreto che va in qualche modo ricostruito.
Non si sa come, e soprattutto non si sa a cosa serva... i servizi sperano che lo scopriate
durante l'investigazione!

Si è scoperto che Dylan è un ex-matematico diventato terrorista, quindi per lui pare sia
stato impossibile resistere alla tentazione di nascondere i codici segreti dietro una serie
di problemi. I problemi possono essere risolti in vari modi, ma quello che i servizi
consigliano consiste nel creare piccoli programmi nel vostro linguaggio di programmazione
preferito in modo da poter risolvere problemi simili nel prossimo futuro.

Come noterete, l'ultima mail non contiene un problema da risolvere, ma solo un sito dove
si suppone sia stato memorizzato l'ultimo codice. Lo so, siete programmatori e non hacker
che violano siti web, ma mai come in questo caso vale il detto "Improvvisare, adattarsi,
raggiungere lo scopo" (cit.).

Ah, un'ultima cosa: i servizi indicano come termine per la risoluzione dell'enigma il giorno
1 Maggio 2012... ma non sappiamo perché, è solo una voce di corridoio.

Queste le mail intercettate...


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



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



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



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

[shinya]

PS.
Chi arriva primo, vince. (Capirete poi perché)
Non mi sono sbattuto troppo, non ho modo di tracciare chi ha vinto il contest.
Non fate troppo casino sull'interwebz, please.
Se avete dubbi o domande che credete possano interessare tutti, scrivete sul forum.
Se avete segnalazioni (bug/errori/ecc...) mandatemi un messaggio privato e vedrò di correggere ASAP.
C'è una parte di trial & error, quindi se vi bloccate in qualche punto, prima di chiedere, fate qualche prova :p

Buon divertimento :)

[banryu79]

Se uno ha trovato la soluzione che fa, la posta direttamente qui o la spedisce a te? (se pubblica subito la soluzione e il termine non è ancora scaduto spoilera a tutti gli altri...)
@EDIT:

Ma hai già risolto tutto?
Se uno ha trovato la soluzione, deve farci qualcosa da qualche parte... (ovviamente non deve postarla qui...)

Ok, ora ho capito :asd:

[shinya]

Ma hai già risolto tutto? :p
Se uno ha trovato la soluzione, deve farci qualcosa da qualche parte... (ovviamente non deve postarla qui...) :)

[rеpne scasb]

■

[shinya]

Scusa... ecco appunto, quando uno è fulminato è fulminato...
Era "il numero di zeri alla fine del FATTORIALE del 1_000_001 numero primo"... correggo nel primo messaggio, sorry :(

[gugoXX]

Grandino...

[rеpne scasb]

■

[gugoXX]

Commentavo sul numero, non sulla metodologia per calcolare la risposta.
E comunque non e' un quesito informatico, piuttosto matematico.

Per il terzo, piu' interessante, mi sto attrezzando :)

[rage88]

Si può avere un piccolo indizio sull'ultimissimo algoritmo :p ? Perchè quel "non è complicato per fortuna" mi ha fatto subito pensare alle soluzioni più banali, ma o ho qualche chiave sbagliata (eppure mi sembra siano giuste) oppure è più complicato di quello che penso :eek: :eek:

[shinya]

Si può avere un piccolo indizio sull'ultimissimo algoritmo :p ? Perchè quel "non è complicato per fortuna" mi ha fatto subito pensare alle soluzioni più banali, ma o ho qualche chiave sbagliata (eppure mi sembra siano giuste) oppure è più complicato di quello che penso :eek: :eek:
Scusa il ritardo ma sono stato fuori casa tutto il giorno. Mandami un PM con i codici che usi e come li combini :)

[banryu79]

Scusa il ritardo ma sono stato fuori casa tutto il giorno. Mandami un PM con i codici che usi e come li combini :)
Anche io compero una vocale! :O (pm spedito)

[shinya]

Complimenti a rage88 che ha risolto l'enigma e nel contempo salvato il mondo!

Kudos! You win cake! :happy:

ps. the cake is a lie...

EDIT: se a qualcuno interessa provare l'ultimo step per arrivare al codice finale posso ripristinare l'ultimo sito... fatemi sapere. :)

[rage88]

Può interessare a qualcuno se stasera posto gli algoritmi che ho usato? :) E gli errori che stavo facendo? (se volete resettare il problema e continuare a provarci ovviamente per me nessun problema)

[shinya]

Ok, resettato! :fagiano:

[banryu79]

Può interessare a qualcuno se stasera posto gli algoritmi che ho usato? :) E gli errori che stavo facendo? (se volete resettare il problema e continuare a provarci ovviamente per me nessun problema)
A me interessa capire come risolvere il quarto problema.
Chiaramente non si tratta di crackare il sito, presumo si abbia già in mano tutto per sgarrupare la password (le soluzioni dei 3 problemi).
Ma non ho la più pallida idea di come usarle :mbe:
Accetto ben volentieri un pm :D

[shinya]

A me interessa capire come risolvere il quarto problema.
Chiaramente non si tratta di crackare il sito
No no. Si tratta proprio di crackare il sito! :)
Puoi aggirare il controllo su user/password. O conoscere la password, ovviamente :p

[banryu79]

http://www.freeimagehosting.net/t/rplr3.jpg (http://www.freeimagehosting.net/rplr3)
Solved! :D

@EDIT:
1) Un ringraziamento a shinya per il bel contest: era dai tempi della "caccia al tesoro" che non mi divertivo così :)
2) e un grazie anche a repne e al suo post, senza il quale non avrei mai risolto il secondo problema (mi sarei stancato prima)

[shinya]

:happy:

[shinya]

Dato che mi pare l'interesse si sia smorzato, per quanto mi riguarda potete anche postare gli algoritmi/script che avete usato per risolvere i problemi e gli errori e gli abbagli che avete fatto :p
Se per voi va bene tiro giù anche i vari siti che ho messo su per il contest, dato che non intendo mantenerli più del dovuto...

[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 = array[i] - 48;
return digits;
}

[I] /**
* 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 * 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};

[I]/**
* 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) continue;
int[] neighbour = Arrays.copyOf(digits, digits.length);
neighbour[idx] = d;
int number = collapseDigits(neighbour);
list.add(number);
}
return list;
}

[I]//
// 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;
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;

[I]/**
* 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 + "}";
}
}