Beta

N By N Skyscrapers

6MoonPresident
Description
Loading description...
Algorithms
Puzzles
View
AllIssues3QuestionsSuggestionsShow Resolved
  • Please sign in or sign up to leave a comment.
  • Voile Avatar

    Kata only provides a fixed set of test cases, which is easy to hard-code.

  • crastinus Avatar

    Too easy task. All test cases fits into 30ms in Release buld.

    • MoonPresident Avatar

      Hey Crastinus. Thank you for the feedback.

      You reminded me I had meant to update this task for a while, so I have rewritten the test cases to extend up to 15x15 and to improve the difficulty. Could you have another go and tell me if its a meaningful improvement?

    • crastinus Avatar

      Hey. Yes. It is a good improvement. But in current problems count of permutations too low. The most of test cases get solved after excluding wrong combinations.

    • MoonPresident Avatar

      Count of permutations? How do you mean? This is designed to use skyscaper problems with only one solution.

    • crastinus Avatar

      This comment has been hidden.

  • matthias.schmidt67 Avatar

    Hi Mr President:) I think I have a solution in Python (not the one where only the clues are given), but I do not know C++. So, I would like to know whether you plan to publish a Python version some day?

    • MoonPresident Avatar

      Sorry for the late reply. I currently have no plans to publish a python version, but if you have a python version that works, I'd be happy to work with you on the translation. I can provide you with some test cases if you would like.

  • SandroWissmann Avatar

    According to the Test I can solve test for Size 10 in ~500ms. But then I always get a time out for cases with size = 11.

    I also run tests on my machine and can run all test including 11 in less than 4 seconds. Still these time outs appear.

    I already try for days with crazy optimizations to make the code faster and start to wonder if its a test suite issue.

    Right now I feelt his way harder than the 1 Kyu 7by7.

    Please Check it it is still solveable.

    • MoonPresident Avatar

      Hi Sandro. The 11 by 11's are fairly computationaly expensive. I am intending to optimise the backend of this puzzle to give the frontend more time to run, if you read down through this post you will see that there are some problems uploading C++ vectors that I need to work out.

    • SandroWissmann Avatar

      Yes I read about that. In the meantime I discussed my solution with some people and we came up that it is not that efficient yet. I try now an completly different approach to solve the puzzles faster. We will see If thats enough for the tests.

    • MoonPresident Avatar

      Hi Sandro, I have changed the problem set. Its more diverse but also potentially more difficult, however it should have removed the particular problems that were causing you difficulty. If you have another go, please let me know how you find it.

    • SandroWissmann Avatar

      Excellent. I will try it out soon. Im working right now on an more efficient solution. I will try it with the old program which could solve in time until it reached 10x10 and the newer potentially faster one.

    • SandroWissmann Avatar

      This comment has been hidden.

    • MoonPresident Avatar

      Incidentally, I have updated the code to go up to 15x15.

  • SandroWissmann Avatar

    any good ressources to find 10x10 and 11x11 puzzles with solution for the unit tests?

    could not find any in the internet.

  • SandroWissmann Avatar

    The last two test cases provided are broken:

    {
    {
        { 0, 0, 0, 0, 0, 3, 0 },
        { 0, 1, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 5, 0, 0, 0 },
        { 0, 0, 0, 7, 0, 0, 0 },
        { 4, 0, 0, 2, 0, 0, 0 },
        { 0, 0, 2, 0, 0, 0, 0}

    },
    {
        { 5, 7, 6, 4, 2, 3, 1 },
        { 3, 1, 5, 6, 4, 2, 7 },
        { 2, 3, 7, 1, 6, 5, 4 },
        { 6, 2, 1, 5, 7, 4, 3 },
        { 1, 5, 4, 7, 3, 6, 2 },
        { 4, 6, 3, 2, 1, 7, 5 },
        { 7, 4, 2, 3, 5, 1, 6}

    },
    { 
        { 3, 1, 2, 3, 4, 4, 2, 5, 1, 4, 3, 3, 2, 2, 2, 2, 2, 2, 4, 3, 1, 1, 3, 3, 2, 3, 4, 2 }
    }
},
{
    {
        { 0, 0, 0, 0, 0, 3, 0 },
        { 0, 1, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 5, 0, 0, 0 },
        { 0, 0, 0, 7, 0, 0, 0 },
        { 4, 0, 0, 2, 0, 0, 0 },
        { 0, 0, 2, 0, 0, 0, 0}

    },
    {
        { 5, 7, 6, 4, 2, 3, 1 },
        { 3, 1, 5, 6, 4, 2, 7 },
        { 2, 3, 7, 1, 6, 5, 4 },
        { 6, 2, 1, 5, 7, 4, 3 },
        { 1, 5, 4, 7, 3, 6, 2 },
        { 4, 6, 3, 2, 1, 7, 5 },
        { 7, 4, 2, 3, 5, 1, 6}

    },
    { 
        { 3, 1, 2, 3, 4, 4, 2, 5, 1, 4, 3, 3, 2, 2, 2, 2, 2, 2, 4, 3, 1, 1, 3, 3, 2, 3, 4, 2 }
    }
}

    There is no valid solution

  • geoffp Avatar

    A nice addition to the Skyscrapers series. In difficulty it seems to lie somewhere between the 4x4 kata (4kyu) and the 6x6 version (2kyu); I've rated it 3kyu. Even though it has puzzles up to 11x11, they're much easier than in the 6x6 and 7x7 kata, so less optimization is required.

    Possible improvements:

    • The test code seems rather slow, taking around 10 seconds to run even when my own code is doing almost nothing.
    • The int N parameter in the C++ version isn't really needed.
    • Some more test cases would be nice.
    • doooom Avatar

      mmm... when first see 11x11, I thought it's insane.

    • MoonPresident Avatar

      Do you know how I can optimise the test code? I had to reduce the number of test cases I was using because putting a large array of them in (1000 lines) caused the test code to time out.

      I have code on my local machine to generate individual kata's, but to generate difficult katas it takes a long time.

    • geoffp Avatar

      It looks like the compiler is taking a long time to compile your vector of vectors of vectors of vectors. (Or maybe it's the initialization that takes the time?)

      You could try a more efficient way of expressing the example test cases. It should be possible to encode them quite tightly if you need to. For an 11x11 puzzle, each row has to be one of the 11! = 39916800 possible permutations of {1..11}, so a single 32-bit integer suffices to encode which permutation it is. Each clue needs only 1 bit: should the clue be given or not? (You don't need the numerical value of the clue, that can easily be computed on the fly). So that's 44 bits for the external clues along the sides and 121 bits for the internal ones in the grid. Something like this:

      #include <bitset>
using namespace std;

struct {
  bitset<44> external_clues;       // which external clues are given
  bitset<61> internal_clues_top;   // which internal clues are given, top half of puzzle
  bitset<60> internal_clues_bot;   // which internal clues are given, bottom half of puzzle
  vector<unsigned> solution_rows;  // permutation of 1..11 in each row
       } test_cases[] = 
  { { 0x102a0311012, 0x1020800060, 0x800c0004, { 0x1234567, 0x0fedcba, 0x1357924, 0x1234567, 0x0fedcba, 0x1357924, 0x1234567, 0x0fedcba, 0x1357924, 0x1234567, 0x0fedcba } },
    // more test cases, one per line of text
       };

      I tried this just now and found that an array of a few hundred of these structures is compiled and initialized in negligible time. Of course, you'll need to write some code to convert the examples to and from this format.

    • hobovsky Avatar

      After C++ 17 was introduced to Codewars, it turned out that compilation for large containers initialized directly in code can take a very long time. Kata with precalculated, large collections of strings or vectors timed out on compilation due to large amount of code emitted for such initialization. There was an issue reported for this behavior in the Codewars runner board, and I think it was fixed, but I cannot find it now.

      One approach you can take is to hardcode fewer test cases and apply some validity preserving transformations, like rotation, transposition, reflections, etc. Unless each of a thousand of your hardcoded boards represents some specific data scenario, reducing it to, lets say, 100 boards and transforming it randomly maybe would suffice?

      I will try to find out what happened to the related issue.

    • MoonPresident Avatar

      Thank you hobovsky! I will try to make this more interesting. My initial intent was to put a Latin square generator up, but the generation method I used ended up taking a pretty long time to produce reduced grids with a single answer (8x8 and bigger). I may have to look into optimizing it. Either way, I will find a weekend soon and see if I can't increase the challenge of this.

    • MoonPresident Avatar

      Hey guys, I have updated the test data to up the challenge and reduce the load time. Can you guys have another try and see how it feels?

    • geoffp Avatar

      The new encoding for the test cases seems much more efficient - but you have a much larger number of test cases now. The upshot is that the load time still seems to be around 8 seconds.

      I did some experimenting and discovered that there seems to be much less overhead if you can encode each test case as a single vector<unsigned long long> (so the whole test_cases structure is vector<vector<unsigned long long>>). Apparently, the compiler is OK with vectors of vectors, but much less well optimized for vectors of vectors of vectors. If this works, it should be a relatively easy speedup to achieve.

      As for the challenge level, there are two of your new test cases (one 11x11, and one 12x12) that my code chokes on; it times out unless those two cases are excluded. Evidently I'm not done with this kata yet. :)

    • MoonPresident Avatar

      That is good information, I can definitely use that to refine the load time.

      As for the difficulty, I know that the previous test cases were comparatively easy, so I tried to turn the difficulty up so that it was closer to the challenge level of the 6 by 6 and 7 by 7 katas. I am still fine tuning the difficulty, and have ideas for how to make the challenges more moderate or more difficult, as well to standardise the average level of challenge. It all depends on the feedback I get.

    • MoonPresident Avatar

      I have updated the encoding to reduce the nesting by another layer and included much harder problems. Up to 15 x 15 now!

  • JohanWiltink Avatar

    .. problem size [ limit ] has been increased to 11

    Love it! :stuck_out_tongue_closed_eyes:

    • MoonPresident Avatar

      Glad you enjoyed it. Let me know if there is anything that could use improvement, this is the first Kata I have written so I am interested in feedback.

    • JohanWiltink Avatar

      I don't do C++, so I can't solve it. :] So I don't have anything to say on the testing; I can't even see it.

      If I may make one suggestion: summarise the requirements in your own description, don't just refer back to previous installments. I caught some sh!t over that and had to expand my initial description a little. Specifically: specify input and output format and mention puzzles have a single solution wait, you already do that.