Tävlingsprogrammering/Uppgifter/Tärningar

Tärningar


FIGUR 3. De fyra tärningarna i exemplet och en möjlighet hur tärning 1, 3 och 4 skulle kunna se ut uppklippt i just det här exemplet. Tärning 2 kan däremot inte ha denna orientering av sidorna.

I den här uppgiften kan sidorna på en tärning vara orienterade hur som helst, det vill säga motstående sidor behöver inte nödvändigtvis ha sammanlagt sju prickar och så vidare. Du ska skriva ett program som tar som indata beskrivningar av fyra slagna tärningar. Tre av dessa är egentligen samma tärning men sedd från olika hörn, medan den fjärde inte kan ha samma orientering av sidorna i förhållande till varandra. Programmet ska avgöra vilken av de fyra tärningarna som inte kan vara identisk med de andra.

Programmet ska fråga efter beskrivningen av var och en av de fyra tärningarna. Beskrivningen av en tärning består av tre siffror: antalet prickar på de tre i medurs ordning avlästa sidorna runt ett av tärningens hörn, se figuren 3, skrivna som ett tresiffrigt tal (eller sträng) utan blanksteg. Programmet ska skriva ut numret på den tärning som inte kan vara identisk med de övriga. I varje testfall kommer det att finnas exakt en lösning.

Körningsexempel:

Tärning 1 ? 135
Tärning 2 ? 164
Tärning 3 ? 412
Tärning 4 ? 521

Udda tärning: 2

Kommentar: Tärningen som beskrivning 1, 3 och 4 visar olika hörn av, kan uppklippt till exempel se ut som i nedre delen av figur 3. Det finns ingen lösning där beskrivning 2 kan visa samma tärning som två av de andra.

Lösning

Det finns många sätt att lösa uppgiften, den beskrivning som ges här följer lösningen nedan. En komplikation är hur man representerar en tärning och framför allt dess rotationer. Man kan dock komma undan problemet i ganska hög utsträckning om man tänker på att i detta problem är det bara tärningens hörn som är intressanta. Så istället för att hålla reda på hur sidorna är relaterade till varandra kan man spara en lista över siffrorna runt de åtta hörnen på en "mönstertärning", t.ex. den som ges uppklippt i uppgiftsfiguren. En godtycklig tärning kan nu ses som en variant av mönstertärningen där man har flyttat om siffrorna. Följaktligen kan hörnen på en godtycklig tärning också erhållas genom att byta ut siffrorna i mönstertärningens hörnbeskrivningar.

Uppgiften kan därför lösas på följande sätt:

• Generera alla permutationer (ordningar) av talen 1..6. Det finns 6! = 720 stycken. Detta är samma problem som i Uppställning och kan göras antingen med en enkel rekursiv funktion eller med C++-funktionen next_permutation.
• Varje permutation t[1..6] representerar en unik tärning genom att siffran 1 på mönstertärningen har bytts ut mot t[1], siffran 2 mot t[2] o.s.v.
• För varje sådan tärning, gå igenom de fyra indatatärningarna och kolla om den givna hörnbeskrivningen återfinns i mönstertärningens hörnlista, givet omnumreringen t. Observera att samma hörn kan beskrivas på tre sätt, t.ex. 123, 231 och 312, så det behövs en extra loop för detta (variablen p i lösningen nedan). Däremot spelar ordningen roll: 123 och 321 är inte samma hörn!
• Om hörnen är korrekta för exakt tre av de fyra tärningarna är lösningen hittad.

#include <stdio.h>
#include <stdlib.h>

int t[7],x[4][3],a,b,c,f,numhits,tagen[7],hit,p;

//Hörnen i den uppklippta tärningen i uppgiftens figur:
int D[8][3]={{1,3,5},{1,5,2},{4,3,1},{4,1,2},{3,6,5},{5,6,2},{4,6,3},{2,6,4}}; 

void MLX(int nr){
  if(nr==7){   //En färdig permutation är klar att testa
    numhits=0;
    for(c=0;c<4;c++) {  //Loopa över indatatärningarna
      hit=0;
      for(a=0;a<8;a++) for(p=0;p<3;p++) {   //Loopa över de åtta hörnen samt de tre beskrivningarna av varje hörn
        for(b=0;b<3;b++)  //Loopa över de tre siffrorna runt hörnet
          if(t[D[a][(b+p)%3]] != x[c][b]) break; //Avbryt om siffran inte stämmer med indata
        if(b==3) hit=1;  //Loopen har gått färdigt: en träff hittad
      }
      if(hit) numhits++;
      else f=c;  //Spara numret på en tärning som inte stämmer, ifall det skulle vara den enda som inte stämmer
    }
    if(numhits==3) {
      printf("Udda tärning: %d\n", f+1);
      exit(0);
    }
    return;
  }
  for(t[nr]=1;t[nr]<=6;t[nr]++) if(!tagen[t[nr]]){
    tagen[t[nr]]=1;
    MLX(nr+1);
    tagen[t[nr]]=0;
  }
}

int main(){
  for(a=0;a<4;a++) {
    printf("Tärning %d ? ",a+1);
    scanf("%d", &b);
    x[a][0]=b/100;
    x[a][1]=(b%100)/10;
    x[a][2]=b%10;
  }
  for(a=1;a<=6;a++) tagen[a]=0;
  MLX(1);
  return 0;
}

Ett lösningsexempel i Java som använder sig av en hjälpklass Dice för att beskriva en tärning samt vilka hörn den innehåller. I exemplet nedan så beskrivs en tärning med hjälp av en String och i exemplet så är beskrivningen bestämd som så att de tre första tecknen i strängen är sidorna som användaren har angett och (här kommer det viktiga) en sidas motstående sida ligger 3 positioner/index bort i strängen. (Tärning #1 i bilden ovan skulle exempelvis beskrivas som "135624".) Sedan är det också oerhört viktigt att man hela tiden beskriver ett hörn på samma sätt (i detta exempel medsols), för om man helt plötsligt börjar beskriva hörn på olika sätt i en tärning, så blir det knas. När man väl fått klart för sig hur en tärning ska beskrivas (vilket görs i huvudet på programmeraren) så genererar man alla olika (relevanta) tärningar och kollar sedan om tre hörn återfinns i någon tärning. Eftersom detta är ett exempel i Java, så är det självklart som så att tärnings-klassen (Dice) själv håller reda på vilka hörn den innehåller i alla dess roterade former.

import java.util.*;

public class Dices
{
	//Här sparar vi tärningarna som vi ska generera.
	static ArrayList <Dice> dices = new ArrayList <Dice> ();

	//Metod för att generera tärningar.
	//sequence: Hur tärningen ser ut so far.
	public static void generateDices(String sequence)
	{
		//Om tärningen har 6 sidor är den klar.
		if(sequence.length()==6)
		{
			//Vi sparar undan den.
			dices.add( new Dice(sequence) );
			return;
		}

		//Testar att lägga till alla olika siffror på denna sida.
		for(int i = 1; i<=6; i++)
		{
			//Såklart får en tärning inte innehålla samma siffra.
			if(!sequence.contains(""+i))
			{
				//Lägger till den.
				generateDices(sequence+i);
			}
		}
	}

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

		System.out.print("Tärning 1: ");
		String dice1 = scan.next();

		System.out.print("Tärning 2: ");
		String dice2 = scan.next();

		System.out.print("Tärning 3: ");
		String dice3 = scan.next();

		System.out.print("Tärning 4: ");
		String dice4 = scan.next();

		//Skapar tärningar utifrån det vi redan vet.
		//Vi vet ju redan tre av sidorna.
		generateDices(dice1);
		generateDices(dice2);
		generateDices(dice3);
		generateDices(dice4);

		//Numret på tärningen som är fel.
		int odd = 0;

		//Går igenom alla tärningar och kollar om tre av våra
		// hörn förekommer i någon tärning samtidigt.
		for(int i = 0; i<dices.size(); i++)
		{
			//Tärningen vi testar på.
			Dice test = dices.get(i);

			//Kollar om respektive hörn finns i tärningen.
			boolean check1 = test.contains(dice1);
			boolean check2 = test.contains(dice2);
			boolean check3 = test.contains(dice3);
			boolean check4 = test.contains(dice4);

			//Sedan får vi dra slutsatser av resultatet.
			if(check1 && check2 && check3)
			{
				odd = 4;
				break;
			}
			else if(check1 && check2 && check4)
			{
				odd = 3;
				break;
			}
			else if(check1 && check3 && check4)
			{
				odd = 2;
				break;
			}
			else if(check2 && check3 && check4)
			{
				odd = 1;
				break;
			}
		}

		//Skriver ut svaret.
		System.out.println("\nUdda tärning: " + odd);
	}
}

class Dice
{
	//Tärningen så som den representeras.
	//Sidorna 0,1,2 i strängen är sidorna användaren angett.
	//Sidorna 0+3,1+3,2+3 är respektive sidas motstående sida.
	String dice;

	//Tärningens hörn.
	ArrayList <String> corners = new ArrayList <String> ();

	public Dice(String dice)
	{
		this.dice = dice;

		//Skapar tärningens hörn.
		makeCorners();
	}

	//Metod för att skapa tärningens 8 hörn.
	//Vi skapar hörnen manuellt, eftersom det blir lättast så.
	private void makeCorners()
	{
		//Ovansidans hörn.
		corners.add(""+dice.charAt(0)+dice.charAt(1)+dice.charAt(2));
		corners.add(""+dice.charAt(0)+dice.charAt(2)+dice.charAt(4));
		corners.add(""+dice.charAt(0)+dice.charAt(4)+dice.charAt(5));
		corners.add(""+dice.charAt(0)+dice.charAt(5)+dice.charAt(1));

		//Undersidans hörn.
		corners.add(""+dice.charAt(1)+dice.charAt(3)+dice.charAt(2));
		corners.add(""+dice.charAt(2)+dice.charAt(3)+dice.charAt(4));
		corners.add(""+dice.charAt(4)+dice.charAt(3)+dice.charAt(5));
		corners.add(""+dice.charAt(5)+dice.charAt(3)+dice.charAt(1));

		//Sedan för enkelhetens skull skapar vi varje hörns rotationer.
		rotate();
	}

	//Metod för att rotera ett hörn.
	private void rotate()
	{
		//Hur många hörn vi har innan vi lagt till några nya.
		//D.v.s. åtta stycken.
		int size = corners.size();

		//Går igenom varje ursprungligt hörn och skapar dess rotationer.
		for(int i = 0; i<size; i++)
		{
			//Vårt hörn.
			String corner = corners.get(i);

			//Hörnets tre sidor.
			char a = corner.charAt(0);
			char b = corner.charAt(1);
			char c = corner.charAt(2);

			//Ett hörn kan beskrivas på tre olika sätt.
			//Vi har redan en av dem, så vi behöver bara
			// skapa de två övriga.
			corners.add(""+b+c+a);
			corners.add(""+c+a+b);
		}
	}

	//Kollar om tärningen innehåller ett visst hörn.
	public boolean contains(String corner)
	{
		return corners.contains(corner);
	}
}

Samma lösning som lösningen i Java ovan, fast i Haskell.

-- Tärningar
module Main where
import IO
import Data.List
import Data.Set (Set, fromList, member)

type Corner = String
type Dice = Set Corner

main = do {
	putStr "Tarning 1: ";
	dice1 <- getLine;
	dices1 <- return $ getAll dice1;
	
	putStr "Tarning 2: ";
	dice2 <- getLine;
	dices2 <- return $ getAll dice2;
	
	putStr "Tarning 3: ";
	dice3 <- getLine;
	dices3 <- return $ getAll dice3;
	
	putStr "Tarning 4: ";
	dice4 <- getLine;
	dices4 <- return $ getAll dice4;
	
	dices <- return $ dices1 ++ dices2 ++ dices3 ++ dices4;
	
	putStrLn $ "\nUdda tarning: " ++ (whichOne dice1 dice2 dice3 dice4 dices)
}

whichOne :: Corner -> Corner -> Corner -> Corner -> [Dice] -> String
whichOne a b c d (h:t)	| case1		= "4"
			| case2		= "3"
			| case3		= "2"
			| case4		= "1"
			| otherwise	= whichOne a b c d t
			where
			case1 = (member a h) && (member b h) && (member c h)
			case2 = (member a h) && (member b h) && (member d h)
			case3 = (member a h) && (member c h) && (member d h)
			case4 = (member b h) && (member c h) && (member d h)

nums = ['1','2','3','4','5','6']

getAll :: String -> [Dice]
getAll s = [ fromList x | x <- (map (rotate.corners) $ genDices s) ]

genDices :: String -> [String]
genDices dice	| length dice == 6	= [dice]
		| otherwise = concat brs
		where
		choices = [ x | x <- nums, notElem x dice]
		brs = map (\x -> genDices (dice ++ [x])) choices
		
rotate :: [String] -> [String]
rotate crnrs = concat $ map (\[h0,h1,h2] -> [[h0,h1,h2],[h1,h2,h0],[h2,h0,h1]]) crnrs

corners :: String -> [String]
corners [h0,h1,h2,h3,h4,h5] = [[h0,h1,h2],[h3,h5,h4],[h0,h2,h4],[h3,h1,h5],[h0,h4,h5],[h3,h2,h1],[h0,h5,h1],[h3,h4,h2]]