Блог пользователя Soul_Full_Of_Thunder

Автор Soul_Full_Of_Thunder, история, 4 года назад, По-английски

Two days ago, one of my friends (Danylo99) told me about a cool problem from a recent SIT contest. The goal was to find a nontrivial cycle that visits all cells on a 2D grid with even sides.

I thought it would be interesting to visualize the results.

Here is a slightly larger one. If anyone knows other approaches, please share :)

By the way, I also made a video of what's going on inside the algorithm.

Hope you all have a great day!

  • Проголосовать: нравится
  • +59
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Damn that's cool!!!

»
4 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

what does non trivial means?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Like you could easily snake back and forth and then on the first column go all the way up to the start. That would be trivial and show a fairly boring picture. This picture is more interesting.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    Since there are no walls, I assume trivial paths are like spirals, or column-wise/row-wise snake patterns. I agree that a formal definition would be interesting.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    Here you can find how it was stated in the problem.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think, general approaches are covered by Maze generation algorithm article from Wikipedia. Most of them may be utilised to solve the problem. I wonder though if there's a way to generate such cycles uniformly at random, as these approaches (including yours, I think) are a bit biased and usually there are cycles that they can't generate at all.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

If anyone wants to try a similar problem — printing a Hamiltonian path on a 2D grid that starts in given cell (or tell if it does not exist) here it is. Sounds easy right? But willingness to suffer is advised.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How about tweaking Hilbert Curve? I think it can also give some interesting results.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hilbert Curve nicely fills a square. So far I think you can just insert some squares anywhere in the image. But I lack the willingness to suffer (ó﹏ò。) .