For CodinGame I'm building a referee for a card game called War. Rules described here). TL;DR: the persons with the highest drawn card adds both cards to the bottom of his/her card stack. I've build a linked-list in Pascal to hold the card stacks. But pascal pointers are not behaving as I expect:
For example, I give the program the following input (slightly modified):
9
8C
KD
AH
QH
3D
KD
AH
QH
6D
9
8D
2D
3H
4D
4S
2D
3H
4D
7H
The example output is:
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
I.e., the nextNode pointer of the last element is mostly not updated properly...
Code:
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.
I have a background in C/C++/C#, which could explain my coding style. The same program in C works correctly. IMHO I've literally translated it...
C code:
#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;
}
Can somebody explain why pascal pointers are behaving so differently, or what I am doing wrong?
I found the problem, which I do not fully understand yet.
The problem is caused by de use of dynamic array cards. That's also the big difference between the C code and the pascal code. I'm was doing
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
That second Setlength seems to have invalidated the last element of my initial array.. It seems player1last^.nextNode and cards[size-1].nextNode were no longer connected. I don't exactly understand what happened underwater... I can only guess that Setlength reallocates the memory and copies the contents thereby invalidating all existing pointers! If this is the case, this was not properly explained in the tutorials I found.
I could luckily fix this as there are a maximum of 52 cards, so by choosing a fixed-length array I could fix this.
cards : Array[0..51] of TNode;
OK I found a source giving me the answer Dynamic array - Free Pascal wiki
Although writing to elements of dynamic arrays does not create a new instance of the array (no copy-on-write as it exists for Ansistrings) using SetLength on such arrays does create a copy! So if 2 dynamic array variables point to the same array (one has been assigned to the other) they do not do so after using SetLength on one (or both) of them. After the SetLength() call the two variables are distinct arrays whose elements are independent from each other.