[Community Puzzle] Seam Carving


#1

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.


#2

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…


#3

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]).


#4

thank you a lot, i see where my fault, i thought all border energy=0, thanks a lot


#5

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?)


#6

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!


#7

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.


#8

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

#9

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?


#10

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.