Jump to content
  • 0

brainstorming


jenkings

Dotaz

Čaute

Mám takový intelektuální (ne)problém. Včera jsem přemýšlel nad logikou, jak počítat skóre u scrabble, v případech, že hráč položením kamenů složí více než jedno slovo.
Ověřování slov proti slovníku teď pomiňme a berme, že pro tento příklad jsou všechna slova validní.
Při mém brainstormingu o řešení jsem vždy došel až do bodu, kdy jsem byl v pátém zanořeném cyklu, a v nedozírné rekurzi, takže vhazuji rukavici do ringu, s výzvou: Kdo to vymyslí nejlépe?

Pro případné vymýšlení nebo zkoušení, kdyby se tím chtěl někdo zabývat, jsou tady podklady:

Funkce pro výpočet skóre za jednotlivá písmena a pole objektů se souřadnicemi bonusů na desce (type 1 je, že se násobí celé složené slovo, type 0, že se násobí pouze písmeno)

    letterValue(letter) {
        var tileScore = {
            0: '?', 1: 'a,e,i,l,n,o,r,s,t,u', 2: 'd,g',
            3: 'b,c,m,p', 4: 'f,h,v,w,y', 5: 'k', 8: 'j,x', 10: 'q,z'
        };
        if (letter.length === 1) {
            for (var v in tileScore) {
                if (tileScore[v].indexOf(letter.toLowerCase()) >= 0) {
                    return v;
                }
            }
        }
        return null;
    }
    
    
    
    static bonuses = [ /*První řádek*/ 	{x:0,y:0,multiplier:3,type:1}, 	{x:3,y:0,multiplier:2,type:0}, 	{x:7,y:0,multiplier:3,type:1}, 	{x:11,y:0,multiplier:2,type:0}, 	{x:14,y:0,multiplier:3,type:1}, /*Druhý řádek	*/ 	{x:1,y:1,multiplier:2,type:1}, 	{x:5,y:1,multiplier:3,type:0}, 	{x:9,y:1,multiplier:3,type:0}, 	{x:13,y:1,multiplier:2,type:1}, /*Třetí řádek	*/ 	{x:2,y:2,multiplier:2,type:1}, 	{x:6,y:2,multiplier:2,type:0}, 	{x:8,y:2,multiplier:2,type:0}, 	{x:12,y:2,multiplier:2,type:1}, /*Čtvrtý řádek	*/ 	{x:0,y:3,multiplier:2,type:0}, 	{x:3,y:3,multiplier:2,type:1}, 	{x:7,y:3,multiplier:2,type:0}, 	{x:11,y:3,multiplier:2,type:1}, 	{x:14,y:3,multiplier:2,type:0}, /*Pátý řádek*/ 	{x:4,y:4,multiplier:2,type:1}, 	{x:10,y:4,multiplier:2,type:1}, /*Šestý řádek*/ 	{x:1,y:5,multiplier:3,type:0}, 	{x:5,y:5,multiplier:3,type:0}, 	{x:9,y:5,multiplier:3,type:0}, 	{x:13,y:5,multiplier:3,type:0}, /*Sedmý řádek*/ 	{x:2,y:6,multiplier:2,type:0}, 	{x:6,y:6,multiplier:2,type:0}, 	{x:8,y:6,multiplier:2,type:0}, 	{x:12,y:6,multiplier:2,type:0}, /*Osmý řádek*/ 	{x:0,y:7,multiplier:3,type:1}, 	{x:3,y:7,multiplier:2,type:0}, 	{x:11,y:7,multiplier:2,type:0}, 	{x:14,y:7,multiplier:3,type:1}, /*Devátý řádek*/ 	{x:2,y:8,multiplier:2,type:0}, 	{x:6,y:8,multiplier:2,type:0}, 	{x:8,y:8,multiplier:2,type:0}, 	{x:12,y:8,multiplier:2,type:0}, /*Desátý řádek*/ 	{x:1,y:9,multiplier:3,type:0}, 	{x:5,y:9,multiplier:3,type:0}, 	{x:9,y:9,multiplier:3,type:0}, 	{x:13,y:9,multiplier:3,type:0}, /*Jedenáctý řádek*/ 	{x:4,y:10,multiplier:2,type:1}, 	{x:10,y:10,multiplier:2,type:1}, /*Dvanáctý řádek	*/ 	{x:0,y:11,multiplier:2,type:0}, 	{x:3,y:11,multiplier:2,type:1}, 	{x:7,y:11,multiplier:2,type:0}, 	{x:11,y:11,multiplier:2,type:1}, 	{x:14,y:11,multiplier:2,type:0}, /*Třináctý řádek	*/ 	{x:2,y:12,multiplier:2,type:1}, 	{x:6,y:12,multiplier:2,type:0}, 	{x:8,y:12,multiplier:2,type:0}, 	{x:12,y:12,multiplier:2,type:1}, /*Čtrnáctý řádek	*/ 	{x:1,y:13,multiplier:2,type:1}, 	{x:5,y:13,multiplier:3,type:0}, 	{x:9,y:13,multiplier:3,type:0}, 	{x:13,y:13,multiplier:2,type:1}, /*Patnáctý řádek*/ 	{x:0,y:14,multiplier:3,type:1}, 	{x:3,y:14,multiplier:2,type:0}, 	{x:7,y:14,multiplier:3,type:1}, 	{x:11,y:14,multiplier:2,type:0}, 	{x:14,y:14,multiplier:3,type:1} ];
    


A pro testování příklad desky před a po tahu, které jsou vstupem funkce pro výpočet skóre v tahu. Je to vždy jen 2D pole představující desku, a položená/nepoložená písmena
 

    static boardOld = [
    ["A","B","O","P","S","","","","","","","","","",""],
    ["","","A","","","","","","","","","","","",""],
    ["","","M","","","","","","","","","","","",""],
    ["","","C","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""]
    ]
    
    
    static boardNew = [
    ["A","B","O","P","S","","","","","","","","","",""],
    ["","","A","C","D","","","","","","","","","",""],
    ["","","M","","","","","","","","","","","",""],
    ["","","C","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""],
    ["","","","","","","","","","","","","","",""]
    ]

 

Link to comment
Share on other sites

7 odpovědí na tuto otázku

Recommended Posts

  • 0

Začal by som tak, že by som najskôr zistil, ktoré znaky sú nové a uložil by som si ich súradnice do nejakého poľa.

Potom by som začal vytvárať pole nových slov...

Treba zistiť, či sú nové písmenká položené vertikálne, alebo horizontálne.

Ak sú položené vertikálne, pre každý nový znak by som sa pozrel vľavo a vpravo od neho (až do prázdneho miesta alebo okraja hracej dosky). Ak by som našiel aspoň 2 znaky, znamenalo by to nové slovo. Takéto slovo by som pridal do poľa všetkých nových slov vo forme jednotlivých písmenok a príslušných bonusov. Bonusy pre staré znaky by som označil ako typ 0, multiplier 1 (žiadny bonus). Bonusy pre nové znaky sa zistia z tvojho poľa bonusov. Potom by som identifikoval začiatok a koniec slova vo vertikálnom smere - treba si dať pozor na to, že v tomto slove môže byť viac nových znakov, a teda viac bonusov. Toto nové slovo by som reprezentoval rovnakým spôsobom ako predošlé slová a vložil do rovnakého poľa.

Ak sú položené horizontálne, postup je analogický s tým rozdielom, že pre každý nový znak sa pozerám hore a dole pre vertikálne slová a potom vľavo a vpravo pre nové horizontálne slovo.

Na záver potrebuješ nejakú funkciu, ktorá dostane reprezentáciu nového slova (pole objektov zložených z písmenka, typu bonusu a multiplieru) a vyhodnotí jeho skóre. Túto funkciu aplikuješ na všetky nájdené nové slová a spočítaš súčet.

Zajtra k tomu skúsim napísať nejaký kód... Mohol by si zatiaľ priložiť nejaké jednoduché testy, aby som si overil, že mi to funguje správne?

Link to comment
Share on other sites

  • 0
  • Majitel

Já bych probublal "dotek" nových písmen do okolních písmen a pak projel všechny směry tvrdým loopem, který se v tom pokusí najít shodu :) 

Ber v potaz, že jsem primárně C# člověk.. Celkově bych herní board řešil přes vlastní datové typy definující specifická písmenka, jejich stav a případně flag jestli byla dotknutá - tím pádem probublání doteků od nových písmenek lze řešit jednoduše

Board jako takový bych definoval jako List písmenek v dalším listu - tím docílím jakéhosi pseudo-dvou-dimenzionálního pole písmenek a Listy pak představují osy X a Y - pokud bych si chtěl ušetřit práci, písmenkám bych do definice zařadil i XY pozici v boardu - tím pádem manipulace s Listy bude o to jednodušší při bublání

S tím už se pak dá pracovat jak potřebuješ ať už se jedná o jakákoliv pravidla

Link to comment
Share on other sites

  • 0

Duff - něco takového jsem měl na mysli taky, ale přišlo mi to hrozně překombinované, tak jsem si říkal, jestli není nějaké elegantnější řešení, ale nakonec to tak asi dopadne. Testy zatím žádné nemám,ale můžu něco zkusit spíchnout.

ffredyk - je pravdou, že by mohlo každé z písmen držet referenci na všechny své bonusy a všechny své sousedy. Pak by asi bylo všechno tohle probublávání o dost jednodušší. Tohle řešení má ale trochu nevýhodu v tom, kolik to zabere paměti. A vzhledem k tomu, že to poběží na serveru, kde může běžet N instancí té hry, tak mám trochu obavy, jak by to dopadlo :/

Link to comment
Share on other sites

  • 0

Tak som niečo zbúchal podľa textu, ktorý som napísal vyššie... Nie je to úplne elegantné a neviem, či to poriadne funguje (nemám testy), ale možno ťa to aspoň trochu inšpiruje:
 

Spoiler
function countMoveScore(oldBoard, newBoard) {
    const newLetters = findNewLetters(oldBoard, newBoard);
    const newWords = findNewWords(newBoard, newLetters);
    const wordScores = newWords.map(countWordScore);
    const moveScore = wordScores.reduce((a, b) => a + b, 0);
    // TODO: add 50 points for using all 7 letters?
    return moveScore;
}

function findNewLetters(oldBoard, newBoard) {
    let newLetters = [];
    for (let x = 0; x < newBoard.length; ++x) {
        for (let y = 0; y < newBoard[x].length; ++y) {
            if (newBoard[x][y] != "" && oldBoard[x][y] == "") {
                newLetters.push({letter: newBoard[x][y], x: x, y: y});
            }
        }
    }
    return newLetters;
}

function findNewWords(newBoard, newLetters) {
    let newWords = [];

    let areNewLettersHorizontal = areLettersHorizontal(newLetters);
    if (areNewLettersHorizontal) {
        for (const letter of newLetters) {
            const verticalWord = findVerticalWord(newBoard, letter.x, letter.y);
            if (verticalWord) {
                applyBonuses(verticalWord, newLetters);
                newWords.push(verticalWord);
            }
        }
        const letter = newLetters[0];
        const horizontalWord = findHorizontalWord(newBoard, letter.x, letter.y);
        if (horizontalWord) {
            applyBonuses(horizontalWord, newLetters);
            newWords.push(horizontalWord);
        }
    }
    else
    {
        for (const letter of newLetters) {
            const horizontalWord = findHorizontalWord(newBoard, letter.x, letter.y);
            if (horizontalWord) {
                applyBonuses(horizontalWord, newLetters);
                newWords.push(horizontalWord);
            }
        }
        const letter = newLetters[0];
        const verticalWord = findVerticalWord(newBoard, letter.x, letter.y);
        if (verticalWord) {
            applyBonuses(verticalWord, newLetters);
            newWords.push(verticalWord);
        }
    }

    return newWords;
}

function areLettersHorizontal(letters) {
    return letters.length > 1 && letters[0].x != letters[1].x;
}

function findHorizontalWord(newBoard, letterX, letterY) {
    return findWord(newBoard, letterX, letterY, [1, 0]);
}

function findVerticalWord(newBoard, letterX, letterY) {
    return findWord(newBoard, letterX, letterY, [0, 1]);
}

function findWord(newBoard, letterX, letterY, direction) {
    const [stepX, stepY] = direction;

    let wordHead = [];
    x = letterX - stepX;
    y = letterY - stepY;
    while (x >= 0 && y >= 0 && newBoard[x][y] != "") {
        wordHead.push({letter: newBoard[x][y], x: x, y: y});
        x -= stepX;
        y -= stepY;
    }

    const wordMid = [
        {letter: newBoard[letterX][letterY], x: letterX, y: letterY}
    ];
    
    let wordTail = []
    x = letterX + stepX;
    y = letterY + stepY;
    while (x < newBoard.length && y < newBoard[x].length && newBoard[x][y] != "") {
        wordTail.push({letter: newBoard[x][y], x: x, y: y});
        x += stepX;
        y += stepY;
    }

    const word = wordHead.reverse()
        .concat(wordMid)
        .concat(wordTail);
    
    if (word.length >= 2) {
        return word;
    }

    return null;
}

function applyBonuses(word, newLetters) {
    const bonuses = [
        /*První řádek*/
        { x: 0, y: 0, multiplier: 3, type: 1 },
        { x: 3, y: 0, multiplier: 2, type: 0 },
        { x: 7, y: 0, multiplier: 3, type: 1 },
        { x: 11, y: 0, multiplier: 2, type: 0 },
        { x: 14, y: 0, multiplier: 3, type: 1 },
        /*Druhý řádek*/ 
        { x: 1, y: 1, multiplier: 2, type: 1 },
        { x: 5, y: 1, multiplier: 3, type: 0 },
        { x: 9, y: 1, multiplier: 3, type: 0 },
        { x: 13, y: 1, multiplier: 2, type: 1 },
        /*Třetí řádek*/ 
        { x: 2, y: 2, multiplier: 2, type: 1 },
        { x: 6, y: 2, multiplier: 2, type: 0 },
        { x: 8, y: 2, multiplier: 2, type: 0 },
        { x: 12, y: 2, multiplier: 2, type: 1 },
        /*Čtvrtý řádek*/ 
        { x: 0, y: 3, multiplier: 2, type: 0 },
        { x: 3, y: 3, multiplier: 2, type: 1 },
        { x: 7, y: 3, multiplier: 2, type: 0 },
        { x: 11, y: 3, multiplier: 2, type: 1 },
        { x: 14, y: 3, multiplier: 2, type: 0 },
        /*Pátý řádek*/ 
        { x: 4, y: 4, multiplier: 2, type: 1 },
        { x: 10, y: 4, multiplier: 2, type: 1 },
        /*Šestý řádek*/ 
        { x: 1, y: 5, multiplier: 3, type: 0 },
        { x: 5, y: 5, multiplier: 3, type: 0 },
        { x: 9, y: 5, multiplier: 3, type: 0 },
        { x: 13, y: 5, multiplier: 3, type: 0 },
        /*Sedmý řádek*/ 
        { x: 2, y: 6, multiplier: 2, type: 0 },
        { x: 6, y: 6, multiplier: 2, type: 0 },
        { x: 8, y: 6, multiplier: 2, type: 0 },
        { x: 12, y: 6, multiplier: 2, type: 0 },
        /*Osmý řádek*/ 
        { x: 0, y: 7, multiplier: 3, type: 1 },
        { x: 3, y: 7, multiplier: 2, type: 0 },
        { x: 11, y: 7, multiplier: 2, type: 0 },
        { x: 14, y: 7, multiplier: 3, type: 1 },
        /*Devátý řádek*/
        { x: 2, y: 8, multiplier: 2, type: 0 },
        { x: 6, y: 8, multiplier: 2, type: 0 },
        { x: 8, y: 8, multiplier: 2, type: 0 },
        { x: 12, y: 8, multiplier: 2, type: 0 },
        /*Desátý řádek*/ 
        { x: 1, y: 9, multiplier: 3, type: 0 },
        { x: 5, y: 9, multiplier: 3, type: 0 },
        { x: 9, y: 9, multiplier: 3, type: 0 },
        { x: 13, y: 9, multiplier: 3, type: 0 },
        /*Jedenáctý řádek*/ 
        { x: 4, y: 10, multiplier: 2, type: 1 },
        { x: 10, y: 10, multiplier: 2, type: 1 },
        /*Dvanáctý řádek*/ 
        { x: 0, y: 11, multiplier: 2, type: 0 },
        { x: 3, y: 11, multiplier: 2, type: 1 },
        { x: 7, y: 11, multiplier: 2, type: 0 },
        { x: 11, y: 11, multiplier: 2, type: 1 },
        { x: 14, y: 11, multiplier: 2, type: 0 },
        /*Třináctý řádek*/ 
        { x: 2, y: 12, multiplier: 2, type: 1 },
        { x: 6, y: 12, multiplier: 2, type: 0 },
        { x: 8, y: 12, multiplier: 2, type: 0 },
        { x: 12, y: 12, multiplier: 2, type: 1 },
        /*Čtrnáctý řádek*/ 
        { x: 1, y: 13, multiplier: 2, type: 1 },
        { x: 5, y: 13, multiplier: 3, type: 0 },
        { x: 9, y: 13, multiplier: 3, type: 0 },
        { x: 13, y: 13, multiplier: 2, type: 1 },
        /*Patnáctý řádek*/ 
        { x: 0, y: 14, multiplier: 3, type: 1 },
        { x: 3, y: 14, multiplier: 2, type: 0 },
        { x: 7, y: 14, multiplier: 3, type: 1 },
        { x: 11, y: 14, multiplier: 2, type: 0 },
        { x: 14, y: 14, multiplier: 3, type: 1 },
    ];

    for (const letter of word) {
        if (newLetters.find(newLetter => letter.x == newLetter.x && letter.y == newLetter.y)) {
            const bonus = bonuses.find(element => element.x == letter.x && element.y == letter.y);
            if (bonus) {
                letter.bonus = { multiplier: bonus.multiplier, type: bonus.type };
            }
        }
    }
}

function countWordScore(word) {
    let wordScoreMultiplier = 1;
    let scoreSum = 0;
    for (const letter of word) {
        const letterScore = getLetterValue(letter.letter);
        const bonus = letter.bonus;
        if (bonus) {
            if (bonus.type == 0) {
                letterScore *= bonus.multiplier;
            } else if (bonus.type == 1) {
                wordScoreMultiplier *= bonus.multiplier;
            }
        }
        scoreSum += letterScore;
    }
    scoreSum *= wordScoreMultiplier;
    return scoreSum;
}

function getLetterValue(letter) {
    const letterValues = {
        'a': 1,
        'e': 1,
        'i': 1,
        'l': 1,
        'n': 1,
        'o': 1,
        'r': 1,
        's': 1,
        't': 1,
        'u': 1,
        'd': 2,
        'g': 2,
        'b': 3,
        'c': 3,
        'm': 3,
        'p': 3,
        'f': 4,
        'h': 4,
        'v': 4,
        'w': 4,
        'y': 4,
        'k': 5,
        'j': 8,
        'x': 8,
        'q': 10,
        'z': 10
    };

    return letterValues[letter.toLowerCase()] ?? 0;
}

 

 

Link to comment
Share on other sites

  • 0

Díky za to :) Je to tedy docela nářez, nicméně to hodím do programu a zkusím to prohnat nějakými testy. Až budu mít nějaké výsledky, tak dám určitě vědět

Link to comment
Share on other sites

  • 0

Tak zatím to vypadá všechno OK, ale ještě jsem to nepouštěl na nějaké extra složité srandy. Jediný problém, na který jsem zatím v tvém kódu musel upravovat po funkční stránce bylo to, že to padalo v případě, že hráč nevloží na desku žádné nové slovo (např. když pouze mění písmena).

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...