My feeling about Detective Pikaptcha

Contests
#3

I really liked this contest. It wasn’t 100% perfect, but still very good. I made 83th, which is a lot better than I expected. I always thought I was a slow coder, but it turns out I my speed is at least mediocre! Still I am glad the next one is a bot-contest again :slight_smile:

Level 1 and 2 were indeed easy, but a good way to get into it. They took me about an hour total. Mostly it was typing and getting used to C# again (I really should have done some puzzles earlier in the day).

I didn’t really understand level 3 from the description either, but it was not that hard to reason out how the sides connect if you look at the test cases (especially the second one). As soon as I stopped trying to fit pieces of paper together, I figured it out pretty quickly.

I don’t really agree about having a “huge ugly heap of ifs” for level 4. It took 4 lines of code to fully define all the connections for a single side including:

  1. which sides are connected to it
  2. what happens to the x and y coordinates for each of the 4 transitions
  3. what happens to the direction pikachu is facing after a transition.

I drew a little picture of the map layout and drew some lines to see how the sides are connected. On my first try I had only 1 bug thankfully (a wrong coordinate transformation).

Instead of using ifs, I could just use the above information stored in a “cubeside” object. I can see why this connection thing can be frustrating if you’re getting nearer the deadline, but then again, you should expect the last level to take more than an hour if the timelimit is 4 hours.

I think that part of being good at these puzzle contests is figuring out how to avoid repeating the same code for every (special) case. I don’t think I succeeded at this completely, but what I described above, worked well enough. I think level 4 was perfect as a last level challenge.

So the only weakness I think this contest had was the description of the level 3 puzzle. It should just say how the map connects horizontally and vertically (with an example) instead of a cryptic explanation about pieces of paper. Something like:

  1. When you go off the map on the top side, you appear in the bottom, with the x-coordinate half a map-width shifted to the right (or left). When you go off the map on the bottom side, you appear at the top with the same x-shift.

  2. If you leave the map on the right, you appear on the left. If you leave the map on the left you appear on the right.

  3. The direction of pikachu does not change upon these horizontal or vertical crossings.

Thanks for the contest! I enjoyed it.

EDIT: err so this is not the official PM thread I guess… will we have one?

2 Likes
#4

I lost a lot of time understanding the Möbius strip as well.
My wall of if conditions for the cube somehow worked in the end, although I had a major bug: when going from one side of the cube to another, I forgot to check if the target side has a wall. You can see that I connected every edge between different sides, while there are walls inside, looking at a debug plot I made during the contest. There is no testcase checking for that.

1 Like
#5

It was a hard one for me. 3 hours to pass the second level, and never understood the 3rd simili-moebius brainfuck.

On step 2, I have an unresolved question :

If you follow the right wall on this situation :
cg1

My opinion is that you should go this way, looking for a wall on the right direction :
cg2

It would be the case if we start from a cell before like that :
cg4

But puzzle 5 on step 2 showed that the right answer was :
cg3

Can somebody explain me that ?

#6

Thank you and kudos for the contest creator @java_coffee_cup!
I really liked this contest, because:

  • I could make it just in time, 12 minutes before deadline, exceeding my own expectations (I was afraid I will be too slow).
  • This 4 hour format during a Saturday is easy to manage (especially if you are in the right time zone…). Doing a 10-day multiplayer contest besides an analog life such as work, family, etc would have been much harder, if want to take it seriously.
  • Code speed did not really count. I could focus on the problem and not on how to squeeze a few millisecs out of the already working PHP code.
  • It did not rely on the usual DFS, BFS, MCTS, etc. etc. “stock” algorithms. These might be also fun to implement but with such short timeframe anybody without experience would be at huge disadvantage versus coders who did it dozens of times.
  • How the 4 puzzles built on each other was just right! Different enough to keep me occupied, but familiar enough to be able to build on the thought process and the code at the previous puzzle.
  • And I liked that being not familiar with the Pokémon universe at all did not cause me any disadvantage…

I realized how time pressure leads to really ugly code. However this morning I refactored my solution so same code solves all puzzles: 3 classes for 2D, Moebius and Cube maps using inheritance and differing only on the “next position” method. Also moving the hell of if statements into associative array constants, describing the map topology. Now looking forward to being able to try out this code by submitting to new training puzzle version of the contest which will hopefully appear.

A note on disambiguity: I see some people found Möbius puzzle description misleading. For me what helped was to follow the instructions verbatim: taking a paper, puting half of the X,Y coordinates on it, etc. so making the real paper loop. Only after this I realizes that I need to add “(width / 2) mod width” to the X coordinate. In my opinion if the description would have included exact “nextX, nextY” formula, it would have been much less of a challenge.

2 Likes
#8

I’m not sure, but did you check the wall direction? It gives you R or L in the input. Some testcases will have R and some will have L.

#9

Being the first contest, it was an enjoyable experience.

In general, the questions were asked really well. Although, agreeing with the mobilus remark. I’ve Googled what it was, which made me really confused given the descriptions, to finally reverse engineer the behavior based on the solutions.

One thing that wasn’t mentioned, is that the test cases didn’t cover all the basics. I might be the only one who doesn’t use the predefined input, though, I did incorrectly read ‘v’, as I’ve compared it with ‘V’ being fast. This only started to fail in the hidden cases of round 2, loosing me about 30m. As I read this might be published as regular puzzles, it could be something to expose.

At the beginning, I was worried to do this in C++, as the 5 minute challenges are unbalanced for the languages, thanks to the standard libraries of those languages.
After being in for an hour, I was really happy to see that the playground was more even. Not an easy thing to do.
Thanks for a fun evening!

1 Like
#10

Thanks many feedback. I fully agree the mobius puzzle should have been better described. There was a hand-drawing diagram I provided in the development stage but it was finally not used. So post it here if it helps someone who are still puzzled by the topology.

stript
stript778×653 44 KB

The diagram described another way to modalize the strip in paper, different from the current statement but the effect is the same.

In fact, the “mobius strip” used in the puzzle is not the standard mobius. It is a variation which was described as “Open Mobius Band” in wikipedia. The difference is to remove the only edge from the strip, making it having only one endless surface and no boundary.

Many of the above descriptions were removed from the final version of the statement, by CG’s professional decision, to make it looks concise.

Also sorry for the incorrect constraint which should have been max 200, not 100.

3 Likes
#11

For anyone who might not know a trick in CG contests. When the testcase input data is “hidden”, it is not really hidden at all. You just need to add a debug printLine statement (exact name and syntax according to your language) after every read data statement, the full input data will be displayed in the web IDE’s console output.

#12

@java_coffee_cup I meant the test cases that are ran after submit, not before them. The visible ones you can indeed debug really well.

#13

Yes, I check the direction and that is the problem. In my opinion, you can’t go to left when you’re following the right wall and there is nothing at right.
If nobody noticed this problem, I think I’m wrong in some way, but don’t know why…

#14

which map in which level you are referring to?

#15

We just realized this morning that we indeed forgot to add this picture to the 3rd level:

mobius2
mobius21440×1080 293 KB

:frowning:

We’re also sorry for the issue affecting the leaderboard. We’re still not sure what happened :confused:

Next contest has been “revealed”: https://www.codingame.com/contests/mystery-sponsor

#16

The contest was fun, but Pikachu should have walked with the wrong output too. Would have made each level easier to understand or debug.

3 Likes
#17

I agree.
It would require a different output formats with directions/coordinates instead of visit counts.
But debugging was a pain, when you didn’t even know where it went wrong. And the sticky camera + zoom wasn’t helpful either.

#18

Ooh, I’m late to this. Thanks @ThePurificator for opening the topic!

The contest

All in all, I had a great time. I really appreciated seeing something speed-based back in the limelight, and the puzzle theming was a nice idea.

Well, in a way I couldn’t care less about the theming, but it didn’t get in the way. Yay!

It seems like I performed just a bit too casual to qualify for a T-shirt (eating, chatting on XMPP and going to the toilet—what was I thinking!) but I’ve decided not to hate myself forever just because of that.

The format

IIRC I skipped straight from I/O-puzzle-based contests to multis, so I’m not quite sure how much of this was new with regard to the solo-based contests. Please correct me when I’m wrong.

Multiple puzzles

In this specific case where the puzzles are closely related, I appreciated the non-binding submit and the ability to switch back and forth between levels. Those two features weren’t obvious to me at all at first, be it from the interface or the pre-contest communication material. I didn’t even discover the puzzle selection buttons until mid-level 2! But they were definitely useful later on, if only to recover the previous code and work from it instead of screaming in despair and starting from scratch as we’d have done with the previous format.

This all goes in the right direction in giving us more time management leeway, and that’s very good.

I’m quite a bit more reserved about the fact the contest consisted solely in very minor variations on the same puzzle.

The viewer

This was a big disappointment. That viewer was utterly useless. Worse, it took a lot of screen space, had its usual painful focus-attracting effect on test, for next to zero benefit. As in: just coloring and displaying the referee :left_right_arrow: agent I/Os would have been better.

More generally: the viewer concept can be useful to show what happens. Transversely, its playback buttons can be useful to navigate the referee interactions in a turn-based game. (in all honesty, with the current interface I think they’re the only way to navigate the interactions.)

But no part of this contest was turn-based at all. It appeared like it could have been; it probably would have helped us to make it so; but in its released state it isn’t.

So we’re left with a graphical representation of a 2D square grid. ASCII would have been fine. Our code features a lot of movement along that grid, but the viewer doesn’t reflect that. All it tells us is where our answer was correct and where it wasn’t (I think—honestly, each time I tried looking at it I got a bit more confused, so in the end I stopped altogether) and it does it in one of the most confusing ways possible: top-down animation of the cells. It’s not the “top-down” part that’s confusing, it’s the part where it doesn’t follow the arrow, sorry, detective Pikaptcha’s movement at all.

The viewer could actually have been a great help in understanding, let alone debugging, the more contrived movement cases (hello Möbius!) But no, all I could get from it was laggy zooming and panning.

I initially wrote this thinking the referee mechanism made sense. That’s because I’m biased and would need it for some other stuff of mine. But it made me realize this entire contest would have been perfectly acceptable as I/O puzzles: static cases, single valid answer and no need for a viewer.

Shoehorning the unadapted solo game interface was a bad fit.

PS: So I tried it again while writing this up, and I actually saw Pikaptcha move around in a way that’s useful to understanding. Was this broken during the contest?! Or is the feature’s discoverability suboptimal? (Or is this user too stupid to use the platform?)

The statement

A small word on topology

Let’s address the elephant in the room right now: the infamous Möbius trainwreck.

I won’t delve again in whether we’re talking about an authentic strip or an open-ended twisty N-dimensional torus or anything weirder; let’s just assume the casual CodinGamer never heard about Möbius and won’t have time to DuckDuckGo or attend a topology course before the end of the contest.

[The level 3 map] is a surface with only one side and only one edge.

Knowing Möbius strips: ok, this checks out.
Not knowing them: in 2D (which was the context until now), a surface is usually considered as having only one side, so no surprise there. “Only one edge” feels weirder. Is that because we’re now considering all sides, sorry, ‘all four straight sections of the boundary’ as a single edge? Or because now only one of them is still impassable?

A reminder from level 1 is absent here:

The maze is enclosed in impassable rocks that are not included in the data.

Ok, so later on this is ‘clarified’:

Pikaptcha can step over the edge of the Möbius strip and continue his wall-following path on the same one and only side of the strip but at a different position.

I can understand it’s hard to tell us (with a straight face) that we have to step to the other side of a single side. But that might have been slightly less confusing than “continuing on the same side”, which gives a much more stable impression that crossing the edge is a no-op. Yes, “but at a different position”, but it’s not given! Not here at least.

So the only place we have something resembling a description of the edge-teleport is in the flawed paper-Möbius-HOWTO near the beginning. Flawed?

  • “Print the first half (along the x-axis) of the grid.”
    I’ll assume the X axis is horizontal even though it’s said nowhere. But still, what do you call the first half along the X-axis? My paper strip that finally worked is an interpretation as ‘the top half’.
    But an interpretation that would make quite a bit of mathematical and English sense would be ‘the left half’, as it’s the half with the lower X-axis values. It would happen to also make a lot sense in that it connects the strip left-to-right, which is a very usual interpretation indeed.

  • What happens if one of the axes is odd-sized?
    Pretty drastic consequences on multiple topics, but not a word about it.

  • “Flip the paper over vertically.”
    Mostly the same issue, though this one was closer to recovering me. What [I assume] was expected: flip the paper over by holding it in your stationary left and right hands. If this were an image editor, I might actually understand vertical flipping as meaning to exchange the top and bottom edges. But this is a piece of paper in a 3D world, so I can conceive of rotating it 180° around an axis—the horizontal one—or flipping it like a book page, which happens to reach a vertical state halfway through.

  • (The rest is standard Möbius.)

This is a special case of something that happens all too often in the community puzzle moderation queue: this is a description of ‘how the author did it’, not of ‘what is [expected] in general’.

So we’re in a good 20/20 hindsight situation: once you know what has been expected all along, all the information does happen to be there. But it’s kind of impossible to call it unambiguous: it’s strewn about, and each place is mildly inconsistent with the others, so we don’t know which to prioritize.

(In my case: my mind rejected the initially correct interpretation of the paper procedure because of the impossible odd size dimension case. Then I hit the no-op situation and went with the ‘it’s equivalent to no edge’ interpretation. As many, I ended up reverse-engineering the “Circle” test case to pass. And crossing my fingers that no validator had an odd-dimension case, because THAT’S STILL NOT FSCK’N SPECIFIED!)

What could have made it better? Here are two options:

  • It’s one-sided? Own it! Give the input as the single side.
  • Paper procedure? Own it! Give us the faces to print before twisting. One might argue that’s the case already, but no, don’t make us guess them, give them with the same representation as level 4’s six faces!
  • (and don’t play on words with the edge pass)

So in the end, ‘twisted torus’ is what describes it best to me. Like, better than any kind of variant of a Möbius strip: passing over the edge negates there being an edge at all. I like the parallelogram roll interpretation a lot, but don’t think it would be appropriate as a puzzle statement.

Too bad for the pictures, but they’re merely photos of a Möbius strip with a Pikaptcha map on it. They unfortunately wouldn’t have disambiguated the actual problem. (And, as mentioned above, the viewer ironically could have.)

The topic

The rest of the statement(s) was nice. I suppose the story’s interesting to someone who’s into that.

The algorithm was a good fit. Wall-following is interesting in general, good for us that it simplified given the input format.

Interesting idea to adjust the topology with subsequent levels. I’ve got a few ideas for possible extensions…

Nits

If you intend to publish, please consider updating:

  • In the level 1 statement (only), the map is described as made of 0s and #s. On CodinGame we usually have . and #. It makes perfect sense for consistency with the other levels that it’s a zero, but please disambiguate it from letter O!
  • “You must analyze the given grid and return it with a small transformation”: this is fine in level 1 and kind of fine in level 2. For levels 3 and 4, it’s only a transformation between the input and the output, not compared to level 2; so it’s a bit confusing: I recall reading it in level 3 and wondering what the change to the output format was this time.

Thanks CG for bringing back speed contests! Give us more!
Thanks a lot @java_coffee_cup for a cool way to spend that Saturday afternoon!

6 Likes
#19

Do you mean it was possible to start the contest with the last puzzle? Argh! Didn’t notice this…

On my side I didn’t expect such contest, so I started fifteen minutes late (I thought it would be an optimization puzzle like A*craft where you can improve your ranking as long as the contest is not finished). At least I appreciated it since the result didn’t depend on language performance and I’m a little tired with GC issues in Java for traditional contests.

#20

The 4 contest pikachu games are now open to review and approval. Many effort was used in improving the Mobius puzzle statement. Do you think it is now better?

#21

They are going to be community puzzles and not official puzzles ? :frowning:

Far less XP, no achievements attached :frowning:

4 Likes
#22

Does the global contest ranking already reflect results from this contest? If not, when does it happen? :man_shrugging:

#23

It does.
But according to the current scoring system it’s worth more points to rank in the top10% of a 2500 player contest, than to win a contest with 1000 players. This contest had a low number of participants, so it hardly affects any global rankings (only the 3 best contest results matter).