Tävlingsprogrammering/Uppgifter/Rondellsimulering
Rondellsimulering
Som en del av ett trafikplaneringspaket ska du skriva ett program som simulerar en rondell. Programmet ska beräkna hur lång tid det tar för ett antal bilar att passera rondellen. För att ta hänsyn till bilisters varierande användning av blinkers ska pro- grammet räkna på två extremfall:
- Med blink: Alla bilar blinkar när de ska lämna rondellen.
- Utan blink: Ingen bil blinkar när den ska lämna rondellen.
Rondellen har N tillfartsvägar som är symmetriskt fördelade runt en cirkel (se figur nedan). Vid tiden 0 finns inga bilar i rondellen men vid varje tillfart finns en kö av bilar. Inga andra bilar tillkommer under simuleringen. Varje bil har en viss tillfartsväg som mål och ska alltså köra moturs (framåt) i rondellen för att komma dit. Mellan varje par av intilliggande tillfartsvägar finns en “position”, som används för att underlätta simuleringen (se figuren nedan). Högst en bil kan befinna sig på en viss position, d.v.s. högst N bilar kan befinna sig i rondellen samtidigt.
FIGUR 1. Bilarnas placering i exemplet vid tiden 0, 1, 2 och 3 för de två olika blink-scenarierna. I indatat ges vägarna i ordningen röd, blå, svart och vit.
Under varje “tidsenhet” sker följande händelser (samtidigt):
- Varje bil som är i rondellen och som befinner sig på positionen omedelbart före sitt mål lämnar rondellen.
- Varje annan bil som är i rondellen flyttar sig en position framåt.
- Den första bilen i varje kö kör in i rondellen till positionen omedelbart efter tillfartsvägen, förutsatt att den vet att denna position inte kommer att upptas av en annan bil. Denna vetskap kan antingen bero på att positionen omedelbart före tillfartsvägen är tom, eller att den bil som befinner sig där just nu tänker lämna rondellen och visar detta genom att blinka.
På första raden i filen rondell.dat står ett heltal N (3 ≤ N ≤ 100), antalet tillfartsvägar. Därefter följer N par av rader, där varje par beskriver kön vid en tillfartsväg. Köerna anges i moturs ordning. På första raden i varje par står ett heltal K (1 ≤ K ≤ 100), antalet bilar i kön. På andra raden står K heltal mellan 1 och N − 1. Dessa tal anger hur många steg framåt (moturs) som varje bil ämnar köra. Talens ordning är samma som bilarnas, det första talet gäller alltså den bil som kör in först i rondellen o.s.v.
Programmet ska skriva ut efter hur många tidsenheter som alla bilarna har kört ige- nom rondellen så att den åter är tom. Detta ska göras för vart och ett av de två blink- scenarierna ovan. Notera att tidsåtgången utan blink aldrig kan vara lägre än med blink.
Körningsexempel: Filen rondell.dat med innehållet
4 5 1 2 3 2 3 6 2 3 1 3 2 3 5 2 3 1 1 3 5 1 1 3 2 2
ska ge svaret
Med blink: 14 Utan blink: 19
Lösning[redigera]
Denna uppgift har inget speciellt krux. Det jobbiga är att vi har mycket att tänka på. Därför kommer den kommande texten att beskriva C++ koden nedan.
För att göra livet lättare inför vi dessa begrepp:
1. En kö. Antingen STL-kön eller en egen implementerad där vi håller reda på index.
2. En två-dimensionell vektor för att representera rondellen.
Kön behöver vi för att veta vilken bil som härnäst kan komma in.
Den två-dimensionella vektorn behöver vi för att kunna flytta på bilarna oberoende på vilken ordning vi flyttar de i. Annars skulle vi behöva ta hänsyn till att vi nyss flyttat på en bil och det hela blir mycket jobbigare.
Rondellen representeras av dessa tal:
-1, 0, 1, 2, ..., n
-1: En tom plats
0: En bil som har 0 vägar kvar att passera
n: En bil som har n vägar kvar att passera.
Vi använder oss av cykliskindex.
Så nästa element efter det i:te elementet är:
(i+1) % N där N är vektorns storlek
samma för det föregående:
(i-1+N) % N
Där +N finns för att komma ur de negativa talen eller så kan man tänka sig att N-1 är ett helt varv minus ett.
Saker att notera i följande lösning är dessa:
1. Vi sparar indatan i qtemp för att återanvända den senare.
2. Andra halvan av koden är nästan en exakt kopia av första. Variablerna initieras på nytt och kön återställs. Enda skillnaden är kravet för att man ska kunna åka in i rondellen. En 0:a (bil som svänger in) låter den första bilen på vägen åka in i första halvan av koden.
3. Flaggan representerar bilars närvaro. Om det finns en bil så är flaggan satt till sann annars falsk och iterationen avbryts. Vi skriver ut tiden-1 för att komma till tiden då de sista bilarna/bilen svänger ut för det är den som uppgiften söker.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int N;
cin >> N;
vector<queue <int> > q(N);
int Rondell[N][2];
for (int i = 0; i < N; ++i) {
Rondell[i][0] = -1;
int nTemp;
cin >> nTemp;
for (int j = 0; j < nTemp; ++j) {
int nTempData;
cin >> nTempData;
q[i].push(nTempData);
}
}
vector<queue <int> > qtemp(N);
qtemp = q;
int index = 0;
int time = 0;
bool flag = true;
while (flag) {
++time;
flag = false;
int nNextVersion = (index+1)%2;
for (int i = 0; i < N; ++i) {
if (!q[i].empty())
flag = true;
Rondell[i][nNextVersion] = -1;
}
for (int i = 0; i < N; ++i) {
if ((Rondell[i][index] == -1) || (Rondell[i][index] == 0)) {
if (Rondell[i][index] == 0)
flag = true;
int nIndexNext = (i+1 + N)%N;
if (!q[i].empty()) {
flag = true;
Rondell[nIndexNext][nNextVersion] = q[i].front() - 1;
q[i].pop();
}
} else {
int nIndexNext = (i+1)%N;
flag = true;
Rondell[nIndexNext][nNextVersion] = Rondell[i][index] - 1;
}
}
index = (index+1)%2;
}
cout << time - 1 << '\n';
q = qtemp;
index = 0;
time = 0;
flag = true;
for (int i = 0; i < N; ++i) {
Rondell[i][0] = -1;
}
while (flag) {
++time;
flag = false;
int nNextVersion = (index+1)%2;
for (int i = 0; i < N; ++i) {
if (!q[i].empty())
flag = true;
Rondell[i][nNextVersion] = -1;
}
for (int i = 0; i < N; ++i) {
if ((Rondell[i][index] == -1)) {
int nIndexNext = (i+1 + N)%N;
if (!q[i].empty()) {
flag = true;
Rondell[nIndexNext][nNextVersion] = q[i].front() - 1;
q[i].pop();
}
} else {
int nIndexNext = (i+1)%N;
flag = true;
Rondell[nIndexNext][nNextVersion] = Rondell[i][index] - 1;
}
}
index = (index+1)%2;
}
cout << time-1 << '\n';
return 0;
}
Här nedan följer ett lösningsexempel i Java. Som sagt uppgiften är inte svår, utan bara jobbig och omständlig.
import java.util.*;
import java.io.*;
public class Rondellsimulering
{
//Roterar bilarna i en rondell.
public static void rotate(int [] rondell)
{
int tmp = rondell[rondell.length-1];
for(int j = rondell.length-1; j>0; j--)
{
//Om det är en bil som flyttas, så kommer den en position
// närmare sitt mål, annars flyttas bara en 0 position.
rondell[j] = (rondell[j-1]>0) ? rondell[j-1] - 1 : 0;
}
//Samma gäller här.
rondell[0] = (tmp>0) ? tmp - 1 : 0;
}
//Hittar och retunerar indexen för alla lediga positioner i rondellen.
public static Integer[] findEmpty(int [] rondell)
{
LinkedList <Integer> empty = new LinkedList <Integer> ();
for(int i = 0; i<rondell.length; i++)
{
if(rondell[i]==0) empty.add(i);
}
//Det är skönare att handskas med en array.
return empty.toArray(new Integer[0]);
}
//Talar om hururvida vi är färdiga eller inte.
public static boolean isFinished(int [] rondell, ArrayList <LinkedList<Integer>> queues)
{
//Om det finns bilar som åker runt i rondellen.
for(int i = 0; i<rondell.length; i++)
{
if(rondell[i]!=0) return false;
}
//Om det finns bilar kvar i någon kö.
for(LinkedList <Integer> queue : queues)
{
if(queue.size()!=0) return false;
}
return true;
}
//Orka fånga exceptions. Vi är lata och säkra på vår sak.
public static void main(String [] klein) throws FileNotFoundException
{
//Vi ska läsa av filen rondell.dat i mappen/katalogen data.
Scanner scan = new Scanner(new File("data\\rondell.dat"));
//Antalet tillfartsvägar.
int N = scan.nextInt();
//Skapar rondell för blink.
int [] rondell = new int [N];
//Skapar rondell utan blink.
int [] rondell2 = new int [N];
//Alla köer för med blink.
ArrayList <LinkedList<Integer>> queues = new ArrayList <LinkedList<Integer>> ();
//Alla köer för utan blink.
ArrayList <LinkedList<Integer>> queues2 = new ArrayList <LinkedList<Integer>> ();
//Läser in alla bilköer för både med blink och utan blink.
for(int i = 0; i<N; i++)
{
int nrCars = scan.nextInt();
LinkedList <Integer> queue = new LinkedList <Integer> ();
LinkedList <Integer> queue2 = new LinkedList <Integer> ();
for(int j = 0; j<nrCars; j++)
{
queue.add(scan.nextInt());
queue2.add(queue.get(j));
}
queues.add(queue);
queues2.add(queue2);
}
//De första bilarna i köerna kör ut på sina positioner.
for(int i = 0; i<N; i++)
{
LinkedList <Integer> queue = queues.get(i);
LinkedList <Integer> queue2 = queues2.get(i);
rondell[i] = queue.removeFirst();
rondell2[i] = queue2.removeFirst();
}
//Det tog en tidsenhet för första draget.
int tid = 1;
//Löser problemet för med blink.
while(!isFinished(rondell, queues))
{
//Ny tidsenhet.
tid++;
//Roterar alla bilar i rondellen.
//Observer att alla bilar som ska svänga in hinner göra det.
rotate(rondell);
//Hittar nu alla lediga positioner.
Integer [] empty = findEmpty(rondell);
//Går igenom alla lediga positioner.
for(int i = 0; i<empty.length; i++)
{
//Kön som står vid den lediga positionen.
LinkedList <Integer> queue = queues.get(empty[i]);
//Om det finns bilar i kön, så får den första köra ut i rondellen.
if(queue.size()!=0) rondell[empty[i]] = queue.removeFirst();
}
}
//Skriver ut svaret.
System.out.println("Med blink: " + tid);
//En tidsenhet har gjorts för utan blink.
tid = 1;
//Löser problemet för utan blink.
while(!isFinished(rondell2, queues2))
{
//Ny tidsenhet.
tid++;
//Hittar alla tomma positioner.
//(Att vi plockar ut positionerna redan nu simulerar
// det faktum att vi inte vet vilka bilar som kommer
// svänga in.)
Integer [] empty = findEmpty(rondell2);
//Alla bilar roterar. (De bilar som är klara blir klara.)
rotate(rondell2);
//Går igenom alla tomma positioner.
for(int i = 0; i<empty.length; i++)
{
//Nu har den tomma positionen hamnat ett steg framåt.
//Om bilarna inte blinkar fokuserar man ju inte på den
//precis framför en utan på den innan. %N fixar så att
// den sista positionen i arrayen hamnar först om så
// skulle behövas.
int next = (empty[i]+1)%N;
//Hämtar kön i vilka bilarna hade ögonen spända på
// den kommande lediga positionen.
LinkedList <Integer> queue = queues2.get(next);
//Om kön inte är tom, så får den första bilen köra ut i rondellen.
if(queue.size()!=0) rondell2[next] = queue.removeFirst();
}
}
//Skriver ut svaret.
System.out.println("Utan blink: " + tid);
}
}
En lite marig lösning i Haskell.
-- Rondellsimulering
module Main where
import IO
import Data.List
main = do {
ih <- openFile "rondell.dat" ReadMode;
content <- hGetContents ih;
rader <- return $ lines content;
n <- return $ read $ head rader;
ques <- return $ map ((map read).words) $ queue $ tail rader;
putStrLn $ "Med blink: " ++ (show $ blink 0 0 (replicate n (-1)) ques);
putStrLn $ "Utan blink: " ++ (show $ blink (-1) 0 (replicate n (-1)) ques);
hClose(ih)
}
queue [] = []
queue (_:h:t) = h:(queue t)
blink :: Int -> Int -> [Int] -> [[Int]] -> Int
blink s n rond qu = if (finished rond qu) then n else blink s (n+1) new a
where
(a,b) = copy s qu rond
new = let nw = map (-1 +) b in (last nw):(init nw)
copy :: Int -> [[Int]] -> [Int] -> ([[Int]], [Int])
copy _ [] [] = ([], [])
copy s (h:t) (h2:t2) = if (h2<=s && h/=[]) then (tail h:a, head h:b) else (h:a, h2:b)
where
(a,b) = copy s t t2
finished :: [Int] -> [[Int]] -> Bool
finished rond qu = (and $ map (0 >) rond) && (and $ map ([]==) qu)