Tävlingsprogrammering/Uppgifter/Uppställning (2)
Uppställning (2)
N personer, numrerade från 1 till N, står uppställda huller om buller på en rad. Du ska få personerna att stå i nummerordning (1, 2, 3, ...,N) genom att ge ett antal kommandon. Med varje kommando omvänder du ordningen på ett valfritt antal intill varandra stående personer. Skriv ett program som beräknar det minsta antalet kommandon du behöver ge.
FIGUR 3.
Den översta raden visar utgångsställningen i det första körningsexemplet,
den mellersta raden ställningen efter ett kommando
och den nedersta raden slutställningen.
Programmet ska fråga efter antalet personer N, där 2 ≤ N ≤ 8, och sedan efter utgångsställningen. Du kan förutsätta att de inmatade talen är mellan 1 och N och att varje tal förekommer exakt en gång. Programmet ska skriva ut det minsta antalet kommandon som krävs för att ställa personerna i nummerordning.
Körningsexempel 1
Antal personer ? 4 Person på position 1 ? 4 Person på position 2 ? 1 Person på position 3 ? 3 Person på position 4 ? 2 Minsta antal kommandon: 2
Körningsexempel 2
Antal personer ? 2 Person på position 1 ? 1 Person på position 2 ? 2 Minsta antal kommandon: 0
Körningsexempel 3
Antal personer ? 5 Person på position 1 ? 3 Person på position 2 ? 5 Person på position 3 ? 1 Person på position 4 ? 4 Person på position 5 ? 2 Minsta antal kommandon: 3
Lösning
[redigera]Här nedan följer en lösning i Java. När man först ser körningsexemplen, så tänker man "det är väl bara att flytta fram 1:an först, sedan 2:an, osv", dvs någon form av girig lösning som i värsta fall kräver N-1 kommandon. Men sedan så lägger man märke till att antalet personer aldrig kommer att vara fler än åtta och då blir man misstänksam. För den knappa siffran åtta skriker ju bokstavligen "du kommer nog vara tvungen att testa många kombinationer, så därför har vi varit snälla och tänker aldrig använda testfall större än åtta", förutsatt då att skaparna av uppgiften inte försöker använda någon form av omvänd psykologi.
Med ovanstående i åtanke, så inser man att man kanske får tänka ett varv extra och det dröjer inte länge innan man hittar ett fall där den giriga lösningen inte är bäst, t.ex. ett fall med uppställningen 87654312. Vi inser då att vi kanske borde implementera någon form av lösning som testar att utföra alla kommandon och hittar det minsta antalet som krävs. Dock kommer det för elakartade testfall att bli väldigt många möjligheter som kommer att testas, men många av kommandona kommer att vara extremt korkade, t.ex. kommer vi besöka samma ställning flera gånger och det vill vi ju inte. Någonstans här bör man dock inse att antalet ställningar som överhuvudtaget kan uppstå är blott 8! (40320, vilket är ingenting). Detta faktum gör att det kan vara lämpligt att spara undan ställningarna man har besökt.
Med ovanstående fakta i bagaget, så skulle någon form av BFS-liknande lösning passa väldigt bra, men i denna lösning har jag valt att köra med någon form av brute-force i kombination med dynamisk programmering. I en sådan lösning kommer vetskapen om att den giriga lösningen aldrig kräver mer än N-1 drag väl till pass, då den kan användas som startgräns för när vi bör avbryta rekursionen. Sedan använder jag mig av standardklassen HashMap (en from av hashtabell) för att spara undan ställningarna jag har besökt. Ett litet problem kan dock vara att det inte är så jävla lyckat att stoppa arrayer i en hashtabell (i Java), i synnerhet inte i detta exempel (eftersom två objekt troligen kommer anses vara lika om de har samma minnesreferens, och i detta exempel jobbar vi på samma objekt hela tiden, så det skulle få rekursionen att avbrytas helt efter bara ett anrop). Så vi måste komma på något sätt som vi kan beskriva en int-array på ett unikt sätt på. En lösning kan vara att använda metoden Arrays.toString() och stoppa in sträng-representation av arrayen i hashtabellen, vilket fungerar utmärkt, men tar lite extra tid och minne (man klarar dock ändå värsta testfallet på dryga 3 sek). Men eftersom vi bara har en array med 8 unika tal mellan 1-8, så kan ju ett praktiskt sätt vara att beskriva arrayen som det tal den får om man läser siffrorna i den från höger-till-vänster (eller vänster-till-höger). Det är detta jag har implementerat med hjälp av metoden hash() i exemplet.
Sedan behöver vi bara tänka på att med denna form av lösning (inte BFS) så är det inte säkert att vi första gången når en ställningen på minsta antal drag, varför vi bör tillsammans med en ställning spara antalet drag som krävts för att nå den.
import java.util.*;
public class Uppstallning2
{
//Minsta antalet kommandon som krävs.
static int min;
//Hashtabell för dynamisk programmering.
static HashMap <Integer, Integer> map = new HashMap <Integer, Integer> ();
//Rekursiv metod som testar alla möjliga drag.
//person: Uppställningen man testar alla drag på.
//drag: Antalet drag man gjort för att nå ställningen.
public static void rek(int [] person, int drag)
{
//Dumt att fortsätta.
if(drag>=min) return;
//Vi har hittat en möjlig lösning.
if(isSorted(person))
{
min = drag;
return;
}
//(Om ställningen inte finns i hashtabellen retuneras null.)
Integer tal = map.get(hash(person));
//Kollar om vi besökt denna ställning tidigare.
//Och om den nåddes på färre drag än vi gjort nu.
//I så fall bör vi avbryta.
if(tal!=null && drag>=tal)
{
return;
}
else
{
//Annars markerar vi ställningen som besökt.
map.put(hash(person), drag);
}
//Utför alla möjliga drag från denna ställning.
for(int i = 0; i<person.length-1; i++)
{
for(int j = i+1; j<person.length; j++)
{
//Utför kommandot/draget.
invert(person, i, j);
//Går vidare och utför kommandon på den nya ställningen.
rek(person, drag+1);
//Nollställer kommandot/draget.
invert(person, i, j);
}
}
}
//Kollar om personerna står i nummerordning.
public static boolean isSorted(int [] person)
{
for(int i = 0; i<person.length; i++)
{
if(person[i]!=(i+1)) return false;
}
return true;
}
//Omvänder (inverterar) personerna inom det givna intervallet.
// (Dvs utför ett "kommando".)
//from: Första (index) personen i intervallet.
//to: Sista (index) personen i intervallet.
public static void invert(int [] person, int from, int to)
{
while(from<to)
{
int tmp = person[from];
person[from] = person[to];
person[to] = tmp;
from++;
to--;
}
}
//Sparar värdena 1...10^(N-1)
private static int [] hash;
//Retunerar en int som beskriver ställningen med ett unikt värde.
private static int hash(int [] person)
{
int total = 0;
for(int i = 0; i<person.length; i++)
{
total += person[i]*hash[i];
}
return total;
}
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
System.out.print("Antal personer: ");
int antal = scan.nextInt();
//Våra personer.
int [] person = new int [antal];
//Läser in personerna.
for(int i = 0; i<antal; i++)
{
System.out.print("Person på position " + (i+1) + ": ");
person[i] = scan.nextInt();
}
//Vi tar fram så många tiopotenser vi behöver.
hash = new int [antal];
hash[0] = 1;
for(int i = 1; i<antal; i++)
{
hash[i] = hash[i-1]*10;
}
//Den giriga trivial-lösningen kräver i värsta fall N-1 kommandon.
min = antal-1;
//Man får inte missa specialfallet att personerna redan står rätt.
if(isSorted(person)) min = 0;
//Finner svaret. Vi ska utföra kommandon på personerna och vi
//har utfört 0 kommandon.
rek(person, 0);
//Skriver ut svaret.
System.out.println("\nMinsta antal kommandon: " + min);
}
}