Tävlingsprogrammering/Uppgifter/Bokstavslek (2)
Bokstavslek
Två personer, låt oss kalla dem Anna och Bosse, turas om att säga en bokstav (Anna säger första bokstaven, Bosse andra, Anna tredje o.s.v.). Samma bokstav kan användas flera gånger. Det finns två regler:
- De bokstäver som hittills är sagda (i ordning) får inte bilda ett avslutat ord.
- De bokstäver som hittills är sagda (i ordning) måste kunna bilda ett ord om fler bokstäver får läggas till på slutet.
Den som bryter mot någon av reglerna förlorar och den andre vinner sålunda (i den verkliga leken kan man bluffa på den andra regeln).
Exempelvis, om bokstäverna S, T och U är sagda, så förlorar Bosse om han säger P eftersom STUP är ett ord. Vidare förlorar han om han säger t.ex. J eftersom inget ord börjar på STUJ. Däremot går leken vidare om han säger G, Anna får då inte säga A eftersom STUGA är ett ord, däremot kan hon säga B och därmed tvinga Bosse att avsluta ordet STUGBY.
För enkelhets skull antar vi här att endast bokstäverna A-Z får användas. Vidare finns en ordlista som innehåller alla bokstavskombinationer som ska betraktas som ord i just denna lek. Skriv ett program som bestämmer vilka bokstäver som är “säkra” att börja med för Anna, d.v.s. de bokstäver som gör att hon kan vinna omgången oavsett vilka bokstäver som Bosse väljer.
På första raden i filen bokstav.dat står ett heltal N (1 ≤ N ≤ 40000), antal ord i ordlistan. Därefter följer N rader med ett ord på varje rad. Orden står i alfabetisk ordning. Varje ord består av högst 20 bokstäver, valda bland versalerna A-Z. Även påhittade ord kan förekomma.
Programmet ska skriva ut en alfabetiskt ordnad lista över de bokstäver som har egenskapen att, om Anna börjar med bokstaven kommer hon kunna vinna oavsett vilka bokstäver Bosse väljer (båda får förstås anpassa sina val efter vad den andre säger).
Körningsexempel: Filen bokstav.dat med innehållet
8 FE FRI FRIA KO SE STUGA STUGBY STUP
ska ge svaret
Säkra bokstäver: K S
Lösning
redigeraDenna uppgift löser vi lätt med djupsökning och enkel spelteori.
Då antalet vägar mellan varje höjd är 28*28 (28 är antalet bokstäver i alfabetet utan å, ä och ö) och det finns totalt 20 våningar på grafen så räcker en 19*28*28 matris för att representera grafen. (Hur räknar man om man får antalet bokstäver A-Z till 28??)
Här är en lösning med en egen implementerad graf bestående av klasser.
#include <iostream>
#include <fstream>
#include <string>
const bool ANNA = 1, BOSSE = 0;
class node {
protected:
node* branch[28];
int status;
node(int n);
public:
friend class tree;
};
node::node(int n) {
for (int i = 0; i < 28; ++i) {
branch[i] = NULL;
}
status = n;
}
class tree {
void insertMechanics(node*& place, std::string sTemp, int nDepth);
node* root;
bool Search(node*& curr, int player);
public:
tree();
void insert(std::string sTemp);
bool anna(int n);
};
tree::tree() {
root = new node(1);
}
bool tree::Search(node*& curr, int player) {
if (curr->status == ANNA)
return ANNA;
if (curr->status == BOSSE)
return BOSSE;
if (player == ANNA) {
for (int i = 0 ; i < 28; ++i) {
if (curr->branch[i] != NULL) {
if (Search(curr->branch[i], BOSSE) == ANNA) {
return ANNA;
}
}
}
return BOSSE;
}
if (player == BOSSE) {
for (int i = 0 ; i < 28; ++i) {
if (curr->branch[i] != NULL) {
if (Search(curr->branch[i], ANNA) == BOSSE) {
return BOSSE;
}
}
}
return ANNA;
}
};
bool tree::anna(int n) {
if (root->branch[n] == NULL)
return BOSSE;
return Search(root->branch[n], BOSSE);
}
void tree::insertMechanics(node*& place, std::string sTemp, int nDepth) {
if (nDepth == sTemp.length()-1) {
if (place->branch[sTemp[nDepth]-'A'] == NULL) {
place->branch[sTemp[nDepth]-'A'] = new node(!(nDepth%2 == 0));
} else {
place->branch[sTemp[nDepth]-'A']->status = !(nDepth%2);
}
} else if (nDepth < sTemp.length()) {
if (place->branch[sTemp[nDepth]-'A'] == NULL) {
place->branch[sTemp[nDepth]-'A'] = new node(-1);
}
insertMechanics(place->branch[sTemp[nDepth]-'A'], sTemp, nDepth+1);
}
return;
}
void tree::insert(std::string sTemp) {
insertMechanics(root, sTemp, 0);
}
int main() {
std::ifstream fin("bokstav5.dat");
tree tr;
int nOrd;
fin >> nOrd;
for (int i = 0; i < nOrd; ++i) {
std::string sTemp;
fin >> sTemp;
tr.insert(sTemp);
}
for (int i = 0; i < 28; ++i) {
if (tr.anna(i)) {
std::cout << char (i + 'A') << ' ';
}
}
std::cout << '\n';
return 0;
}
Här kommer ett liknande lösningsförslag som är lite kortare. Den bygger också på ett träd. Första bokstaven har en array med 26 element, som representerar var sin bokstav som kommer efter denna bokstav. NULL = finns inget sådant ord, 1 = Finns sådant ord, fast detta är sista bokstaven. Adress = adressen till en annan 26-elementarray som representerar bokstaven efter det. Sedan gör vi bara en djupsökning där vi testar alla fall. Eftersom vi bara har 40 000 ord så går det rätt så snabbt (under 100 ms på min dator på värsta testdatan). För enkelhetens skull läser denna från stdin och inte från fil. Så kör t.ex. "./bokstav < bokstav5.dat" eller "bokstav.exe < bokstav5.dat".
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef void* pointer;
//Ett träd av orden, detta är rotnoden (första bokstaven), där
//varje element innehåller antingen NULL (inget sådant ord),
//1 (slut på ordet här), eller en adress till nästa nod i trädet (array med 26 element) av samma struktur,
//dvs. nästa bokstav som man kan säga.
//Så t.ex. för att hämta ut vad som händer om man börjar med bokstäverna ABCE, hämtar man ut ordlista[0][1][2][4],
//förutsatt att alla noder existerar och att man har rätt pekartyp.
pointer ordlista[26];
void ordlista_add(char* ord){
const int len = strlen(ord);
//ptr är 26-elementsarrayen man för tillfället är på. Startar på rotnoden, alltså första bokstaven.
pointer* ptr = ordlista;
for(int i=0; i<len; i++){
if(ord[i+1] == '\0'){
//Vi är på sista bokstaven i ett ord, sätt 1 som värde på denna bokstavs index i arrayen för att visa det
ptr[ord[i]-'A'] = (pointer)1;
} else if(ptr[ord[i]-'A']==NULL){
//Det finns inget träd på denna position i arrayen, så skapa ett
ptr[ord[i]-'A'] = malloc(26*sizeof(pointer));
memset(ptr[ord[i]-'A'], 0, 26*sizeof(pointer));
//Hoppa fram till denna nod
ptr = (pointer*)ptr[ord[i]-'A'];
} else if(ptr[ord[i]-'A']==(pointer)1) {
//Det finns redan ett ord som slutar så här, onödigt att lägga till ett längre ord,
//eftersom man aldrig (enligt reglerna) kommer att kunna säga det
break;
} else {
//Det finns ett träd för denna bokstav, så gå till det
ptr = (pointer*)ptr[ord[i]-'A'];
}
}
}
//Det är en persons tur.
//pointer ordlistan[] = en 26-element-array, med vilka bokstäver man kan använda (en nod i trädet)
//Returnerar: true om det går att vinna om man kör optimalt, för personen som här väljer bokstav
//false om hur aktuell spelare än försöker kan motspelaren alltid vinna
bool say(pointer ordlistan[26]){
//Testa säg alla bokstäver som det finns ord för
for(int i=0; i<26; i++){
if(ordlistan[i]==NULL) continue;
if(ordlistan[i]==(pointer)1){
//Detta skulle resultera i förlust för den som säger denna bokstav
} else {
//Kollar vad som händer med nästa person om man själv kör på denna bokstav
if(!say((pointer*)ordlistan[i]))
return true; //Vi vet nu att det går att vinna för personen som säger denna bokstav,
//eftersom motspelaren (personen i nästa drag) inte kan vinna
}
}
return false; //Vi hittade ingen nästa bokstav som resulterade i vinst för personen som säger denna bokstav
}
int main(){
for(int i=0; i<26; i++) ordlista[i] = NULL;
int N;
scanf("%d", &N);
for(int i=0; i<N; i++){
char ord[21];
scanf("%s", ord);
ordlista_add(ord);
}
printf("Säkra bokstäver: ");
for(int i=0; i<26; i++){
if(ordlista[i]==NULL) continue;
if(ordlista[i]==(pointer)1){
//Anna kan inte vinna om ett ord är en ensam bokstav
} else {
//Det finns ord med minst två bokstäver som börjar med denna bokstav
//Om Bosse inte vinner (det är Bosse man går efter eftersom han säger andra bokstaven) vinner Anna
if(!say((pointer*)ordlista[i]))
printf("%c ", 'A'+i);
}
}
//Vi skiter i att rensa upp minnet från våra malloc()-anrop eftersom vårt program
//ändå inte behöver utrymmet för något annat. Vi låter operativsystemet ta hand om det istället.
}
Här nedan följer ett lösningsexempel i Java. Lösningen kanske inte är lika effektiv som ovanstående (eller effektiv i allmänhet), men jag hoppas att den ska vara något mer lättförståelig. Lösningen går till på så sätt att vi bygger ett träd av alla ord. Om vi t.ex. har ordet APA, så bygger vi upp trädet (Rot)-A-AP-APA; om vi sedan vill lägga till ordet APUNGE, så bygger vi på trädet från AP med AP-APU-APUN-APUNG-APUNGE. Sedan när vi har genererat alla delord som kan fås av alla ord i ordlistan (bokstav.dat), så återstår det bara att ange vem som vinner ett visst delord. Vem som vinner avgörs av följande villkor:
- Anna vinner ett delord om delordet finns i ordlistan och har ett jämnt antal bokstäver. D.v.s. ett ord som Bosse skulle tvingas säga om vi kom dit. Bosse vinner å andra sidan om (del)ordet (som finns i ordlistan) har ett udda antal bokstäver. I mitt lilla exempel ovan så kan vi se att Bosse vinner ordet APA, medan ANNA vinner ordet APUNGE.
- Anna vinner ett delord om delordet har ett udda antal bokstäver (det är hennes att säga) och alla delord som kan nås från delordet också vinns av Anna. Annars vinner Bosse (eftersom han då kommer välja ordet som tar honom till seger). Exempel på detta scenario är (del)ordet APUNG (eller APU), eftersom alla ord som kan nås (i detta fall bara ett, nämligen APUNGE) från det vinns av ANNA.
- Anna vinner ett delord om delordet har ett jämnt antal bokstäver och det finns något (en eller flera) delord som kan nås från delordet som också vinns av Anna. Exempel på detta scenario är (del)ordet AP. Visserligen vinns ordet APA av Bosse, men Anna är ju inte dum, så hon väljer givetvis att säga U, vilket leder till APU vilket är ett delord som vinns av henne.
Så i mitt lilla exempel skulle alltså A vara en säker bokstav för Anna att säga. Sedan kan väl nämnas att vi använder ett HashSet som ordlista, eftersom vi vill ha konstant tid för sökningsoperationen (contains). Valet av ArrayList för att lagra noderna finns det dock ingen baktanke med, troligen skulle det kanske vara smartare att lagra noderna i en länkad lista.
import java.util.*;
import java.io.*;
public class Bokstavslek2
{
//Ordlista som innehåller alla ord.
static HashSet <String> ordlista = new HashSet <String> ();
//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 bokstav.dat i mappen/katalogen data.
Scanner scan = new Scanner(new File("data\\bokstav.dat"));
//Antalet ord.
int N = scan.nextInt();
//Lagrar alla ord. (Egentligen onödigt.)
String [] ord = new String [N];
//Vårt sökträd.
MyTree tree = new MyTree();
//Läser in alla ord.
for(int i = 0; i<N; i++)
{
//Läser in ordet.
ord[i] = scan.next();
//Lägger till det i ordlistan.
ordlista.add(ord[i]);
//Bygger på sökträdet med det här ordet.
//D.v.s. lägger till alla substrings som ges av ordet.
for(int j = 1; j<=ord[i].length(); j++)
{
tree.add(ord[i].substring(0,j));
}
}
//Skriver ut alla säkra bokstäver.
System.out.println("Säkra bokstäver:" + tree.getSafe());
}
//Hemmagjord klass som beskriver ett "träd" i denna uppgift.
private static class MyTree
{
//Roten har "level" 0.
private int root = 0;
//Alla olika första bokstäver man får säga.
private ArrayList <BNode> children;
//Vilka substrings som redan finns i trädet.
HashSet <String> used = new HashSet <String> ();
//Skapar trädet.
public MyTree()
{
children = new ArrayList <BNode> ();
}
//Lägger till en nod i trädet.
//I vårt fall en del av ett ord (en substring).
public void add(String s)
{
//Om den delen redan fanns, så behöver vi inte lägga till den.
if(!used.add(s)) return;
//Om det bara är en bokstav ska den växa ut ifrån roten.
if(s.length()==root+1)
{
children.add(new BNode(s));
}
else //Annars läggs den till på rätt plats.
{
//Går igenom alla noder till denna nod (roten).
for(int i = 0; i<children.size(); i++)
{
BNode parent = children.get(i);
//Om den här noden är förälder till den
// noden vi tänker lägga till, så ska vår
// nod placeras någonstans under den.
if(parent.isParent(s))
{
parent.add(s);
break;
}
}
}
}
//Retunerar alla säkra bokstäver.
public String getSafe()
{
String safe = "";
//Går igenom alla noder (första bokstäver).
for(BNode node : children)
{
//Om den är säker.
if(node.isSafe())
{
safe += " " + node.getWord();
}
}
return safe;
}
//Hemmagjord klass som beksriver en nod i trädet.
private class BNode
{
//Vilken nivå vi är i. (Hur många bokstäver delordet innehåller.)
private int level;
//Själva (del)ordet.
private String word;
//Alla delord som kan nås från detta ord.
private ArrayList <BNode> nodes;
//Skapar noden.
public BNode(String s)
{
word = s;
level = s.length();
nodes = new ArrayList <BNode> ();
}
//Retunerar huruvida det här ordet är säkert för Anna.
//true = vinst för Anna. false = vinst för Bosse.
public boolean isSafe()
{
//Om ordlistan innehåller det här ordet.
if(ordlista.contains(word))
{
//Om det är Bosse som tvingas säga detta ord, så vinner Anna.
//Annars vinner Bosse (det är Anna som måste säga ordet).
//Kollar om ordet har jämnt antal bokstäver, för då är det
// Bosses ord att säga.
if(level%2==0) return true;
else return false;
}
else
{
//Om Anna ska säga detta ord.
if(level%2==1)
{
//Så är ordet säkert om alla ord som kan nås från detta
// ord också är säkra.
for(BNode node : nodes)
{
//Om det finns ett ord som kan nås som är osäkert, så
// är detta (del)ord också osäkert, eftersom Bosse
// alltid kommer välja det ord som är osäkert för Anna.
if(!node.isSafe()) return false;
}
return true;
}
else //Om Bosse ska säga detta ord.
{
//Så är detta ord säkert (för Anna) om det finns något ord
// som kan nås från detta (del)ord som också är säkert.
for(BNode node : nodes)
{
if(node.isSafe()) return true;
}
return false;
}
}
}
//Lägger till en nod någonstans under denna nod.
public void add(String s)
{
//Om (del)ordet bara är en bokstav längre än detta så ska
// ordet länkas till från denna nivå (detta ord).
if(s.length()==level+1)
{
nodes.add(new BNode(s));
}
else
{
//Annars skickar vi vidare ordet till någon mer
// närstående förälder.
for(int i = 0; i<nodes.size(); i++)
{
BNode parent = nodes.get(i);
if(parent.isParent(s))
{
parent.add(s);
break;
}
}
}
}
//Retunerar huruvida detta ord är förälder tillden givna ordet (s).
public boolean isParent(String s)
{
//Det är vi om ordet börjar med vårt ord.
return s.startsWith(word);
}
//Retunerar denna nods ord. (Behövs när trädet ska accessa alla level 1 ord.)
public String getWord()
{
return word;
}
}
}
/*** MyTree Ends ***/
}
Enormt elegant lösning i Haskell.
-- Bokstavslek 2
module Main where
import IO
import Data.List
import Data.Ord (comparing)
import Data.Set (Set, member, fromList)
data Tree = Tree {letter :: Char, level :: Int, kids :: [Tree]}
myGroup = groupBy (\a b -> (head a) == (head b))
mySort = sortBy (comparing head)
main = do {
ih <- openFile "bokstav.dat" ReadMode;
content <- hGetContents ih;
vocab <- return $ (myGroup.tail.words) content;
safe <- return $ [head (head x) | x <- vocab, isSafe (fromList x) [] (buildTree 1 x)];
putStrLn $ "Sakra bokstaver: " ++ (foldr (\x xs -> x:' ':xs) [] safe);
hClose(ih)
}
buildTree :: Int -> [String] -> Tree
buildTree n s@(h:_) = Tree (head h) n (map (buildTree $ n+1) next)
where
next = myGroup $ mySort $ filter (/= []) $ map tail s
isSafe :: (Set String) -> String -> Tree -> Bool
isSafe dict ord tree
| odd $ level tree = anna
| otherwise = bosse
where
say = ord ++ [letter tree]
bad = member say dict
next = (map (isSafe dict say) (kids tree))
anna = if bad then False else and next
bosse = if bad then True else or next