16.el

;;;; Advent of Code 2020
;;;; 16 Dec
;;;; jens.jensen@stfc.ac.uk


;;; (solve1 +classes-test+ +tickets-test+)
;;; => 71
;;;
;;; My ticket is not counted:
;;; (time (solve1 +classes-input+ (cdr +tickets-input+)))
;;; => (0.009371 . ...)


(defvar +classes-input+
"departure location: 29-458 or 484-956
departure station: 40-723 or 738-960
departure platform: 30-759 or 784-956
departure track: 37-608 or 623-964
departure date: 31-664 or 685-950
departure time: 27-498 or 508-959
arrival location: 36-245 or 269-961
arrival station: 35-808 or 814-973
arrival platform: 40-831 or 856-951
arrival track: 36-857 or 875-971
class: 43-161 or 167-963
duration: 25-75 or 91-966
price: 37-708 or 724-972
route: 39-370 or 396-971
row: 47-280 or 299-949
seat: 41-105 or 125-952
train: 43-351 or 359-966
type: 34-575 or 586-965
wagon: 27-397 or 420-953
zone: 48-206 or 226-965
"
"Input classes as a single string")

(defvar +classes-test+
"class: 1-3 or 5-7
row: 6-11 or 33-44
seat: 13-40 or 45-50
"
"Test classes as a single string")


(defvar +classes-test2+
"class: 0-1 or 4-19
row: 0-5 or 8-19
seat: 0-13 or 16-19
"
"Second set of test data for classes")


;;; (parse-ticket-ranges +classes-test+)
;;; => ((seat (13 . 40) (45 . 50)) (row (6 . 11) (33 . 44)) (class (1 . 3) (5 . 7)))


(defun parse-ticket-ranges (data-string)
  "Parse ranges strings, returning a list of (name (lo1 . up1) (lo2 . up2))"
  (let* ((result nil)
	 (pos 0))		      ;starting pos for parsing string
    (while (string-match "^\\([a-z ]+\\): \\([0-9]+\\)-\\([0-9]+\\) or \\([0-9]+\\)-\\([0-9]+\\)$" data-string pos)
      (let ((name (match-string 1 data-string))
	    (numbers (mapcar (lambda (k) (string-to-int (match-string k data-string))) '(2 3 4 5))))

	;; Advance to next (or at least past current)
	(setq pos (+ pos (length (match-string 0 data-string))))
	;; For fun, let's use a symbol as the key
	;; Note it needs to use #'intern and not #'make-symbol as
	;; the latter makes symbols that are uninterned
	(push
	 (list (intern (replace-regexp-in-string " " "-" name))
	       ;; First interval, lower upper
	       (cons (nth 0 numbers) (nth 1 numbers))
	       ;; Second interval
	       (cons (nth 2 numbers) (nth 3 numbers)))
	 result)))
    result))



(defun ticket-fail1 (ticket intervals)
  "Check a single ticket against classes, returning a list of invalid numbers in the ticket"
  (remove-if (lambda (ticket-entry)
	       ;; See if ticket-entry is in any interval
	       (find-if (lambda (intv) (<= (car intv) ticket-entry (cdr intv))) intervals))
	     ticket))




(defun solve1 (class-string tickets)
  (let* ((classes (parse-ticket-ranges class-string))
	 ;; collect just the intervals; ignore the category
	 (intervals (mapcan #'cdr classes)))
    (apply #'+ (mapcan (lambda (ticket) (ticket-fail1 ticket intervals)) tickets))))



(defun solve2 (class-string tickets)
  (let* ((my-ticket (car tickets))
	 (your-tickets (cdr tickets))
	 (classes (parse-ticket-ranges class-string))
	 (intervals (mapcan #'cdr classes))
	 (valid (remove-if (lambda (ticket) (ticket-fail1 ticket intervals)) your-tickets))
	 ;; Transpose is like matrix transpose; puts all the cars
	 ;; together, then all the cadrs together, then caddrs etc.
	 (transposed-tickets (transpose valid))
	 (matches
	  (simple-eliminate
	   (mapcar (lambda (numbers)
		     "Go through each of the transposed rows (ie same pos in every ticket), returning the symbols of classes consistent with all numbers"
		     (classpass classes numbers))
		   transposed-tickets))))
    ;; sanity check
    (unless (eql (length matches) (length my-ticket))
      (error "Got %d matches but tickets have %d positions" (length matches) (length my-ticket)))
    ;; now we can calculate the solution - note this won't work on the
    ;; test data because they have no entries with "departure" in them
    (calculate-solution matches my-ticket)))




;;; (transpose '((a b c)  (d e  f) (g h i)))
;;; => ((a d g) (b e h) (c f i))

(defun transpose (list-of-lists)
  "Transpose list of lists (as in matrix transpose).  This implementation assumes all (sub)lists have the same length"
  ;; This seems a bit hacky; there must be a better way; but it works
  ;; for some definition of works
  (let* ((len (length (car list-of-lists)))
	 (iota (loop for i below len collect i)))
    (mapcar (lambda (idx)
	      (mapcar (lambda (lst) (nth idx lst)) list-of-lists))
	    iota)))



;;; This is a bit like the #'ticket-fail1 in implementation.
;;; These should be given more sensible names, but given (say)
;;; (seat (0 . 13) (16 . 19))
;;; the accessors of the elements are:
;;; name -> car
;;; first intv. lower -> caadr
;;; first intv. upper -> cdadr
;;; second intv lower -> caaddr
;;; second intv upper -> cdaddr
;;;
;;; (solve2 +classes-test2+ +tickets-test2+)
;;; => ((row) (row class) (seat row class))
;;;
;;; This means the first must be row, the second must be class
;;; because it can't be row, and the third must be seat.


(defun classpass (classes numbers)
  "Given classes (as returned by #'parse-ticket-ranges), and a set (list) of numbers, return a list of symbols identifying classes consistent with all given numbers"
  ;; Keep just the symbols from the relevant classes
  (mapcar #'car
	  (remove-if (lambda (class)
			   (find-if (lambda (num)
				      ;; Is there a number not in one or other interval?
				      ;; See comment above for access to class
				      (not (or (<= (caadr class) num (cdadr class))
					       (<= (caaddr class) num (cdaddr class)))))
				    numbers) )
			 classes)))



;;; There are two ways to solve the remaining cases.
;;; (solve2 +classes-test2+ +tickets-test2+)
;;; => ((row) (row class) (seat row class))
;;;
;;; The simple way is to look for unique matches like
;;; first is row, above, and then eliminate from the rest.
;;;
;;; The more sophisticated version looks at it like a bipartite graph,
;;; and looks for a maximal matching between both sides (historically
;;; called "the marriage problem" as it imagined matching N men with N
;;; women.)
;;;
;;; (simple-eliminate (list (list 'row) (list 'row 'class) (list 'seat 'row 'class)))
;;; => ((seat . 2) (class . 1) (row . 0))

(defun simple-eliminate (stuff)
  "Given a list of lists of not-null symbols, return an alist of (symbol . nth) where the nth entry contains the symbol and all symbols and entries are matched.  The input is modified."
  (let ((result nil)
	(todo (length stuff)))
    ;; Anaphoric while is defined in util.el in the same repo.
    ;; The lambda is a faster find-list-with-one-element as long as
    ;; this element is not nil.
    (awhile (position-if (lambda (sublist) (and (car sublist) (endp (cdr sublist)))) stuff)
	    (let ((entry (car (nth it stuff))))
	      (push (cons entry it) result)
	      ;; Now delete from all sublists.  We need to use a
	      ;; counter so we have a *place* to work with (it is not
	      ;; sufficient to modify the sublist alone, we must
	      ;; modify the outer list).
	      (dotimes (ctr todo)
		(setf (nth ctr stuff) (delete entry (nth ctr stuff))))))
    result))



(defun calculate-solution (matches my-ticket)
  "Calculate the product of the values in my-ticket at positions identified by symbols in matches beginning with 'departure"
  ;;; It would have made sense to keep the symbols as strings;
  ;;; but never mind.
  (let ((product 1)
	(factors 0))			; count how many multiplications
    (dolist (entry matches)
      (when (string-match "^departure" (symbol-name (car entry)))
	(setq product (* product (nth (cdr entry) my-ticket))
	      factors (1+ factors))))

    (unless (eql factors 6)
      (error "expected 6 factors, got %d" factors))
    product))







;;; Test data; "my" ticket is the first one

(defvar +tickets-test+ '(
(7 1 14)
(7 3 47)
(40 4 50)
(55 2 20)
(38 6 12)
))


(defvar +tickets-test2+ '(
(11 12 13)
(3 9 18)
(15 1 5)
(5 14 9))
"Second set of test data for tickets")


;;; Ticket data translated with Emacs macros.  "My" ticket is the first

(defvar +tickets-input+ '((61 151 59 101 173 71 103 167 127 157 137 73 181 97 179 149 131 139 67 53)
(136 368 517 218 187 318 185 172 146 646 804 747 816 625 695 701 420 588 167 302)
(144 452 191 495 196 652 878 605 607 61 932 897 539 82 456 806 587 595 153 168)
(517 981 569 738 886 608 935 882 943 627 884 644 228 698 640 53 748 570 880 322)
(65 428 312 692 61 465 626 312 644 645 539 189 485 182 310 555 442 493 550 275)
(701 547 434 796 278 451 179 397 233 645 741 512 442 800 693 213 188 429 654 707)
(898 573 456 132 190 898 705 447 875 160 688 592 627 520 434 81 517 634 240 185)
(155 433 198 917 513 425 143 149 421 131 815 13 69 887 928 451 497 923 623 347)
(908 896 430 539 532 406 439 75 857 134 589 631 552 541 633 933 522 557 807 917)
(367 397 712 343 276 195 334 131 137 881 884 912 197 548 817 744 54 226 457 899)
(340 453 916 915 430 487 816 543 485 712 703 899 638 756 431 649 364 925 238 815)
(525 70 427 894 279 430 792 365 278 946 624 568 371 61 453 595 324 947 598 104)
(986 444 243 741 822 745 484 878 457 486 937 368 746 652 126 589 907 317 828 741)
(171 830 687 65 815 368 508 799 71 230 560 595 364 303 312 757 112 274 597 881)
(917 135 661 130 898 699 618 58 206 73 149 488 458 818 69 803 572 328 888 75)
(270 133 228 458 519 56 425 450 277 750 365 538 591 522 925 201 533 982 857 190)
(810 599 315 529 515 898 857 605 92 438 629 533 899 491 360 603 537 458 542 597)
(307 128 930 489 156 323 924 900 309 216 101 127 312 647 605 491 237 523 746 875)
(632 660 660 701 700 106 169 144 341 625 432 196 799 880 808 944 443 200 341 750)
(349 881 943 793 541 772 643 171 540 572 647 55 882 569 934 365 944 199 278 568)
(703 755 639 929 140 196 897 235 342 79 360 370 302 314 818 786 565 535 186 444)
(936 458 393 624 509 563 540 830 788 902 200 628 896 917 795 95 496 332 941 308)
(154 234 305 793 927 947 632 661 367 271 273 205 527 638 151 547 285 806 186 328)
(641 530 616 660 626 274 368 171 280 149 269 456 658 336 306 194 659 102 318 149)
(322 72 125 138 550 365 688 280 442 303 491 509 136 696 996 235 202 704 334 913)
(640 571 170 700 803 650 592 545 421 703 600 638 590 242 316 203 3 531 906 233)
(424 899 571 333 226 66 159 698 326 330 62 662 140 191 933 742 755 478 349 99)
(645 790 316 205 637 935 187 700 565 485 746 947 130 188 436 726 311 827 309 58)
(153 200 307 361 169 634 608 312 228 163 313 654 520 511 527 705 300 173 306 433)
(125 56 770 177 237 447 425 55 557 192 275 652 160 568 495 508 525 100 487 588)
(877 457 275 799 205 889 890 304 568 893 237 825 597 202 911 175 917 164 337 822)
(312 306 427 893 562 326 904 931 703 693 946 71 181 631 328 566 552 190 750 709)
(91 137 910 193 277 702 142 457 562 335 228 568 672 195 349 139 759 754 946 57)
(548 892 303 808 883 514 69 705 942 615 128 822 514 366 54 934 554 420 433 926)
(306 518 931 549 652 792 282 808 157 752 60 857 341 104 632 202 806 98 336 940)
(144 991 568 185 756 367 893 695 784 631 901 797 607 69 545 696 369 944 948 641)
(60 542 350 690 178 793 273 322 688 321 719 433 592 67 518 808 449 758 180 447)
(901 740 339 828 898 913 895 284 93 794 789 894 529 238 75 439 519 797 54 890)
(301 314 556 624 202 207 161 277 140 138 330 740 908 553 190 432 99 532 789 54)
(534 67 160 994 129 272 550 599 657 630 786 556 626 319 245 692 64 948 397 532)
(518 545 351 652 920 142 105 706 185 167 268 549 540 184 140 347 597 830 653 753)
(275 75 743 916 512 918 162 805 150 798 797 178 67 935 603 300 94 494 491 452)
(555 322 542 648 363 787 747 747 909 245 305 203 455 758 920 110 349 150 451 315)
(640 309 891 542 541 519 69 720 699 435 799 131 699 686 948 541 520 703 529 696)
(918 924 201 345 458 359 821 535 528 431 164 93 563 497 657 187 606 102 325 897)
(154 877 828 160 346 675 144 300 304 174 605 708 437 831 934 234 234 911 550 793)
(428 128 570 341 530 891 303 184 366 752 485 573 156 277 335 104 217 202 174 149)
(500 558 336 927 881 135 640 440 931 242 648 304 338 235 895 232 126 61 308 551)
(201 899 52 447 175 624 677 518 519 915 343 788 429 664 647 233 420 276 655 490)
(396 884 892 744 877 186 988 203 639 103 143 181 900 510 346 556 631 788 742 177)
(630 534 685 517 134 590 908 627 370 525 541 907 320 807 302 186 706 340 815 247)
(791 490 78 232 73 273 890 589 543 271 655 169 180 530 441 137 629 918 278 920)
(814 0 436 661 362 458 497 787 72 318 900 341 190 130 897 896 487 602 95 904)
(918 179 141 508 886 99 307 894 686 634 641 318 546 232 563 165 543 885 705 929)
(652 807 144 143 642 265 420 887 55 51 157 513 748 169 420 427 651 692 880 937)
(318 565 305 929 754 587 318 308 306 825 568 457 72 218 146 805 160 342 269 70)
(555 688 323 557 816 651 229 491 237 795 694 517 931 827 629 586 150 229 108 663)
(907 230 149 455 109 536 910 601 801 548 346 942 159 125 158 59 74 174 446 496)
(396 756 177 597 157 940 802 337 122 623 795 938 883 746 397 227 741 70 900 55)
(536 159 803 195 336 426 228 888 434 911 887 753 888 735 309 185 876 920 799 623)
(280 920 396 155 202 367 656 454 454 875 324 24 240 562 885 821 493 519 702 142)
(491 199 150 134 433 186 949 200 101 97 546 152 706 788 337 56 760 366 145 857)
(644 528 644 422 752 165 351 593 549 347 941 243 244 512 757 537 99 626 905 804)
(631 901 747 424 904 510 206 99 594 820 180 910 357 171 231 488 59 328 805 656)
(229 923 194 517 656 364 74 485 99 804 943 190 946 343 573 751 392 819 420 236)
(616 823 922 633 149 746 565 558 322 593 319 897 695 496 914 568 552 511 94 587)
(119 568 129 320 302 305 804 554 232 647 303 194 923 891 915 744 485 551 540 68)
(74 336 432 197 715 923 914 527 278 660 910 53 692 452 422 513 568 531 650 944)
(787 604 243 646 429 56 73 546 553 883 170 883 432 200 634 701 920 22 54 896)
(318 271 875 590 360 445 177 63 999 154 746 637 535 329 92 892 949 204 442 435)
(51 558 155 421 441 325 920 568 820 300 804 537 544 423 74 231 91 616 245 312)
(659 652 941 431 349 351 50 662 520 646 305 642 96 490 350 697 671 637 495 797)
(776 131 949 887 272 457 910 642 940 425 702 176 746 510 271 245 885 928 886 562)
(313 420 594 938 946 571 193 999 938 534 161 100 607 136 101 894 934 595 561 590)
(269 745 143 347 305 593 722 69 487 662 60 137 569 240 653 71 590 891 648 632)
(542 623 629 806 515 178 898 230 496 143 748 509 485 604 518 445 918 981 818 626)
(706 303 536 635 196 190 642 884 300 55 179 920 813 634 520 328 796 189 560 101)
(239 542 116 685 104 801 759 52 567 436 322 745 628 487 687 520 203 856 191 641)
(332 748 664 896 929 593 740 881 318 654 427 148 7 235 939 205 422 348 128 800)
(919 553 103 430 426 727 437 663 368 368 795 103 912 751 933 922 361 492 231 516)
(231 586 567 204 101 574 762 167 567 567 161 568 317 934 603 510 68 655 892 907)
(491 273 431 135 161 192 930 484 167 361 396 197 247 830 938 454 939 363 605 931)
(339 888 500 830 328 630 629 750 273 300 279 603 562 103 57 277 127 342 309 306)
(733 68 884 341 650 602 804 656 307 891 551 789 201 485 185 488 69 188 183 600)
(525 601 168 649 235 519 922 453 130 193 87 105 529 943 799 880 898 788 320 56)
(822 164 814 195 519 700 546 896 595 94 916 492 457 745 491 919 597 278 67 894)
(703 310 529 551 898 564 857 924 915 538 530 61 529 788 920 819 730 314 493 699)
(497 337 168 443 698 502 911 496 700 800 814 905 422 62 493 202 881 820 430 891)
(185 794 689 155 191 797 131 103 163 91 897 602 902 154 520 927 686 447 364 277)
(927 607 746 440 322 752 202 596 427 101 194 22 346 630 127 128 752 947 561 508)
(159 513 441 763 644 856 146 698 527 595 239 439 178 918 142 600 149 494 820 552)
(343 557 340 70 452 655 381 883 785 137 130 908 496 653 877 894 940 791 151 433)
(169 586 177 757 332 717 367 540 826 536 815 750 542 800 520 792 831 364 324 902)
(935 516 687 946 99 337 447 625 936 422 351 518 79 661 149 826 184 457 73 434)
(744 289 881 568 484 703 640 334 520 917 828 133 199 328 304 137 345 370 560 439)
(804 487 367 273 67 239 739 587 892 697 158 508 929 143 523 909 418 637 184 135)
(297 627 931 235 828 324 941 586 703 520 934 634 423 439 941 158 67 180 883 902)
(432 155 443 557 254 311 340 450 807 239 277 243 628 817 789 689 591 554 696 517)
(307 73 278 429 881 197 328 792 900 918 882 332 105 740 58 758 933 195 92 81)
(697 759 167 816 537 430 875 444 790 943 498 649 144 525 655 359 463 909 324 573)
(370 883 875 67 428 97 206 143 518 124 920 513 439 201 918 179 791 176 650 641)
(792 63 139 564 738 520 175 520 365 591 694 932 631 249 887 438 103 946 174 98)
(945 909 559 597 605 270 928 692 881 149 366 571 703 754 784 744 572 898 495 162)
(754 316 191 157 704 153 111 551 883 535 362 800 925 130 929 949 425 686 91 923)
(551 440 753 714 104 749 691 445 143 340 427 555 277 167 758 606 300 305 314 302)
(433 604 649 372 751 889 568 305 654 160 194 536 921 930 573 337 230 552 303 817)
(568 926 140 332 144 183 724 924 313 935 132 935 795 535 798 823 146 201 591 233)
(351 605 724 662 56 704 443 562 896 787 347 234 793 816 494 561 659 898 552 454)
(857 893 188 127 184 93 562 795 125 490 54 243 361 943 276 348 988 818 103 540)
(308 787 793 232 426 273 704 397 740 907 830 311 126 100 985 542 628 636 157 485)
(650 551 594 909 534 514 277 554 745 432 569 494 582 230 590 922 750 562 126 311)
(814 904 444 204 821 160 492 205 324 489 792 912 699 454 828 341 983 275 830 187)
(637 924 804 175 948 515 211 604 624 827 746 820 798 742 485 451 785 488 184 100)
(153 208 199 827 200 56 530 185 655 821 177 700 148 170 535 337 707 900 343 521)
(192 878 310 319 922 133 898 368 794 804 898 96 311 622 787 894 564 690 589 942)
(242 899 820 143 58 623 811 52 661 342 702 562 878 146 538 510 307 206 795 900)
(928 893 947 827 895 161 275 266 99 338 882 930 227 445 129 50 192 626 337 906)
(756 554 564 101 96 287 198 800 192 92 798 639 687 878 932 321 785 694 153 631)
(789 743 557 565 915 188 481 740 538 422 159 625 70 270 660 143 139 695 523 701)
(437 657 397 336 698 592 329 175 452 913 492 816 492 478 313 923 915 181 819 645)
(926 248 489 490 180 526 273 91 819 515 742 875 65 875 62 307 439 930 701 442)
(787 892 816 592 332 299 331 786 151 547 161 755 798 95 572 235 499 567 644 311)
(754 125 490 559 71 553 514 279 397 437 929 5 204 327 228 132 234 340 560 633)
(913 87 426 522 242 240 184 193 708 750 510 558 697 103 151 651 625 332 948 571)
(300 427 555 241 423 949 59 230 339 590 685 806 647 914 100 630 544 213 71 100)
(755 343 926 350 822 445 943 693 932 200 905 97 129 664 159 916 251 450 557 589)
(698 54 529 201 71 55 693 187 488 24 607 915 456 448 179 489 454 160 876 545)
(437 756 54 565 445 901 194 206 945 821 349 59 696 496 902 532 166 160 633 150)
(101 177 158 698 165 928 572 364 60 545 547 554 706 350 319 200 95 97 327 697)
(51 68 223 67 883 827 533 432 949 643 497 906 519 66 312 593 188 97 635 66)
(306 98 918 128 664 184 428 140 181 492 758 325 291 922 590 441 231 878 562 789)
(468 541 235 433 334 946 192 97 449 940 168 61 495 155 560 639 657 825 587 948)
(451 541 754 99 586 534 692 19 132 758 441 366 929 531 420 690 633 876 178 532)
(553 331 320 193 887 433 104 817 241 374 91 700 708 498 269 708 151 269 635 739)
(630 824 178 166 829 645 68 339 397 747 103 132 857 243 596 204 690 97 898 335)
(550 741 634 426 58 381 934 363 456 895 345 487 898 703 99 906 528 498 635 360)
(907 934 498 698 793 810 691 275 423 238 313 438 575 425 141 563 322 884 135 201)
(14 330 588 105 146 173 309 897 59 176 334 891 785 656 492 315 571 426 104 795)
(153 876 887 321 657 931 855 510 362 333 556 92 64 591 180 641 54 179 931 910)
(361 328 275 565 359 532 894 133 61 567 701 632 470 67 509 806 626 747 911 271)
(2 198 322 698 608 447 817 454 532 68 888 540 690 447 434 921 949 705 946 97)
(182 361 485 348 368 922 52 799 433 187 298 369 238 168 693 797 156 631 200 936)
(754 553 559 545 685 191 490 634 589 539 392 879 128 105 701 509 549 815 511 687)
(882 564 261 156 564 655 455 908 739 359 137 516 485 426 904 933 597 307 349 660)
(419 896 64 802 443 543 804 300 746 914 793 593 426 314 489 803 929 743 275 59)
(171 636 681 93 927 315 520 587 168 694 50 130 333 441 795 628 702 202 68 920)
(139 738 164 895 128 344 806 653 438 887 136 939 351 458 361 239 746 102 510 594)
(921 911 367 799 548 897 51 122 366 934 929 229 625 157 685 945 130 513 916 367)
(947 195 626 827 707 535 439 700 707 326 657 455 109 179 147 450 599 96 690 159)
(438 95 521 520 937 226 794 364 522 127 883 645 424 423 524 704 312 917 1 344)
(947 635 455 738 814 740 422 450 793 138 519 988 232 947 792 64 426 65 663 428)
(840 367 447 188 909 333 130 245 927 241 73 315 574 173 229 325 273 508 878 689)
(882 143 361 90 309 447 909 929 330 234 509 363 743 50 931 756 336 603 516 332)
(129 829 154 143 646 350 105 155 524 443 171 65 338 345 336 742 302 644 982 688)
(575 739 805 347 944 747 308 509 686 569 928 203 757 92 436 912 822 281 205 808)
(744 710 565 141 237 67 694 569 147 434 664 949 700 528 820 623 337 597 68 340)
(719 185 486 550 369 316 831 175 420 632 490 629 899 364 912 485 923 657 61 646)
(885 276 511 745 789 313 400 545 573 708 687 650 72 692 876 625 202 823 750 608)
(74 930 695 875 635 608 335 658 642 689 227 657 743 16 896 142 944 795 167 525)
(423 831 603 795 452 351 794 238 857 97 606 360 735 426 426 895 931 336 514 315)
(902 227 487 754 520 177 98 191 316 332 745 738 502 645 828 240 148 826 703 541)
(136 173 317 265 640 348 653 894 75 686 563 125 949 443 641 183 634 104 650 334)
(191 628 943 661 808 657 645 160 316 148 316 637 166 606 652 344 277 943 565 448)
(370 949 693 569 147 938 204 926 796 700 880 437 328 891 172 308 5 100 635 145)
(498 304 533 453 446 52 184 310 634 527 933 59 405 913 650 624 545 521 59 446)
(451 14 454 313 143 799 643 784 485 690 651 58 565 938 330 742 300 756 193 556)
(799 103 882 650 785 603 820 317 636 453 111 593 626 902 630 795 638 928 534 527)
(303 134 527 820 145 127 548 825 200 232 801 573 594 598 920 456 925 723 593 341)
(829 540 461 605 702 534 785 237 587 155 635 143 176 489 930 205 126 705 228 320)
(915 144 484 559 142 804 158 76 237 335 921 660 531 370 194 457 891 660 627 508)
(426 239 910 745 557 805 435 154 431 795 528 856 989 539 206 346 659 231 182 326)
(54 893 815 195 567 142 940 452 628 638 533 319 936 760 547 425 569 695 749 818)
(663 157 244 699 323 129 489 510 93 100 143 821 72 543 549 172 335 648 165 228)
(597 426 936 829 799 315 787 148 98 259 913 497 200 326 344 641 276 278 201 822)
(250 941 689 157 312 639 631 588 572 902 632 334 311 226 921 522 647 240 566 820)
(746 928 535 791 342 51 931 167 637 935 155 655 848 831 926 342 881 882 126 136)
(437 792 745 628 556 69 91 893 161 436 64 877 186 436 533 679 423 184 552 170)
(147 192 755 556 570 199 181 642 103 128 125 549 593 741 934 202 984 435 101 308)
(275 948 568 340 538 947 338 156 541 487 334 336 219 561 738 365 530 188 624 422)
(531 397 664 617 908 57 93 171 149 364 598 148 875 818 199 823 455 128 328 820)
(193 489 794 169 159 365 76 803 75 484 915 634 276 330 229 421 156 98 587 456)
(324 159 6 66 237 458 489 167 887 155 530 934 321 53 226 97 748 605 359 179)
(744 596 339 431 759 453 889 456 441 130 12 485 927 877 498 561 746 545 457 300)
(944 194 517 587 426 489 129 96 136 885 801 788 554 157 457 538 615 154 527 428)
(628 485 820 803 883 203 888 599 204 794 784 564 245 692 606 288 327 906 434 146)
(510 314 660 644 698 568 262 351 359 513 946 361 657 607 56 310 351 884 624 498)
(798 928 439 531 555 159 4 331 742 75 931 790 532 822 425 792 144 196 305 902)
(786 751 749 893 808 91 190 445 944 877 921 887 686 165 97 820 135 234 337 662)
(829 925 635 819 559 748 205 594 803 71 791 319 449 937 203 132 71 386 62 520)
(892 226 631 900 803 172 203 305 495 397 143 175 328 194 72 171 588 130 722 320)
(301 518 630 913 143 548 226 132 184 448 304 229 662 231 608 763 245 906 828 437)
(453 273 189 550 269 600 441 703 125 299 631 759 436 321 882 125 644 263 815 426)
(787 879 590 455 154 203 74 95 334 359 559 314 552 319 513 454 24 299 364 656)
(429 437 322 739 827 230 168 197 708 701 186 441 749 312 635 856 445 777 902 635)
(946 4 831 146 508 326 450 206 492 662 69 98 897 650 658 547 333 889 197 129)
(300 917 642 791 661 825 306 450 278 237 940 943 188 158 138 713 630 946 550 817)
(511 340 588 630 545 554 359 443 269 824 325 639 752 829 128 423 493 936 787 123)
(928 92 807 754 161 280 317 337 877 493 299 546 940 802 820 877 716 143 707 902)
(207 424 789 178 179 552 707 785 275 233 455 598 887 68 921 641 522 754 432 738)
(514 116 60 191 534 633 598 427 327 369 341 54 130 599 347 572 707 337 102 232)
(807 530 347 364 543 330 695 93 901 190 333 603 615 57 648 697 449 320 592 822)
(878 696 303 298 892 366 697 234 754 186 443 572 488 188 172 700 443 935 927 183)
(495 147 901 788 647 197 171 925 745 919 701 941 73 568 542 390 429 912 529 131)
(800 696 330 793 655 914 59 180 447 816 50 321 806 917 58 51 78 900 430 881)
(166 808 924 185 139 428 64 888 659 151 519 336 277 194 91 484 875 488 526 363)
(875 172 904 364 919 794 926 236 915 816 816 135 909 118 595 750 530 925 656 193)
(807 379 919 57 440 741 931 426 307 757 487 940 487 362 485 195 226 623 323 493)
(206 789 424 130 573 831 355 945 60 658 790 368 931 944 548 534 757 942 341 486)
(948 280 664 190 126 560 436 885 571 893 550 785 68 281 159 889 881 312 942 705)
(557 542 818 697 913 351 635 130 801 930 66 946 351 230 170 260 508 93 438 903)
(890 570 314 658 785 245 882 510 325 636 929 322 337 710 923 451 303 550 187 458)
(891 790 943 449 689 549 519 588 2 443 304 160 556 240 553 75 320 275 436 572)
(56 946 556 623 142 930 875 318 686 285 454 562 637 935 152 902 496 704 97 917)
(637 102 294 643 179 522 493 442 546 453 884 185 351 652 178 206 129 341 931 168)
(522 626 821 308 198 547 637 792 984 827 693 456 596 330 73 204 646 234 698 149)
(198 327 324 564 815 904 947 702 798 70 203 758 233 129 647 96 880 269 2 904)
(682 420 455 944 928 168 368 943 947 273 940 556 552 424 924 135 346 324 56 561)
(508 101 190 526 934 622 945 925 341 159 586 549 180 703 437 820 65 368 635 396)
(748 787 876 487 158 589 169 653 905 334 631 637 329 270 338 615 625 324 238 228)
(183 803 751 563 206 204 320 876 13 949 594 647 568 317 750 628 877 155 546 880)
(90 818 606 509 636 172 59 599 818 498 435 229 234 801 904 168 802 315 567 458)
(522 327 105 857 186 641 131 234 821 154 817 887 718 608 232 140 566 598 804 485)
(645 744 827 913 103 602 229 525 569 187 544 163 370 793 450 925 245 510 68 738)
(932 365 93 115 147 237 654 137 50 913 485 92 458 787 342 174 898 58 817 910)
(315 488 205 645 638 699 235 364 663 74 687 597 771 749 896 631 139 532 897 550)
(145 130 336 914 322 76 492 338 359 798 536 64 361 509 917 370 95 586 934 935)
(525 544 796 226 96 572 367 916 652 71 634 745 161 998 591 942 547 344 227 626)
(794 806 486 897 231 361 808 739 183 370 227 192 69 136 560 439 887 109 269 331)
(496 928 270 550 800 179 788 646 197 789 906 511 640 550 904 227 592 81 895 92)
(396 334 738 230 104 929 502 137 302 440 927 175 449 169 304 451 421 559 901 513)
(899 187 303 161 608 545 638 160 496 537 338 426 516 374 66 303 650 430 453 758)
(95 991 554 932 943 95 740 276 323 190 856 697 888 270 498 595 600 786 149 454)
(384 155 54 630 181 230 645 58 540 745 548 520 430 935 155 755 171 571 592 892)
(892 695 529 937 330 605 60 901 520 539 553 330 205 588 538 472 689 753 934 423)
(53 195 67 817 21 625 543 912 368 945 509 183 425 486 367 922 156 829 755 793)
(271 337 271 229 827 947 313 163 548 278 823 186 687 747 59 328 149 897 926 892)))