Every year I participate in a number of online code challenges like Facebook Hacker Cup, Google Code Jam and Advent of Code. Although I never make it really far I quite enjoy the puzzles which I usually make in C#. Definitely not the fastest language out there, but LINQ makes life easy 🙂 . Since I spent every week a considerable amount of time PLC programming, I found myself wondering if I could solve A Code Jam challenge with Structured Text. Spoiler alert, yes you can, but it doesn’t come very easy.. So I decided to write a small post about it, pointing out the challenges I faced. I used TwinCAT V3.1.4022 turning my Microsoft Surface PRO laptop in a Soft-PLC.
Ampel Syrup
I chose the challenge 1C 2017 Ampel Syrup. I solved it back in 2017 with C# and I still had the source code. In this challenge you get an unordered list of N pancakes, with an radius and an Height. Your task is to maximize the exposed area of a stack of K pancakes. The stack should be bottom to top in non-increasing order of radius. The full analysis of this challenge can be found at the Google Code Jam website. In this post I will focus on an implementation in Structured Text.
The basic of my PLC program is an state machine which runs through the following steps:
- Open challenge input file
- Open challenge output file
- Read number of challenges
- Read and parse the challenge header (Available pancakes and requested stack size)
- Parse all available pancakes and safe the data in an array
- Solve challenge
- Write challenge solution to the output file
- If number of solved challenges is lower than available challenges go to 4
- Close input file
- Close output file
File reading and writing
A great deal of the state machine is about file reading and writing. For this I used the ‘tc2_System library’. More specific, I used the function blocks:
- FB_FileOpen – Create a handle to a file, and sets the data pointer to the begin of the file.
- FB_FileGets – Read a file line by a line
- FB_FilePuts – Write a line to the a file
- FB_FileClose – Close the files and destroy the handles.
First step is to create the file handles to the input and output files. This is an example from opening the input file.
fbStringReader:FB_FileGets; fbFileOpener:FB_FileOpen; fbFileCloser:FB_FileClose; fbFileWriter:FB_FilePuts;
1: fbFileOpener.sPathName :='C:\A-large-practice.in';
fbFileOpener.nMode := FOPEN_MODEREAD;
fbFileOpener.ePath := PATH_GENERIC;
fbFileOpener(bExecute:=TRUE);
State:=State+1;
2: fbFileOpener(bExecute:=FALSE);
IF NOT fbFileOpener.bBusy THEN
State:=State+1;
fbStringReader.hFile := fbFileOpener.hFile;
fbFileOpener(bExecute:=TRUE);
//Cleared some lines here not needed for this example of opening a file
END_IF
Notice that the file handle is assigned to the fbStringReader after the file is opened. Opening a file for output works the same way. We only change the path to our desired output file and set the mode to writing:
fbFileOpener.sPathName :='C:\Solution.out'; fbFileOpener.nMode := FOPEN_MODEWRITE;
With the file handle assigned to the fbStringReader we can now read the first string which is the number of challenges ‘T’. We directly convert this to an integer. After reading a string the data pointer is set to the next line, Which means that if you set bExecute to true again it will give you the next line of the file, or if you are at the end of the file it sets the output boolean ‘bEOF’.
4: fbStringReader.tTimeout:= T#1S;
fbStringReader(bExecute := TRUE );
State:=State+1;
5: fbStringReader(bExecute := FALSE);
IF NOT fbStringReader.bBusy THEN
T := STRING_TO_INT(fbStringReader.sLine);
State:=State+1;
//Cleared some lines here not needed for this example of reading a line.
END_IF
Writing a output to a file works more or less the same way as reading. Make sure you have assigned the file handle from the FbFileOpener function block to fbFileWriter function block. Compose a string, assign it to the fbFileWriter which writes it to the specified output file. Notice at line 3 that I manually have to add an new line feed the the end of our string.
8: fbFileWriter.sLine := CONCAT(CONCAT('Case #',INT_TO_STRING(ChallengeCounter+1)),': ');
fbFileWriter.sLine := CONCAT(fbFileWriter.sLine,LREAL_TO_STRING(SolveChallenge(N:=N,K:=K,Pancakes:=Pancakes)));
fbFileWriter.sLine := CONCAT(fbFileWriter.sLine,'$N');
fbFileWriter.tTimeout :=T#1S;
fbFileWriter(bExecute:=FALSE);
fbFileWriter(bExecute:=TRUE);
State:=State+1;
9: fbFileWriter(bExecute:=FALSE);
IF NOT fbFileWriter.bBusy THEN
//Cleared some lines here not needed for this example of writing a line.
END_IF
Don’t forget to close your file handles after you are done reading and writing!
10: fbFileCloser.hFile := <span class="pl-s">fbFileWriter</span>.hFile;
fbFileCloser.tTimeout :=T#1S;
fbFileCloser(bExecute:=FALSE);
fbFileCloser(bExecute:=TRUE);
State:=State+1;
11: fbFileCloser(bExecute:=FALSE);
IF NOT fbFileCloser.bBusy THEN
State:=State+1;
fbFileCloser.hFile := fbStringReader.hFile;
fbFileCloser(bExecute:=TRUE);
END_IF
12: fbFileCloser(bExecute:=FALSE);
IF NOT fbFileCloser.bBusy THEN
State:=0;
END_IF
Parsing the input
Now we have covered the file reading and writing lets focus on how to parse and prepare the input. Each test case comes with a test case header telling us how many pancakes (N) there are available and how many there are requested on the stack (K). This header comes in the format ‘N K’. Even in the large data set they won’t be larger than 1000 so integer variables will do just fine. To convert the string to two integers we can use the function STRING_TO_INT (). But before we do this we have split the string first. We can do this using the FIND function and search for the index of the splitting SPACE. By using the LEFT function we can grab the left part of the found index of the space.
We could use the RIGHT function to take the part on the right of the index. However, the last two characters of a line are not numbers of K any more but are: ‘$N’ indicating a new line. I noticed that including these character in our STRING_TO_INT function gives in some cases the wrong numbers! So I decided to use the MID function where we can specify the number of characters we want to grab from a starting index. Using the LEN function to determine the total length of the string and subtracting two from that we have all the needed information to grab and convert the right number. Combining al this information results in the following code:
STRING_TO_INT SplitPosition := FIND(STR1:= fbStingReader.sLine, str2:= ' '); N:=STRING_TO_INT(LEFT(STR:=fbStingReader.sLine,SplitPosition)); K:=STRING_TO_INT(MID(STR:=fbStingReader.sLine,LEN:= LEN(fbStingReader.sLine)-2,POS:=SplitPosition));
After we have captured the challenge header N more lines follow containing, in a similar format, the radius (R) and the height (H). I decided to store the individual pancake information in a STRUCT. Together with the directly calculated side area of the pancake and its total exposed area. I made an array of the pancake structure to store all pancakes in. For the array size I created a global constant variable to make it easy for me to experiment a little bit with the array dimensions.
TYPE Pancake : STRUCT Height:DINT; Radius:DINT; SideArea:LREAL; TotalArea:LREAL; END_STRUCT END_TYPE
VAR_GLOBAL CONSTANT MaxArraySize:INT:=999; END_VAR
Pancakes : ARRAY[0..GVL.MaxArraySize] OF Pancake;
SplitPosition := FIND(STR1:= fbStingReader.sLine, str2:= ' '); Pancakes[PancakeCounter].Radius:=STRING_TO_DINT(LEFT(STR:=fbStingReader.sLine,SplitPosition)); Pancakes[PancakeCounter].Height:=STRING_TO_DINT(MID(STR:=fbStingReader.sLine,LEN:= LEN(fbStingReader.sLine)-2,POS:=SplitPosition)); Pancakes[PancakeCounter].SideArea:= 2*PI*Pancakes[PancakeCounter].Radius *Pancakes[PancakeCounter].Height; Pancakes[PancakeCounter].TotalArea :=PI *Pancakes[PancakeCounter].Radius *Pancakes[PancakeCounter].Radius +Pancakes[PancakeCounter].SideArea;
Sorting the data
To solve this challenge we have to perform some sorting on the pancake array. As far as I’m aware the default TwinCAT libraries don’t have any sorting functions included, so I decided to write a Structured Text version of the bottom up merge sort algorithm. Where many sorting algorithms are recursive, I selected an iterative algorithm. Yes, TwinCAT does support some forms of recursion but I would always try to avoid it. For more info on why you shouldn’t use it have look the the PLCopen Coding Guidelines. I extended the algorithm with a toggle bit to select sorting by radius or sorting by the side area.
FUNCTION PanCakeBottomUpMergeSort
VAR_INPUT
N:INT;//Number of elements
SortBySideArea:BOOL; //True to sort the array by the side area of the pancakes. Other wise sort by radius
END_VAR
VAR_IN_OUT
ArrayToSort: ARRAY[0..GVL.MaxArraySize] OF Pancake;
WorkingArray: ARRAY[0..GVL.MaxArraySize] OF Pancake;
END_VAR
VAR
Width:INT;
i:INT;
END_VAR
Width:=1;
WHILE (Width ‹ N) DO
i:=0;
WHILE (i ‹ N)DO
BottomUpMerge(i, MIN (i+Width,N),MIN(i+2*width, N),SortBySideArea,ArrayToSort,WorkingArray);
i:=i+2*Width;
END_WHILE
CopyArray(N:=N,Source:= WorkingArray,Target:=ArrayToSort);
Width:= Width *2;
END_WHILE
FUNCTION BottomUpMerge
VAR_INPUT
Left:INT;
Right:INT;
End:INT;
SortBySideArea:BOOL;//True to sort the array by the side area of the pancakes. Other wise sort by radius
END_VAR
VAR_IN_OUT
ArrayToSort: ARRAY[0..GVL.MaxArraySize] OF Pancake;
WorkingArray: ARRAY[0..GVL.MaxArraySize] OF Pancake;
END_VAR
VAR
i:INT;
j:INT;
k:INT;
END_VAR
i:=Left;
j:=Right;
FOR k:=left TO End DO
IF (i ‹ Right AND (j › =End OR
((NOT SortBySideArea AND ArrayToSort[i].Radius ‹= ArrayToSort[j].Radius) OR
(SortBySideArea AND ArrayToSort[i].SideArea ‹= ArrayToSort[j].SideArea)))) THEN
WorkingArray[k] := ArrayToSort[i];
i:=i+1;
ELSE
WorkingArray[k] := ArrayToSort[j];
j:=j+1;
END_IF
END_FOR
The implementation of the algorithm is a direct translation of the code on the Wikipedia page. But notice in the declaration part above that I declared the pancake arrays as VAR_IN_OUT. However it’s tempting to declare the ‘ArrayToSort’ as a VAR_INPUT and the ‘WorkingArray’ as private VAR. And this will work, but only for small arrays.
Unlike many other languages in the IEC 61131-3 arrays are handled as value types. Each time you would call the sort function two new arrays would be created and the input values copied to it. By declaring them as VAR_IN_OUT the input arrays are only references to the actual arrays. This gives of course a huge performance boost and saves you all kind of stack overflow messages..
Solving the challenge
With the read and parsed data and the sorting algorithm in place our final task is writing the solving algorithm itself. It’s a pretty straightforward algorithm with the following approach:
- Sort all pancakes by radius small to large
- Loop through the sorted by radius list starting at K-1, and select a bottom pancake.
- Select all pancakes above our selected bottom pancake
- Sort the selected pancakes by their side area
- Add the side area of the largest K-1 pancakes to the total area of bottom pancake
- Store the exposed area if it’s larger then the previously largest value
- Return to 2 and select the next bottom pancake.
Translating this to Structured Text:
FUNCTION SolveChallenge : LREAL
VAR_INPUT
N:INT; //Number of available pancakes
K:INT; //Ordered pancakes
END_VAR
VAR_IN_OUT
Pancakes : ARRAY[0..GVL.MaxArraySize] OF Pancake;
END_VAR
VAR
i:INT;
j:INT;
PancakesBYSide : ARRAY[0..GVL.MaxArraySize] OF Pancake;
WorkingArray : ARRAY[0..GVL.MaxArraySize] OF Pancake;
StackArea:LREAL;
END_VAR
PanCakeBottomUpMergeSort(N:=N, SortBySideArea:=FALSE,ArrayToSort:=Pancakes, WorkingArray:=WorkingArray);
FOR i:=K-1 TO N-1 DO
PancakesBYSide := Pancakes;
StackArea :=Pancakes[i].TotalArea;
PanCakeBottomUpMergeSort(N:=i, SortBySideArea:=TRUE,ArrayToSort:=PancakesBYSide , WorkingArray:=WorkingArray);
FOR j:= 0 TO K-2 DO
StackArea:= StackArea + PancakesBYSide[i-1 -j].SideArea;
END_FOR
SolveChallenge := MAX(SolveChallenge,StackArea);
END_FOR
And that’s it! After a lot of preparation code this is pretty straight forward 🙂 . I have to working arrays here declared as VAR as explained earlier this affects your performance. I could optimize this further by making them references as well. However, for this challenge it was not needed as the solving algorithm is only called T times (100).
Conclusion solving a Code Jam challenge with Structured Text
From the start this was more for fun than anything else. But as expected you actually can solve A Code Jam challenge with Structured Text on your PLC with Structured Text. Does it make very much sense? No. You have to write a lot of overhead code for reading and writing and there is not a big toolkit available for all kinds of data manipulation like sorting. You could write it yourself but Structured Text was never intended for this purpose. It gave however some interesting insights especially regarding the handling of arrays.
The full source code which solves the challenge can be found on my GitHub. For any further questions or remarks feel free to contact me.
