| | | 1 | | // -------------------------------------------------------------------------------- |
| | | 2 | | // Copyright (C) 2025 Eugene Eremeev (also known as Yevhenii Yeriemeieiv). |
| | | 3 | | // All Rights Reserved. |
| | | 4 | | // -------------------------------------------------------------------------------- |
| | | 5 | | // This software is the confidential and proprietary information of Eugene Eremeev |
| | | 6 | | // (also known as Yevhenii Yeriemeieiv) ("Confidential Information"). You shall not |
| | | 7 | | // disclose such Confidential Information and shall use it only in accordance with |
| | | 8 | | // the terms of the license agreement you entered into with Eugene Eremeev (also |
| | | 9 | | // known as Yevhenii Yeriemeieiv). |
| | | 10 | | // -------------------------------------------------------------------------------- |
| | | 11 | | |
| | | 12 | | namespace LeetCode.Algorithms.SlidingPuzzle; |
| | | 13 | | |
| | | 14 | | /// <inheritdoc /> |
| | | 15 | | public class SlidingPuzzlePrecomputedDictionary : ISlidingPuzzle |
| | | 16 | | { |
| | 3 | 17 | | private readonly Dictionary<int, int> _movesDictionary = new() |
| | 3 | 18 | | { |
| | 3 | 19 | | { 123450, 0 }, |
| | 3 | 20 | | { 120453, 1 }, |
| | 3 | 21 | | { 123405, 1 }, |
| | 3 | 22 | | { 102453, 2 }, |
| | 3 | 23 | | { 103425, 2 }, |
| | 3 | 24 | | { 123045, 2 }, |
| | 3 | 25 | | { 12453, 3 }, |
| | 3 | 26 | | { 152403, 3 }, |
| | 3 | 27 | | { 13425, 3 }, |
| | 3 | 28 | | { 130425, 3 }, |
| | 3 | 29 | | { 23145, 3 }, |
| | 3 | 30 | | { 412053, 4 }, |
| | 3 | 31 | | { 152043, 4 }, |
| | 3 | 32 | | { 152430, 4 }, |
| | 3 | 33 | | { 413025, 4 }, |
| | 3 | 34 | | { 135420, 4 }, |
| | 3 | 35 | | { 203145, 4 }, |
| | 3 | 36 | | { 412503, 5 }, |
| | 3 | 37 | | { 52143, 5 }, |
| | 3 | 38 | | { 150432, 5 }, |
| | 3 | 39 | | { 413205, 5 }, |
| | 3 | 40 | | { 135402, 5 }, |
| | 3 | 41 | | { 230145, 5 }, |
| | 3 | 42 | | { 243105, 5 }, |
| | 3 | 43 | | { 402513, 6 }, |
| | 3 | 44 | | { 412530, 6 }, |
| | 3 | 45 | | { 502143, 6 }, |
| | 3 | 46 | | { 105432, 6 }, |
| | 3 | 47 | | { 403215, 6 }, |
| | 3 | 48 | | { 413250, 6 }, |
| | 3 | 49 | | { 135042, 6 }, |
| | 3 | 50 | | { 235140, 6 }, |
| | 3 | 51 | | { 243015, 6 }, |
| | 3 | 52 | | { 243150, 6 }, |
| | 3 | 53 | | { 42513, 7 }, |
| | 3 | 54 | | { 420513, 7 }, |
| | 3 | 55 | | { 410532, 7 }, |
| | 3 | 56 | | { 520143, 7 }, |
| | 3 | 57 | | { 542103, 7 }, |
| | 3 | 58 | | { 15432, 7 }, |
| | 3 | 59 | | { 43215, 7 }, |
| | 3 | 60 | | { 430215, 7 }, |
| | 3 | 61 | | { 410253, 7 }, |
| | 3 | 62 | | { 35142, 7 }, |
| | 3 | 63 | | { 235104, 7 }, |
| | 3 | 64 | | { 240153, 7 }, |
| | 3 | 65 | | { 542013, 8 }, |
| | 3 | 66 | | { 423510, 8 }, |
| | 3 | 67 | | { 401532, 8 }, |
| | 3 | 68 | | { 523140, 8 }, |
| | 3 | 69 | | { 542130, 8 }, |
| | 3 | 70 | | { 415032, 8 }, |
| | 3 | 71 | | { 435210, 8 }, |
| | 3 | 72 | | { 401253, 8 }, |
| | 3 | 73 | | { 305142, 8 }, |
| | 3 | 74 | | { 205134, 8 }, |
| | 3 | 75 | | { 235014, 8 }, |
| | 3 | 76 | | { 204153, 8 }, |
| | 3 | 77 | | { 423501, 9 }, |
| | 3 | 78 | | { 41532, 9 }, |
| | 3 | 79 | | { 431502, 9 }, |
| | 3 | 80 | | { 523104, 9 }, |
| | 3 | 81 | | { 540132, 9 }, |
| | 3 | 82 | | { 415302, 9 }, |
| | 3 | 83 | | { 435201, 9 }, |
| | 3 | 84 | | { 41253, 9 }, |
| | 3 | 85 | | { 451203, 9 }, |
| | 3 | 86 | | { 350142, 9 }, |
| | 3 | 87 | | { 345102, 9 }, |
| | 3 | 88 | | { 25134, 9 }, |
| | 3 | 89 | | { 250134, 9 }, |
| | 3 | 90 | | { 35214, 9 }, |
| | 3 | 91 | | { 24153, 9 }, |
| | 3 | 92 | | { 254103, 9 }, |
| | 3 | 93 | | { 403521, 10 }, |
| | 3 | 94 | | { 423051, 10 }, |
| | 3 | 95 | | { 541032, 10 }, |
| | 3 | 96 | | { 431052, 10 }, |
| | 3 | 97 | | { 431520, 10 }, |
| | 3 | 98 | | { 503124, 10 }, |
| | 3 | 99 | | { 523014, 10 }, |
| | 3 | 100 | | { 504132, 10 }, |
| | 3 | 101 | | { 405312, 10 }, |
| | 3 | 102 | | { 415320, 10 }, |
| | 3 | 103 | | { 405231, 10 }, |
| | 3 | 104 | | { 435021, 10 }, |
| | 3 | 105 | | { 241053, 10 }, |
| | 3 | 106 | | { 451023, 10 }, |
| | 3 | 107 | | { 451230, 10 }, |
| | 3 | 108 | | { 352140, 10 }, |
| | 3 | 109 | | { 345012, 10 }, |
| | 3 | 110 | | { 345120, 10 }, |
| | 3 | 111 | | { 125034, 10 }, |
| | 3 | 112 | | { 254130, 10 }, |
| | 3 | 113 | | { 305214, 10 }, |
| | 3 | 114 | | { 124053, 10 }, |
| | 3 | 115 | | { 254013, 10 }, |
| | 3 | 116 | | { 43521, 11 }, |
| | 3 | 117 | | { 430521, 11 }, |
| | 3 | 118 | | { 23451, 11 }, |
| | 3 | 119 | | { 541302, 11 }, |
| | 3 | 120 | | { 31452, 11 }, |
| | 3 | 121 | | { 53124, 11 }, |
| | 3 | 122 | | { 530124, 11 }, |
| | 3 | 123 | | { 23514, 11 }, |
| | 3 | 124 | | { 54132, 11 }, |
| | 3 | 125 | | { 534102, 11 }, |
| | 3 | 126 | | { 45312, 11 }, |
| | 3 | 127 | | { 450312, 11 }, |
| | 3 | 128 | | { 410325, 11 }, |
| | 3 | 129 | | { 45231, 11 }, |
| | 3 | 130 | | { 450231, 11 }, |
| | 3 | 131 | | { 35421, 11 }, |
| | 3 | 132 | | { 241503, 11 }, |
| | 3 | 133 | | { 51423, 11 }, |
| | 3 | 134 | | { 352104, 11 }, |
| | 3 | 135 | | { 340125, 11 }, |
| | 3 | 136 | | { 125304, 11 }, |
| | 3 | 137 | | { 350214, 11 }, |
| | 3 | 138 | | { 315204, 11 }, |
| | 3 | 139 | | { 124503, 11 }, |
| | 3 | 140 | | { 54213, 11 }, |
| | 3 | 141 | | { 543021, 12 }, |
| | 3 | 142 | | { 203451, 12 }, |
| | 3 | 143 | | { 501342, 12 }, |
| | 3 | 144 | | { 541320, 12 }, |
| | 3 | 145 | | { 301452, 12 }, |
| | 3 | 146 | | { 153024, 12 }, |
| | 3 | 147 | | { 534120, 12 }, |
| | 3 | 148 | | { 203514, 12 }, |
| | 3 | 149 | | { 154032, 12 }, |
| | 3 | 150 | | { 534012, 12 }, |
| | 3 | 151 | | { 452310, 12 }, |
| | 3 | 152 | | { 401325, 12 }, |
| | 3 | 153 | | { 245031, 12 }, |
| | 3 | 154 | | { 305421, 12 }, |
| | 3 | 155 | | { 201543, 12 }, |
| | 3 | 156 | | { 241530, 12 }, |
| | 3 | 157 | | { 501423, 12 }, |
| | 3 | 158 | | { 302154, 12 }, |
| | 3 | 159 | | { 352014, 12 }, |
| | 3 | 160 | | { 304125, 12 }, |
| | 3 | 161 | | { 105324, 12 }, |
| | 3 | 162 | | { 125340, 12 }, |
| | 3 | 163 | | { 354210, 12 }, |
| | 3 | 164 | | { 315024, 12 }, |
| | 3 | 165 | | { 315240, 12 }, |
| | 3 | 166 | | { 104523, 12 }, |
| | 3 | 167 | | { 124530, 12 }, |
| | 3 | 168 | | { 504213, 12 }, |
| | 3 | 169 | | { 543201, 13 }, |
| | 3 | 170 | | { 230451, 13 }, |
| | 3 | 171 | | { 253401, 13 }, |
| | 3 | 172 | | { 51342, 13 }, |
| | 3 | 173 | | { 510342, 13 }, |
| | 3 | 174 | | { 540321, 13 }, |
| | 3 | 175 | | { 310452, 13 }, |
| | 3 | 176 | | { 351402, 13 }, |
| | 3 | 177 | | { 153204, 13 }, |
| | 3 | 178 | | { 230514, 13 }, |
| | 3 | 179 | | { 213504, 13 }, |
| | 3 | 180 | | { 154302, 13 }, |
| | 3 | 181 | | { 34512, 13 }, |
| | 3 | 182 | | { 452301, 13 }, |
| | 3 | 183 | | { 41325, 13 }, |
| | 3 | 184 | | { 421305, 13 }, |
| | 3 | 185 | | { 245301, 13 }, |
| | 3 | 186 | | { 350421, 13 }, |
| | 3 | 187 | | { 325401, 13 }, |
| | 3 | 188 | | { 21543, 13 }, |
| | 3 | 189 | | { 210543, 13 }, |
| | 3 | 190 | | { 240531, 13 }, |
| | 3 | 191 | | { 510423, 13 }, |
| | 3 | 192 | | { 521403, 13 }, |
| | 3 | 193 | | { 32154, 13 }, |
| | 3 | 194 | | { 320154, 13 }, |
| | 3 | 195 | | { 52314, 13 }, |
| | 3 | 196 | | { 34125, 13 }, |
| | 3 | 197 | | { 324105, 13 }, |
| | 3 | 198 | | { 15324, 13 }, |
| | 3 | 199 | | { 150324, 13 }, |
| | 3 | 200 | | { 120345, 13 }, |
| | 3 | 201 | | { 354201, 13 }, |
| | 3 | 202 | | { 310245, 13 }, |
| | 3 | 203 | | { 14523, 13 }, |
| | 3 | 204 | | { 140523, 13 }, |
| | 3 | 205 | | { 120534, 13 }, |
| | 3 | 206 | | { 540213, 13 }, |
| | 3 | 207 | | { 514203, 13 }, |
| | 3 | 208 | | { 503241, 14 }, |
| | 3 | 209 | | { 543210, 14 }, |
| | 3 | 210 | | { 231450, 14 }, |
| | 3 | 211 | | { 253041, 14 }, |
| | 3 | 212 | | { 253410, 14 }, |
| | 3 | 213 | | { 351042, 14 }, |
| | 3 | 214 | | { 512340, 14 }, |
| | 3 | 215 | | { 504321, 14 }, |
| | 3 | 216 | | { 312450, 14 }, |
| | 3 | 217 | | { 351420, 14 }, |
| | 3 | 218 | | { 103254, 14 }, |
| | 3 | 219 | | { 153240, 14 }, |
| | 3 | 220 | | { 234510, 14 }, |
| | 3 | 221 | | { 213054, 14 }, |
| | 3 | 222 | | { 213540, 14 }, |
| | 3 | 223 | | { 104352, 14 }, |
| | 3 | 224 | | { 154320, 14 }, |
| | 3 | 225 | | { 304512, 14 }, |
| | 3 | 226 | | { 402351, 14 }, |
| | 3 | 227 | | { 452031, 14 }, |
| | 3 | 228 | | { 341025, 14 }, |
| | 3 | 229 | | { 421035, 14 }, |
| | 3 | 230 | | { 421350, 14 }, |
| | 3 | 231 | | { 205341, 14 }, |
| | 3 | 232 | | { 245310, 14 }, |
| | 3 | 233 | | { 325041, 14 }, |
| | 3 | 234 | | { 325410, 14 }, |
| | 3 | 235 | | { 521043, 14 }, |
| | 3 | 236 | | { 204531, 14 }, |
| | 3 | 237 | | { 513420, 14 }, |
| | 3 | 238 | | { 521430, 14 }, |
| | 3 | 239 | | { 132054, 14 }, |
| | 3 | 240 | | { 324150, 14 }, |
| | 3 | 241 | | { 502314, 14 }, |
| | 3 | 242 | | { 134025, 14 }, |
| | 3 | 243 | | { 324015, 14 }, |
| | 3 | 244 | | { 102345, 14 }, |
| | 3 | 245 | | { 304251, 14 }, |
| | 3 | 246 | | { 354021, 14 }, |
| | 3 | 247 | | { 301245, 14 }, |
| | 3 | 248 | | { 514023, 14 }, |
| | 3 | 249 | | { 143520, 14 }, |
| | 3 | 250 | | { 102534, 14 }, |
| | 3 | 251 | | { 514230, 14 }, |
| | 3 | 252 | | { 53241, 15 }, |
| | 3 | 253 | | { 530241, 15 }, |
| | 3 | 254 | | { 231405, 15 }, |
| | 3 | 255 | | { 250413, 15 }, |
| | 3 | 256 | | { 512304, 15 }, |
| | 3 | 257 | | { 54321, 15 }, |
| | 3 | 258 | | { 524301, 15 }, |
| | 3 | 259 | | { 312405, 15 }, |
| | 3 | 260 | | { 13254, 15 }, |
| | 3 | 261 | | { 130254, 15 }, |
| | 3 | 262 | | { 150243, 15 }, |
| | 3 | 263 | | { 234501, 15 }, |
| | 3 | 264 | | { 14352, 15 }, |
| | 3 | 265 | | { 140352, 15 }, |
| | 3 | 266 | | { 340512, 15 }, |
| | 3 | 267 | | { 314502, 15 }, |
| | 3 | 268 | | { 42351, 15 }, |
| | 3 | 269 | | { 420351, 15 }, |
| | 3 | 270 | | { 52431, 15 }, |
| | 3 | 271 | | { 341205, 15 }, |
| | 3 | 272 | | { 21435, 15 }, |
| | 3 | 273 | | { 25341, 15 }, |
| | 3 | 274 | | { 250341, 15 }, |
| | 3 | 275 | | { 240315, 15 }, |
| | 3 | 276 | | { 320415, 15 }, |
| | 3 | 277 | | { 24531, 15 }, |
| | 3 | 278 | | { 513402, 15 }, |
| | 3 | 279 | | { 520431, 15 }, |
| | 3 | 280 | | { 132504, 15 }, |
| | 3 | 281 | | { 520314, 15 }, |
| | 3 | 282 | | { 134205, 15 }, |
| | 3 | 283 | | { 24315, 15 }, |
| | 3 | 284 | | { 12345, 15 }, |
| | 3 | 285 | | { 142305, 15 }, |
| | 3 | 286 | | { 34251, 15 }, |
| | 3 | 287 | | { 340251, 15 }, |
| | 3 | 288 | | { 31245, 15 }, |
| | 3 | 289 | | { 143502, 15 }, |
| | 3 | 290 | | { 12534, 15 }, |
| | 3 | 291 | | { 510234, 15 }, |
| | 3 | 292 | | { 531240, 16 }, |
| | 3 | 293 | | { 201435, 16 }, |
| | 3 | 294 | | { 231045, 16 }, |
| | 3 | 295 | | { 205413, 16 }, |
| | 3 | 296 | | { 512034, 16 }, |
| | 3 | 297 | | { 524031, 16 }, |
| | 3 | 298 | | { 524310, 16 }, |
| | 3 | 299 | | { 302415, 16 }, |
| | 3 | 300 | | { 312045, 16 }, |
| | 3 | 301 | | { 134250, 16 }, |
| | 3 | 302 | | { 105243, 16 }, |
| | 3 | 303 | | { 234051, 16 }, |
| | 3 | 304 | | { 314052, 16 }, |
| | 3 | 305 | | { 142350, 16 }, |
| | 3 | 306 | | { 342510, 16 }, |
| | 3 | 307 | | { 314520, 16 }, |
| | 3 | 308 | | { 342051, 16 }, |
| | 3 | 309 | | { 502431, 16 }, |
| | 3 | 310 | | { 341250, 16 }, |
| | 3 | 311 | | { 251340, 16 }, |
| | 3 | 312 | | { 204315, 16 }, |
| | 3 | 313 | | { 503412, 16 }, |
| | 3 | 314 | | { 513042, 16 }, |
| | 3 | 315 | | { 132540, 16 }, |
| | 3 | 316 | | { 104235, 16 }, |
| | 3 | 317 | | { 142035, 16 }, |
| | 3 | 318 | | { 103542, 16 }, |
| | 3 | 319 | | { 143052, 16 }, |
| | 3 | 320 | | { 501234, 16 }, |
| | 3 | 321 | | { 531204, 17 }, |
| | 3 | 322 | | { 210435, 17 }, |
| | 3 | 323 | | { 25413, 17 }, |
| | 3 | 324 | | { 215403, 17 }, |
| | 3 | 325 | | { 32415, 17 }, |
| | 3 | 326 | | { 15243, 17 }, |
| | 3 | 327 | | { 145203, 17 }, |
| | 3 | 328 | | { 342501, 17 }, |
| | 3 | 329 | | { 310524, 17 }, |
| | 3 | 330 | | { 532401, 17 }, |
| | 3 | 331 | | { 251304, 17 }, |
| | 3 | 332 | | { 214305, 17 }, |
| | 3 | 333 | | { 53412, 17 }, |
| | 3 | 334 | | { 530412, 17 }, |
| | 3 | 335 | | { 13542, 17 }, |
| | 3 | 336 | | { 130542, 17 }, |
| | 3 | 337 | | { 14235, 17 }, |
| | 3 | 338 | | { 140235, 17 }, |
| | 3 | 339 | | { 42135, 17 }, |
| | 3 | 340 | | { 43152, 17 }, |
| | 3 | 341 | | { 51234, 17 }, |
| | 3 | 342 | | { 531024, 18 }, |
| | 3 | 343 | | { 215430, 18 }, |
| | 3 | 344 | | { 425013, 18 }, |
| | 3 | 345 | | { 215043, 18 }, |
| | 3 | 346 | | { 432015, 18 }, |
| | 3 | 347 | | { 145023, 18 }, |
| | 3 | 348 | | { 145230, 18 }, |
| | 3 | 349 | | { 302541, 18 }, |
| | 3 | 350 | | { 301524, 18 }, |
| | 3 | 351 | | { 532041, 18 }, |
| | 3 | 352 | | { 532410, 18 }, |
| | 3 | 353 | | { 201354, 18 }, |
| | 3 | 354 | | { 251034, 18 }, |
| | 3 | 355 | | { 214035, 18 }, |
| | 3 | 356 | | { 214350, 18 }, |
| | 3 | 357 | | { 453012, 18 }, |
| | 3 | 358 | | { 402135, 18 }, |
| | 3 | 359 | | { 403152, 18 }, |
| | 3 | 360 | | { 31524, 19 }, |
| | 3 | 361 | | { 425103, 19 }, |
| | 3 | 362 | | { 432105, 19 }, |
| | 3 | 363 | | { 45123, 19 }, |
| | 3 | 364 | | { 32541, 19 }, |
| | 3 | 365 | | { 320541, 19 }, |
| | 3 | 366 | | { 321504, 19 }, |
| | 3 | 367 | | { 21354, 19 }, |
| | 3 | 368 | | { 210354, 19 }, |
| | 3 | 369 | | { 453102, 19 }, |
| | 3 | 370 | | { 420135, 19 }, |
| | 3 | 371 | | { 430152, 19 }, |
| | 3 | 372 | | { 405123, 20 }, |
| | 3 | 373 | | { 425130, 20 }, |
| | 3 | 374 | | { 432150, 20 }, |
| | 3 | 375 | | { 321540, 20 }, |
| | 3 | 376 | | { 321054, 20 }, |
| | 3 | 377 | | { 453120, 20 }, |
| | 3 | 378 | | { 450123, 21 } |
| | 3 | 379 | | }; |
| | | 380 | | |
| | | 381 | | /// <summary> |
| | | 382 | | /// Time complexity - O(1) |
| | | 383 | | /// Space complexity - O(1) |
| | | 384 | | /// </summary> |
| | | 385 | | /// <param name="board"></param> |
| | | 386 | | /// <returns></returns> |
| | | 387 | | public int SlidingPuzzle(int[][] board) |
| | 3 | 388 | | { |
| | 3 | 389 | | var id = 0; |
| | | 390 | | |
| | 18 | 391 | | for (var i = 0; i < 2; i++) |
| | 6 | 392 | | { |
| | 48 | 393 | | for (var j = 0; j < 3; j++) |
| | 18 | 394 | | { |
| | 18 | 395 | | id = (id * 10) + board[i][j]; |
| | 18 | 396 | | } |
| | 6 | 397 | | } |
| | | 398 | | |
| | 3 | 399 | | return _movesDictionary.GetValueOrDefault(id, -1); |
| | 3 | 400 | | } |
| | | 401 | | } |