15 puzzle solver: Difference between revisions
m
→{{header|Uiua}}: Improved algorithm
m (→{{header|Uiua}}: Added Uiua Pad link) |
m (→{{header|Uiua}}: Improved algorithm) |
||
Line 10,560:
=={{header|Uiua}}==
{{Works with |Uiua|0.12.0-dev.1}} Uses experimental `◹` and `astar`.
[https://www.uiua.org/pad?src=0_12_0-dev_1__IyBTb2x2ZSBhIDE1IHB1enpsZSBodHRwczovL3Jvc2V0dGFjb2RlLm9yZy93aWtpLzE1X3B1enpsZV9zb2x2ZXIjVWl1YQojIEV4cGVyaW1lbnRhbCEKVCDihpAg4oavNF80IOKGuzHih6ExNgojIFJldHVybiBzaHVmZmxlZCBjb3B5IG9mIHRoZSBpbnB1dC4KU2h1ZmZsZSDihpAg4oqP4oq4KOKNj1vijaXimoJd4qe7KQojIFBvc2l0aW9ucyBvZiB0aGUgbnVtYmVycyAobm90IDApClBvcyDihpAg4omhKOKKouKKmuKMlSnihpgx4oehMTbCpAoKIyBBcHBseWluZyBhIHZlcnkgZ2VudGxlIHdlaWdodGluZyB0byBjZXJ0YWluIGNlbGxzIG1hc3NpdmVseQojIHNwZWVkcyB1cCB0aGUgYWxnb3JpdGhtCldlaWdodHMg4oaQIFtbMiAxIDEgMl0gWzIgMSAxIDJdIFsyIDEgMSAyXSBbMiAxIDEgMV1dCkRpc3RhbmNlIOKGkCAvK8OX4oqhOldlaWdodHM64omhLyvijLUt4oqZLuKIqVBvcwpIZXVyaXN0aWMg4oaQIERpc3RhbmNlIFQKCiMgRm91ciBwb3NzaWJsZSBuZWlnaGJvdXJzCk5mb3VyIOKGkCBbWzEgMF0gW8KvMSAwXSBbMCAxXSBbMCDCrzFdXQojIEFjdHVhbCBuZWlnaGJvdXJzIGF0IGEgcG9pbnQuClZhbGlkTiDihpAg4omhKOKKginiipnCpDrin5wo4pa94oq4KOKJpTDiiaEv4oanKeKWveKKuCg8NOKJoS_ihqUpK05mb3VyKcKkCiMgUHJlY2FsY3VsYXRlIHRoZW0uClZhbGlkTnMg4oaQIOKKnijilqEgVmFsaWRO4oqfKeKHoTQg4oehNAoKIyBHZXQgdGhlIHZhbGlkIChmcm9tIHRvKSBtb3ZlcyBmcm9tIHRoaXMgY2VsbC4KTW92ZXMg4oaQIMKw4pah4oqhOlZhbGlkTnPiiqLiiprijJUwCiMgU3dhcCB0aGUgdmFsdWVzIGF0IHRoZSBpbmRleGVzIFswIDFdIFthIGIgMiAzXSAtPiBbYiBhIDIgM10KU3dhcCDihpAg4o2cKOKKoXziiJjil4wpIOKKgyjih4ziipniiJh84oqhKQojIExpc3QgdGhlIHBvc3NpYmxlIG5leHQgcG9zaXRpb25zIGZvciBhIHBvc2l0aW9uCk5leHQg4oaQIOKKmeKXjOKJoShTd2FwIOKKmS4p4oqZwqTiirhNb3ZlcwpTb2x2ZSDihpAgKAogICZwIlJ1bm5pbmcuLi4iJnAuCiAg4o2cbm93YXN0YXIoTmV4dHxIZXVyaXN0aWN84omNVCkKICAmcCQiXyBzZWNvbmRzIgogICMgVHJhY2sgdGhlIG1vdmVtZW50IG9mIHRoZSAwIGJldHdlZW4gYWRqYWNlbnQgc3RlcHMuCiAg4omhKC8tKeKXqzLil4fiiaEo4oqi4oqa4oyVMCnih4ziiqIKICAjIE1hcCBlYWNoIHRvIGEgZGlyZWN0aW9uIHN0cmluZyBhbmQgam9pbi4KICAv4oqC4oeM4omh4o2jKCJkIiDCsMKvMV8wfCJ1IiDCsDFfMHwiciIgwrAwX8KvMXwibCIgwrAwXzF84oiYKQopCgojIFVuY29tbWVudCBvbmUgb2YgdGhlIGZvbGxvd2luZyBsaW5lcyB0byB0cnkgcmFuZG9tIGdyaWRzCiMg4o2lKFN3YXDiiqHiirgo4oyKw5fimoLip7sp4oq4TW92ZXMpOTAgVAojIFtbMiAxNCA2IDRdIFs1IDEgMyA4XSBbOSAxMCA3IDExXSBbMTMgMCAxNSAxMl1dICMgU2ltcGxlIDQwIHNodWZmbGVzCiMgW1s1IDEgMiAzXSBbNiAxMCA3IDRdIFsxMyA5IDExIDhdIFsxNCAwIDE1IDEyXV0gIyBTaW1wbGUgMTIgc3RlcHMKIyBbWzkgMSAyIDRdIFsxMyA2IDUgN10gWzMgMTEgMTQgMTVdIFsxMCAwIDggMTJdXSAjIDM0IHN0ZXBzCiMgW1sxMCAzIDEgNF0gWzEzIDUgOCA3XSBbOSA2IDAgMTFdIFsxNCAxNSAxMiAyXV0gIyAzOCBzdGVwcyAoYSBmZXcgc2Vjb25kcykKW1sxNSAxNCAxIDZdIFs5IDExIDQgMTJdIFswIDEwIDcgM10gWzEzIDggNSAyXV0gIyBNYWluIENoYWxsZW5nZQojIFtbMCAxMiA5IDEzXSBbMTUgMTEgMTAgMTRdIFszIDcgMiA1XSBbNCA4IDYgMV1dICMgRXh0cmEgQ3JlZGl0CgpTb2x2ZQo= Try it in Uiua Pad!] (runs about a third of the speed of native).
<syntaxhighlight lang="uiua">
# Solve a 15 puzzle https://rosettacode.org/wiki/15_puzzle_solver#Uiua
# Experimental!
T ← ↯4_4 ↻1⇡16
Line 10,571:
# Positions of the numbers (not 0)
Pos ← ≡(⊢⊚⌕)↘1⇡16¤
# Applying a very gentle weighting to certain cells massively
Distance ← /+/+⌵-∩Pos▼
# speeds up the algorithm
Weights ← [[2 1 1 2] [2 1 1 2] [2 1 1 2] [2 1 1 1]]
▲Distance ← /+×⊡:Weights:≡/+⌵-⊙.∩Pos
Heuristic ←
# Four possible neighbours
Line 10,596 ⟶ 10,591:
# List the possible next positions for a position
Next ← ⊙◌≡(Swap ⊙.)⊙¤⊸Moves
Solve ← (
&p"Running..."&p.▼
⍜nowastar(Next|Heuristic|≍T)▼
&p$"_ seconds"▼
# Track the movement of the 0 between adjacent steps.▼
≡(/-)◫2◇≡(⊢⊚⌕0)⇌⊢▼
# Map each to a direction string and join.
/⊂⇌≡⍣("d" °¯1_0|"u" °1_0|"r" °0_¯1|"l" °0_1|∘)▼
)
# Uncomment one of the following lines to try random grids
# ⍥(Swap⊡⊸(⌊×⚂⧻)⊸Moves)90 T
# [[2 14 6 4] [5 1 3 8] [9 10 7 11] [13 0 15 12]] # Simple 40 shuffles
# [[5 1 2 3] [6 10 7 4] [13 9 11 8] [14 0 15 12]] # Simple 12 steps
# [[9 1 2 4] [13 6 5 7] [3 11 14 15] [10 0 8 12]] # 34 steps
# [[
[[15 14 1 6] [9 11 4 12] [0 10 7 3] [13 8 5 2]] # Main Challenge
# [[0 12 9 13] [15 11 10 14] [3 7 2 5] [4 8 6 1]] # Extra Credit
Solve
▲&p"Running..."&p.
▲⍜nowastar(Next|Heuristic|≍T)
▲&p$"_ seconds"
▲# Track the movement of the 0 between adjacent steps.
▲≡(/-)◫2◇≡(⊢⊚⌕0)⇌⊢
▲/⊂⇌≡⍣("d" °¯1_0|"u" °1_0|"r" °0_¯1|"l" °0_1|∘)
</syntaxhighlight>
{{out}}
Line 10,620 ⟶ 10,621:
╯
Running...
52
"rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd"
| |||