Tävlingsprogrammering/Uppgifter/Överraskande strängar

Överraskande strängar

Betrakta strängen "ABCBACC". På två ställen i strängen förekommer bokstaven ′A′ två positioner före bokstaven ′C′. En sträng kallas överraskande om det inte finns två bokstäver, x och y, i strängen så att de förekommer två gånger (eller fler) i samma ordning och på samma avstånd från varandra. Den nämnda strängen är alltså inte en överraskande sträng. Ej heller är "ABACA" det, då bokstaven A förekommer två steg före bokstaven A (överlapp räknas alltså). Däremot är "ABACB" och "AABA" överraskande strängar.

Skriv ett program som tar som indata en överraskande sträng, och som utdata returnerar nästa överraskande sträng i alfabetisk ordning. Indatasträngen kommer endast bestå av stora bokstäver mellan A...Z (max 20 tecken). Den nya strängen får inte innehålla några andra bokstäver än de som finns i indatasträngen (även om antalet av en viss bokstav kan vara fler eller färre).

Körningsexempel

Överraskande sträng ? AABAC
Nästa överraskande sträng: AABC

Lösning

Detta är faktiskt en ganska rolig uppgift där det gäller att inse några enkla principer för att uppnå en effektiv lösning. Några av dem är följande:

• Ett längre ord kommer efter ett kortare ord i alfabetisk ordning. Exempelvis kommer JKLYAFB efter JKLY i alfabetisk ordning.
  • Detta innebär att vi kan på en redan överraskande sträng lägga till bokstäver för att få en ny överraskande sträng. För att komma så nära efter en överraskande sträng som möjligt i alfabetisk ordning bör vi alltså börja med att testa att addera olika bokstäver på en sträng, med de som kommer främst i alfabetet först.
• Om en sträng inte är en överraskande sträng, så är heller inga andra strängar som innehåller den strängen en överraskande sträng.
  • Detta innebär att om vi till en överraskande sträng inte erhållit en ny överraskande sträng genom att addera en bokstav, så kommer vi inte heller kunna uppnå en överraskande sträng genom att addera flera bokstäver.
• Om en sträng är en överraskande sträng, så är även alla dess substrängar överraskande strängar.
  • Detta innebär att om vi tar bort den sista bokstaven av en överraskande sträng, så har vi fortfarande en överraskande sträng. Så om vi inte lyckades få en överraskande sträng genom att lägga till en bokstav, så kan vi ta bort den sista bokstaven av den ursprungliga överraskande strängen och lägga till en bokstav som kommer efter bokstaven som tidigare stod på positionen i alfabetet (annars kommer vi ju få en överraskande sträng som inte är nästa överraskande sträng, utan en som kommer innan). Denna procedur kan upprepas flera gånger. I kombination med huvudpunkt 1 och 2 innebär detta att den första överraskande strängen vi finner med denna procedur kommer att vara den vi söker.

Sammanfattningsvis kan vi beskriva algoritmen på följande sätt:

1. Lägg till första (i alfabetisk ordning) tillåtna bokstav på den ursprungliga överraskande strängen. Kolla om detta är en överraskande sträng. Om inte, testa att lägga till nästa tillåtna bokstav istället. Kolla om detta är en överraskande sträng, osv, tills mängden tillåtna bokstäver är slut.
2. Har du inte erhållit en ny överraskande sträng, så ta bort den sista bokstaven av den ursprungliga överraskande strängen. Betrakta nu denna trunkerade sträng som din nya ursprungliga överraskande sträng. Återupprepa proceduren i punkt 1 med skillnaden att du ska börja med att lägga till tillåtna bokstäver som kommer efter bokstaven du tog bort i alfabetisk ordning.
3. Har du ännu inte erhållit en överraskande sträng, så återupprepa proceduren i punkt 2.

• När du väl finner en överraskande sträng, så kommer denna att vara "nästa överraskande sträng" och du har funnit svaret och kan avbryta.

Så hur kollar man nu att en sträng är överraskande då? Det är inte särskilt svårt. Börja med att generera alla bokstavspar som ligger med avstånd 1 från varandra. Om dubbletter förekommer är detta ingen överraskande sträng. Generera alla bokstavspar med avstånd 2 från varandra. Osv tills avståndet har blivit lika långt som ordet självt, har nu ännu inga dubbletter påträffats, så har du funnit en överraskande sträng. (Observera att en hashtabell med fördel kan användas för att lagra bokstavsparen, eftersom den inte kan innehålla dubbletter och säger till om man försöker lägga till en dubblett.)

Här nedan följer en lösning i Java, som bygger på ovanstående idé. Kom ihåg också att du bara får använda bokstäverna som redan förekommer i den överraskande strängen i din nya "nästa överraskande sträng", så att spara dessa bokstäver som är de tillåtna i en array i sorterad ordning kan vara både lämpligt och behändigt.

import java.util.*;

public class SurprisingStrings
{
	//Avgör om en sträng är en överraskande sträng.
	public static boolean isSurprising(String s)
	{
		//Sparar tillfälligt de bokstavspar som gäller för ett avstånd.
		HashSet <String> pair = new HashSet <String> ();

		//För varje avstånd...
		for(int i = 1; i<s.length(); i++)
		{
			//(Rensar bort gamla bokstavspar.)
			pair.clear();

			//...genererar vi alla bokstavspar.
			for(int j = 0; j+i<s.length(); j++)
			{
				//Om det dyker upp en dubblett är detta ingen överraskande sträng.
				if(!pair.add(""+s.charAt(j)+s.charAt(j+i))) return false;
			}
		}

		//Det fanns ingen dubblett, detta är en överraskande sträng.
		return true;
	}

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

		System.out.print("Överraskande sträng: ");
		String surprise = scan.next();

		//Sparar alla bokstäver i ordet i en sorterad mängd.
		TreeSet <Character> letters = new TreeSet <Character> ();

		//Lägger till bokstäverna i mängden (dubbletter försvinner automatiskt).
		for(int i = 0; i<surprise.length(); i++)
		{
			letters.add( surprise.charAt(i) );
		}

		//Hämtar alla de bokstäver som är tillåtna att använda vid ordbildandet.
		//Bokstäverna kommer att vara sorterade.
		Character [] valid = letters.toArray(new Character[0]);

		//Indexet för den tillåtna bokstav vi ska börja på.
		//Första gången får vi (ska vi) börja på första bokstaven.
		int start = 0;

		//Håller på tills vi hittat nästa överraskande sträng.
		solve: while(true)
		{
			//Testar att lägga till tillåtna bokstäver på en överraskande sträng.
			for(int i = start; i<valid.length; i++)
			{
				//Om vi har hittat nästa överrsaknde sträng.
				if(isSurprising(surprise+valid[i]))
				{
					//Så sparar vi den och avbryter.
					surprise += valid[i];
					break solve;
				}
			}

			//Genom att lägga till någon bokstav på den nuvarande överraskande strängen
			//hittade vi ingen nästa överraskande strängen. Detta innebär att vi måste
			//ändra på en tidigare bokstav i den ursprungliga överraskande strängen.
			//Givetvis kan vi inte ersätta bokstaven vi ska ändra på med en bokstav som
			//kommer innan i alfabetet, för då kommer ju vår överraskande sträng att hamna
			//innan den urprungliga. Därför måste vi börja med en bokstav som ligger
			//efter i alfabetet (och är tillåten). Denna bokstav är givetvis den som kommer
			//efter bokstaven som ska ändras på i listan (arrayen) över tillåtna bokstäver.

			//Hämtar indexet för bokstaven som ska ändras på och adderar ett (vi får index för nästa bokstav).
			start = Arrays.binarySearch(valid, surprise.charAt(surprise.length()-1)) + 1;

			//Tar bort bokstaven vi ska ändra på. (Vilket är den sista om man ska hamna så nära som möjligt.)
			surprise = surprise.substring(0, surprise.length()-1);
		}

		//Skriver ut svaret.
		System.out.println("Nästa överraskande sträng: " + surprise);
	}
}

Samma lösning fast i Haskell.

-- Överraskande strängar
module Main where
import IO
import Data.List

main = do {
	putStr "Overraskande strang ? ";
	s <- getLine;
	valid <- return $ (sort.nub) s;
	
	putStrLn $ "Nasta overraskande strang: " ++ (next valid (s++['@']))
}

next :: String -> String -> String
next valid s = if (null surprise) then (next valid (init s)) else (head surprise)
	where
	surprise = [x | x <- (map (\y -> (init s)++[y]) new), isSurprising x]
	new = let h = (last s) in dropWhile (<= h) valid

isSurprising :: String -> Bool
isSurprising s = and $ zipWith (\x y -> (length x)==(length y)) new (map nub new)
	where
	new = map (map (\x -> (head x, last x))) (pairs s)

pairs :: String -> [[String]]
pairs [_] = []
pairs s@(_:t) = let p = (drop 2 $ inits s) in (zipWith (\x y -> x:y) p (pairs t)) ++ [[last p]]