[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!