[Community Puzzle] CGFunge interpreter

https://www.codingame.com/training/medium/cgfunge-interpreter

Send your feedback or ask for help here!

This one (https://www.codingame.com/training/medium/cgfunge-interpreter) I had given feedback for when it was in the queue, but hadnā€™t actually implemented it at the time, so hereā€™s the remainder now:

  • specification bug: the flow control instructions say ā€œif the top of the stack isā€. The validation cases behave as ā€œif the top of the stack is (ā€¦) and then pop itā€.

  • IDE infelicity: itā€™s a real pain that the input program canā€™t be an actual rectangle because of whitespace trimming.

  • and thatā€™s it. Iā€™ve tried to find other actual specification bugs, and though there is some minor undercoverageā€¦ the test cases are actually robust against them. Just wow!

Accept my deepest and most sincere congratulations, @player_one! That problem was exceptionally well set, and I donā€™t say that often! Please become an inspiration for the serial crap problem setters.

4 Likes

My humble thanks. I agree I should have specified that a value is popped for the flow control instructions. Ooops. Oh well. Iā€™m glad you enjoyed the puzzle.

  • danBhentschel

It seems not to be working correctly with Python3, or is it me ? The test cases involving a new line character wont validate, this is the output I get:

Standard Output Stream:

99 bottles of beer on the wall
99 bottles of beer
take one down, pass it around

Failure
Found: Nothing
Expected: ā€œ9ā€

I had the same problem @Shugah, and it seam that in the 5th validator, an ā€œEā€ (end of program) should be passed with a ā€œSā€, I just implemented it in my loop and now it works.

Correct. An ā€œSā€ character skips. This is in the Goal description:

ā€˜Sā€™ - Skip the next character and continue with the subsequent character

Test case #3 uses ā€œSā€ as well, but on further inspection, it turns out that it will work just fine without implementing ā€œSā€ behavior because the character that it skips is a ā€œGā€, which has no functionality. So as long as your program ignores unrecognized characters, test 3 works fine without the ā€œSā€.

In hindsight, I should have made test 3 require that ā€œSā€ behavior works properly. I really wanted to introduce that concept at that point. :blush:

  • danBhentschel
1 Like

Here is an extra test case to help pass validator #3:
Input:

3
vell, vell, vell

>0I Empty lines are special, you know.

Expected output:
0

1 Like

Thanks finn_troll! I donā€™t like this behavior as this is nowhere specified! Making empty cells equivalent to spaces is just arbitraryā€¦

Actually it is: :wink:

Execution always starts on the first character of the first line and proceeds to the right. Spaces are ignored. So, for example, the following are equivalentā€¦

The fact that unknown characters other than spaces are to be ignored is not specified, though, as far as I can tell.

Edit: I understood this explanation as meaning that space characters are ignored, including " ", ā€œ\tā€ and ā€œ\nā€. But I donā€™t think there is a test where the ā€œarrowā€ has you move to a point where there is no character. If you modify finn_trollā€™s example to include a bunch of whitespace on the empty line, it should work fine.

I suspect that itā€™s exactly those whitespaces that are missing (or automatically stripped) for the third validator - at least that was the only change I had to implement to pass that test. I donā€™t see any problem with that because - as far as I remember - the specification does not promise that all lines will have an equal length.

Ok my bad, maybe this appears in the validator too. My algorithm passes your test, but I have no idea why trying to access chars in the empty string doesnā€™t cause a segfault. :smiley:

Just checked. You are correct. The third validator does go ā€œoff the endā€ of a string. :frowning: If I had noticed this, I would have done AT LEAST one of the following:

  • Fix the validator so it didnā€™t do that
  • Introduce this behavior in a test, rather than a validator
  • Make it more explicit in the problem statement that this could happen

Darn. I put so much effort into this puzzle too! :sweat_smile:

  • danBhentschel

My guess is that with certain C compilers, indexing row 1 element 0 gives you row 2 element 0 in case of an empty row 1.

Itā€™s still one of my favourite community puzzle so far. It must have been quite challenging to program the test cases for this imaginary machineā€¦

1 Like

Itā€™s C++, and it is a vector of strings. Plus it does process an empty (or unprintable) char, it doesnā€™t skip directly to the >. And it works with this as well (trying to access element 1 of an empty string):

>vell, vell, vell

>>0I Empty lines are special, you know.

I was looking at my code, trying to figure out why this didnā€™t bite me, and then I realized that itā€™s technically not a problem. There is an ā€˜Sā€™ character before the short line, so your code is supposed to jump over that point. If you are trying to dereference that line, then you havenā€™t implemented the ā€˜Sā€™ behavior correctly.

Even so, I would have done things differently if I had noticed.

  • danBhentschel

CGFrunge ā€” Framed CGFunge.

I think itā€™s not just the empty lines. For instance what I first did was fill in the empty lines with a bunch of spaces but that didnā€™t pass Validator 3. What I did afterwards was to equalize the lines to have the same length as the longest line [I added ā€™ ā€™ to any line shorter than the longest] and that did it. Now, maybe I didnā€™t added enough spaces with the original solution but the latter one fixes inputs with different lengths of lines as well.

>>>>>>>>>>>>>>>>>v
E short line
^ short line no 2
^<<<<<<<<<<<<<<<<<<<<<

So, as I mentioned above, you donā€™t really NEED to fill in empty or short lines to solve the problem. The fact that the short line is skipped with an ā€˜Sā€™ character means that this shouldnā€™t (for some, though not all implementations) be necessary. A better test case that illustrates this would be:

4
                v Go down!
Skip next line  S
Short line
Finish here --> > "!yaY" CCCCE

Answer:

Yay!

My own solution (and many others) pass this test just fine without adding any spaces to the short line. Just an FYI.

  • danBhentschel
1 Like

My two quick fixes to this were

  1. Return a space if the program tries to execute passed a trimmed line (i.e. - detect a bad dereference and just return white space)
  2. Collect all of the printable output into one String throughout the program, and print it at the end.

Loved the puzzle!