Question

Для CodinGame Я создаю судью для карточной игры под названием Война. Правила описаны здесь ). TL; DR: люди с самой большой вытянутой картой добавляют обе карты в конец своей стопки карт. Я построил связанный список в Паскале, чтобы держать стеки карт. Но указатели на паскаль ведут себя не так, как я ожидаю:

Например, я даю программе следующий ввод (слегка измененный):

9
8C
KD
AH
QH
3D
KD
AH
QH
6D
9
8D
2D
3H
4D
4S
2D
3H
4D
7H

Пример вывода:

nrCards: 5
Player1: 13 14 12 6
Player2: 2 3 4 7
Player1: 14 12 6
Player2: 3 4 7
Player1: 12 6
Player2: 4 7
Player1: 6
Player2: 7
Player1:
Player2: 6 7
2 5

Т.е. указатель nextNode последнего элемента в основном не обновляется должным образом ...

Код:

program Answer;
{$H+}
uses sysutils, math, strutils;

type
    TNode = record
        val : Int32;
        nextNode : ^TNode;
    end;
    TNodePtr = ^TNode;
    TNodePtrPtr = ^TNodePtr;
var
    size1 : Int32;
    size2 : Int32;
    cards : Array of TNode;
    player1first : TNodePtr = nil;
    player1last : TNodePtr = nil;
    player2first : TNodePtr = nil;
    player2last : TNodePtr = nil;
    winnerLast : TNodePtrPtr = nil;
    i : Int32;
    Line: String;
    turns : Int32 = 0;
    nrCards : Int32 = 1;
    cardIt : TNodePtr = nil;

    function ParseIn(i : Int32) : String;
    begin
        ParseIn := ExtractWord(i, Line, [' ']);
    end;

    function War(pl1it, pl2it : TNodePtr) : Int32;
    var
        nrCards : Int32 = 5;
        i :Int32; // not reuse?
    begin
        for i := 0 to 3 do begin
            pl1it := pl1it^.nextNode;
            pl2it := pl2it^.nextNode;
            if (pl1it = nil) or (pl2it = nil) then
                exit(0);
        end;
        while (pl1it^.val = pl2it^.val) do begin
            nrCards := nrCards + 4;
            for i := 0 to 3 do begin
                pl1it := pl1it^.nextNode;
                pl2it := pl2it^.nextNode;
                if (pl1it = nil) or (pl2it = nil) then
                    exit(0);
            end;
        end;
        if pl1it^.val > pl2it^.val then
            // player 1 wins
            War := nrCards
        else
            // player 2 wins
            War := -nrCards;
    end;
begin
    readln(Line);
    size1 := StrToInt(ParseIn(1));
    Setlength(cards, size1);
    for i := 0 to size1-1 do begin
        readln(Line);
        //writeln(StdErr, Line);
        case Line[1] of
            '1' : cards[i].val := 10;
            'J' : cards[i].val := 11;
            'Q' : cards[i].val := 12;
            'K' : cards[i].val := 13;
            'A' : cards[i].val := 14;
            else cards[i].val := Integer(Line[1])-48;
        end;
        if i = size1-1 then
            cards[i].nextNode := nil
        else
            cards[i].nextNode := @cards[i+1];
    end;

    readln(Line);
    size2 := StrToInt(ParseIn(1));
    Setlength(cards, size1+size2);
    for i := size1 to size1+size2-1 do begin
        readln(Line);
        //writeln(StdErr, Line);
        case Line[1] of
            '1' : cards[i].val := 10;
            'J' : cards[i].val := 11;
            'Q' : cards[i].val := 12;
            'K' : cards[i].val := 13;
            'A' : cards[i].val := 14;
            else cards[i].val := Integer(Line[1])-48;
        end;
        if i = size1+size2-1 then
            cards[i].nextNode := nil
        else
            cards[i].nextNode := @cards[i+1];
    end;

    player1first := @cards[0];
    player1last := @cards[size1-1];
    player2first := @cards[size1];
    player2last := @cards[size1+size2-1];

    // now for the game
    while (player1first <> nil) and (player2first <> nil) do begin
        if player1first^.val <> player2first^.val then begin
            if player1first^.val > player2first^.val then begin
                // player 1 wins
                writeln(StdErr, 'Player1 wins');
                winnerLast := @player1last;
            end else begin
                // player 2 wins
                writeln(StdErr, 'Player2 wins');
                winnerLast := @player2last;
            end;
            winnerLast^^.nextNode := player1first;
            winnerLast^ := player1first;
            player1first := player1first^.nextNode;
            winnerLast^^.nextNode := player2first;
            winnerLast^ := player2first;
            player2first := player2first^.nextNode;
            winnerLast^^.nextNode := nil;
        end else begin
            // war
            nrCards := War(player1first, player2first);
            writeln(StdErr, 'nrCards: ', nrCards);
            if nrCards = 0 then
                break;
            if nrCards > 0 then begin
                writeln(StdErr, 'Player1 wins');
                winnerLast := @player1last;
            end else begin
                writeln(StdErr, 'Player2 wins');
                winnerLast := @player2last;
                nrCards := -nrCards;
            end;
            for i := 0 to nrCards-1 do begin
                winnerLast^^.nextNode := player1first;
                winnerLast^ := player1first;
                player1first := player1first^.nextNode;
            end;
            for i := 0 to nrCards-1 do begin
                winnerLast^^.nextNode := player2first;
                winnerLast^ := player2first;
                player2first := player2first^.nextNode;
            end;
            winnerLast^^.nextNode := nil;
        end;
        turns := turns + 1;
        write(StdErr, 'Player1: ');
        cardIt := player1first;
        while cardIt <> nil do begin
            write(StdErr, cardIt^.val, ' ');
            cardIt := cardIt^.nextNode;
        end;
        writeln(StdErr, ' ');
        write(StdErr, 'Player2: ');
        cardIt := player2first;
        while cardIt <> nil do begin
            write(StdErr, cardIt^.val, ' ');
            cardIt := cardIt^.nextNode;
        end;
        writeln(StdErr, ' ');
    end;

    // end game
    if nrCards = 0 then
        // equal
        writeln('PAT')
    else if player2first = nil then
        // player 2 won
        writeln('1 ',turns)
    else 
        // player 2 won
        writeln('2 ',turns);

    flush(StdErr); flush(output); // DO NOT REMOVE
end.

У меня есть опыт работы в C / C ++ / C #, который может объяснить мой стиль кодирования. Эта же программа на С работает корректно. ИМХО я буквально перевел это ...

код C:

#define _CRT_SECURE_NO_WARNINGS

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct TNode {
    int val;
    struct TNode* nextNode;
};

int War(struct TNode* pl1It, struct TNode* pl2It) {
    int nrCards = 5;
    for (int i = 0; i < 4; ++i) {
        pl1It = pl1It->nextNode;
        pl2It = pl2It->nextNode;
        if (pl1It == NULL || pl2It == NULL) {
            return 0;
        }
    }
    while (pl1It->val == pl2It->val) {
        nrCards += 4;
        for (int i = 0; i < 4; ++i) {
            pl1It = pl1It->nextNode;
            pl2It = pl2It->nextNode;
            if (pl1It == NULL || pl2It == NULL) {
                return 0;
            }
        }
    }
    if (pl1It->val > pl2It->val) {
        // player 1 wins
        return nrCards;
    } else {
        // player 2 wins
        return -nrCards;
    }
}

int main()
{
    struct TNode cards[52];

    int size1;
    scanf("%d", &size1);
    for (int i = 0; i < size1; ++i) {
        char Line[4];
        scanf("%s", Line);
             if (Line[0] == '1') cards[i].val = 10;
        else if (Line[0] == 'J') cards[i].val = 11;
        else if (Line[0] == 'Q') cards[i].val = 12;
        else if (Line[0] == 'K') cards[i].val = 13;
        else if (Line[0] == 'A') cards[i].val = 14;
        else cards[i].val = (int)Line[0] - 48;

        if (i == size1 - 1) cards[i].nextNode = NULL;
        else cards[i].nextNode = &cards[i + 1];
    }

    int size2;
    scanf("%d", &size2);
    for (int i = size1; i < size1 + size2; ++i) {
        char Line[4];
        scanf("%s", Line);
             if (Line[0] == '1') cards[i].val = 10;
        else if (Line[0] == 'J') cards[i].val = 11;
        else if (Line[0] == 'Q') cards[i].val = 12;
        else if (Line[0] == 'K') cards[i].val = 13;
        else if (Line[0] == 'A') cards[i].val = 14;
        else cards[i].val = (int)Line[0] - 48;

        if (i == size1 + size2 - 1) cards[i].nextNode = NULL;
        else cards[i].nextNode = &cards[i + 1];
    }

    struct TNode* player1first = &cards[0];
    struct TNode* player1last = &cards[size1 - 1];
    struct TNode* player2first = &cards[size1];
    struct TNode* player2last = &cards[size1 + size2 - 1];

    int nrOfCards = 1; // has to do with check
    int turns = 0;
    // now for the game
    while (player1first != NULL && player2first != NULL) {
        if (player1first->val != player2first->val) {
            struct TNode** winnerLast = NULL;
            if (player1first->val > player2first->val) {
                // player 1 wins
                fprintf(stderr, "Player 1 wins.\n");
                winnerLast = &player1last;
            } else {
                // player 2 wins
                fprintf(stderr, "Player 2 wins.\n");
                winnerLast = &player2last;
            }
            (*winnerLast)->nextNode = player1first;
            (*winnerLast) = player1first;
            player1first = player1first->nextNode;
            (*winnerLast)->nextNode = player2first;
            (*winnerLast) = player2first;
            player2first = player2first->nextNode;
            (*winnerLast)->nextNode = NULL;
        } else {

            // war
            fprintf(stderr, "War: ");
            nrOfCards = War(player1first, player2first);
            if (nrOfCards == 0) break;
            struct TNode** winnerLast;
            if (nrOfCards > 0) {
                // Player 1 wins
                fprintf(stderr, "Player 1 wins.\n");
                winnerLast = &player1last;
            } else {
                // Player 2 wins
                fprintf(stderr, "Player 2 wins.\n");
                nrOfCards = -nrOfCards;
                winnerLast = &player2last;
            }
            for (int i = 0; i < nrOfCards; ++i) {
                (*winnerLast)->nextNode = player1first;
                (*winnerLast) = player1first;
                player1first = player1first->nextNode;
            }
            for (int i = 0; i < nrOfCards; ++i) {
                (*winnerLast)->nextNode = player2first;
                (*winnerLast) = player2first;
                player2first = player2first->nextNode;
            }
            (*winnerLast)->nextNode = NULL;
        }
        turns = turns + 1;
    }

    // end game
    if (nrOfCards == 0) {
        // equal
        printf("PAT\n");
    } else if (player2first == NULL) {
        // player 2 won
        printf("1 %d\n", turns);
    } else {
        // player 2 won
        printf("2 %d\n", turns);
    }
    // Write an action using printf(). DON'T FORGET THE TRAILING \n
    // To debug: fprintf(stderr, "Debug messages...\n");

    return 0;
}

Может кто-нибудь объяснить, почему указатели Паскаля ведут себя так по-разному, или что я делаю неправильно?

JHBonarius · Answer 1 · 01 сентября 2018

Я обнаружил проблему, которую пока не до конца понимаю.

Проблема вызвана отключением динамического массива cards. Это также большая разница между кодом C и кодом паскаля. Я делал

readln(Line);
size1 := StrToInt(ParseIn(1));
Setlength(cards, size1);
for i := 0 to size1-1 do begin
    readln(Line);
    [...]
end;

readln(Line);
size2 := StrToInt(ParseIn(1));
Setlength(cards, size1+size2);
for i := size1 to size1+size2-1 do begin

Эта вторая Setlength, кажется, сделала недействительным последний элемент моего исходного массива. Кажется, player1last^.nextNode и cards[size-1].nextNode больше не были подключены. Я не совсем понимаю, что произошло под водой ... Я могу только догадываться, что Setlength перераспределяет память и копирует содержимое , тем самым аннулируя все существующие указатели ! Если это так, это не было должным образом объяснено в найденных мной уроках.

К счастью, я мог бы это исправить, поскольку там было максимум 52 карты, поэтому, выбрав массив фиксированной длины, я мог бы это исправить.

cards : Array[0..51] of TNode;

EDIT:

ОК. Я нашел источник, дающий мне ответ Динамический массив - Free Pascal wiki

Хотя запись в элементы динамических массивов не создает новый экземпляр массива (без копирования при записи, поскольку он существует для Ansistrings), использование SetLength для таких массивов создает копию! Поэтому, если две переменные динамического массива указывают на один и тот же массив (одна была назначена другой), они не делают этого после использования SetLength для одной (или обеих) из них. После вызова SetLength () две переменные являются отдельными массивами, элементы которых не зависят друг от друга.

Указатели на Паскаль ведут себя не так, как ожидалось

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

EDIT:

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Указатели на Паскаль ведут себя не так, как ожидалось

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

EDIT:

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы