Tävlingsprogrammering/Uppgifter/Träjärnvägen
Träjärnväg
Träjärnväg är en klassisk leksak. I denna uppgift används en enkel variant där det finns två sorters bitar:
- Raka bitar med längden R
- Kurvbitar som motsvarar exakt en fjärdedel av en cirkel med radien R. Dessa är vändbara så att de kan svänga såväl åt höger som åt vänster.
Nora är tre år och har tröttnat på att dra sitt tåg fram och tillbaka. Det hon funderar över är hur många olika sätt man kan bygga ihop en given uppsättning bitar till en tågbana. Hjälp henne genom att skriva ett datorprogram som räknar ut svaret.
En tågbana måste innehålla alla bitarna och den måste sitta ihop så att tåget kan köra runt. Den får inte korsa sig själv eller ens ha någon punkt eller sträcka gemensam. Två tågbanor räknas som identiska om man kan starta ett tåg på vardera banan (valfri plats och riktning) och tågen då “upplever” precis samma serie av kurvor och raksträckor då de kör ett varv. Sådana tågbanor ska alltså inte räknas dubbelt. Det totala antalet bitar överstiger aldrig 18.
Visar de olika tågbanorna
FIGUR 1. Körningsexempel 1.
Visar de olika tågbanorna
FIGUR 2. Körningsexempel 2.
Körningsexempel 1:
Antal raka bitar? 8 Antal kurvbitar? 6 Antal tågbanor: 10
Körningsexempel 2:
Antal raka bitar? 0 Antal kurvbitar? 12 Antal tågbanor: 3
Körningsexempel 3:
Antal raka bitar? 2 Antal kurvbitar? 6 Antal tågbanor: 0
Körningsexempel 4:
Antal raka bitar? 4 Antal kurvbitar? 6 Antal tågbanor: 1
Körningsexempel 5:
Antal raka bitar? 2 Antal kurvbitar? 8 Antal tågbanor: 6
Lösning
[redigera]Här nedan följer en lösning i Java. Jag är dock inte helt 100% säker på den, men den klarar alla tester, så vad mer kan man begära? Sedan finns det troligen någon betydligt simplare lösning, men det kan ju också vara bra att se hur man går tillväga metodiskt och strukturerat när man inte riktigt vet var man ska. (Så någon "expert" får gärna komma med en alternativ lösning.)
Kruxet med den här uppgiften är inte (som så ofta) tidsåtgång eller minnesåtgång. Grovt uppskattat kan vi ju aldrig ens konstruera i närheten av 3^18 tågbanor. Nej kruxet är hur vi ska beskriva en tågbana och hur vi ska kunna avgöra om två tågbanor är lika. Detta har jag löst genom att beskriva en tågbana som en serie av 0, L och R. Där 0 beskriver en raksträcka, L en vänstersväng och R en högersväng. Sedan har jag en klass för en tågbana, vilken håller reda på alla olika sätt en tågbana kan beskrivas. Med notationen klar för oss, så måste vi också generera de olika beskrivningarna. Eftersom man kan börja var som helst på tågbanan, så gäller det att generera varje version av bokstavsföljden, dvs man läser serien från vänster till höger med start på alla olika positioner (man kan också se det som att man roterar bokstavsföljden åt vänster (eller höger) tills man har kommit tillbaka dit där man började). Men vi måste också ta i beräkning att man kan köra åt vilket håll som helst (moturs såväl som medurs). När man färdas i motsatt riktning så innebär det att alla högersvängar i beskrivningen kommer att vara vänstersvängar och vice versa; detta är alltså inte särskilt svårt att simulera, man byter ut alla L mot R och alla R mot L, sedan så genererar man alla rotationer av serien också. Med alla dessa beskrivningar så är det enkelt att avgöra om två tågbanor är lika, vilket är när den ena innehåller någon av den andres beskrivningar, faktum är att de båda kommer att dela exakt samma beskrivningar om de är lika, vilket gör att vi kan nöja oss med att välja den "minsta" sträng-representationen av tågbanan (den som ges av String-klassens compareTo()-metod) som beskrivning av den. På så sätt sparar vi en del minne och snabbar upp programmet lite (faktiskt avsevärt för testfall som ligger över 18 tågbitar, men det är överkurs).
Och om man är lat (vilket jag är), så kan man överlagra Javas equals() och hashCode() metoder, vilket gör att man kan spara objekt av klassen i ett HashSet; och i ett HashSet kan inte dubbletter existera, så de försvinner automatiskt, och när man vill ha svaret kollar man bara hur många objekt hashtabellen (HashSet) innehåller.
Nu återstår bara problemet med att generera alla olika (giltiga!) tågbanor. Kruxet i det här steget är att få tågbanan att sluta (korrekt) där den börjar och att se till att tågbanan inte korsar sig själv. Problemet med avslutningen har jag löst på så sätt att jag alltid börjar bygga tågbanan i en punkt (0,0) med riktning uppåt, så om en tågbana ska avslutas korrekt ska den sluta i punkten (0,0) med riktning uppåt. Kravet med riktning uppåt finns med för att man inte ska kunna avsluta med en 90 graders anslutning (vilket inte är tillåtet). Att se till att tågbanan inte korsar sig själv kan vara lite klurigare. Först och främst kan man spara undan för tillfället de punkter som ingår i tågbanan och se till att en punkt inte förekommer två gånger, på detta sätt kan man så gott som garantera att raka bitar inte skär raka bitar och att kurviga bitar inte skär raka bitar (och tvärtom). Vad man dock har missat är när två kurviga bitar kan skära varandra (körningsexempel 5 testar detta); för går man bara efter punkterna som ingår i tågbanan kan man missa ett fall där en kurvbit går från exempelvis (2,2) till (3,3) och en annan kurvbit går från (3,2) till (2,3), vilket inte ska vara tillåtet eftersom banan då korsar sig själv. Lösningen på detta problem är att kolla innan man lägger ut en kurvbit att någon av punkterna i rutan/kvadraten som kurvbiten inte ansluter emellan är ledig, om båda är upptagna betyder det (troligen) att en kurva går mellan de punkterna varpå vi inte kan lägga vår kurvbit.
Sedan har jag också lagt till en liten grov koll i början av den rekursiva metoden för att undvika några sista onödiga rekursiva anrop. T.ex. är det ju onödigt att fortsätta om vi befinner oss 5 punkter i x-led ifrån start/slutpunkten (0,0) och bara totalt har 4 bitar kvar att lägga ut, eftersom det då är omöjligt att nå tillbaka till målet p.g.a. att 4 bitar max kan åstadkomma 4 punkters förflyttning i x-led.
(Vi importerar awt-biblioteket för att få tillgång till klassen Point.)
import java.util.*;
import java.awt.*;
public class Jarnvag
{
//Sparar våra olika tågbanor.
static HashSet <Tagbana> banor = new HashSet <Tagbana> ();
//Sparar för tillfället vilka punkter som ingår i den järnväg
//vi för tillfället håller på att bygga.
static HashSet <Point> visited = new HashSet <Point> ();
//Rekursiv metod som bygger alla möjliga tänkbara varianter av en järnväg.
//(x, y): Koordinaten vi för tillfället befinner oss på.
//raka, kurviga: Antalet raka och kurviga bitar vi har kvar.
//direction: Riktningen i vilken vi bygger för tillfället.
//bana: Sparar järnvägen vi bygger. (Representerar själva järnvägen.)
//i: (Indexet för) Vilken träbit i ordningen vi ska placera ut.
public static void rek(int x, int y, int raka, int kurviga, int direction, char [] bana, int i)
{
//En grov uppskattning för när det garanterat är lönlöst att överhuvutaget
//försöka bygga vidare. (Vi har inte tillräckligt många bitar kvar för att
//kunna nå tillbaka till där järnvägen startade.)
if(Math.max(Math.abs(x), Math.abs(y))>raka+kurviga) return;
//Järnvägen är färdigbyggd.
if(i==bana.length)
{
//För att järnvägen skall vara giltig måste den ansluta där vi startade
//och i samma riktning som vi startade. (90 graders svängar är inte OK.)
if(x==0 && y==0 && direction==1)
{
//Sparar undan järnvägen.
//Observera att dubletter automatiskt kommer att försvinna.
banor.add( new Tagbana(bana) );
}
//Avbryter.
return;
}
//Punkten vi för tillfället befinner oss på.
Point p = new Point(x, y);
//Lägger till punkten. Avbryter om den redan ingick i järnvägen.
if(!visited.add(p)) return;
//Punkter som används för att avgöra om en sväng är tillåten eller ej.
Point p1 = new Point(x, y);
Point p2 = new Point(x, y);
if(direction==1) //Upp
{
//Om vi har raka bitar kvar.
if(raka>0)
{
//Vi lägger en rak bit.
bana[i] = '0';
//Om vi har riktning uppåt så innebär en rak bit att vi
//förflyttar oss i y-led ett steg uppåt. Riktningen förblir
//oförändrad och antalet raka bitar minskas. Sedan fortsätter
//vi att bygga på vår järnväg utifrån detta tillstånd.
rek(x, y+1, raka-1, kurviga, 1, bana, i+1);
}
//Om vi har kurviga bitar kvar.
if(kurviga>0)
{
//Punkter som beskriver hörnen i kvadraten/rutan i vilken
//vi ska svänga igenom och som själva inte ska ingå i järnvägen.
p1.x = x-1; p1.y = y;
p2.x = x; p2.y = y+1;
//Vi lägger en vänstersväng.
bana[i] = 'L';
//Om de två specifierade punkterna redan finns i järnvägen,
//så betyder detta att svängen är otillåten, ty järnvägen
//inte får korsa sig själv.
if(!visited.contains(p1) || !visited.contains(p2))
{
//En vänstersväng med riktning uppåt innebär att man i
//x-led förflyttar sig åt vänster och i y-led uppåt.
//Antalet kurviga bitar minskas och efter svängen kommer
//riktningen att vara åt vänster (4). Sedan går vi vidare
//på nästa bit och fortsätter att bygga järnvägen.
rek(x-1, y+1, raka, kurviga-1, 4, bana, i+1);
}
p1.x = x+1; p1.y = y;
p2.x = x; p2.y = y+1;
//Vi lägger en högersväng.
bana[i] = 'R';
if(!visited.contains(p1) || !visited.contains(p2))
rek(x+1, y+1, raka, kurviga-1, 2, bana, i+1);
}
} //Samma princip som ovan gäller här nedan, fast med lite andra förflyttningar.
else if(direction==2) //Höger
{
if(raka>0)
{
bana[i] = '0';
rek(x+1, y, raka-1, kurviga, 2, bana, i+1);
}
if(kurviga>0)
{
p1.x = x+1; p1.y = y;
p2.x = x; p2.y = y+1;
bana[i] = 'L';
if(!visited.contains(p1) || !visited.contains(p2))
rek(x+1, y+1, raka, kurviga-1, 1, bana, i+1);
p1.x = x+1; p1.y = y;
p2.x = x; p2.y = y-1;
bana[i] = 'R';
if(!visited.contains(p1) || !visited.contains(p2))
rek(x+1, y-1, raka, kurviga-1, 3, bana, i+1);
}
}
else if(direction==3) //Ner
{
if(raka>0)
{
bana[i] = '0';
rek(x, y-1, raka-1, kurviga, 3, bana, i+1);
}
if(kurviga>0)
{
p1.x = x+1; p1.y = y;
p2.x = x; p2.y = y-1;
bana[i] = 'L';
if(!visited.contains(p1) || !visited.contains(p2))
rek(x+1, y-1, raka, kurviga-1, 2, bana, i+1);
p1.x = x-1; p1.y = y;
p2.x = x; p2.y = y-1;
bana[i] = 'R';
if(!visited.contains(p1) || !visited.contains(p2))
rek(x-1, y-1, raka, kurviga-1, 4, bana, i+1);
}
}
else //Vänster
{
if(raka>0)
{
bana[i] = '0';
rek(x-1, y, raka-1, kurviga, 4, bana, i+1);
}
if(kurviga>0)
{
p1.x = x-1; p1.y = y;
p2.x = x; p2.y = y-1;
bana[i] = 'L';
if(!visited.contains(p1) || !visited.contains(p2))
rek(x-1, y-1, raka, kurviga-1, 3, bana, i+1);
p1.x = x-1; p1.y = y;
p2.x = x; p2.y = y+1;
bana[i] = 'R';
if(!visited.contains(p1) || !visited.contains(p2))
rek(x-1, y+1, raka, kurviga-1, 1, bana, i+1);
}
}
//Eller så kanske inte den här punkten ska ingå i järnvägen.
//Tar bort den.
visited.remove(p);
}
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
System.out.print("Antal raka bitar: ");
int raka = scan.nextInt();
System.out.print("Antal kurvbitar: ");
int kurviga = scan.nextInt();
//Skapar positionerna för vilka vi ska placera
//våra järnvägsbitar på.
char [] bana = new char [raka+kurviga];
//Börjar bygga på vår järnväg.
//Vi startar i punkten (0,0) med riktning uppåt
//och ska placera ut vår första bit (index = 0).
rek(0, 0, raka, kurviga, 1, bana, 0);
//Ett HashSet kan inte innehålla dubbletter, därför
//är antalet järnvägar som den håller det unika antalet.
int svar = banor.size();
//Skriver ut svaret.
System.out.println("Antal tågbanor: " + svar);
}
//En egenskriven klass som beskriver en järnväg/tågbana.
//En järnväg beskrivs av en serie av tre olika typer av tecken.
//Där 0 representerar en raksträcka, L en vänstersväng, och
//R en högersväng.
private static class Tagbana
{
//Sparar den minsta beskrivningen.
private String tagbana;
public Tagbana(char [] bana)
{
//Skapar vår ursprungliga beskrivning.
tagbana = new String(bana);
//Genererar det "minsta sätt" man kan beskriva järnvägen på.
generateVersion(bana);
}
//Metod för att generera alla olika tänkbara beskrivningar och sparar den minsta.
private void generateVersion(char [] bana)
{
//Skapar beskrivningar med start på varje tänkbar startposition.
for(int i = 0; i<bana.length; i++)
{
//Skapar en sträng representation av banan.
String s = new String(bana);
//Om den är mindre än vår nuvarande minsta, så är den vår nya minsta.
if(s.compareTo(tagbana)<0) tagbana = s;
moveStart(bana);
}
//Inverterar järnvägen. Dvs beskriver den på det sätt som den skulle beskrivas
//om vi färdades på den i motsatt riktning (medsols blir motsols och vice versa).
invert(bana);
//Skapar alla tänkbara beskrivningar för den inverterade versionen.
for(int i = 0; i<bana.length; i++)
{
String s = new String(bana);
if(s.compareTo(tagbana)<0) tagbana = s;
moveStart(bana);
}
//Inverterar tillbaka järnvägen. (Viktigt eftersom vi jobbar på en referens.)
invert(bana);
}
//Förflyttar startpositionen för tåget ett steg åt vänster.
private void moveStart(char [] bana)
{
char tmp = bana[bana.length-1];
for(int i = bana.length-1; i>0; i--)
{
bana[i] = bana[i-1];
}
bana[0] = tmp;
}
//Inverterar järnvägen. Alla högersvängar blir vänstersvängar och vice versa.
private void invert(char [] bana)
{
for(int i = 0; i<bana.length; i++)
{
if(bana[i]=='L')
{
bana[i] = 'R';
}
else if(bana[i]=='R')
{
bana[i] = 'L';
}
}
}
//Retunerar huruvida detta objekt är likadant som det givna objektet.
//(Dvs kollar om två järnvägar är lika.)
public boolean equals(Object ob)
{
Tagbana tb = (Tagbana)ob;
//Två järnvägar är lika om de har samma (minsta) beskrivning.
return tagbana.equals(tb.toString());
}
//Retunerar hashvärdet för denna järnväg, vilket är beskrivningens hashvärde.
//På så sätt garanteras två järnvägar som är lika att ha samma hashvärde.
public int hashCode()
{
return tagbana.hashCode();
}
//Retunerar (den minsta) beskrivningen av järnvägen.
public String toString()
{
return tagbana;
}
}
}