Tävlingsprogrammering/Uppgifter/Tvetydiga datum

Från Wikibooks

TVETYDIGA DATUM

Datum skrivs på olika sätt i olika länder. Till exempel skulle datumet 03/05/01 i Sverige betyda 1 maj 2003, medan det i USA skulle vara 5 mars 2001 och i en del andra länder 3 maj 2001 (vi kan utgå ifrån att årtalet alltid är under 2000-talet, dvs mellan 2000 och 2099).

Detta kan bland annat orsaka bekymmer när man tittar på bäst-före datumet på en gammal konservburk. Om man inte har en aning om vilket format ett datum har, kan man behöva pröva alla möjligha betydelser och, för att vara på den säkra sidan, välja det tidigaste giltiga datumet.

För att ett datum ska vara giltigt måste förstås månaden vara mellan 1 och 12 och dagen mellan 1 och antalet dagar i månaden. Antalet dagar i de tolv månaderna är i tur och ordning

31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31

utom under skottår (vilka, för perioden 2000 − 2099, infaller om årtalet är jämnt delbart med 4) då februari har 29 dagar.

Skriv ett program som läser in de tre delarna av ett datum och skriver ut det tidigaste giltiga datumet som indata kan tänkas representera.

Körningsexempel

Del 1: 3
Del 2: 5
Del 3: 1
År 2001, månad 3, dag 5.

Lösning[redigera]

Här handlar det helt om att prova alla möjligheter, och som uppgiften beskriver skriva ut den lägst möjliga. Min lösning följer nedan:

#include <vector>
#include <algorithm>
#include <iostream>

struct Date{
	size_t year,month,day;
};
bool operator<(const Date& d1,const Date& d2){
	if(d1.year==d2.year){
		if(d1.month==d2.month){
			return d1.day<d2.day;
		}
		return d1.month<d2.month;
	}
	return d1.year<d2.year;
}
std::ostream& operator<<(std::ostream& os,const Date& d){
	return os << "År " << d.year << ", månad " << d.month << 
		", dag " << d.day << "." << std::endl;
}

void addDate(std::vector<Date>& dates,size_t year,size_t month,size_t day){
	const size_t mDaysV[12]={31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	if(year<100)year+=2000;

	if(month>12 || month<1 || day<1)return;
	size_t mDays=(month==2?(year%4==0?29:28):mDaysV[month]);
	if(day>mDays)return;

	Date dt={year,month,day};
	dates.push_back(dt);
}

int main(){
	size_t del1,del2,del3;
	std::cout << "Del 1: ";
	std::cin >> del1;
	std::cout << "Del 2: ";
	std::cin >> del2;
	std::cout << "Del 3: ";
	std::cin >> del3;
	std::vector<Date> dates;
	addDate(dates,del1,del2,del3);
	addDate(dates,del3,del1,del2);
	addDate(dates,del3,del2,del1);
	std::vector<Date>::iterator iter=std::min_element(dates.begin(),dates.end());
	if(iter==dates.end())
		std::cout << "Omöjligt!" << std::endl;
	else
		std::cout << *iter;
	return 0;
}


Lösning i Java. Det är helt enkelt bara att testa alla sätt datumet kan tolkas på (vilket är 6 stycken) och dels kolla om datumet är giltigt och dels kolla om det är det minsta datumet (hittills). Inga konstigheter.

import java.util.*;

public class TvetydigaDatum
{
	//År, månad, dag för vårt slutgiltiga svar.
	static int year, month, day;
	static String date;

	//Dagarna i respektive månad. (Månad 0 har 0 dagar.)
	static int [] dagar = {0,31,28,31,30,31,30,31,31,30,31,30,31};

	public static void makeDate(int year, int month, int day)
	{
		//Vanligtvis har Februari 28 dagar.
		dagar[2] = 28;

		//Om det är skottår har Februari 29 dagar.
		if(year%4==0) dagar[2] = 29;

		String tmp = ""+year;

		//Ogiltig månad.
		if(month>12) return;

		tmp += month;

		//Ogiltig dag.
		if(day>dagar[month]) return;

		tmp += day;

		//Vi har skapat ett datum.
		if(date==null)
		{
			date = tmp;
		}
		else
		{
			//Om detta dautm var "mindre" än det tidigare minsta så spara undan det.
			//Annars avbryt.
			if(tmp.compareTo(date)<0) date = tmp;
			else return;
		}

		//Sparar datumet.
		TvetydigaDatum.year = year;
		TvetydigaDatum.month = month;
		TvetydigaDatum.day = day;
	}

	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		System.out.print("Del 1: ");
		int del1 = scan.nextInt();

		System.out.print("Del 2: ");
		int del2 = scan.nextInt();

		System.out.print("Del 3: ");
		int del3 = scan.nextInt();

		//Det finns 6 olika sätt man kan tolka datumet på.
		makeDate(2000+del1, del2, del3);
		makeDate(2000+del2, del3, del1);
		makeDate(2000+del3, del1, del2);
		makeDate(2000+del3, del2, del1);
		makeDate(2000+del2, del1, del3);
		makeDate(2000+del1, del3, del2);

		//Skriver ut svaret.
		System.out.println("År "+year+", månad "+month+", dag "+day+".");
	}
}

Alternativ lösning m.h.a Javas Calendar-API

import java.util.*;

public class TvetydigaDatum {

    public static void main(String[] args) {
        //Läs in i delar och spara i parts
        Scanner sc = new Scanner(System.in);
        System.out.println("Del 1:");
        int[] parts = new int[3];
        parts[0] = sc.nextInt();
        System.out.println("Del 2:");
        parts[1] = sc.nextInt();
        System.out.println("Del 3:");
        parts[2] = sc.nextInt();
        Calendar earliest = Calendar.getInstance();
        earliest.setTime(new Date(2099, 12, 31, 0, 0, 0)); //Sätt det senaste möjliga datum som standard
        //gå igenom alla möjligheter
        for (int i = 0; i < 3; i++) {
            //år
            for (int j = 0; j < 3; j++) {
                //månad - om månaden är 0 (omöjligt) eller i==j (år == månad) fortsätt
                if (i == j || parts[j] == 0) {
                    continue;
                }
                for (int k = 0; k < 3; k++) {
                    //dag
                    if (k == j || k == i || parts[k] == 0) {
                        continue;
                    }
                    //skapa en calendar, sätt år-månad.dag (månad är 0-baserad, så ta bort 1)
                    Calendar cal = Calendar.getInstance();
                    cal.set(2000 + parts[i], parts[j] - 1, parts[k]);
                    //dubbelkolla så att dagen är rätt. Motverkar felaktiga datum producerade (att sätta 32 som dag kommer sätta month+1 istället)
                    //gör att vi slipper manuellt hantera dagar och skottår
                    if (cal.get(Calendar.DAY_OF_MONTH) != parts[k] || cal.get(Calendar.MONTH)+1 != parts[j]) {
                        continue;
                    }
                    //om det här datum är tidigare än det tidigaste vi provat, ersätt det
                    if (cal.getTimeInMillis() < earliest.getTimeInMillis()) {
                        earliest = cal;
                    }
                }
            }
        }
        System.out.println("År " + earliest.get(Calendar.YEAR) + ", månad " + (earliest.get(Calendar.MONTH) + 1) + ", dag " + earliest.get(Calendar.DAY_OF_MONTH));

    }
}

Lösning i Haskell.

-- Tvetydiga datum
module Main where
import IO
import Data.List

year = [0,31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
skott = [0,31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];

main = do {
	putStr "Del 1: ";
	del1 <- getLine;
	
	putStr "Del 2: ";
	del2 <- getLine;
	
	putStr "Del 3: ";
	del3 <- getLine;
	
	[y,m,d] <- (return.head.(dropWhile unvalid).sort.permutations) $ map read [del1, del2, del3];
	
	putStrLn $ "Ar " ++ (show $ 2000+y) ++ ", manad " ++ (show m) ++ ", dag " ++ (show d) ++ "."
}

unvalid = (not.valid)

valid :: [Int] -> Bool
valid [y,m,d] =  m<13 && d <= (months !! m)
	where
	months = if (mod y 4 == 0) then skott else year