https://www.codingame.com/training/medium/seam-carving
Send your feedback or ask for help here!
Created by @Niako,validated by @JBM,@Coni and @bbb000bbbyyy.
If you have any issues, feel free to ping them.
Hello, for the first test, i found this path [16, 16, 16, 17, 18, 18, 17, 17] for energy as 167, but i cannot find where i am wrong in the calculation…
The corresponding energy function should be:
0 11 1 1 2 5 2 6 7 1 4 1 4 3 7 5 5 44 1 20 23 4 19 5 13 20 2 10 23 0
71 161 95 87 131 104 102 94 72 35 24 30 30 29 43 52 31 82 177 88 86 100 126 123 114 72 51 41 21 39
50 19 47 46 69 99 72 91 156 105 2 21 22 18 14 21 35 65 25 65 43 72 54 76 82 97 125 75 53 38
74 108 73 139 91 38 26 61 98 172 59 50 37 27 16 18 7 4 44 21 34 65 97 9 61 46 77 203 95 43
63 65 31 94 161 87 137 95 110 140 146 54 77 80 61 52 54 37 18 31 32 74 110 94 22 46 25 121 219 9
23 74 45 50 98 80 63 130 167 172 137 90 35 54 73 66 66 79 60 45 46 93 85 134 80 118 132 160 113 57
4 47 46 33 48 52 66 118 52 118 32 147 81 41 25 26 18 19 72 56 64 71 23 52 26 20 101 81 133 72
0 13 15 21 31 13 28 20 16 45 20 38 26 22 32 12 8 3 25 24 1 1 30 44 7 29 38 24 48 0
The lowest path is [15, 16, 16, 17, 18, 18, 17, 17] (corresponding energies [5, 31, 35, 4, 18, 60, 19, 3]).
1 Like
thank you a lot, i see where my fault, i thought all border energy=0, thanks a lot
You’re welcome (if all the border cells had 0 energy, the lowest path would always be the first column with 0 energy, so I guess you had to explicitly exclude these cells in your computation?)
yes, i just ignored all 4 borders, by the way this puzzle is so nice, very interesting algorithme, love it a lot, the video is lovely too, really great puzzle, thanks!
1 Like
I, too, have to thank you for that puzzle. The linked video is very cool for demonstration.
I am afraid not very people will solve it, though, because of the wall of text in the description. But unfortunately I have no idea how to overcome that problem. Meanwhile I have a different one: It is unbelievable hard to debug. I got the first 3 tests running, but from the 4th on I do not success. I guess somehow my shrinking broke it, since the tests never fail on identifying the correct (or at least one with the very same sum) first path to delete. Maybe someone could help me out here: I got the path (bottom-up) [1, 90, 26, 0, 6, 9, 3, 3, 1, 0, 0, 0, 0, 2, 0, 0, 1, 1, 1] which sums up to 144 as the second path in the fourth testcase, although I should get 141.
2 Likes
Thanks for the feedback!
The lowest path indices (lex-min from top to bottom to break ties) should be [0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7] corresponding to the energies [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 3, 3, 9, 6, 0, 26, 90, 1].
The first path to remove was [14, 15, 16, 15, 16, 17, 18, 18, 19, 20, 21, 21, 21, 22, 23, 23, 23, 24, 24] (energies[0, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 4, 5, 2, 3, 0, 29, 83, 1]) and after its removal the energy function becomes:
0 2 1 1 1 1 1 0 0 1 2 1 0 0 0 1 1 0 1 1 0 0 0 0 1 7 10 32 14 23 4 1 0 1 1 0 0 1 0
0 1 2 1 2 2 1 2 2 0 2 2 2 2 1 0 2 1 0 1 1 2 2 8 46 137 233 123 129 30 6 1 2 2 0 2 2 2 1
0 1 1 2 0 2 2 0 2 2 1 2 1 1 2 2 1 2 1 0 1 4 8 36 238 211 131 138 171 13 2 1 2 0 2 2 2 2 1
0 2 0 2 2 0 2 2 0 2 1 1 2 2 0 2 2 1 2 1 7 11 13 221 201 21 47 200 108 14 1 1 1 2 2 1 2 0 0
1 2 2 0 2 1 0 2 2 1 2 1 0 2 2 0 2 2 2 11 74 136 181 211 51 47 66 236 74 9 2 2 2 1 0 1 1 0 1
1 1 2 2 1 2 0 0 2 2 1 2 2 0 2 2 1 3 10 65 173 205 211 40 90 169 130 261 33 7 0 2 1 0 1 2 2 2 1
0 1 0 2 2 2 2 0 0 2 1 2 3 2 1 1 1 1 5 36 257 157 170 126 116 133 297 148 24 3 2 2 1 1 2 2 2 1 0
1 2 0 0 2 2 2 2 1 2 2 11 9 3 2 2 1 3 2 15 138 274 91 88 223 53 215 240 96 18 6 2 1 1 3 3 1 0 1
1 3 4 2 0 2 2 1 1 2 16 83 60 14 3 1 2 7 1 9 47 235 135 86 56 160 205 220 308 96 15 3 1 4 10 7 3 2 1
2 2 11 3 3 0 2 2 2 14 108 255 174 57 9 2 7 29 12 3 16 73 224 57 46 160 203 102 244 116 13 3 2 11 53 42 11 4 1
7 15 106 29 6 3 1 3 13 44 300 183 214 82 12 12 73 216 65 13 2 9 109 221 130 158 47 139 333 73 14 6 5 70 189 200 48 7 3
22 242 222 231 20 9 3 4 19 118 277 142 232 38 4 47 310 186 312 39 11 7 15 199 197 98 50 327 222 113 10 4 22 156 121 145 181 35 1
129 330 41 346 143 7 3 7 20 145 127 190 149 90 20 129 313 63 349 133 14 4 17 130 271 149 280 277 162 250 199 7 7 67 166 64 120 145 10
111 63 43 165 192 20 9 10 40 119 63 30 106 102 21 188 182 41 202 197 22 9 8 78 265 235 353 125 160 105 309 197 17 39 124 153 137 220 53
70 23 37 171 189 22 6 11 66 148 175 176 196 161 6 170 173 62 271 210 21 4 2 18 74 135 66 148 236 47 121 313 109 29 156 174 52 171 75
134 169 37 234 152 14 0 7 47 238 182 93 219 172 10 206 195 152 333 75 17 3 1 3 10 16 25 55 249 149 74 169 165 22 52 225 216 80 133
9 177 71 200 145 45 34 26 37 119 297 13 213 170 109 216 154 252 118 94 32 32 30 30 27 27 26 57 115 146 140 161 77 58 94 65 192 222 4
93 177 71 177 167 109 105 90 98 125 173 90 210 205 97 28 117 49 74 121 99 91 87 85 87 84 87 100 93 45 37 54 66 87 97 61 42 103 107
0 47 11 45 16 2 5 1 7 6 120 88 116 102 3 1 2 2 3 2 2 3 2 1 1 1 2 7 3 5 9 5 3 1 2 3 2 7 0
1 Like
Hey @Niako, awesome puzzle. I get the first 5 tests to pass but tests 6-10 all fail and I can’t for the life of me figure out where the bug is in my algorithm. What is being introduced in test number 6 that isn’t there in tests 1-5?
1 Like
Nothing in particular (tests 1-4 are small images with few columns to remove, the others are “big” images with an increasing number of columns to remove).
Here are the total energy / path indices / corresponding energies (from top to bottom) of the successively removed paths of test 6:
365
[69, 69, 69, 69, 69, 69, 68, 67, 66, 65, 64, 63, 63, 64, 65, 66, 67, 68, 68, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69]
[0, 23, 10, 23, 7, 15, 6, 2, 7, 2, 10, 4, 3, 1, 1, 4, 2, 2, 0, 1, 1, 0, 1, 1, 19, 50, 32, 24, 19, 5, 1, 27, 24, 19, 7, 12, 0]
539
[68, 68, 68, 68, 68, 68, 68, 67, 68, 67, 68, 68, 67, 66, 65, 65, 66, 67, 68, 67, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 67, 68, 68]
[0, 37, 28, 62, 79, 45, 6, 4, 3, 0, 8, 9, 2, 6, 1, 2, 3, 1, 1, 1, 1, 1, 1, 11, 20, 25, 27, 20, 10, 3, 44, 26, 14, 20, 1, 17, 0]
661
[64, 64, 63, 64, 65, 65, 65, 64, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 43, 43, 42, 41, 41, 40, 39]
[19, 12, 61, 50, 87, 47, 6, 5, 12, 10, 3, 7, 9, 4, 4, 1, 4, 6, 6, 1, 4, 5, 14, 32, 15, 23, 67, 39, 37, 13, 9, 13, 12, 2, 11, 8, 3]
721
[3, 2, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 2, 2, 3, 9, 5, 2, 3, 2, 3, 1, 4, 3, 4, 2, 1, 3, 1, 5, 4, 7, 9, 16, 41, 115, 146, 11, 9, 91, 132, 7, 27, 6, 22, 19, 4, 0]
679
[0, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0, 1, 2, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 2, 2, 1, 0, 0, 1, 2, 3, 3, 2]
[0, 2, 3, 2, 6, 5, 7, 7, 1, 3, 2, 5, 6, 0, 2, 4, 3, 1, 5, 4, 34, 44, 94, 121, 13, 5, 4, 2, 7, 130, 72, 25, 27, 4, 17, 12, 0]
738
[29, 30, 31, 32, 33, 34, 34, 35, 36, 37, 38, 39, 38, 39, 40, 41, 41, 42, 42, 43, 42, 41, 42, 41, 40, 40, 39, 39, 38, 37, 36, 37, 36, 37, 38, 38, 37]
[23, 51, 36, 40, 34, 24, 27, 169, 25, 43, 14, 5, 5, 2, 3, 3, 2, 0, 0, 0, 4, 3, 24, 36, 24, 9, 4, 38, 6, 25, 4, 6, 13, 13, 17, 6, 0]
739
[11, 11, 12, 12, 13, 14, 15, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 30, 31, 32, 32, 32, 31, 30]
[2, 10, 59, 12, 7, 9, 2, 1, 2, 3, 2, 5, 8, 6, 9, 3, 4, 8, 8, 7, 21, 57, 12, 45, 101, 46, 34, 26, 16, 81, 55, 18, 16, 6, 20, 14, 4]
760
[0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 2, 3, 3, 2, 2, 1, 0, 0, 0, 0, 1, 2, 3, 2]
[0, 1, 3, 3, 3, 2, 7, 10, 6, 2, 3, 5, 4, 6, 5, 2, 2, 1, 2, 65, 195, 102, 31, 20, 10, 5, 11, 16, 28, 42, 70, 60, 10, 2, 8, 18, 0]
807
[0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 2, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8, 7, 7, 6, 7, 8, 8, 9, 10]
[0, 0, 2, 2, 3, 3, 6, 12, 3, 2, 1, 5, 4, 1, 1, 1, 4, 2, 5, 58, 272, 10, 45, 11, 20, 6, 11, 24, 6, 5, 20, 3, 82, 25, 34, 117, 1]
829
[43, 43, 43, 44, 45, 45, 44, 44, 43, 43, 42, 42, 43, 42, 41, 40, 39, 38, 37, 36, 36, 36, 36, 37, 38, 37, 36, 35, 34, 35, 35, 35, 35, 35, 36, 37, 37]
[14, 5, 35, 45, 37, 30, 44, 55, 69, 41, 122, 51, 16, 3, 11, 4, 4, 1, 1, 5, 0, 2, 13, 47, 27, 14, 4, 36, 1, 30, 5, 13, 14, 14, 7, 7, 2]
784
[45, 44, 43, 42, 42, 41, 40, 41, 42, 42, 41, 42, 42, 42, 42, 41, 40, 39, 38, 37, 36, 35, 36, 36, 37, 36, 35, 34, 34, 34, 33, 33, 33, 33, 32, 31, 31]
[2, 26, 16, 54, 50, 22, 80, 33, 26, 87, 50, 66, 15, 4, 6, 6, 5, 3, 0, 1, 4, 4, 11, 43, 28, 14, 17, 32, 6, 15, 7, 7, 8, 13, 9, 14, 0]
785
[44, 43, 42, 42, 42, 41, 40, 41, 42, 41, 41, 42, 41, 40, 39, 38, 37, 36, 37, 37, 36, 37, 38, 38, 37, 36, 36, 35, 34, 35, 34, 34, 35, 34, 35, 35, 34]
[6, 31, 9, 33, 32, 47, 34, 34, 49, 84, 50, 67, 37, 8, 4, 5, 3, 1, 1, 0, 5, 5, 15, 39, 18, 25, 3, 41, 11, 22, 9, 9, 16, 19, 7, 4, 2]
841
[2, 2, 2, 3, 4, 5, 6, 7, 6, 7, 8, 9, 9, 10, 11, 12, 13, 12, 13, 12, 12, 12, 11, 11, 11, 11, 11, 10, 9, 8, 7, 6, 6, 7, 7, 8, 9]
[0, 3, 4, 5, 2, 2, 10, 13, 5, 2, 2, 2, 1, 4, 11, 1, 28, 150, 61, 25, 49, 40, 37, 32, 10, 7, 7, 13, 11, 10, 8, 24, 41, 34, 63, 121, 3]
835
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 5, 4, 4, 4, 4, 5, 6, 7, 7, 6, 6, 6, 5, 5]
[0, 1, 2, 2, 2, 3, 12, 12, 1, 0, 2, 4, 6, 0, 1, 0, 4, 1, 5, 88, 205, 47, 44, 42, 28, 10, 1, 22, 11, 7, 19, 19, 21, 12, 139, 58, 4]
846
[42, 41, 40, 39, 40, 41, 42, 43, 44, 44, 45, 45, 45, 44, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 35, 34, 33, 32, 31, 32, 31, 31, 30, 29, 30, 29, 29]
[5, 17, 30, 37, 28, 43, 89, 85, 45, 54, 96, 8, 4, 3, 3, 2, 8, 6, 3, 3, 1, 6, 15, 29, 15, 29, 25, 42, 22, 24, 5, 17, 15, 19, 9, 3, 1]
Make sure to compute the lexicographically-min path from top to bottom.
1 Like
hello,@Niako,it’s a greate puzzle.when I tests I-3,I can’t pass ;there is frist path:0:24 1:24 2:24 3:23 4:23 5:22 6:22 7:21;i can’t get 148 when the thrid times;where i am wrong in the calculation…
by the way,the path is bottom to top
@yinteman Hi, I’m sorry I really don’t get your message. Are you talking about test 4? What is the path you’re talking about (length should be 19, the height of the image)?
Very good puzzle, I learned something cool in the process 
1 Like
Almost the same problem is featured in the week 2 assignment of the free “Algorithms part II by Princeton” course on Coursera (link), although slightly different input/output requirements. Additional insight and tips can be found on that assignment’s specification and faq pages.
I solved CG version first, after that the other one was piece of cake.
2 Likes
Thanks a lot for this puzzle @Niako ! I am Junior Software Engineer in Image Processing and I never heard about this algorithm, always nice to discover new things !
Also there is a kind of typo error in the pre-generated code in Python: in the second for loop i = int(j) while i is also the row iteration value, it can be a bit misleading 
2 Likes
Just solved it, nice puzzle, I like the effect.
At each step I recalculate my whole energy matrix E and my whole lowest_energy matrix L (I use a DP method).
It feels a bit dumb to do so, and your last paragraph hints that there’s a way to go faster than this, so I gave it some thoughts, but there’s something that bothers me.
I get that you can just update energy along the seam, but if you want to delete a cell in each row of E it’ll be O(W) per row with a basic array of arrays so O(W*H) at each step, so indeed it might be a bit faster than just recalculating the whole E but it’s the same complexity.
So the only huge improprement I can imagine is using an array of linked lists instead, for more efficient cell removals.
So let’s say you refactor it like this.
Now comes the real problem: the L matrix.
Cause even with linked lists and trying to update as few values as possible, removing a single cell in the last row will propagate with a kind of triangularish shape in rows above and the area you’d be forced to update will be O(W*H) anyway.
So it feels like even with those optimisations (which would be a bit painful to implement for languages without buidin linked lists), I don’t see how you can beat an O(W*H) complexity each turn.
Am I missing something ?
2 Likes
@pardouin Using these optimizations (some kind of “backpropagation” to update the DP, doubly-linked cells data structure, …) the worst case complexity will indeed be the same (O(W*H), i.e. linear in the size of the image), but it should be more efficient in practice.
2 Likes
I just passed all test cases however I still can’t pass validators number 5,8 and 10.
Can you give me some clarification on this please!