Lottery: test de programación by Spotify

Solución en Java para el problema de la lotería expuesto por Spotify. Para resolverlo hay que tener claro el concepto de probabilidad en conjuntos. Para ver en detalle el código acceder al siguiente enlace.

	import java.util.Scanner;
	import java.io.BufferedInputStream;
	public class Lottery {
	public static double LotteryProbability (String lottery) {
	int m=0,n=0,t=0,p=0,requiredForWin=0;
	double result=0.0;
	String[] number = lottery.split(" ");
	m=Integer.parseInt(number[0]);
	n=Integer.parseInt(number[1]);
	t=Integer.parseInt(number[2]);
	p=Integer.parseInt(number[3]);
	requiredForWin=(int)Math.ceil((double)p/t);
	if (requiredForWin>n) { return result; }
	for (int i=requiredForWin;i<(Math.min(n,p)+1);i++) {
	result+=probability(i,p,n,m);
	}
	return result;
	}
	private static double probability (int x, int p, int n, int m) {
	double result=0.0,y=0.0;
	y=combination(m,n);
	if (y==0.0) { return result; } else {
	result=combination(p, x)*combination(m-p, n-x)/y;
	}
	return result;
	}
	private static double combination(int n, int m) {
	double result=1.0;
	if ((m<0)||(m>n)) { return 0.0; }
	if (m>(n-m)) { m=(n-m); }
	for (int i=0;i<m;i++) {
	result=result*(n-(m-(i+1)));
	result=result/(i+1);
	}
	return result;
	}
	public static boolean validEntry (String line) {
	int val1=0,val2=0,val3=0,val4=0;
	boolean result=true;
	String[] number = line.split(" ");
	if (number.length==4) {
	String n_line= new String (line.replaceAll("[0-9]+", ""));
	if (n_line.length()!=3) { result=false; } else {
	val1=Integer.parseInt(number[0]);
	val2=Integer.parseInt(number[1]);
	val3=Integer.parseInt(number[2]);
	val4=Integer.parseInt(number[3]);
	if ((val1<1)||(val2<1)||(val3<1)||(val4<1)) { result=false; }
	if ((val1>1000)||(val2>val1)||(val3>100)||(val4>val1)) { result=false; }
	}
	} else {
	result=false;
	}
	return result;
	}
	public static void main(String[] args) {
	try {
	double result=0.0;
	Scanner sca = new Scanner(new BufferedInputStream(System.in));
	String line = sca.nextLine();
	if (validEntry(line)) { result=LotteryProbability(line); }
	System.out.printf("%.10f\n", result);
	} catch (Exception e) {
	System.err.println("Error: " + e.getMessage());
	}
	}
	}

view raw Lottery.java hosted with ❤ by GitHub

Best Before: test de programación by Spotify

En el sitio web de Spotify existe una sección en la que su gente nos reta a resolver problemas de computación. Es una practica muy extendida actualmente por las grandes empresas el realizar este tipo de filtros para reducir rápidamente el número de posibles candidatos a un puesto. En el caso de Spotify no están directamente asociados a ninguna posición, pero imagino que, ya que el envío para verificar el código se hace a través de correo electrónico, a buen seguro guardarán aquellas respuestas correctas y es posible que las tengan en consideración para una futura entrevista. De cualquier forma es un ejercicio intelectual muy recomendable. A mi personalmente me ha servido para poner a punto mis habilidades de programación.

En el ejercicio Best Before Spotify nos propone resolver un problema de fechas. Como bien sabemos, según el formato, una tupla de números puede representar varias fechas válidas. Dada una tupla nos piden encontrar, por combinaciones, la menor fecha correcta posible. Consejo: lee detenidamente el enunciado. Hay varias limitaciones sobre cómo pueden aparecer los datos (esto es, con diferencia, lo que me entretuvo mas tiempo a la hora de llegar a la solución correcta). A continuación os detallo el código Java que lo resuelve. He intentado que sea lo mas legible y hacer uso de tipos de fecha, que me parecía lo mas elegante (el código puede verse con mayor claridad en el siguiente enlace):

	import java.util.Date;
	import java.util.Scanner;
	import java.util.LinkedList;
	import java.util.Iterator;
	import java.text.SimpleDateFormat;
	public class BestBefore {
	//Verify if it is a leap year
	public static boolean isaleapyear (int year) {
	boolean result=false;
	if ((year%4==0)&&((year%100!=0)||(year%400==0))) { result=true; }
	return result;
	}
	//Verify is generated date could be a valid date
	public static boolean correctDate(String s_year, String s_month, String s_day) {
	int year=Integer.parseInt(s_year),month=Integer.parseInt(s_month),day=Integer.parseInt(s_day);
	int[] monthDays={0,31,28,31,30,31,30,31,31,30,31,30,31};
	boolean result=true;
	if (isaleapyear(year)) { monthDays[2]=29; }
	if ((month<=0)||(month>12)) {
	result=false;
	} else {
	if ((day<=0)||(day>monthDays[month])) { result=false; }
	}
	return result;
	}
	//Transform input year in a four digit year
	public static String extendedYear (String s_year) {
	int year=0;
	year=Integer.parseInt(s_year);
	if (year<2000) { year=year+2000; }
	return String.valueOf(year);
	}
	//Verify input string is correctly formated
	public static boolean inputStringisCorrect(String line) {
	int k=0,x=0,y=0,fourDigitYear=0;
	String n_line;
	boolean result=true;
	n_line = new String(line.replaceAll("/", ""));
	if ((n_line.length()+2)!=line.length()) {
	result=false;
	} else {
	String[] number = line.split("/");
	for (int i=0;i<3;i++) {
	if (number[i].length()==4) { fourDigitYear++; k=i; }
	}
	if (fourDigitYear>1){
	result=false;
	} else {
	if (fourDigitYear==1) {
	switch(k) {
	case 0: x=1; y=2; break;
	case 1: x=0; y=2; break;
	case 2: x=0; y=1; break;
	}
	if ((Integer.parseInt(number[k])<2000)||(Integer.parseInt(number[k])>2999)) { result=false; }
	if ((number[x].length()<1)||(number[x].length()>2)) { result=false; }
	if ((number[y].length()<1)||(number[y].length()>2)) { result=false; }
	} else {
	for (int i=0; i<3; i++) {
	if ((number[i].length()<1)||(number[i].length()>2)) { result=false; }
	}
	}
	}
	}
	return result;
	}
	//Main
	public static void main(String[] args) {
	try {
	long value=0;
	boolean anyDate=false;
	int val1=0,val2=0,val3=0;
	Date currentDate;
	Date resultDate = new Date();
	LinkedList<Date> listofDates = new LinkedList<Date>();
	SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy/MM/dd");
	//Read initial date from the standard system input
	Scanner sca = new Scanner(System.in);
	String line = sca.nextLine();
	//Verify input string is correct
	if (inputStringisCorrect(line)) {
	String[] number = line.split("/");
	//In each iteration we change the position of array elements to generate all possible date combinations (up to six)
	for (int i=0;i<6;i++) {
	switch (i) {
	case 0: val1=0;val2=1;val3=2; break;
	case 1: val1=0;val2=2;val3=1; break;
	case 2: val1=1;val2=0;val3=2; break;
	case 3: val1=1;val2=2;val3=0; break;
	case 4: val1=2;val2=0;val3=1; break;
	case 5: val1=2;val2=1;val3=0; break;
	}
	if (correctDate(extendedYear(number[val1]), number[val2], number[val3])) {
	currentDate=dateFormat.parse(extendedYear(number[val1])+"/"+number[val2]+"/"+number[val3]);
	if (currentDate.getTime()>=value) { value=currentDate.getTime(); }
	listofDates.add(currentDate);
	}
	}
	//Now, we got a list of valid dates. We're going to search on it to find the earliest one
	Iterator<Date> iterator = listofDates.iterator();
	while(iterator.hasNext())
	{
	currentDate = (Date) iterator.next();
	if (currentDate.getTime()<=value) {
	anyDate=true;
	value=currentDate.getTime();
	resultDate = currentDate;
	}
	}
	//Finally, if there is any valid date, we show it in the required output format
	if (anyDate) {
	java.text.SimpleDateFormat sdf=new java.text.SimpleDateFormat("yyyy-MM-dd");
	System.out.println(sdf.format(resultDate));
	} else {
	System.out.println(line+" is illegal");
	}
	} else {
	//Input string is incorrect so we write an illegal message on standard output
	System.out.println(line+" is illegal");
	}
	}catch (Exception e){
	System.err.println("Error: " + e.getMessage());
	}
	}
	}

view raw BestBefore.java hosted with ❤ by GitHub