Tävlingsprogrammering/Uppgifter/Klockradion

Klockradion

Sture har lärt sig se vad klockan är genom att uppskatta ljusnivån i rummet. Ljuset kommer från hans klockradio, vars display alltid visar fyra siffror (t.ex. följer 00:00 efter 23:59) och varje siffra består av ett antal tända streckformade lampor. Siffrorna ser ut så här:

FIGUR 1. De 10 olika siffrorna.

Det Sture gör är att han utifrån ljusnivån kan avgöra det totala antalet tända streck på displayen. Men det finns många tidpunkter som ger samma antal streck. Därför måste han ofta låta tiden gå en stund och göra upprepade mätningar innan han kan vara helt säker på vad klockan är.

Skriv ett program som, givet en serie mätningar (varje minut) av hur många strecklampor som totalt är tända, skriver ut vad klockan är (vid senaste mätningen), så fort detta är entydigt bestämt.

Observera att programmet inte ska vänta på någon signal om att indatan är slut utan skriva ut svaret så fort det går att avgöra tidpunkten.

Körningsexempel 1

Ljusnivå ? 16
Ljusnivå ? 15
Ljusnivå ? 16
Ljusnivå ? 12

Klockan är 17:51

Körningsexempel 2

Ljusnivå ? 18
Ljusnivå ? 22
Ljusnivå ? 18

Klockan är 22:01

Lösning

Tricket är att kontinuerligt sortera bort tidpunkter som inte har den angivna ljusnivån tills vi bara har en tidpunkt kvar, vilket då är vårt svar.

Kort och gott:

1. Användaren matar in en ljusnivå.
2. Sortera bort alla tidpunkter som inte har den angivna ljusnivån.
3. Om det nu bara finns en tidpunkt kvar, så är den svaret. Avsluta.
4. Ticka fram varje tidpunkt en minut.
5. Gå tillbaka till 1.

En uppvisning i objektorienterad programmering.

import java.util.*;

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

		//Kö där vi lagrar alla tidpunkter.
		LinkedList <Tid> qu = new LinkedList <Tid> ();

		//Lägger alla klockslag i kön.
		for(int h = 0; h<24; h++)
		for(int m = 0; m<60; m++)
		qu.add(new Tid(h,m));

		//Kör på så länge det finns fler än en möjlig tidpunkt.
		while(qu.size()>1)
		{
			System.out.print("Ljusnivå ? ");
			int ljus = scan.nextInt();

			//Går igenom kön.
			Iterator <Tid> it = qu.iterator();
			while(it.hasNext())
			{
				Tid t = it.next();
				
				//Tickar fram tidpunkten en minut.
				// (Att vi gör detta ett steg för tidigt gör inget, då alla klockslag finns
				// i kön från början.)
				t.inc();
				
				//Om dess ljusstyrka skiljer sig från den angivna plockas den bort ur kön.
				if(t.streck()!=ljus) it.remove();
			}
		}

		//Tidpunkten som är svaret.
		Tid svar = qu.pop();

		//Skriver ut svaret.
		System.out.println("\nKlockan är: " + svar);
	}

	private static class Tid
	{
		//Timma och minut.
		int hour, min;
		
		//Antalet streck för respektive siffra.
		static int [] streck = {6,2,5,5,4,5,6,3,7,6};

		//Skapar en tid.
		public Tid(int h, int m)
		{
			hour = h; min = m;
		}

		//Returnerar antalet streck för tidpunkten.
		public int streck()
		{
			return streck[hour/10%10]+streck[hour%10]+streck[min/10%10]+streck[min%10];
		}

		//Tickar fram klockan/tidpunkten en minut.
		public void inc()
		{
			min++;
			min %= 60;
			if(min==0) hour++;
			hour %= 24;
		}

		//Ger en strängrepresentation för tidpunkten.
		public String toString()
		{
			String ret;

			if(hour<10) ret = "0"+hour+":";
			else ret = hour+":";

			if(min<10) ret += "0"+min;
			else ret += min;

			return ret;
		}
	}
}

Motsvarande program, fast i Haskell.

-- Klockradion
module Main where
import IO

data Tid = Tid Int Int
instance Show Tid where show (Tid h m) = (if h<10 then "0" else "") ++ show h ++ (if m<10 then ":0" else ":") ++ show m

tic (Tid h m) = Tid (mod (if mn==0 then h+1 else h) 24) mn where mn = mod (m+1) 60

ljus (Tid h m) = sum $ map streck [mod (div h 10) 10, mod h 10, mod (div m 10) 10, mod m 10] 
	where streck = (!!) [6,2,5,5,4,5,6,3,7,6]

main = ask [Tid h m | h <- [0..23], m <- [0..59]] >>= putStrLn.("\nKlockan ar " ++).show

ask x = putStr "Ljusniva ? " >> getLine >>= \n -> let y = filter ((read n==).ljus) x in if length y>1 then ask (map tic y) else return (head y)