Skip to content

Instantly share code, notes, and snippets.

@coolcomputery

coolcomputery/part1.txt

Created August 1, 2021 14:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save coolcomputery/c4af0f79f7a2d8a9c774395845058c04 to your computer and use it in GitHub Desktop.
Save coolcomputery/c4af0f79f7a2d8a9c774395845058c04 to your computer and use it in GitHub Desktop.
Download ZIP
5x5: 0x0->3x3cGN <= 17
Raw
part1.txt
stdout:
5x5: 11111x11111 --> ... --> 00011x00011
threshold=17, midstates=[10011x10011, 10011x01011, 10011x00111, 01011x10011, 01011x01011, 01011x00111, 00111x10011, 00111x01011, 00111x00111]
0 1 2 3 4
5 '6 '7 8 9
10 '11 '12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:64 3:492 4:2974 5:14584 6:49562 7:97448 8:95449 9:39425 10:3592 11:1
#reached=303600
D=12
total BFS time=357
'0 '1 '2 3 4
'5 X X 6 7
'8 X X 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:105 4:508 5:2386 6:10441 7:41483 8:143791 9:398056 10:738804 11:744707 12:321693 13:39351 14:530
#reached=2441880
D=15
total BFS time=1638
0 1 2 3 4
'5 6 '7 8 9
'10 11 '12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:72 3:584 4:3458 5:15430 6:48290 7:94393 8:97852 9:40185 10:3323 11:4
#reached=303600
D=12
total BFS time=206
'0 '1 '2 3 4
X '5 X 6 7
X '8 X 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:108 4:548 5:2597 6:11461 7:46124 8:160146 9:432659 10:766050 11:715679 12:276512 13:29742 14:229
#reached=2441880
D=15
total BFS time=1542
0 1 2 3 4
'5 '6 7 8 9
'10 '11 12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:64 3:492 4:2974 5:14584 6:49562 7:97448 8:95449 9:39425 10:3592 11:1
#reached=303600
D=12
total BFS time=188
'0 '1 '2 3 4
X X '5 6 7
X X '8 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:105 4:508 5:2386 6:10441 7:41483 8:143791 9:398056 10:738804 11:744707 12:321693 13:39351 14:530
#reached=2441880
D=15
total BFS time=1522
0 '1 '2 3 4
5 6 7 8 9
10 '11 '12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:72 3:584 4:3458 5:15430 6:48290 7:94393 8:97852 9:40185 10:3323 11:4
#reached=303600
D=12
total BFS time=178
'0 X X 1 2
'3 '4 '5 6 7
'8 X X 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:108 4:548 5:2597 6:11461 7:46124 8:160146 9:432659 10:766050 11:715679 12:276512 13:29742 14:229
#reached=2441880
D=15
total BFS time=1547
'0 1 '2 3 4
5 6 7 8 9
'10 11 '12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:80 3:664 4:3796 5:15962 6:47742 7:92414 8:96736 9:41771 10:4390 11:36
#reached=303600
D=12
total BFS time=269
X '0 X 1 2
'3 '4 '5 6 7
X '8 X 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:104 4:524 5:2548 6:11636 7:47752 8:168062 9:462318 10:835988 11:726280 12:182763 13:3880
#reached=2441880
D=14
total BFS time=1557
'0 '1 2 3 4
5 6 7 8 9
'10 '11 12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:72 3:584 4:3458 5:15430 6:48290 7:94393 8:97852 9:40185 10:3323 11:4
#reached=303600
D=12
total BFS time=221
X X '0 1 2
'3 '4 '5 6 7
X X '8 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:108 4:548 5:2597 6:11461 7:46124 8:160146 9:432659 10:766050 11:715679 12:276512 13:29742 14:229
#reached=2441880
D=15
total BFS time=1566
0 '1 '2 3 4
5 '6 '7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:64 3:492 4:2974 5:14584 6:49562 7:97448 8:95449 9:39425 10:3592 11:1
#reached=303600
D=12
total BFS time=228
'0 X X 1 2
'3 X X 4 5
'6 '7 '8 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:105 4:508 5:2386 6:10441 7:41483 8:143791 9:398056 10:738804 11:744707 12:321693 13:39351 14:530
#reached=2441880
D=15
total BFS time=1557
'0 1 '2 3 4
'5 6 '7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:72 3:584 4:3458 5:15430 6:48290 7:94393 8:97852 9:40185 10:3323 11:4
#reached=303600
D=12
total BFS time=225
X '0 X 1 2
X '3 X 4 5
'6 '7 '8 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:108 4:548 5:2597 6:11461 7:46124 8:160146 9:432659 10:766050 11:715679 12:276512 13:29742 14:229
#reached=2441880
D=15
total BFS time=1557
'0 '1 2 3 4
'5 '6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:64 3:492 4:2974 5:14584 6:49562 7:97448 8:95449 9:39425 10:3592 11:1
#reached=303600
D=12
total BFS time=240
X X '0 1 2
X X '3 4 5
'6 '7 '8 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:105 4:508 5:2386 6:10441 7:41483 8:143791 9:398056 10:738804 11:744707 12:321693 13:39351 14:530
#reached=2441880
D=15
total BFS time=1546
total tree preprocessing time=16508
10011x10011:399432042449
10011x01011:383895895962
10011x00111:399432042449
01011x10011:383895895962
01011x01011:365419870881
01011x00111:383895895962
00111x10011:399432042449
00111x01011:383895895962
00111x00111:399432042449
main midstate=01011x01011
memoizing all scramble actions of...
tree[0][0]: 304 ms
tree[1][0]: 375 ms
tree[2][0]: 373 ms
tree[3][0]: 355 ms
tree[5][0]: 391 ms
tree[6][0]: 305 ms
tree[7][0]: 396 ms
tree[8][0]: 334 ms
total combos to improve=365,419,870,881
memoizing scramble actions: 26 ms
5,13: ncombos=61,932,560
elapsed sec #combos #combos/sec
prefixDepth-->1
prefixDepth-->2
prefixDepth-->3
20.000 21,894,860 1,094,743.000
59.378 61,932,560 1,043,021.995
memoizing scramble actions: 336 ms
6,12: ncombos=8,725,471,146
elapsed sec #combos #combos/sec
20.000 24,178,900 1,208,945.000
prefixDepth-->4
113.137 147,422,308 1,303,042.400
311.769 416,630,731 1,336,344.316
640.000 792,478,583 1,238,247.786
1,118.033 1,442,089,154 1,289,844.892
1,763.632 2,256,625,912 1,279,533.322
2,592.836 3,321,327,622 1,280,963.247
3,620.386 4,507,937,903 1,245,153.943
4,860.000 5,974,277,059 1,229,275.115
6,324.555 7,631,643,592 1,206,668.863
7,298.305 8,725,471,146 1,195,547.616
memoizing scramble actions: 46 ms
6,13: ncombos=185,238,960
elapsed sec #combos #combos/sec
20.000 12,993,302 649,665.100
113.137 76,553,955 676,648.267
289.188 185,238,960 640,548.570
memoizing scramble actions: 1122 ms
7,11: ncombos=67,118,439,920
elapsed sec #combos #combos/sec
20.000 22,498,649 1,124,932.450
113.137 126,090,131 1,114,490.671
311.769 363,388,871 1,165,570.891
640.000 762,487,056 1,191,386.025
1,118.033 1,344,979,663 1,202,987.446
1,763.632 2,230,397,682 1,264,661.609
2,592.836 3,312,302,400 1,277,482.417
3,620.386 4,651,091,776 1,284,694.996
4,860.000 5,918,098,346 1,217,715.709
6,324.555 7,548,929,289 1,193,590.583
8,026.231 9,775,866,334 1,217,989.656
9,976.612 12,480,185,692 1,250,944.278
prefixDepth-->5
12,186.763 15,178,966,908 1,245,529.014
14,667.296 18,087,001,899 1,233,151.762
17,428.425 21,242,775,506 1,218,858.015
20,480.000 24,648,976,749 1,203,563.318
23,831.550 28,923,144,181 1,213,649.309
27,492.311 32,928,435,577 1,197,732.543
31,471.250 37,408,624,067 1,188,660.256
35,777.087 42,013,178,275 1,174,304.053
40,418.317 47,285,618,069 1,169,905.666
45,403.224 52,346,010,107 1,152,913.945
50,739.897 57,989,892,913 1,142,885.507
56,436.243 63,546,735,997 1,125,991.608
60,087.328 67,118,439,920 1,117,014.887
memoizing scramble actions: 321 ms
7,12: ncombos=16,889,859,882
elapsed sec #combos #combos/sec
20.000 12,222,958 611,147.900
113.137 70,970,588 627,297.772
311.769 219,509,826 704,078.423
640.000 460,230,081 719,109.502
1,118.033 851,351,605 761,472.698
1,763.632 1,293,893,620 733,652.837
2,592.836 1,789,680,861 690,240.671
3,620.386 2,594,371,212 716,600.719
4,860.000 3,494,908,840 719,117.045
6,324.555 4,544,153,121 718,493.731
8,026.231 5,708,055,085 711,175.032
9,976.612 7,060,848,542 707,740.117
12,186.764 8,608,314,793 706,365.922
14,667.296 10,254,625,920 699,149.040
17,428.425 12,052,629,119 691,550.104
20,480.000 13,963,521,063 681,812.552
23,831.550 15,930,605,878 668,467.048
25,454.135 16,889,859,882 663,540.909
memoizing scramble actions: 85 ms
7,13: ncombos=358,566,320
elapsed sec #combos #combos/sec
20.000 7,820,864 391,043.200
113.137 40,210,329 355,412.721
311.769 117,605,997 377,221.587
640.000 234,846,691 366,947.955
1,026.632 358,566,320 349,264.702
memoizing scramble actions: 1177 ms
8,10: ncombos=80,870,135,168
elapsed sec #combos #combos/sec
20.000 24,567,897 1,228,394.850
113.137 109,246,305 965,610.764
311.769 250,563,154 803,682.066
640.000 585,825,849 915,352.889
1,118.033 1,023,344,837 915,308.257
1,763.632 1,624,283,404 920,987.714
2,592.836 2,417,311,314 932,303.977
3,620.386 3,451,805,765 953,435.839
4,860.000 4,752,852,876 977,953.267
6,324.555 6,257,624,655 989,417.383
8,026.231 7,798,336,748 971,606.318
9,976.612 9,816,239,030 983,925.107
12,186.763 11,583,150,201 950,469.801
14,667.296 13,626,713,597 929,054.244
17,428.425 16,201,707,182 929,613.960
20,480.000 19,398,370,918 947,186.080
23,831.550 23,020,198,059 965,954.714
27,492.311 26,434,669,296 961,529.545
31,471.250 29,874,560,138 949,265.127
35,777.087 33,622,792,537 939,785.638
40,418.317 37,572,626,296 929,594.033
45,403.224 42,166,195,409 928,704.874
50,739.897 47,061,889,848 927,512.522
56,436.243 51,960,639,091 920,696.282
62,500.000 56,743,662,364 907,898.598
68,938.743 62,110,714,266 900,955.132
75,759.902 67,646,367,705 892,904.636
82,970.761 72,997,039,756 879,792.337
90,578.472 78,122,631,256 862,485.638
94,841.350 80,870,135,168 852,688.571
memoizing scramble actions: 1130 ms
8,11: ncombos=70,257,422,080
elapsed sec #combos #combos/sec
20.000 16,556,436 827,821.800
113.137 76,994,977 680,546.391
311.769 180,219,835 578,055.660
640.000 374,767,634 585,574.428
1,118.033 643,181,765 575,279.768
1,763.632 1,038,457,126 588,817.353
2,592.836 1,550,345,217 597,934.161
3,620.386 2,225,132,591 614,611.975
4,860.000 3,071,876,169 632,073.286
6,324.555 4,072,967,665 643,992.765
8,026.231 5,216,360,181 649,914.036
9,976.612 6,516,189,803 653,146.559
12,186.763 8,124,994,131 666,706.502
14,667.296 9,399,358,815 640,837.876
17,428.425 10,646,523,585 610,871.240
20,480.000 12,445,482,258 607,689.563
23,831.550 14,554,550,521 610,726.139
27,492.311 17,072,361,730 620,986.782
31,471.250 19,803,665,325 629,262.115
35,777.087 22,351,486,331 624,743.047
40,418.317 24,919,487,081 616,539.454
45,403.224 28,002,966,923 616,761.641
50,739.897 31,193,879,596 614,780.113
56,436.243 34,006,240,438 602,560.316
62,500.000 37,912,602,963 606,601.647
68,938.743 41,521,231,288 602,291.679
75,759.902 45,534,023,385 601,030.653
82,970.761 49,341,371,245 594,683.846
90,578.472 53,374,011,997 589,257.147
98,590.060 57,628,994,631 584,531.490
107,012.431 61,525,830,601 574,940.967
115,852.375 65,719,522,988 567,269.536
125,116.574 69,792,366,274 557,818.713
126,325.693 70,257,422,080 556,160.987
memoizing scramble actions: 365 ms
8,12: ncombos=17,679,761,568
elapsed sec #combos #combos/sec
20.000 7,753,983 387,699.150
113.137 40,539,635 358,323.404
311.769 114,547,867 367,412.626
640.000 230,372,873 359,957.614
1,118.033 414,064,709 370,351.062
1,763.632 685,341,559 388,596.691
2,592.836 1,030,577,749 397,471.243
3,620.386 1,481,679,515 409,260.094
4,860.000 2,055,413,460 422,924.580
6,324.555 2,448,565,223 387,152.175
8,026.231 2,951,797,222 367,768.785
9,976.612 3,704,363,085 371,304.716
12,186.763 4,622,426,713 379,298.975
14,667.296 5,507,799,147 375,515.647
17,428.425 6,523,993,750 374,330.655
20,480.000 7,649,716,376 373,521.307
23,831.550 8,655,301,920 363,186.697
27,492.311 10,000,777,751 363,766.355
31,471.250 11,467,564,705 364,382.244
35,777.087 12,935,918,218 361,569.913
40,418.317 14,374,971,057 355,654.865
45,403.224 15,874,024,924 349,623.298
50,739.897 17,361,069,708 342,158.158
52,048.923 17,679,761,568 339,675.839
memoizing scramble actions: 108 ms
8,13: ncombos=375,335,680
elapsed sec #combos #combos/sec
20.000 3,929,721 196,486.050
113.137 26,699,025 235,988.448
311.769 64,413,670 206,607.039
640.000 133,678,789 208,873.108
1,118.033 229,016,349 204,838.631
1,763.632 347,830,445 197,223.936
1,936.568 375,335,680 193,814.872
memoizing scramble actions: 550 ms
9,9: ncombos=19,311,485,178
elapsed sec #combos #combos/sec
20.000 14,953,135 747,656.750
113.137 65,439,810 578,412.102
311.769 149,600,334 479,843.519
640.000 317,449,380 496,014.656
1,118.033 580,002,668 518,770.616
1,763.632 931,790,454 528,336.101
2,592.836 1,397,953,489 539,160.012
3,620.386 2,035,038,696 562,105.448
4,860.000 2,711,818,258 557,987.296
6,324.555 3,504,649,632 554,133.790
8,026.231 4,431,177,078 552,086.911
9,976.612 5,322,291,739 533,476.870
12,186.763 6,515,706,683 534,654.418
14,667.296 8,056,225,053 549,264.503
17,428.425 9,535,397,728 547,117.581
20,480.000 10,859,137,971 530,231.346
23,831.550 12,540,364,819 526,208.527
27,492.311 14,382,405,350 523,142.829
31,471.250 16,102,124,492 511,645.533
35,777.087 17,906,785,626 500,509.883
40,289.956 19,311,485,178 479,312.640
memoizing scramble actions: 1105 ms
9,10: ncombos=34,920,054,748
elapsed sec #combos #combos/sec
20.000 13,586,853 679,342.650
113.137 54,182,721 478,912.478
311.769 122,465,649 392,808.935
640.000 205,713,854 321,427.897
1,118.033 341,471,446 305,421.616
1,763.632 637,169,469 361,282.552
2,592.836 971,083,223 374,525.509
3,620.388 1,321,344,204 364,973.092
4,860.000 1,794,427,211 369,223.706
6,324.555 2,440,549,171 385,884.726
8,026.231 3,155,108,331 393,099.617
9,976.612 4,003,014,046 401,239.824
12,186.763 4,824,654,118 395,892.996
14,667.296 5,824,460,884 397,105.294
17,428.425 6,764,478,339 388,129.067
20,480.000 8,044,843,377 392,814.618
23,831.550 9,074,361,594 380,770.936
27,492.311 10,260,283,023 373,205.549
31,471.250 11,815,235,651 375,429.500
35,777.087 13,629,521,028 380,956.701
40,418.317 15,626,897,639 386,629.103
45,403.224 17,342,508,898 381,966.463
50,739.897 19,004,422,593 374,545.943
56,436.243 21,026,798,667 372,576.159
62,500.000 22,926,018,636 366,816.298
68,938.743 25,271,272,200 366,575.761
75,759.902 27,403,648,506 361,717.053
82,970.761 29,607,975,403 356,848.305
90,578.499 31,871,008,067 351,860.634
98,590.068 33,809,051,833 342,925.535
104,386.817 34,920,054,748 334,525.525
memoizing scramble actions: 999 ms
9,11: ncombos=30,337,441,880
elapsed sec #combos #combos/sec
20.000 9,388,751 469,437.550
113.137 33,474,146 295,872.668
311.769 94,695,229 303,735.230
640.000 139,468,141 217,918.970
1,118.036 253,891,059 227,086.658
1,763.632 447,200,203 253,567.753
2,592.836 666,019,940 256,869.289
3,620.387 927,878,186 256,292.542
4,860.000 1,240,751,899 255,298.745
6,324.555 1,655,117,365 261,697.047
8,026.231 2,207,387,119 275,021.628
9,976.612 2,798,548,767 280,510.936
12,186.763 3,434,305,281 281,806.193
14,667.296 4,084,208,584 278,456.819
17,428.425 4,837,569,538 277,567.797
20,480.000 5,671,398,243 276,923.742
23,831.555 6,675,907,625 280,128.914
27,492.311 7,485,810,082 272,287.407
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at LoopoverBFSImprove.prodperm(LoopoverBFSImprove.java:25)
at LoopoverBFSImprove.scrambleAction(LoopoverBFSImprove.java:45)
at LoopoverBFSImprove.improve(LoopoverBFSImprove.java:183)
at LoopoverBFSImprove.main(LoopoverBFSImprove.java:259)
Process finished with exit code 1
code:
import java.util.*;
/**
* given a start state S and end state E:
* ex. 5x5 Loopover states 11111x11111 and 00011x00011
* along with a list of middle states M[]:
* ex. 00111x00111, 00111x01011, 10011x01011, etc.
* use these midstates to find an upper bound on the God's number of transforming the starting state to the end state
*
* more formally, choose a threshold D
* choose a midstate M[a] to be the "default"
* then go through all scrambles such that naively using the two trees S-->M[a] and M[a]-->E yields a solution of >D moves
* for each scramble:
* for each i!=a, try solving it with the trees S-->M[i] and M[i]-->E until a solution of <=D moves is found
* if a solution is not found, try applying an arbitrary sequence of prefix moves to the scramble,
* and then try solving it with the trees S-->M[i] and M[i]-->E (this time including i==a)
* repeat for all possible prefix sequences of length 1, 2, ... until a short enough solution is found
*/
public class LoopoverBFSImprove {
private static int mod(int n, int k) {
return (n%k+k)%k;
}
private static int[] prodperm(int[] A, int[] B) {
//B is a permutation array
//return [ B[A[i]] for all i]
int[] out=new int[A.length];
for (int i=0; i<A.length; i++)
out[i]=B[A[i]];
return out;
}
private static String boardStr(int[] solvedscrm, int[] scrm, int R, int C) {
int[] display=new int[R*C]; Arrays.fill(display,-1);
for (int i=0; i<scrm.length; i++)
display[scrm[i]]=solvedscrm[i];
StringBuilder out=new StringBuilder();
String form="%"+(R*C<=26?1:3)+"s";
for (int r=0; r<R; r++) {
for (int c=0; c<C; c++)
out.append(String.format(form,display[r*C+c]==-1?".":(R*C<=26?""+(char)('A'+display[r*C+c]):(display[r*C+c]+1))));
out.append('\n');
}
return out.toString();
}
private static int[] scrambleAction(int R, int C, int[] mvseq, int[][] mvactions) {
int[] out=new int[R*C]; for (int i=0; i<R*C; i++) out[i]=i;
for (int mvi:mvseq) out=prodperm(out,mvactions[mvi]);
return out;
}
private int R, C;
private String ststate, enstate;
public LoopoverBFSImprove(int R, int C, String sts, String ens) {
System.out.println(R+"x"+C+": "+sts+" --> ... --> "+ens);
this.R=R; this.C=C;
ststate=sts;
enstate=ens;
}
private boolean improve(int threshold, String[] midstates, boolean[] computeAllScrms) {
//prefix move sequences
int M=0;
for (int c=0; c<ststate.length(); c++)
if (ststate.charAt(c)=='1') M+=2;
int[][] mvs, mvactions, mvreduc;
boolean[][] rcfree0=LoopoverBFS.parseState(ststate);
mvs=new int[M][]; mvactions=new int[M][]; {
int idx=0;
for (int mr=0; mr<R; mr++)
if (rcfree0[0][mr])
for (int s=-1; s<=1; s+=2) {
mvs[idx]=new int[] {0,mr,s};
mvactions[idx]=new int[R*C];
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
mvactions[idx][r*C+c]=r*C+(r==mr?mod(c+s,C):c);
idx++;
}
for (int mc=0; mc<C; mc++)
if (rcfree0[1][mc])
for (int s=-1; s<=1; s+=2) {
mvs[idx]=new int[] {1,mc,s};
mvactions[idx]=new int[R*C];
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
mvactions[idx][r*C+c]=(c==mc?mod(r+s,R):r)*C+c;
idx++;
}
}
mvreduc=LoopoverBFS.mvreduc(mvs);
List<int[]> mvseqs=new ArrayList<>(),
mvseqactions=new ArrayList<>(),
mvseqfront=new ArrayList<>();
mvseqfront.add(new int[] {});
Set<String> seen=new HashSet<>();
seen.add(Arrays.toString(scrambleAction(R,C,mvseqfront.get(0),mvactions)));
int prefixDepth=0;
int A=midstates.length;
System.out.println("threshold="+threshold+", midstates="+Arrays.toString(midstates));
long timest=System.currentTimeMillis();
LoopoverBFS[][] trees=new LoopoverBFS[A][2];
for (int a=0; a<A; a++) {
trees[a][0]=new LoopoverBFS(R,C,ststate,midstates[a]);
trees[a][1]=new LoopoverBFS(R,C,midstates[a],enstate);
trees[a][0].computeAllDepths();
trees[a][1].computeAllDepths();
}
System.out.println("total tree preprocessing time="+(System.currentTimeMillis()-timest));
int bestidx=0; //decide which midstate minimizes the total # of scrambles we must process
long bscr=Long.MAX_VALUE;
for (int a=0; a<A; a++) {
long scr=0;
for (int d0=0; d0<trees[a][0].D; d0++)
for (int d1=0; d1<trees[a][1].D; d1++)
if (d0+d1>threshold)
scr+=trees[a][0].codesAtDepth(d0).length*(long)trees[a][1].codesAtDepth(d1).length;
System.out.println(midstates[a]+":"+scr);
if (scr<bscr) {
bscr=scr;
bestidx=a;
}
}
System.out.println("main midstate="+midstates[bestidx]);
System.out.println("memoizing all scramble actions of...");
for (int a=0; a<A; a++) if (a!=bestidx&&computeAllScrms[a]) {
System.out.print("tree["+a+"][0]: ");
long st=System.currentTimeMillis();
trees[a][0].computeAllActions();
System.out.println((System.currentTimeMillis()-st)+" ms");
}
LoopoverBFS tree0=trees[bestidx][0], tree1=trees[bestidx][1];
int tK=tree0.K+tree1.K;
System.out.printf("total combos to improve=%,d%n",bscr);
timest=System.currentTimeMillis();
long ntrials=0, ntries=0, nskips=0, maxtries=0;
for (int d0=0; d0<tree0.D; d0++) for (int d1=0; d1<tree1.D; d1++) if (d0+d1>threshold) {
int[] bin0=tree0.codesAtDepth(d0), bin1=tree1.codesAtDepth(d1);
long st=System.currentTimeMillis();
int[][] scrms0=new int[bin0.length][], scrms1=new int[bin1.length][];
for (int idx0=0; idx0<bin0.length; idx0++)
scrms0[idx0]=tree0.scrambleaction(bin0[idx0]);
for (int idx1=0; idx1<bin1.length; idx1++)
scrms1[idx1]=tree1.scrambleaction(bin1[idx1]);
System.out.println("memoizing scramble actions: "+(System.currentTimeMillis()-st)+" ms");
System.out.println(d0+","+d1+": ncombos="+String.format("%,d",bin0.length*(long)bin1.length));
long stage=0, mark0=20_000, mark=mark0;
String form="%12s%20s%20s%n";
System.out.printf(form,"elapsed sec","#combos","#combos/sec");
long reps=0;
st=System.currentTimeMillis();
for (int idx0=0; idx0<bin0.length; idx0++)
for (int idx1=0; idx1<bin1.length; idx1++) {
int[] scrm1=scrms1[idx1], scrm0=scrms0[idx0];
//a piece in location i is moved to location scrm0[scrm1[i]]
boolean reduced=false;
//List<List<int[]>> seqs=new ArrayList<>();
ntrials++;
long ntries0=ntries;
for (int a=0; a<A; a++) if (a!=bestidx) {
ntries++;
//seqs.clear();
int code0=trees[a][0].codeAfterScramble(scrm0,scrm1);
//seqs.add(trees[a][0].solvemvs(code0));
/*if (trees[a][0].depth(code0)+(trees[a][1].D-1)<=threshold) {
nskips++;
reduced=true;
break;
}*/
int code1=trees[a][1].codeAfterScramble(trees[a][0].solveaction(code0),scrm0,scrm1);
//seqs.add(trees[a][1].solvemvs(code1));
if (trees[a][0].depth[code0]+trees[a][1].depth[code1]<=threshold) {
reduced=true;
break;
}
}
if (!reduced)
PREFIXANDALTBLOCK: for (int mvsi=0;; mvsi++) {
if (mvsi==mvseqactions.size()) {
List<int[]> nmvseqfront=new ArrayList<>();
for (int[] mseq:mvseqfront)
for (int mi:mvreduc[mseq.length==0?M:mseq[prefixDepth-1]]) {
int[] nmseq=new int[prefixDepth+1];
System.arraycopy(mseq,0,nmseq,0,prefixDepth);
nmseq[prefixDepth]=mi;
int[] action=scrambleAction(R,C,nmseq,mvactions);
String code=Arrays.toString(action);
if (!seen.contains(code)) {
seen.add(code);
nmvseqfront.add(nmseq);
mvseqs.add(nmseq);
mvseqactions.add(action);
}
}
mvseqfront=nmvseqfront;
prefixDepth++;
System.out.println("prefixDepth-->"+prefixDepth);
}
for (int a=0; a<A; a++) {
ntries++;
int[] prefixaction=mvseqactions.get(mvsi);
/*seqs.clear();
seqs.add(new ArrayList<>());
for (int mi:mvseqs.get(mvsi))
seqs.get(0).add(mvs[mi]);*/
int code0=trees[a][0].codeAfterScramble(prefixaction,scrm0,scrm1);
//seqs.add(trees[a][0].solvemvs(code0));
/*if (mvseqs.get(mvsi).length+trees[a][0].depth(code0)+(trees[a][1].D-1)<=threshold) {
nskips++;
break PREFIXANDALTBLOCK;
}*/
int code1=trees[a][1].codeAfterScramble(trees[a][0].solveaction(code0),prefixaction,scrm0,scrm1);
//seqs.add(trees[a][1].solvemvs(code1));
if (mvseqs.get(mvsi).length+trees[a][0].depth[code0]+trees[a][1].depth[code1]<=threshold)
break PREFIXANDALTBLOCK;
}
}
maxtries=Math.max(maxtries,ntries-ntries0);
/*if (Math.random()<1/1000_000.0) {
int[] solvedscrm=new int[tK];
System.arraycopy(tree0.pcstosolve,0,solvedscrm,0,tree0.K);
System.arraycopy(tree1.pcstosolve,0,solvedscrm,tree0.K,tree1.K);
System.out.print(boardStr(solvedscrm,prodperm(prodperm(solvedscrm.clone(),scrm1),scrm0),R,C));
for (List<int[]> tmp:seqs)
System.out.println(LoopoverBFS.mvseqStr(tmp));
}*/
reps++;
long time=System.currentTimeMillis()-st;
if (time>=mark) {
System.out.printf(form,String.format("%,.3f",time/1000.0),String.format("%,d",reps),
String.format("%,.3f",1000*reps/(double)time));
stage++;
mark=(long)(mark0*Math.exp(Math.sqrt(stage)));
}
}
System.out.printf(form,String.format("%,.3f",(System.currentTimeMillis()-st)/1000.0),String.format("%,d",reps),
String.format("%,.3f",1000*reps/(double)(System.currentTimeMillis()-st)));
}
System.out.println("improvement time (sec)="+(System.currentTimeMillis()-timest)/1000.0);
System.out.println("mean # alternate attempted solutions per scramble="+ntries+"/"+ntrials+"="+(ntries/(double)ntrials));
System.out.println("maximum # attempts on a scramble="+maxtries);
System.out.println("mean # skips per scramble="+nskips+"/"+ntrials+"="+(nskips/(double)ntrials));
System.out.println("max prefix sequence length needed="+prefixDepth);
return true;
}
public static void main(String[] args) {
//TODO: 5x5:0x0->3x3, 6x6:0x0->3x3
long st=System.currentTimeMillis();
LoopoverBFSImprove improver=new LoopoverBFSImprove(5,5,"11111x11111","00011x00011");
List<String> mids=new ArrayList<>();
for (int r=0; r<3; r++)
for (int c=0; c<3; c++) {
StringBuilder s=new StringBuilder("00011x00011");
s.setCharAt(r,'1');
s.setCharAt(6+c,'1');
mids.add(s.toString());
}
boolean[] tmp=new boolean[mids.size()];
Arrays.fill(tmp,true);
improver.improve(17,
mids.toArray(new String[0]),
tmp
);
System.out.println("total program time="+(System.currentTimeMillis()-st));
}
}
//storing scramble depths directly in an array instead of using the data[] field in LoopoverBFS gave a ~30% speedup
import java.util.*;
public class LoopoverBFS {
//TODO: REFACTOR USING ABSTRACT CLASS
private static int mod(int n, int k) {
return (n%k+k)%k;
}
private static boolean[] mask(String s) {
boolean[] out=new boolean[s.length()];
for (int i=0; i<s.length(); i++)
out[i]=s.charAt(i)=='1';
return out;
}
public static boolean[][] parseState(String s) {
String[] pcs=s.split("x");
if (pcs.length!=2) throw new RuntimeException("Not in 2 pieces: "+s);
return new boolean[][] {mask(pcs[0]),mask(pcs[1])};
}
private static boolean free(boolean[][] boardState, int r, int c) {
return boardState[0][r]||boardState[1][c];
}
public static String mvseqStr(List<int[]> S) {
StringBuilder str=new StringBuilder();
for (int[] m:S)
str.append(" ").append(m[0]==0?"R":"C").append(m[1]).append(m[2]==1?" ":m[2]==-1?"'":("("+m[2]+")"));
return str.toString();
}
//define absolute indexing as mapping coordinate (r,c) to index r*C+c
//every scramble is represented by an array L[], where piece i is at location L[i]
private int R, C;
private int F;
private boolean[][] rcfree;
//a location (r,c) is free iff Rfree[r]||Cfree[c]
private int[] tofree, freeto;
//tofree[r*C+c]=i, where free location (r,c) is assigned to index i
public int K;
public int[] pcstosolve; //list of pieces this tree tries to solve, in absolute indexing
private int[][] mvactions, mvs;
private int[][] solveactions, scrambleactions;
public static int[][] mvreduc(int[][] mvs) {
int M=mvs.length;
//move sequence reduction
//when doing two moves of the same type, one after the other: [t,a,r], [t,b,s]:
//WLOG a<=b, or else the two moves can be arranged to satisfy this condition without changing the final scramble
//if a==b, then r+s!=0, else the two moves cancel each other out
int[][] mvreduc=new int[M+1][];
for (int m=0; m<M; m++) {
List<Integer> l=new ArrayList<>();
for (int m2=0; m2<M; m2++)
if (mvs[m][0]!=mvs[m2][0]
||mvs[m][1]<mvs[m2][1]
||(mvs[m][1]==mvs[m2][1]&&mvs[m][2]+mvs[m2][2]!=0))
l.add(m2);
mvreduc[m]=new int[l.size()];
for (int i=0; i<l.size(); i++)
mvreduc[m][i]=l.get(i);
}
mvreduc[M]=new int[M];
for (int i=0; i<M; i++) mvreduc[M][i]=i;
return mvreduc;
}
private int M;
public int ncombos;
//bfs stuff
private long[] data;
public int[] depth;
private List<int[]> fronts; //BFS fronts
public int D; //(largest depth of BFS tree)+1
//c-->(depth,move from parent combo to c,parent combo)
private long compressed(int depth, int parent, int move) {
return ((long)depth*M+move)*ncombos+parent;
}
public int depth(int code) {
return data[code]==-1?-1:(int)(data[code]/ncombos/M);
}
private int par(int code) {
return data[code]==-1?-1:(int)(data[code]%ncombos);
}
private int mvi(int code) {
return data[code]==-1?-1:(int)((data[code]/ncombos)%M);
}
public LoopoverBFS(int R, int C, String state0, String state1) {
long st=System.currentTimeMillis();
this.R=R; this.C=C;
rcfree=parseState(state0);
tofree=new int[R*C]; freeto=new int[R*C];
F=0;
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
if (free(rcfree,r,c)) {
tofree[r*C+c]=F;
freeto[F]=r*C+c;
F++;
}
else tofree[r*C+c]=-1;
freeto=Arrays.copyOfRange(freeto,0, F);
boolean[][] nrcfree=parseState(state1);
K=0; pcstosolve=new int[R*C];
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
if (free(rcfree,r,c)&&!free(nrcfree,r,c))
pcstosolve[K++]=r*C+c;
pcstosolve=Arrays.copyOfRange(pcstosolve,0,K);
for (int r=0; r<R; r++) {
for (int c=0; c<C; c++)
System.out.printf("%4s",
free(rcfree,r,c)?
((free(nrcfree,r,c)?"":"'")+tofree[r*C+c]):
"X"
//': piece that this BFS tree tries to solve; *: gripped piece
);
System.out.println();
}
{
long tmp=1;
for (int rep=0; rep<K; rep++) tmp*=F-rep;
if (tmp>400_000_000) throw new RuntimeException("Too many combinations to handle.");
ncombos=(int)tmp;
}
System.out.println("ncombos="+ncombos);
//moves: every move is represented with [t,a,r]:
//t: type (0=row shift, 1=clm shift)
//a: the a-th (row if t==0, else clm)
//r: # units to shift (right if t==0, else down)
M=0;
for (boolean[] axis:rcfree)
for (boolean b:axis) if (b) M+=2;
mvactions=new int[M][]; mvs=new int[M][]; {
//mvactions[m][i]=free loc. that i-th free loc. will go to after move m is applied
int idx=0;
for (int mr=0; mr<R; mr++)
if (rcfree[0][mr])
for (int s=-1; s<=1; s+=2) {
mvs[idx]=new int[] {0,mr,s};
mvactions[idx]=new int[F];
for (int i=0; i<F; i++) {
int r=freeto[i]/C, c=freeto[i]%C;
mvactions[idx][i]=tofree[r*C+(r==mr?mod(c+s,C):c)];
}
idx++;
}
for (int mc=0; mc<C; mc++)
if (rcfree[1][mc])
for (int s=-1; s<=1; s+=2) {
mvs[idx]=new int[] {1,mc,s};
mvactions[idx]=new int[F];
for (int i=0; i<F; i++) {
int r=freeto[i]/C, c=freeto[i]%C;
mvactions[idx][i]=tofree[(c==mc?mod(r+s,R):r)*C+c];
}
idx++;
}
}
int[][] mvreduc=mvreduc(mvs);
//BFS
solveactions=new int[ncombos][];
scrambleactions=new int[ncombos][];
data=new long[ncombos]; Arrays.fill(data,-1);
fronts=new ArrayList<>();
{
int[] solvedscrm=new int[K];
for (int i=0; i<K; i++)
solvedscrm[i]=tofree[pcstosolve[i]];
int solvedscrmcode=comboCode(solvedscrm);
fronts.add(new int[] {solvedscrmcode});
data[solvedscrmcode]=0;
}
int[] nfront=new int[ncombos];
int reached=0;
for (D=0;; D++) {
if (fronts.get(D).length==0) break;
reached+=fronts.get(D).length;
System.out.print((D>0?" ":"")+D+":"+fronts.get(D).length);
int sz=0;
for (int f:fronts.get(D)) {
int[] scrm=codeCombo(f);
int[] mvlist=mvreduc[D==0?M:mvi(f)];
for (int mi:mvlist) {
int nf=comboCode(scrm,mvactions[mi]);
if (data[nf]==-1) {
data[nf]=compressed(D+1,f,mi);
nfront[sz++]=nf;
}
}
}
fronts.add(new int[sz]);
System.arraycopy(nfront,0,fronts.get(D+1),0,sz);
}
System.out.println("\n#reached="+reached);
System.out.println("D="+D);
System.out.println("total BFS time="+(System.currentTimeMillis()-st));
}
public void computeAllDepths() {
depth=new int[ncombos];
for (int code=0; code<ncombos; code++)
depth[code]=data[code]==-1?-1:depth(code);
}
public int[] codesAtDepth(int d) {
return fronts.get(d);
}
/*
encoding ordered combinations
A[0]...A[K-1], 0<=A[i]<N, all A[i] distinct
possible to transform permutation [0...N-1] into [....|A]
using a sequence of swaps (i,J_i) for i=N-1 to N-K inclusive
--> encode A as J_(N-1)+N*(J_(N-2)+(N-1)*(...+(N-K+2)*J_(N-K)...)
for this program, N=Nfree, K=K
*/
public int comboCode(int[] A) {
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
int[] L=P.clone();
int out=0;
for (int i=F-1, pow=1; i>=F-K; i--) {
//swap idxs i and L[A[i-(N-K)]] in P
int j=L[A[i-(F-K)]];
int pi=P[i];//, pj=P[j];
//P[i]=pj; //<--idx i will never be touched again
P[j]=pi;
L[pi]=j;
//L[pj]=i;
//J_i==j
out+=pow*j;
pow*=i+1;
}
return out;
}
private int comboCode(int[] A, int[] f) {
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
int[] L=P.clone();
int out=0;
for (int i=F-1, pow=1; i>=F-K; i--) {
int j=L[f[A[i-(F-K)]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
public int codeAfterScramble(int[] scrm0, int[] scrm1) {
//A[i]=tofree[scrm0[scrm1[pcstosolve[i]]]]
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
int[] L=P.clone();
int out=0;
for (int i=F-1, pow=1; i>=F-K; i--) {
int j=L[tofree[scrm0[scrm1[pcstosolve[i-(F-K)]]]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
public int codeAfterScramble(int[] scrm0, int[] scrm1, int[] scrm2) {
//A[i]=tofree[scrm0[scrm1[scrm2[pcstosolve[i]]]]]
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
int[] L=P.clone();
int out=0;
for (int i=F-1, pow=1; i>=F-K; i--) {
int j=L[tofree[scrm0[scrm1[scrm2[pcstosolve[i-(F-K)]]]]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
public int codeAfterScramble(int[] scrm0, int[] scrm1, int[] scrm2, int[] scrm3) {
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
int[] L=P.clone();
int out=0;
for (int i=F-1, pow=1; i>=F-K; i--) {
int j=L[tofree[scrm0[scrm1[scrm2[scrm3[pcstosolve[i-(F-K)]]]]]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
private int[] codeCombo(int code) {
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
for (int v=F; v> F-K; v--) {
int i=v-1, j=code%v;
code/=v;
int pi=P[i]; P[i]=P[j]; P[j]=pi;
}
int[] out=new int[K];
System.arraycopy(P, F-K,out,0,K);
return out;
}
public void computeAllActions() {
for (int code=0; code<ncombos; code++) if (data[code]!=-1) {
solveactions[code]=solveaction_help(code);
scrambleactions[code]=inv(solveactions[code]);
}
}
public int[] solveaction(int code) {
return solveactions[code]==null?solveaction_help(code):solveactions[code];
}
private int[] solveaction_help(int code) {
if (data[code]==-1) throw new RuntimeException("Invalid combination code: "+code);
int[] out=new int[F];
for (int i=0; i<F; i++) out[i]=i;
for (int c=code; depth(c)>0; c=par(c)) {
int[] mva=inv(mvactions[mvi(c)]);
int[] nout=new int[F];
for (int i=0; i<F; i++)
nout[i]=mva[out[i]];
out=nout;
}
return mva2abs(out);
}
public int[] scrambleaction(int code) {
return scrambleactions[code]==null?inv(solveaction(code)):scrambleactions[code];
}
public List<int[]> solvemvs(int code) {
List<int[]> out=new ArrayList<>();
for (int c=code; depth(c)>0; c=par(c)) {
int[] mv=mvs[mvi(c)];
out.add(new int[] {mv[0],mv[1],-mv[2]});
}
return out;
}
private static int[] inv(int[] P) {
//return inverse permutation of P
int[] I=new int[P.length];
for (int i=0; i<P.length; i++)
I[P[i]]=i;
return I;
}
private int[] mva2abs(int[] mva) {
//convert mva to array A
//where A[a]=b describes absolute location a being shifted to absolute location b
int[] out=new int[R*C];
for (int a=0; a<R*C; a++)
out[a]=tofree[a]==-1?a:freeto[mva[tofree[a]]];
return out;
}
public static void main(String[] args) {
new LoopoverBFS(5,5,"11111x11111","00111x00111");
new LoopoverBFS(5,5,"00111x00111","00011x00011");
}
}
Raw
part2.txt
stdout:
5x5: 11111x11111 --> ... --> 00011x00011
5x5-11111x11111-00000x00000\
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
threshold=17, midstates=[10011x10011, 10011x01011, 10011x00111, 01011x10011, 01011x01011, 01011x00111, 00111x10011, 00111x01011, 00111x00111]
0 1 2 3 4
5 '6 '7 8 9
10 '11 '12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:64 3:492 4:2974 5:14584 6:49562 7:97448 8:95449 9:39425 10:3592 11:1
#reached=303600
D=12
total BFS time=413
'0 '1 '2 3 4
'5 X X 6 7
'8 X X 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:105 4:508 5:2386 6:10441 7:41483 8:143791 9:398056 10:738804 11:744707 12:321693 13:39351 14:530
#reached=2441880
D=15
total BFS time=2048
0 1 2 3 4
'5 6 '7 8 9
'10 11 '12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:72 3:584 4:3458 5:15430 6:48290 7:94393 8:97852 9:40185 10:3323 11:4
#reached=303600
D=12
total BFS time=200
'0 '1 '2 3 4
X '5 X 6 7
X '8 X 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:108 4:548 5:2597 6:11461 7:46124 8:160146 9:432659 10:766050 11:715679 12:276512 13:29742 14:229
#reached=2441880
D=15
total BFS time=1967
0 1 2 3 4
'5 '6 7 8 9
'10 '11 12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:64 3:492 4:2974 5:14584 6:49562 7:97448 8:95449 9:39425 10:3592 11:1
#reached=303600
D=12
total BFS time=213
'0 '1 '2 3 4
X X '5 6 7
X X '8 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:105 4:508 5:2386 6:10441 7:41483 8:143791 9:398056 10:738804 11:744707 12:321693 13:39351 14:530
#reached=2441880
D=15
total BFS time=1768
0 '1 '2 3 4
5 6 7 8 9
10 '11 '12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:72 3:584 4:3458 5:15430 6:48290 7:94393 8:97852 9:40185 10:3323 11:4
#reached=303600
D=12
total BFS time=232
'0 X X 1 2
'3 '4 '5 6 7
'8 X X 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:108 4:548 5:2597 6:11461 7:46124 8:160146 9:432659 10:766050 11:715679 12:276512 13:29742 14:229
#reached=2441880
D=15
total BFS time=1718
'0 1 '2 3 4
5 6 7 8 9
'10 11 '12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:80 3:664 4:3796 5:15962 6:47742 7:92414 8:96736 9:41771 10:4390 11:36
#reached=303600
D=12
total BFS time=254
X '0 X 1 2
'3 '4 '5 6 7
X '8 X 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:104 4:524 5:2548 6:11636 7:47752 8:168062 9:462318 10:835988 11:726280 12:182763 13:3880
#reached=2441880
D=14
total BFS time=1735
'0 '1 2 3 4
5 6 7 8 9
'10 '11 12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:72 3:584 4:3458 5:15430 6:48290 7:94393 8:97852 9:40185 10:3323 11:4
#reached=303600
D=12
total BFS time=260
X X '0 1 2
'3 '4 '5 6 7
X X '8 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:108 4:548 5:2597 6:11461 7:46124 8:160146 9:432659 10:766050 11:715679 12:276512 13:29742 14:229
#reached=2441880
D=15
total BFS time=1701
0 '1 '2 3 4
5 '6 '7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:64 3:492 4:2974 5:14584 6:49562 7:97448 8:95449 9:39425 10:3592 11:1
#reached=303600
D=12
total BFS time=262
'0 X X 1 2
'3 X X 4 5
'6 '7 '8 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:105 4:508 5:2386 6:10441 7:41483 8:143791 9:398056 10:738804 11:744707 12:321693 13:39351 14:530
#reached=2441880
D=15
total BFS time=1722
'0 1 '2 3 4
'5 6 '7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:72 3:584 4:3458 5:15430 6:48290 7:94393 8:97852 9:40185 10:3323 11:4
#reached=303600
D=12
total BFS time=241
X '0 X 1 2
X '3 X 4 5
'6 '7 '8 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:108 4:548 5:2597 6:11461 7:46124 8:160146 9:432659 10:766050 11:715679 12:276512 13:29742 14:229
#reached=2441880
D=15
total BFS time=1722
'0 '1 2 3 4
'5 '6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
ncombos=303600
0:1 1:8 2:64 3:492 4:2974 5:14584 6:49562 7:97448 8:95449 9:39425 10:3592 11:1
#reached=303600
D=12
total BFS time=262
X X '0 1 2
X X '3 4 5
'6 '7 '8 9 10
11 12 13 14 15
16 17 18 19 20
ncombos=2441880
0:1 1:4 2:20 3:105 4:508 5:2386 6:10441 7:41483 8:143791 9:398056 10:738804 11:744707 12:321693 13:39351 14:530
#reached=2441880
D=15
total BFS time=1676
total tree preprocessing time=18396
10011x10011:399432042449
10011x01011:383895895962
10011x00111:399432042449
01011x10011:383895895962
01011x01011:365419870881
01011x00111:383895895962
00111x10011:399432042449
00111x01011:383895895962
00111x00111:399432042449
main midstate=01011x01011
memoizing all scramble actions of...
tree[0][0]: 339 ms
tree[1][0]: 381 ms
tree[2][0]: 371 ms
tree[3][0]: 383 ms
tree[5][0]: 444 ms
tree[6][0]: 308 ms
tree[7][0]: 332 ms
tree[8][0]: 348 ms
total combos to improve=365,419,870,881
NOT COMPLETE IMPROVEMENT
memoizing scramble actions: 1217 ms
9,11: ncombos=30,337,441,880
elapsed sec #combos #combos/sec
20.000 869,285,951 43,464,297.550
113.137 4,742,103,542 41,914,701.132
prefixDepth-->1 (#mvseqs=20)
prefixDepth-->2 (#mvseqs=320)
prefixDepth-->3 (#mvseqs=4640)
prefixDepth-->4 (#mvseqs=65560)
prefixDepth-->5 (#mvseqs=910744)
311.769 7,502,406,085 24,063,989.957
640.006 7,543,011,389 11,785,844.803
1,118.033 7,597,601,268 6,795,507.170
1,763.632 7,705,169,359 4,368,921.271
2,592.860 7,842,123,351 3,024,507.051
prefixDepth-->6 (#mvseqs=12526474)
3,641.072 8,005,372,021 2,198,630.519
4,860.516 8,081,314,761 1,662,645.439
6,324.877 8,225,268,374 1,300,462.977
8,026.231 8,411,715,721 1,048,028.112
9,976.612 8,628,631,497 864,885.945
12,186.788 8,916,557,286 731,657.701
14,667.296 9,225,895,643 629,011.349
17,428.888 9,585,432,759 549,973.857
20,480.000 9,961,389,210 486,395.958
23,831.550 10,412,970,875 436,940.563
27,492.312 10,900,991,219 396,510.531
31,471.974 11,461,181,929 364,171.054
35,777.708 11,960,678,125 334,305.320
40,418.317 12,608,690,532 311,954.863
45,403.226 13,263,156,022 292,119.243
50,739.897 13,928,327,957 274,504.459
56,436.344 14,535,850,093 257,561.866
62,500.000 15,170,874,786 242,733.997
68,938.889 15,815,363,022 229,411.342
75,759.977 16,606,407,206 219,197.627
82,970.761 17,484,676,732 210,732.992
90,578.777 18,409,591,482 203,243.984
98,590.351 19,312,891,970 195,890.285
107,012.431 19,951,971,384 186,445.362
115,852.921 20,906,081,434 180,453.641
125,116.574 22,031,481,304 176,087.633
134,811.607 23,029,431,217 170,826.769
144,943.955 24,145,774,972 166,586.975
155,520.000 25,180,292,915 161,910.320
166,546.038 26,243,312,332 157,573.922
178,028.276 27,370,819,648 153,744.227
189,972.839 28,342,440,693 149,192.068
202,385.964 29,307,887,946 144,811.860
215,273.036 30,156,110,277 140,083.082
218,274.313 30,337,441,880 138,987.687
memoizing scramble actions: 4227 ms
9,12: ncombos=7,634,193,273
elapsed sec #combos #combos/sec
20.000 3,542,854 177,142.700
113.137 16,123,299 142,511.283
311.769 34,453,938 110,511.109
640.000 69,871,331 109,173.955
1,118.033 144,435,000 129,186.706
1,763.637 225,809,829 128,036.455
2,592.836 331,483,939 127,846.088
3,620.386 507,294,720 140,121.722
4,860.000 689,428,429 141,857.701
6,324.555 891,361,737 140,936.673
8,026.231 1,113,319,700 138,710.149
9,976.612 1,382,978,395 138,622.049
12,186.763 1,716,254,271 140,829.379
14,667.296 1,929,695,589 131,564.508
17,428.425 2,192,916,730 125,824.148
20,480.000 2,582,583,280 126,102.699
23,831.550 3,024,771,844 126,923.001
27,492.311 3,500,732,619 127,334.971
31,471.250 3,935,845,157 125,061.609
35,777.317 4,499,730,663 125,770.489
40,418.317 4,968,195,478 122,919.405
45,403.237 5,506,972,137 121,290.298
50,739.897 6,110,911,520 120,436.025
56,436.243 6,679,457,782 118,354.047
62,500.000 7,217,341,734 115,477.468
67,924.635 7,634,193,273 112,392.113
memoizing scramble actions: 70 ms
9,13: ncombos=162,071,480
elapsed sec #combos #combos/sec
20.000 1,515,895 75,794.750
113.137 11,141,252 98,475.759
311.769 29,954,026 96,077.628
640.000 54,272,912 84,801.425
1,118.033 94,694,607 84,697.506
1,763.635 140,691,926 79,773.834
2,126.683 162,071,480 76,208.575
memoizing scramble actions: 1776 ms
10,8: ncombos=737,792,180
elapsed sec #combos #combos/sec
20.001 4,133,213 206,650.317
113.195 14,099,758 124,561.668
311.769 41,896,690 134,383.758
640.000 95,916,629 149,869.733
1,118.033 183,767,091 164,366.428
1,763.632 284,041,086 161,054.623
2,592.851 425,096,645 163,949.508
3,620.386 586,214,027 161,920.311
4,860.006 737,115,418 151,669.652
4,878.174 737,792,180 151,243.514
memoizing scramble actions: 6838 ms
10,9: ncombos=2,029,576,020
elapsed sec #combos #combos/sec
20.000 2,240,694 112,034.700
113.137 13,534,302 119,627.549
312.301 30,037,921 96,182.596
640.000 49,031,537 76,611.777
1,118.033 86,735,988 77,579.095
1,763.632 155,566,894 88,208.251
2,592.836 236,314,708 91,141.402
3,620.386 338,059,111 93,376.538
4,860.000 479,931,719 98,751.383
6,324.677 622,801,718 98,471.703
8,026.231 771,352,818 96,103.989
9,977.136 970,479,723 97,270.371
12,186.763 1,192,973,891 97,890.957
14,667.297 1,456,035,061 99,270.851
17,428.427 1,670,772,987 95,864.818
20,480.000 1,923,612,475 93,926.390
22,568.651 2,029,576,020 89,928.991
memoizing scramble actions: 16793 ms
10,10: ncombos=3,669,987,320
elapsed sec #combos #combos/sec
20.004 1,806,193 90,291.592
113.844 6,460,417 56,747.980
312.041 20,870,142 66,882.692
640.000 37,810,124 59,078.319
1,118.740 57,093,125 51,033.417
1,763.632 76,426,195 43,334.548
2,592.836 122,231,137 47,141.870
3,620.834 163,478,878 45,149.509
4,860.002 234,898,955 48,333.098
6,325.102 324,352,925 51,280.268
8,026.475 408,934,948 50,948.262
9,977.271 506,241,264 50,739.452
12,186.763 642,542,443 52,724.620
14,667.296 787,250,936 53,673.897
17,428.573 951,904,839 54,617.486
20,480.464 1,092,989,619 53,367.425
23,831.550 1,251,161,734 52,500.225
27,492.312 1,426,807,249 51,898.409
31,471.880 1,656,731,413 52,641.641
35,777.087 1,858,702,437 51,952.313
40,418.333 2,108,870,849 52,176.097
45,403.225 2,398,899,856 52,835.451
50,739.933 2,674,631,346 52,712.552
56,436.403 2,899,150,265 51,370.217
62,500.000 3,199,578,703 51,193.259
68,939.203 3,454,007,498 50,102.226
75,759.904 3,655,629,605 48,252.828
76,560.147 3,669,987,320 47,936.001
memoizing scramble actions: 15186 ms
10,11: ncombos=3,188,369,200
elapsed sec #combos #combos/sec
20.000 1,545,249 77,262.450
113.137 5,679,166 50,197.248
311.769 17,719,452 56,835.195
640.000 33,663,284 52,598.881
1,118.667 51,088,007 45,668.646
1,764.088 70,797,253 40,132.495
2,592.836 111,156,611 42,870.668
3,620.386 155,173,169 42,860.946
4,860.001 210,954,783 43,406.325
6,324.555 290,885,114 45,992.977
8,026.231 360,013,592 44,854.626
9,976.613 441,492,825 44,252.776
12,186.763 565,761,626 46,424.274
14,667.296 685,748,651 46,753.584
17,428.425 810,186,703 46,486.513
20,480.004 936,535,735 45,729.275
23,831.551 1,068,394,728 44,831.103
27,492.311 1,215,634,238 44,217.245
31,471.250 1,421,515,722 45,168.709
35,777.087 1,582,929,441 44,244.224
40,418.317 1,778,542,269 44,003.373
45,403.224 2,014,823,019 44,376.210
50,739.897 2,244,889,291 44,243.079
56,436.243 2,450,824,369 43,426.427
62,500.002 2,709,725,466 43,355.606
68,938.743 2,933,396,209 42,550.764
75,759.902 3,133,051,104 41,355.005
78,443.654 3,188,369,200 40,645.343
memoizing scramble actions: 3442 ms
10,12: ncombos=802,329,570
elapsed sec #combos #combos/sec
20.000 961,698 48,084.900
113.137 6,499,384 57,447.024
311.769 15,579,246 49,970.478
640.000 33,241,684 51,940.131
1,118.033 62,287,954 55,712.089
1,763.632 94,371,268 53,509.614
2,592.836 144,986,009 55,917.925
3,620.461 194,080,567 53,606.590
4,860.000 254,759,815 52,419.715
6,324.555 325,849,255 51,521.294
8,026.231 405,812,978 50,560.840
9,976.615 497,109,922 49,827.514
12,186.763 598,528,937 49,113.037
14,667.296 706,622,139 48,176.715
17,428.425 799,563,597 45,876.985
17,531.060 802,329,570 45,766.176
memoizing scramble actions: 17 ms
10,13: ncombos=17,033,200
elapsed sec #combos #combos/sec
20.000 879,710 43,985.500
113.137 4,609,573 40,743.285
311.772 11,403,038 36,574.927
500.917 17,033,200 34,004.037
memoizing scramble actions: 51 ms
11,7: ncombos=1,719,072
elapsed sec #combos #combos/sec
20.000 1,059,588 52,979.400
31.985 1,719,072 53,746.194
memoizing scramble actions: 1750 ms
11,8: ncombos=6,050,232
elapsed sec #combos #combos/sec
20.000 764,297 38,214.850
113.137 4,563,974 40,340.242
153.629 6,050,232 39,382.096
memoizing scramble actions: 6875 ms
11,9: ncombos=16,643,448
elapsed sec #combos #combos/sec
20.000 734,067 36,703.350
113.137 3,129,419 27,660.438
311.770 8,483,352 27,210.290
632.021 16,643,448 26,333.695
memoizing scramble actions: 16821 ms
11,10: ncombos=30,095,568
elapsed sec #combos #combos/sec
20.000 433,980 21,699.000
113.763 2,053,592 18,051.493
312.145 5,428,398 17,390.629
640.000 10,662,108 16,659.544
1,118.560 17,705,390 15,828.735
1,764.156 26,845,866 15,217.399
1,994.927 30,095,568 15,086.050
memoizing scramble actions: 14394 ms
11,11: ncombos=26,146,080
elapsed sec #combos #combos/sec
20.000 384,765 19,238.250
113.138 2,080,877 18,392.379
311.769 5,245,306 16,824.335
640.007 10,447,335 16,323.782
1,118.034 16,200,429 14,490.104
1,763.805 24,081,830 13,653.340
1,932.088 26,146,080 13,532.551
memoizing scramble actions: 3432 ms
11,12: ncombos=6,579,468
elapsed sec #combos #combos/sec
20.000 466,816 23,340.800
113.141 2,440,804 21,573.117
311.771 5,053,598 16,209.327
408.090 6,579,468 16,122.591
memoizing scramble actions: 10 ms
11,13: ncombos=139,680
elapsed sec #combos #combos/sec
11.197 139,680 12,473.656
improvement time (sec)=494065.082
mean # alternate attempted solutions per scramble=827618195376/41180357589=20.09740186416136
maximum # attempts on a scramble=17771728
mean # skips per scramble=0/41180357589=0.0
max prefix sequence length needed=6
total program time=494086424
Process finished with exit code 0
code:
import java.util.*;
/**
* given a start state S and end state E:
* ex. 5x5 Loopover states 11111x11111 and 00011x00011
* along with a list of middle states M[]:
* ex. 00111x00111, 00111x01011, 10011x01011, etc.
* use these midstates to find an upper bound on the God's number of transforming the starting state to the end state
*
* more formally, choose a threshold D
* choose a midstate M[a] to be the "default"
* then go through all scrambles such that naively using the two trees S-->M[a] and M[a]-->E yields a solution of >D moves
* for each scramble:
* for each i!=a, try solving it with the trees S-->M[i] and M[i]-->E until a solution of <=D moves is found
* if a solution is not found, try applying an arbitrary sequence of prefix moves to the scramble,
* and then try solving it with the trees S-->M[i] and M[i]-->E (this time including i==a)
* repeat for all possible prefix sequences of length 1, 2, ... until a short enough solution is found
*/
public class LoopoverBFSImprove {
private static int mod(int n, int k) {
return (n%k+k)%k;
}
private static int[] prodperm(int[] A, int[] B) {
//B is a permutation array
//return [ B[A[i]] for all i]
int[] out=new int[A.length];
for (int i=0; i<A.length; i++)
out[i]=B[A[i]];
return out;
}
private static String boardStr(int[] solvedscrm, int[] scrm, int R, int C) {
int[] display=new int[R*C]; Arrays.fill(display,-1);
for (int i=0; i<scrm.length; i++)
display[scrm[i]]=solvedscrm[i];
StringBuilder out=new StringBuilder();
String form="%"+(R*C<=26?1:3)+"s";
for (int r=0; r<R; r++) {
for (int c=0; c<C; c++)
out.append(String.format(form,display[r*C+c]==-1?".":(R*C<=26?""+(char)('A'+display[r*C+c]):(display[r*C+c]+1))));
out.append('\n');
}
return out.toString();
}
private static int[] scrambleAction(int R, int C, int[] mvseq, int[][] mvactions) {
int[] out=new int[R*C]; for (int i=0; i<R*C; i++) out[i]=i;
for (int mvi:mvseq) out=prodperm(out,mvactions[mvi]);
return out;
}
private int R, C;
private String ststate, enstate;
public LoopoverBFSImprove(int R, int C, String sts, String ens) {
System.out.println(R+"x"+C+": "+sts+" --> ... --> "+ens);
this.R=R; this.C=C;
ststate=sts;
enstate=ens;
}
private boolean improve(int threshold, String[] midstates, boolean[] computeAllScrms) {
//prefix move sequences
int M=0;
for (int c=0; c<ststate.length(); c++)
if (ststate.charAt(c)=='1') M+=2;
int[][] mvs, mvactions, mvreduc;
boolean[][] rcfree0=LoopoverBFS.parseState(ststate);
mvs=new int[M][]; mvactions=new int[M][]; {
int idx=0;
for (int mr=0; mr<R; mr++)
if (rcfree0[0][mr])
for (int s=-1; s<=1; s+=2) {
mvs[idx]=new int[] {0,mr,s};
mvactions[idx]=new int[R*C];
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
mvactions[idx][r*C+c]=r*C+(r==mr?mod(c+s,C):c);
idx++;
}
for (int mc=0; mc<C; mc++)
if (rcfree0[1][mc])
for (int s=-1; s<=1; s+=2) {
mvs[idx]=new int[] {1,mc,s};
mvactions[idx]=new int[R*C];
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
mvactions[idx][r*C+c]=(c==mc?mod(r+s,R):r)*C+c;
idx++;
}
}
mvreduc=LoopoverBFS.mvreduc(mvs);
List<int[]> mvseqs=new ArrayList<>(),
mvseqactions=new ArrayList<>(),
mvseqfront=new ArrayList<>();
mvseqfront.add(new int[] {});
Set<Long> seen=new HashSet<>();
LoopoverBFSLarge calc=new LoopoverBFSLarge(R,C,"1".repeat(R),"1".repeat(C),"0".repeat(R),"0".repeat(C));
seen.add(calc.comboCode(scrambleAction(R,C,mvseqfront.get(0),mvactions)));
int prefixDepth=0;
int A=midstates.length;
System.out.println("threshold="+threshold+", midstates="+Arrays.toString(midstates));
long timest=System.currentTimeMillis();
LoopoverBFS[][] trees=new LoopoverBFS[A][2];
for (int a=0; a<A; a++) {
trees[a][0]=new LoopoverBFS(R,C,ststate,midstates[a]);
trees[a][1]=new LoopoverBFS(R,C,midstates[a],enstate);
//trees[a][0].computeAllDepths();
//trees[a][1].computeAllDepths();
}
System.out.println("total tree preprocessing time="+(System.currentTimeMillis()-timest));
int bestidx=0; //decide which midstate minimizes the total # of scrambles we must process
long bscr=Long.MAX_VALUE;
for (int a=0; a<A; a++) {
long scr=0;
for (int d0=0; d0<trees[a][0].D; d0++)
for (int d1=0; d1<trees[a][1].D; d1++)
if (d0+d1>threshold)
scr+=trees[a][0].codesAtDepth(d0).length*(long)trees[a][1].codesAtDepth(d1).length;
System.out.println(midstates[a]+":"+scr);
if (scr<bscr) {
bscr=scr;
bestidx=a;
}
}
System.out.println("main midstate="+midstates[bestidx]);
System.out.println("memoizing all scramble actions of...");
for (int a=0; a<A; a++) if (a!=bestidx&&computeAllScrms[a]) {
System.out.print("tree["+a+"][0]: ");
long st=System.currentTimeMillis();
trees[a][0].computeAllActions();
System.out.println((System.currentTimeMillis()-st)+" ms");
}
LoopoverBFS tree0=trees[bestidx][0], tree1=trees[bestidx][1];
System.out.printf("total combos to improve=%,d%n",bscr);
timest=System.currentTimeMillis();
long ntrials=0, ntries=0, nskips=0, maxtries=0;
System.out.println("NOT COMPLETE IMPROVEMENT");
for (int d0=9; d0<tree0.D; d0++) for (int d1=(d0==9?11:0); d1<tree1.D; d1++) if (d0+d1>threshold) {
int[] bin0=tree0.codesAtDepth(d0), bin1=tree1.codesAtDepth(d1);
long st=System.currentTimeMillis();
int[][] scrms0=new int[bin0.length][], scrms1=new int[bin1.length][];
for (int idx0=0; idx0<bin0.length; idx0++)
scrms0[idx0]=tree0.scrambleaction(bin0[idx0]);
for (int idx1=0; idx1<bin1.length; idx1++)
scrms1[idx1]=tree1.scrambleaction(bin1[idx1]);
System.out.println("memoizing scramble actions: "+(System.currentTimeMillis()-st)+" ms");
System.out.println(d0+","+d1+": ncombos="+String.format("%,d",bin0.length*(long)bin1.length));
long stage=1, mark0=20_000, mark=mark0;
String form="%12s%20s%20s%n";
System.out.printf(form,"elapsed sec","#combos","#combos/sec");
long reps=0;
st=System.currentTimeMillis();
for (int idx0=0; idx0<bin0.length; idx0++)
for (int idx1=0; idx1<bin1.length; idx1++) {
if (d0!=9||d1!=11||reps>=7_485_810_082L) {
int[] scrm1=scrms1[idx1], scrm0=scrms0[idx0];
//a piece in location i is moved to location scrm0[scrm1[i]]
boolean reduced=false;
//List<List<int[]>> seqs=new ArrayList<>();
ntrials++;
long ntries0=ntries;
for (int a=0; a<A; a++) if (a!=bestidx) {
ntries++;
//seqs.clear();
int code0=trees[a][0].codeAfterScramble(scrm0,scrm1);
//seqs.add(trees[a][0].solvemvs(code0));
/*if (trees[a][0].depth(code0)+(trees[a][1].D-1)<=threshold) {
nskips++;
reduced=true;
break;
}*/
int code1=trees[a][1].codeAfterScramble(trees[a][0].solveaction(code0),scrm0,scrm1);
//seqs.add(trees[a][1].solvemvs(code1));
if (trees[a][0].depth(code0)+trees[a][1].depth(code1)<=threshold) {
reduced=true;
break;
}
}
if (!reduced)
PREFIXANDALTBLOCK: for (int mvsi=0;; mvsi++) {
if (mvsi==mvseqactions.size()) {
List<int[]> nmvseqfront=new ArrayList<>();
for (int[] mseq:mvseqfront)
for (int mi:mvreduc[mseq.length==0?M:mseq[prefixDepth-1]]) {
int[] nmseq=new int[prefixDepth+1];
System.arraycopy(mseq,0,nmseq,0,prefixDepth);
nmseq[prefixDepth]=mi;
int[] action=scrambleAction(R,C,nmseq,mvactions);
long code=calc.comboCode(action);
if (!seen.contains(code)) {
seen.add(code);
nmvseqfront.add(nmseq);
mvseqs.add(nmseq);
mvseqactions.add(action);
}
}
mvseqfront=nmvseqfront;
prefixDepth++;
System.out.println("prefixDepth-->"+prefixDepth+" (#mvseqs="+mvseqs.size()+")");
}
for (int a=0; a<A; a++) {
try {
ntries++;
int[] prefixaction=mvseqactions.get(mvsi);
/*seqs.clear();
seqs.add(new ArrayList<>());
for (int mi:mvseqs.get(mvsi))
seqs.get(0).add(mvs[mi]);*/
int code0=trees[a][0].codeAfterScramble(prefixaction,scrm0,scrm1);
//seqs.add(trees[a][0].solvemvs(code0));
/*if (mvseqs.get(mvsi).length+trees[a][0].depth(code0)+(trees[a][1].D-1)<=threshold) {
nskips++;
break PREFIXANDALTBLOCK;
}*/
int code1=trees[a][1].codeAfterScramble(trees[a][0].solveaction(code0),prefixaction,scrm0,scrm1);
//seqs.add(trees[a][1].solvemvs(code1));
if (mvseqs.get(mvsi).length+trees[a][0].depth(code0)+trees[a][1].depth(code1)<=threshold)
break PREFIXANDALTBLOCK;
}
catch (Exception e) {
e.printStackTrace();
System.out.println("reps="+reps);
System.out.println("scrm0="+Arrays.toString(scrm0)+", scrm1="+Arrays.toString(scrm1));
return false;
}
}
}
maxtries=Math.max(maxtries,ntries-ntries0);
/*if (Math.random()<1/1000_000.0) {
int[] solvedscrm=new int[tK];
System.arraycopy(tree0.pcstosolve,0,solvedscrm,0,tree0.K);
System.arraycopy(tree1.pcstosolve,0,solvedscrm,tree0.K,tree1.K);
System.out.print(boardStr(solvedscrm,prodperm(prodperm(solvedscrm.clone(),scrm1),scrm0),R,C));
for (List<int[]> tmp:seqs)
System.out.println(LoopoverBFS.mvseqStr(tmp));
}*/
}
reps++;
long time=System.currentTimeMillis()-st;
if (time>=mark) {
System.out.printf(form,String.format("%,.3f",time/1000.0),String.format("%,d",reps),
String.format("%,.3f",1000*reps/(double)time));
stage++;
mark=(long)(mark0*Math.pow(stage,2.5));
}
}
System.out.printf(form,String.format("%,.3f",(System.currentTimeMillis()-st)/1000.0),String.format("%,d",reps),
String.format("%,.3f",1000*reps/(double)(System.currentTimeMillis()-st)));
}
System.out.println("improvement time (sec)="+(System.currentTimeMillis()-timest)/1000.0);
System.out.println("mean # alternate attempted solutions per scramble="+ntries+"/"+ntrials+"="+(ntries/(double)ntrials));
System.out.println("maximum # attempts on a scramble="+maxtries);
System.out.println("mean # skips per scramble="+nskips+"/"+ntrials+"="+(nskips/(double)ntrials));
System.out.println("max prefix sequence length needed="+prefixDepth);
return true;
}
public static void main(String[] args) {
long st=System.currentTimeMillis();
LoopoverBFSImprove improver=new LoopoverBFSImprove(5,5,"11111x11111","00011x00011");
List<String> mids=new ArrayList<>();
for (int r=0; r<3; r++)
for (int c=0; c<3; c++) {
StringBuilder s=new StringBuilder("00011x00011");
s.setCharAt(r,'1');
s.setCharAt(6+c,'1');
mids.add(s.toString());
}
boolean[] tmp=new boolean[mids.size()];
Arrays.fill(tmp,true);
improver.improve(17,
mids.toArray(new String[0]),
tmp
);
System.out.println("total program time="+(System.currentTimeMillis()-st));
}
}
import java.util.*;
public class LoopoverBFS {
//TODO: REFACTOR USING ABSTRACT CLASS
private static int mod(int n, int k) {
return (n%k+k)%k;
}
private static boolean[] mask(String s) {
boolean[] out=new boolean[s.length()];
for (int i=0; i<s.length(); i++)
out[i]=s.charAt(i)=='1';
return out;
}
public static boolean[][] parseState(String s) {
String[] pcs=s.split("x");
if (pcs.length!=2) throw new RuntimeException("Not in 2 pieces: "+s);
return new boolean[][] {mask(pcs[0]),mask(pcs[1])};
}
private static boolean free(boolean[][] boardState, int r, int c) {
return boardState[0][r]||boardState[1][c];
}
public static String mvseqStr(List<int[]> S) {
StringBuilder str=new StringBuilder();
for (int[] m:S)
str.append(" ").append(m[0]==0?"R":"C").append(m[1]).append(m[2]==1?" ":m[2]==-1?"'":("("+m[2]+")"));
return str.toString();
}
//define absolute indexing as mapping coordinate (r,c) to index r*C+c
//every scramble is represented by an array L[], where piece i is at location L[i]
private int R, C;
private int F;
private boolean[][] rcfree;
//a location (r,c) is free iff Rfree[r]||Cfree[c]
private int[] tofree, freeto;
//tofree[r*C+c]=i, where free location (r,c) is assigned to index i
public int K;
public int[] pcstosolve; //list of pieces this tree tries to solve, in absolute indexing
private int[][] mvactions, mvs;
private int[][] solveactions, scrambleactions;
public static int[][] mvreduc(int[][] mvs) {
int M=mvs.length;
//move sequence reduction
//when doing two moves of the same type, one after the other: [t,a,r], [t,b,s]:
//WLOG a<=b, or else the two moves can be arranged to satisfy this condition without changing the final scramble
//if a==b, then r+s!=0, else the two moves cancel each other out
int[][] mvreduc=new int[M+1][];
for (int m=0; m<M; m++) {
List<Integer> l=new ArrayList<>();
for (int m2=0; m2<M; m2++)
if (mvs[m][0]!=mvs[m2][0]
||mvs[m][1]<mvs[m2][1]
||(mvs[m][1]==mvs[m2][1]&&mvs[m][2]+mvs[m2][2]!=0))
l.add(m2);
mvreduc[m]=new int[l.size()];
for (int i=0; i<l.size(); i++)
mvreduc[m][i]=l.get(i);
}
mvreduc[M]=new int[M];
for (int i=0; i<M; i++) mvreduc[M][i]=i;
return mvreduc;
}
private int M;
public int ncombos;
//bfs stuff
private long[] data;
public int[] depth;
private List<int[]> fronts; //BFS fronts
public int D; //(largest depth of BFS tree)+1
//c-->(depth,move from parent combo to c,parent combo)
private long compressed(int depth, int parent, int move) {
return ((long)depth*M+move)*ncombos+parent;
}
public int depth(int code) {
return data[code]==-1?-1:(int)(data[code]/ncombos/M);
}
private int par(int code) {
return data[code]==-1?-1:(int)(data[code]%ncombos);
}
private int mvi(int code) {
return data[code]==-1?-1:(int)((data[code]/ncombos)%M);
}
public LoopoverBFS(int R, int C, String state0, String state1) {
long st=System.currentTimeMillis();
this.R=R; this.C=C;
rcfree=parseState(state0);
tofree=new int[R*C]; freeto=new int[R*C];
F=0;
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
if (free(rcfree,r,c)) {
tofree[r*C+c]=F;
freeto[F]=r*C+c;
F++;
}
else tofree[r*C+c]=-1;
freeto=Arrays.copyOfRange(freeto,0, F);
boolean[][] nrcfree=parseState(state1);
K=0; pcstosolve=new int[R*C];
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
if (free(rcfree,r,c)&&!free(nrcfree,r,c))
pcstosolve[K++]=r*C+c;
pcstosolve=Arrays.copyOfRange(pcstosolve,0,K);
for (int r=0; r<R; r++) {
for (int c=0; c<C; c++)
System.out.printf("%4s",
free(rcfree,r,c)?
((free(nrcfree,r,c)?"":"'")+tofree[r*C+c]):
"X"
//': piece that this BFS tree tries to solve; *: gripped piece
);
System.out.println();
}
{
long tmp=1;
for (int rep=0; rep<K; rep++) tmp*=F-rep;
if (tmp>400_000_000) throw new RuntimeException("Too many combinations to handle.");
ncombos=(int)tmp;
}
System.out.println("ncombos="+ncombos);
//moves: every move is represented with [t,a,r]:
//t: type (0=row shift, 1=clm shift)
//a: the a-th (row if t==0, else clm)
//r: # units to shift (right if t==0, else down)
M=0;
for (boolean[] axis:rcfree)
for (boolean b:axis) if (b) M+=2;
mvactions=new int[M][]; mvs=new int[M][]; {
//mvactions[m][i]=free loc. that i-th free loc. will go to after move m is applied
int idx=0;
for (int mr=0; mr<R; mr++)
if (rcfree[0][mr])
for (int s=-1; s<=1; s+=2) {
mvs[idx]=new int[] {0,mr,s};
mvactions[idx]=new int[F];
for (int i=0; i<F; i++) {
int r=freeto[i]/C, c=freeto[i]%C;
mvactions[idx][i]=tofree[r*C+(r==mr?mod(c+s,C):c)];
}
idx++;
}
for (int mc=0; mc<C; mc++)
if (rcfree[1][mc])
for (int s=-1; s<=1; s+=2) {
mvs[idx]=new int[] {1,mc,s};
mvactions[idx]=new int[F];
for (int i=0; i<F; i++) {
int r=freeto[i]/C, c=freeto[i]%C;
mvactions[idx][i]=tofree[(c==mc?mod(r+s,R):r)*C+c];
}
idx++;
}
}
int[][] mvreduc=mvreduc(mvs);
//BFS
solveactions=new int[ncombos][];
scrambleactions=new int[ncombos][];
data=new long[ncombos]; Arrays.fill(data,-1);
fronts=new ArrayList<>();
{
int[] solvedscrm=new int[K];
for (int i=0; i<K; i++)
solvedscrm[i]=tofree[pcstosolve[i]];
int solvedscrmcode=comboCode(solvedscrm);
fronts.add(new int[] {solvedscrmcode});
data[solvedscrmcode]=0;
}
int[] nfront=new int[ncombos];
int reached=0;
for (D=0;; D++) {
if (fronts.get(D).length==0) break;
reached+=fronts.get(D).length;
System.out.print((D>0?" ":"")+D+":"+fronts.get(D).length);
int sz=0;
for (int f:fronts.get(D)) {
int[] scrm=codeCombo(f);
int[] mvlist=mvreduc[D==0?M:mvi(f)];
for (int mi:mvlist) {
int nf=comboCode(scrm,mvactions[mi]);
if (data[nf]==-1) {
data[nf]=compressed(D+1,f,mi);
nfront[sz++]=nf;
}
}
}
fronts.add(new int[sz]);
System.arraycopy(nfront,0,fronts.get(D+1),0,sz);
}
System.out.println("\n#reached="+reached);
System.out.println("D="+D);
System.out.println("total BFS time="+(System.currentTimeMillis()-st));
}
public void computeAllDepths() {
depth=new int[ncombos];
for (int code=0; code<ncombos; code++)
depth[code]=data[code]==-1?-1:depth(code);
}
public int[] codesAtDepth(int d) {
return fronts.get(d);
}
/*
encoding ordered combinations
A[0]...A[K-1], 0<=A[i]<N, all A[i] distinct
possible to transform permutation [0...N-1] into [....|A]
using a sequence of swaps (i,J_i) for i=N-1 to N-K inclusive
--> encode A as J_(N-1)+N*(J_(N-2)+(N-1)*(...+(N-K+2)*J_(N-K)...)
for this program, N=Nfree, K=K
*/
public int comboCode(int[] A) {
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
int[] L=P.clone();
int out=0;
for (int i=F-1, pow=1; i>=F-K; i--) {
//swap idxs i and L[A[i-(N-K)]] in P
int j=L[A[i-(F-K)]];
int pi=P[i];//, pj=P[j];
//P[i]=pj; //<--idx i will never be touched again
P[j]=pi;
L[pi]=j;
//L[pj]=i;
//J_i==j
out+=pow*j;
pow*=i+1;
}
return out;
}
private int comboCode(int[] A, int[] f) {
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
int[] L=P.clone();
int out=0;
for (int i=F-1, pow=1; i>=F-K; i--) {
int j=L[f[A[i-(F-K)]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
public int codeAfterScramble(int[] scrm0, int[] scrm1) {
//A[i]=tofree[scrm0[scrm1[pcstosolve[i]]]]
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
int[] L=P.clone();
int out=0;
for (int i=F-1, pow=1; i>=F-K; i--) {
int j=L[tofree[scrm0[scrm1[pcstosolve[i-(F-K)]]]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
public int codeAfterScramble(int[] scrm0, int[] scrm1, int[] scrm2) {
//A[i]=tofree[scrm0[scrm1[scrm2[pcstosolve[i]]]]]
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
int[] L=P.clone();
int out=0;
for (int i=F-1, pow=1; i>=F-K; i--) {
int j=L[tofree[scrm0[scrm1[scrm2[pcstosolve[i-(F-K)]]]]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
public int codeAfterScramble(int[] scrm0, int[] scrm1, int[] scrm2, int[] scrm3) {
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
int[] L=P.clone();
int out=0;
for (int i=F-1, pow=1; i>=F-K; i--) {
int j=L[tofree[scrm0[scrm1[scrm2[scrm3[pcstosolve[i-(F-K)]]]]]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
private int[] codeCombo(int code) {
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
for (int v=F; v> F-K; v--) {
int i=v-1, j=code%v;
code/=v;
int pi=P[i]; P[i]=P[j]; P[j]=pi;
}
int[] out=new int[K];
System.arraycopy(P, F-K,out,0,K);
return out;
}
public void computeAllActions() {
for (int code=0; code<ncombos; code++) if (data[code]!=-1) {
solveactions[code]=solveaction_help(code);
scrambleactions[code]=inv(solveactions[code]);
}
}
public int[] solveaction(int code) {
return solveactions[code]==null?solveaction_help(code):solveactions[code];
}
private int[] solveaction_help(int code) {
if (data[code]==-1) throw new RuntimeException("Invalid combination code: "+code);
int[] out=new int[F];
for (int i=0; i<F; i++) out[i]=i;
for (int c=code; depth(c)>0; c=par(c)) {
int[] mva=inv(mvactions[mvi(c)]);
int[] nout=new int[F];
for (int i=0; i<F; i++)
nout[i]=mva[out[i]];
out=nout;
}
return mva2abs(out);
}
public int[] scrambleaction(int code) {
return scrambleactions[code]==null?inv(solveaction(code)):scrambleactions[code];
}
public List<int[]> solvemvs(int code) {
List<int[]> out=new ArrayList<>();
for (int c=code; depth(c)>0; c=par(c)) {
int[] mv=mvs[mvi(c)];
out.add(new int[] {mv[0],mv[1],-mv[2]});
}
return out;
}
private static int[] inv(int[] P) {
//return inverse permutation of P
int[] I=new int[P.length];
for (int i=0; i<P.length; i++)
I[P[i]]=i;
return I;
}
private int[] mva2abs(int[] mva) {
//convert mva to array A
//where A[a]=b describes absolute location a being shifted to absolute location b
int[] out=new int[R*C];
for (int a=0; a<R*C; a++)
out[a]=tofree[a]==-1?a:freeto[mva[tofree[a]]];
return out;
}
public static void main(String[] args) {
new LoopoverBFS(5,5,"11111x11111","00111x00111");
new LoopoverBFS(5,5,"00111x00111","00011x00011");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment