[Community Puzzle] Seam Carving

Puzzles
#21

I answered in PM to avoid spoiling here.

1 Like
#22

I just came across this puzzle and wanted to thank you for it! It was really nice discovering that cool algorithm and I think you ‘shaped’ the rules perfectly so that it’s quite fast to implement without loosing any interesting part.
Hope you ll submit another image processing puzzle :smiley:

2 Likes
#23

I know that it would be quite the task, but @Niako , would you consider making another level 2 of this that would require more optimization (such as caching, as you allude to in the problem statement)? I could perhaps make it if you don’t want to because it would be too much effort?

I think that it would be natural to be concerned about that being too small of a change for an entirely new puzzle, so perhaps a 3-channel version of this problem could be possible with much larger images to force some caching?

Any feedback (not just from the creator) would be appreciated!

1 Like
#24

Thanks for your feedback. The purpose of this puzzle was to provide a simple enough introduction to the algorithm (and not the technical aspects) behind seam carving. From there, anybody is free to go further and implement the technique in both directions on RGB images, experiment with energy functions…

Going further with a sequel on CG though would not necessarily be very interesting as it would still be the same algorithm at the heart of the puzzle. Furthermore it would require much larger images, while inputs are limited to 10000 chars. To circumvent that limitation, we usually provide a RNG formula in the statement, a seed as input and ask the player to generate the data. But using seam carving on random images would be very artificial.

#25

Hello @Niako,
Thank you for your interesting puzzle, I could be interested by your answer to @katiia’s message. I face the same difficulty as I pass all test cases but not the validators number 5, 8 and 10.
Would you please have a suggestion or a description of these validators?

#26

I replied in PM.

#27

I implemented a dfs with memo instead of dp. It failed at test case 7, 10 and validator 7 because of time out. Would you give some advices for reducing the time cost?

My C code of dfs:

void dfs(int x,int y,int energy){
    if(energy>f[x][y]||energy>min_e)return;
    f[x][y]=energy;
    if(x==n){ // if on last row of image
        if(f[x][y]<min_e){
            // update the known lowest energy solution
            min_e=f[x][y];
            for(int i=1;i<=n;++i){
                min_e_y_route[i]=y_route[i];
            }
        }
        return;
    }
    for(int j=y-1;j<=y+1;++j)if(j>=1&&j<=m){
        y_route[x+1]=j; // record the route of dfs
        dfs(x+1,j,energy+E(x+1,j));
    }
}
#30

terrible puzzle.

#31

When you give your feedback on a puzzle, please be civil and support your feedback with proper reasons and constructive ideas.

You’re also reminded to observe the code of conduct, and I quote here:

Be humble and supportive of each other.

#32

I like this puzzle, but I don’t know yet what approach to use (my current approach times out from case 2 onwards).

My current approach: iteratively find all possible paths (first from first row with first and second from second row, etcetera etcetera) - and when all possible paths are found, to compare the energy for every path and keep the lowest. Obviously that results in way too many iterations. But I am at a loss for ideas of how to make this more efficient. Any advice what to look for / what algorithm names to google for?

#33

There’s a faq link above, and some other discussion that follows. Do they help you?

1 Like
#34

You are right, that faq gives me quite a few pointers to think about. I was quite proud of a energy calculation per cell that I implemented, but it seems that I should kill that darling. I need to let it sink in for a bit.

#35

I am writing this to give you feedback on this puzzle as it desperately needs an honest one; so be professional and don’t delete my comment. Don’t put my account on hold. (!!)

  1. This puzzle is definitely not Medium Level but a weird hard one.
  2. It is vaguely described, and it is not a proper Codingame puzzle. Read some popular puzzles and learn from them the way they familiarize the reader with the question.
  3. Test cases are horrible to read, work with and get help from in terms of debugging.

These are the reasons only 49% were successful for a medium puzzle which obviously shows something is wrong.

Below is my code:
4 test cases outputs wrongly, the rest (6 cases) are correct. Why? God knows… .
End of feedback.

[Mod edit: Please avoid posting your code on the forum]

#36

Thank you for writing a proper feedback comment (instead of a one-liner without elaboration).

Please avoid posting your code on the forum. Please try to describe your approach in detail instead.

For the visible test cases, you’re able to access the full expected output, so you can compare that to the answer produced by your code for debugging.

You’re also suggested to refer to the earlier discussion for some hints and guidance on how to solve this puzzle.

I’m not the author of the puzzle, so I can’t comment on other aspects raised in your message on the author’s behalf.

#37

Only a tweak was needed to solve it 100% but that doesn’t mean I take back my words.

#38

I think this problem perfectly fits in the medium category, the memoization required to solve it is not exceptionally difficult to see and once it’s found, the rest of the problem kind of just falls into place.

I do agree tho, that the prompt is a bit cryptic, using strange ascii art representations of calculus symbols, and requires reading/watching the references to fully understand the problem.

The Mars Lander Episode 2 is far harder than this and is also classified as medium.