| 1 | | def drinks_water() -> str: |
| 2 | | pass |
| 1 | import itertools |
| 3 | 2 | |
| 3 | def drinks_water() -> str: |
| 4 | # Solve the puzzle and return the name of the resident who drinks water |
| 5 | solution = solve_puzzle() |
| 6 | for resident in solution: |
| 7 | if resident['drink'] == 'water': |
| 8 | return resident['nationality'] |
| 9 | return '' |
| 4 | 10 | |
| 5 | 11 | def owns_zebra() -> str: |
| 6 | | pass |
| 12 | # Solve the puzzle and return the name of the resident who owns the zebra |
| 13 | solution = solve_puzzle() |
| 14 | for resident in solution: |
| 15 | if resident['pet'] == 'zebra': |
| 16 | return resident['nationality'] |
| 17 | return '' |
| 18 | |
| 19 | def solve_puzzle(): |
| 20 | # Use constraint satisfaction with aggressive pruning |
| 21 | nationalities = ['Englishman', 'Spaniard', 'Ukrainian', 'Norwegian', 'Japanese'] |
| 22 | colors = ['red', 'green', 'ivory', 'yellow', 'blue'] |
| 23 | pets = ['dog', 'snail', 'fox', 'horse', 'zebra'] |
| 24 | drinks = ['coffee', 'tea', 'milk', 'orange juice', 'water'] |
| 25 | hobbies = ['dancing', 'painting', 'reading', 'football', 'chess'] |
| 26 | |
| 27 | # Generate all permutations but apply constraints early to prune |
| 28 | for colors_perm in itertools.permutations(colors): |
| 29 | # Early constraint checks for colors |
| 30 | if not early_color_check(colors_perm): |
| 31 | continue |
| 32 | |
| 33 | for nationalities_perm in itertools.permutations(nationalities): |
| 34 | # Early constraint checks for nationalities |
| 35 | if not early_nationality_check(nationalities_perm, colors_perm): |
| 36 | continue |
| 37 | |
| 38 | for drinks_perm in itertools.permutations(drinks): |
| 39 | # Early constraint checks for drinks |
| 40 | if not early_drink_check(drinks_perm, colors_perm, nationalities_perm): |
| 41 | continue |
| 42 | |
| 43 | for hobbies_perm in itertools.permutations(hobbies): |
| 44 | # Early constraint checks for hobbies |
| 45 | if not early_hobby_check(hobbies_perm, colors_perm, nationalities_perm, drinks_perm): |
| 46 | continue |
| 47 | |
| 48 | for pets_perm in itertools.permutations(pets): |
| 49 | # Create residents |
| 50 | residents = [ |
| 51 | { |
| 52 | 'nationality': nationalities_perm[i], |
| 53 | 'color': colors_perm[i], |
| 54 | 'pet': pets_perm[i], |
| 55 | 'drink': drinks_perm[i], |
| 56 | 'hobby': hobbies_perm[i] |
| 57 | } |
| 58 | for i in range(5) |
| 59 | ] |
| 60 | |
| 61 | # Final constraint check |
| 62 | if check_constraints(residents): |
| 63 | return residents |
| 64 | return [] |
| 65 | |
| 66 | def early_color_check(colors): |
| 67 | # Constraint 6: The green house is immediately to the right of the ivory house |
| 68 | ivory_pos = colors.index('ivory') if 'ivory' in colors else -1 |
| 69 | green_pos = colors.index('green') if 'green' in colors else -1 |
| 70 | |
| 71 | if ivory_pos != -1 and green_pos != -1: |
| 72 | if green_pos != ivory_pos + 1: |
| 73 | return False |
| 74 | |
| 75 | # Green can't be at position 0 (no house to its left) |
| 76 | if colors[0] == 'green': |
| 77 | return False |
| 78 | |
| 79 | # Ivory can't be at position 4 (no house to its right) |
| 80 | if colors[4] == 'ivory': |
| 81 | return False |
| 82 | |
| 83 | return True |
| 84 | |
| 85 | def early_nationality_check(nationalities, colors): |
| 86 | # Constraint 10: Norwegian lives in the first house |
| 87 | if nationalities[0] != 'Norwegian': |
| 88 | return False |
| 89 | |
| 90 | # Constraint 2: The Englishman lives in the red house |
| 91 | english_pos = nationalities.index('Englishman') if 'Englishman' in nationalities else -1 |
| 92 | red_pos = colors.index('red') if 'red' in colors else -1 |
| 93 | |
| 94 | if english_pos != -1 and red_pos != -1: |
| 95 | if english_pos != red_pos: |
| 96 | return False |
| 97 | |
| 98 | # Constraint 15: The Norwegian lives next to the blue house |
| 99 | norwegian_pos = 0 # We know Norwegian is at position 0 |
| 100 | blue_pos = colors.index('blue') if 'blue' in colors else -1 |
| 101 | |
| 102 | if blue_pos != -1: |
| 103 | if abs(norwegian_pos - blue_pos) != 1: |
| 104 | return False |
| 105 | |
| 106 | return True |
| 107 | |
| 108 | def early_drink_check(drinks, colors, nationalities): |
| 109 | # Constraint 9: The person in the middle house drinks milk |
| 110 | if drinks[2] != 'milk': |
| 111 | return False |
| 112 | |
| 113 | # Constraint 4: The person in the green house drinks coffee |
| 114 | green_pos = colors.index('green') if 'green' in colors else -1 |
| 115 | if green_pos != -1: |
| 116 | if drinks[green_pos] != 'coffee': |
| 117 | return False |
| 118 | |
| 119 | # Constraint 5: The Ukrainian drinks tea |
| 120 | ukrainian_pos = nationalities.index('Ukrainian') if 'Ukrainian' in nationalities else -1 |
| 121 | if ukrainian_pos != -1: |
| 122 | if drinks[ukrainian_pos] != 'tea': |
| 123 | return False |
| 124 | |
| 125 | return True |
| 126 | |
| 127 | def early_hobby_check(hobbies, colors, nationalities, drinks): |
| 128 | # Constraint 8: The person in the yellow house is a painter |
| 129 | yellow_pos = colors.index('yellow') if 'yellow' in colors else -1 |
| 130 | if yellow_pos != -1: |
| 131 | if hobbies[yellow_pos] != 'painting': |
| 132 | return False |
| 133 | |
| 134 | # Constraint 14: The Japanese person plays chess |
| 135 | japanese_pos = nationalities.index('Japanese') if 'Japanese' in nationalities else -1 |
| 136 | if japanese_pos != -1: |
| 137 | if hobbies[japanese_pos] != 'chess': |
| 138 | return False |
| 139 | |
| 140 | # Constraint 13: The person who plays football drinks orange juice |
| 141 | football_pos = hobbies.index('football') if 'football' in hobbies else -1 |
| 142 | if football_pos != -1: |
| 143 | if drinks[football_pos] != 'orange juice': |
| 144 | return False |
| 145 | |
| 146 | return True |
| 147 | |
| 148 | def backtrack(solution, nationalities, colors, pets, drinks, hobbies): |
| 149 | # Find the first empty slot |
| 150 | empty_pos = None |
| 151 | empty_attr = None |
| 152 | |
| 153 | for i in range(5): |
| 154 | for attr in ['nationality', 'color', 'pet', 'drink', 'hobby']: |
| 155 | if solution[i][attr] is None: |
| 156 | empty_pos = i |
| 157 | empty_attr = attr |
| 158 | break |
| 159 | if empty_pos is not None: |
| 160 | break |
| 161 | |
| 162 | # If no empty slots, check if solution is valid |
| 163 | if empty_pos is None: |
| 164 | return check_constraints(solution) |
| 165 | |
| 166 | # Get possible values for this attribute |
| 167 | if empty_attr == 'nationality': |
| 168 | values = get_available_values(solution, 'nationality', nationalities) |
| 169 | elif empty_attr == 'color': |
| 170 | values = get_available_values(solution, 'color', colors) |
| 171 | elif empty_attr == 'pet': |
| 172 | values = get_available_values(solution, 'pet', pets) |
| 173 | elif empty_attr == 'drink': |
| 174 | values = get_available_values(solution, 'drink', drinks) |
| 175 | elif empty_attr == 'hobby': |
| 176 | values = get_available_values(solution, 'hobby', hobbies) |
| 177 | |
| 178 | # Try each possible value |
| 179 | for value in values: |
| 180 | solution[empty_pos][empty_attr] = value |
| 181 | |
| 182 | # Early pruning: check if current partial assignment violates any constraints |
| 183 | if partial_constraint_check(solution): |
| 184 | if backtrack(solution, nationalities, colors, pets, drinks, hobbies): |
| 185 | return True |
| 186 | |
| 187 | # Backtrack |
| 188 | solution[empty_pos][empty_attr] = None |
| 189 | |
| 190 | return False |
| 191 | |
| 192 | def get_available_values(solution, attr, all_values): |
| 193 | used_values = set() |
| 194 | for house in solution: |
| 195 | if house[attr] is not None: |
| 196 | used_values.add(house[attr]) |
| 197 | return [v for v in all_values if v not in used_values] |
| 198 | |
| 199 | def partial_constraint_check(solution): |
| 200 | # Check constraints that can be evaluated with partial information |
| 201 | # This helps prune the search space early |
| 202 | |
| 203 | # Constraint 10: Norwegian lives in the first house (already applied) |
| 204 | if solution[0]['nationality'] is not None and solution[0]['nationality'] != 'Norwegian': |
| 205 | return False |
| 206 | |
| 207 | # Constraint 9: Person in the middle house drinks milk (already applied) |
| 208 | if solution[2]['drink'] is not None and solution[2]['drink'] != 'milk': |
| 209 | return False |
| 210 | |
| 211 | # Constraint 6: The green house is immediately to the right of the ivory house |
| 212 | for i in range(4): |
| 213 | if solution[i]['color'] == 'ivory' and solution[i+1]['color'] is not None: |
| 214 | if solution[i+1]['color'] != 'green': |
| 215 | return False |
| 216 | elif solution[i]['color'] == 'green' and solution[i+1]['color'] is not None: |
| 217 | if solution[i]['color'] != 'ivory': |
| 218 | return False |
| 219 | |
| 220 | # Check if green house is at position 0 (can't be, since ivory would need to be at -1) |
| 221 | if solution[0]['color'] == 'green': |
| 222 | return False |
| 223 | |
| 224 | # Check if ivory house is at position 4 (can't be, since green would need to be at 5) |
| 225 | if solution[4]['color'] == 'ivory': |
| 226 | return False |
| 227 | |
| 228 | # Constraint 15: The Norwegian lives next to the blue house |
| 229 | norwegian_pos = None |
| 230 | for i in range(5): |
| 231 | if solution[i]['nationality'] == 'Norwegian': |
| 232 | norwegian_pos = i |
| 233 | break |
| 234 | |
| 235 | if norwegian_pos is not None: |
| 236 | # Check if Norwegian has a neighbor that must be blue |
| 237 | if norwegian_pos > 0 and solution[norwegian_pos-1]['color'] is not None: |
| 238 | if solution[norwegian_pos-1]['color'] != 'blue': |
| 239 | # Check if the other neighbor could be blue |
| 240 | if norwegian_pos < 4 and solution[norwegian_pos+1]['color'] is not None: |
| 241 | if solution[norwegian_pos+1]['color'] != 'blue': |
| 242 | return False |
| 243 | elif norwegian_pos == 4: # Norwegian is at position 4, only left neighbor |
| 244 | return False |
| 245 | elif norwegian_pos < 4 and solution[norwegian_pos+1]['color'] is not None: |
| 246 | if solution[norwegian_pos+1]['color'] != 'blue': |
| 247 | # Check if the other neighbor could be blue |
| 248 | if norwegian_pos > 0 and solution[norwegian_pos-1]['color'] is not None: |
| 249 | if solution[norwegian_pos-1]['color'] != 'blue': |
| 250 | return False |
| 251 | elif norwegian_pos == 0: # Norwegian is at position 0, only right neighbor |
| 252 | return False |
| 253 | |
| 254 | return True |
| 255 | |
| 256 | def check_constraints(residents): |
| 257 | # Constraint 1: There are five houses (implicitly satisfied by our structure) |
| 258 | |
| 259 | # Constraint 2: The Englishman lives in the red house |
| 260 | # Edge Case: Englishman or red house not found |
| 261 | englishman_found = False |
| 262 | for resident in residents: |
| 263 | if resident['nationality'] == 'Englishman' and resident['color'] == 'red': |
| 264 | englishman_found = True |
| 265 | break |
| 266 | if not englishman_found: |
| 267 | return False |
| 268 | |
| 269 | # Constraint 3: The Spaniard owns the dog |
| 270 | # Edge Case: Spaniard or dog not found |
| 271 | spaniard_found = False |
| 272 | for resident in residents: |
| 273 | if resident['nationality'] == 'Spaniard' and resident['pet'] == 'dog': |
| 274 | spaniard_found = True |
| 275 | break |
| 276 | if not spaniard_found: |
| 277 | return False |
| 278 | |
| 279 | # Constraint 4: The person in the green house drinks coffee |
| 280 | # Edge Case: Green house or coffee not found |
| 281 | green_coffee_found = False |
| 282 | for resident in residents: |
| 283 | if resident['color'] == 'green' and resident['drink'] == 'coffee': |
| 284 | green_coffee_found = True |
| 285 | break |
| 286 | if not green_coffee_found: |
| 287 | return False |
| 288 | |
| 289 | # Constraint 5: The Ukrainian drinks tea |
| 290 | # Edge Case: Ukrainian or tea not found |
| 291 | ukrainian_tea_found = False |
| 292 | for resident in residents: |
| 293 | if resident['nationality'] == 'Ukrainian' and resident['drink'] == 'tea': |
| 294 | ukrainian_tea_found = True |
| 295 | break |
| 296 | if not ukrainian_tea_found: |
| 297 | return False |
| 298 | |
| 299 | # Constraint 6: The green house is immediately to the right of the ivory house |
| 300 | # Edge Case: Green or ivory house not found |
| 301 | green_right_of_ivory = False |
| 302 | for i in range(4): # Only check positions 0-3 for ivory (green would be at 1-4) |
| 303 | if residents[i]['color'] == 'ivory' and residents[i+1]['color'] == 'green': |
| 304 | green_right_of_ivory = True |
| 305 | break |
| 306 | if not green_right_of_ivory: |
| 307 | return False |
| 308 | |
| 309 | # Constraint 7: The snail owner likes to go dancing |
| 310 | # Edge Case: Snail or dancing not found |
| 311 | snail_dancing_found = False |
| 312 | for resident in residents: |
| 313 | if resident['pet'] == 'snail' and resident['hobby'] == 'dancing': |
| 314 | snail_dancing_found = True |
| 315 | break |
| 316 | if not snail_dancing_found: |
| 317 | return False |
| 318 | |
| 319 | # Constraint 8: The person in the yellow house is a painter |
| 320 | # Edge Case: Yellow house or painting not found |
| 321 | yellow_painter_found = False |
| 322 | for resident in residents: |
| 323 | if resident['color'] == 'yellow' and resident['hobby'] == 'painting': |
| 324 | yellow_painter_found = True |
| 325 | break |
| 326 | if not yellow_painter_found: |
| 327 | return False |
| 328 | |
| 329 | # Constraint 9: The person in the middle house drinks milk |
| 330 | # Edge Case: Middle house (index 2) doesn't have milk |
| 331 | if residents[2]['drink'] != 'milk': |
| 332 | return False |
| 333 | |
| 334 | # Constraint 10: The Norwegian lives in the first house |
| 335 | # Edge Case: First house (index 0) doesn't have Norwegian |
| 336 | if residents[0]['nationality'] != 'Norwegian': |
| 337 | return False |
| 338 | |
| 339 | # Constraint 11: The person who enjoys reading lives in the house next to the person with the fox |
| 340 | # Edge Case: Reading or fox not found |
| 341 | reading_next_to_fox = False |
| 342 | for i in range(5): |
| 343 | if residents[i]['hobby'] == 'reading': |
| 344 | # Check neighbors |
| 345 | if i > 0 and residents[i-1]['pet'] == 'fox': |
| 346 | reading_next_to_fox = True |
| 347 | break |
| 348 | if i < 4 and residents[i+1]['pet'] == 'fox': |
| 349 | reading_next_to_fox = True |
| 350 | break |
| 351 | if not reading_next_to_fox: |
| 352 | return False |
| 353 | |
| 354 | # Constraint 12: The painter's house is next to the house with the horse |
| 355 | # Edge Case: Painting or horse not found |
| 356 | painter_next_to_horse = False |
| 357 | for i in range(5): |
| 358 | if residents[i]['hobby'] == 'painting': |
| 359 | # Check neighbors |
| 360 | if i > 0 and residents[i-1]['pet'] == 'horse': |
| 361 | painter_next_to_horse = True |
| 362 | break |
| 363 | if i < 4 and residents[i+1]['pet'] == 'horse': |
| 364 | painter_next_to_horse = True |
| 365 | break |
| 366 | if not painter_next_to_horse: |
| 367 | return False |
| 368 | |
| 369 | # Constraint 13: The person who plays football drinks orange juice |
| 370 | # Edge Case: Football or orange juice not found |
| 371 | football_orange_found = False |
| 372 | for resident in residents: |
| 373 | if resident['hobby'] == 'football' and resident['drink'] == 'orange juice': |
| 374 | football_orange_found = True |
| 375 | break |
| 376 | if not football_orange_found: |
| 377 | return False |
| 378 | |
| 379 | # Constraint 14: The Japanese person plays chess |
| 380 | # Edge Case: Japanese or chess not found |
| 381 | japanese_chess_found = False |
| 382 | for resident in residents: |
| 383 | if resident['nationality'] == 'Japanese' and resident['hobby'] == 'chess': |
| 384 | japanese_chess_found = True |
| 385 | break |
| 386 | if not japanese_chess_found: |
| 387 | return False |
| 388 | |
| 389 | # Constraint 15: The Norwegian lives next to the blue house |
| 390 | # Edge Case: Norwegian or blue house not found |
| 391 | norwegian_next_to_blue = False |
| 392 | for i in range(5): |
| 393 | if residents[i]['nationality'] == 'Norwegian': |
| 394 | # Check neighbors |
| 395 | if i > 0 and residents[i-1]['color'] == 'blue': |
| 396 | norwegian_next_to_blue = True |
| 397 | break |
| 398 | if i < 4 and residents[i+1]['color'] == 'blue': |
| 399 | norwegian_next_to_blue = True |
| 400 | break |
| 401 | if not norwegian_next_to_blue: |
| 402 | return False |
| 403 | |
| 404 | # All constraints satisfied |
| 405 | return True |
| 406 | |
| 407 | # Handled Edge Cases: Englishman or red house not found, Spaniard or dog not found, Green house or coffee not found, |
| 408 | # Ukrainian or tea not found, Green or ivory house not found, Snail or dancing not found, Yellow house or painting not found, |
| 409 | # Middle house (index 2) doesn't have milk, First house (index 0) doesn't have Norwegian, Reading or fox not found, |
| 410 | # Painting or horse not found, Football or orange juice not found, Japanese or chess not found, Norwegian or blue house not found |