Wave function collapse: Difference between revisions

← Older edit

Wave function collapse (view source)

Revision as of 11:53, 16 February 2024

100,778 bytes added , 3 months ago

m

→‎{{header|Wren}}: Minor tidy

PureFox

9,483

edits

Revision as of 10:27, 10 July 2022 (view source) Rdm (talk \| contribs) m (→‎{{header\|J}}) ← Older edit		Latest revision as of 11:53, 16 February 2024 (view source) PureFox (talk \| contribs) m (→‎{{header\|Wren}}: Minor tidy)
(61 intermediate revisions by 7 users not shown)
Line 1: {{draft task}} {{Clarify task}} The '''Wave Function Collapse''' algorithm is a heuristic for generating tiled images. Write the solution for Wave Function Collapse based on the [https://youtu.be/rI_y2GAlQFM Coding Challenge 171: Wave Function Collapse] and create new map 8x8 tiles with fourth T-blocks with variously directions (┤ ┴ ┬ ├) or blank tiles (space). The algorithm begins with a collection of equal sized image blocks and randomly places them, one at a time, within a grid subject to the tiling constraint and an entropy constraint, and it wraps (the top row of blocks in the grid is treated as ''adjacent'' to the bottom row of blocks, and similarly the left and right columns of blocks are treated as adjacent to each other). The blocks are tiled within the grid. ''Tiled'' means they are placed with a one pixel overlap and the tiling constraint requires that the pixels overlapping border between two adjacent blocks match. ''Entropy'', here, means the number of blocks eligible to be placed in an unassigned grid location. The entropy constraint here is that each block is placed in a grid location with minimum entropy. (Placing a block may constrain the entropy of its four nearest neighbors -- up, down, left, right.) For this task, we start with five blocks of 3x3 pixels and place them in an 8x8 grid to form a 17x17 tile. A tile is a block which may be tiled with itself. Here, we show these five blocks adjacent but not ''tiled'': <table border="1px"><tr><td> <table><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr></table> </td><td> <table><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr></table> </td><td> <table><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr></table> </td><td> <table><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr></table> </td><td> <table><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr></table> </td></tr></table> Note that this algorithm sometimes does not succeed. If an unassigned grid location has an entropy of 0, the algorithm fails and returns an empty or null result. We'll ignore those failure cases for this task. ;Reference [https://www.boristhebrave.com/2020/04/13/wave-function-collapse-explained/ WFC explained] and [https://github.com/mxgmn/WaveFunctionCollapse another WFC explained] =={{header\|C}}== {{trans\|J}}<syntaxhighlight lang="c">#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define XY(row, col, width) ((col)+(row)(width)) #define XYZ(page, row, col, height, width) XY(XY(page, row, height), col, width) char blocks[5][3][3]= { { {0, 0, 0}, {0, 0, 0}, {0, 0, 0} },{ {0, 0, 0}, {1, 1, 1}, {0, 1, 0} },{ {0, 1, 0}, {0, 1, 1}, {0, 1, 0} },{ {0, 1, 0}, {1, 1, 1}, {0, 0, 0} },{ {0, 1, 0}, {1, 1, 0}, {0, 1, 0} } }; / avoid problems with slightly negative numbers and C's X%Y / #define MOD(X,Y) ((Y)+(X))%(Y) char wfc(char blocks, int bdim /* 5,3,3 /, int tdim /* 8,8 /) { int N= tdim[0]tdim[1], td0= tdim[0], td1= tdim[1]; int adj= calloc(N4, sizeof (int)); /* indices in R of the four adjacent blocks / for (int i= 0; i<td0; i++) { for (int j=0; j<td1; j++) { adj[XYZ(i,j,0,td1,4)]= XY(MOD(i-1, td0), MOD(j, td1), td1); / above (index 1 in a 3x3 grid) / adj[XYZ(i,j,1,td1,4)]= XY(MOD(i, td0), MOD(j-1, td1), td1); / left (index 3 in a 3x3 grid) / adj[XYZ(i,j,2,td1,4)]= XY(MOD(i, td0), MOD(j+1, td1), td1); / right (index 5 in a 3x3 grid) / adj[XYZ(i,j,3,td1,4)]= XY(MOD(i+1, td0), MOD(j, td1), td1); / below (index 7 in a 3x3 grid) / } } int bd0= bdim[0], bd1= bdim[1], bd2= bdim[2]; char horz= malloc(bd0bd0); / blocks which can sit next to each other horizontally / for (int i= 0; i<bd0; i++) { for (int j= 0; j<bd0; j++) { horz[XY(i,j,bd0)]= 1; for (int k= 0; k<bd1; k++) { if (blocks[XYZ(i, k, 0, bd1, bd2)] != blocks[XYZ(j, k, bd2-1, bd1, bd2)]) { horz[XY(i, j, bd0)]= 0; } } } } char vert= malloc(bd0bd0); / blocks which can sit next to each other vertically / for (int i= 0; i<bd0; i++) { for (int j= 0; j<bd0; j++) { vert[XY(i,j,bd0)]= 1; for (int k= 0; k<bd2; k++) { if (blocks[XYZ(i, 0, k, bd1, bd2)] != blocks[XYZ(j, bd1-1, k, bd1, bd2)]) { vert[XY(i, j, bd0)]= 0; break; } } } } char allow= malloc(4(bd0+1)bd0); /* all block constraints, based on neighbors / memset(allow, 1, 4(bd0+1)bd0); for (int i= 0; i<bd0; i++) { for (int j= 0; j<bd0; j++) { allow[XYZ(0, i, j, bd0+1, bd0)]= vert[XY(j, i, bd0)]; / above (north) / allow[XYZ(1, i, j, bd0+1, bd0)]= horz[XY(j, i, bd0)]; / left (west) / allow[XYZ(2, i, j, bd0+1, bd0)]= horz[XY(i, j, bd0)]; / right (east) / allow[XYZ(3, i, j, bd0+1, bd0)]= vert[XY(i, j, bd0)]; / below (south) / } } free(horz); free(vert); int todo= calloc(N, sizeof (int)); char wave= malloc(Nbd0); int entropy= calloc(N, sizeof (int)); int indices= calloc(N, sizeof (int)); int min; int possible= calloc(bd0, sizeof (int)); int R= calloc(N, sizeof (int)); /* tile expressed as list of block indices / for (int i= 0; i<N; i++) R[i]= bd0; while (1) { int c= 0; for (int i= 0; i<N; i++) if (bd0==R[i]) todo[c++]= i; if (!c) break; min= bd0; for (int i= 0; i<c; i++) { entropy[i]= 0; for (int j= 0; j<bd0; j++) { int K= 4todo[i]; entropy[i]+= wave[XY(i, j, bd0)]= allow[XYZ(0, R[adj[XY(todo[i],0,4)]], j, bd0+1, bd0)] & allow[XYZ(1, R[adj[XY(todo[i],1,4)]], j, bd0+1, bd0)] & allow[XYZ(2, R[adj[XY(todo[i],2,4)]], j, bd0+1, bd0)] & allow[XYZ(3, R[adj[XY(todo[i],3,4)]], j, bd0+1, bd0)]; } if (entropy[i] < min) min= entropy[i]; } if (!min) { free(R); R= NULL; break; } int d= 0; for (int i= 0; i<c; i++) { if (min==entropy[i]) indices[d++]= i; } int ndx= indices[random()%d]; int ind= ndxbd0; d= 0; for (int i= 0; i<bd0; i++) { if (wave[ind+i]) possible[d++]= i; } R[todo[ndx]]= possible[random()%d]; } free(adj); free(allow); free(todo); free(wave); free(entropy); free(indices); free(possible); if (!R) return NULL; char tile= malloc((1+td0(bd1-1))(1+td1(bd2-1))); for (int i0= 0; i0<td0; i0++) for (int i1= 0; i1<bd1; i1++) for (int j0= 0; j0<td1; j0++) for (int j1= 0; j1<bd2; j1++) tile[XY(XY(j0, j1, bd2-1), XY(i0, i1, bd1-1), 1+td1(bd2-1))]= blocks[XYZ(R[XY(i0, j0, td1)], i1, j1, bd1, bd2)]; free(R); return tile; } int main() { int bdims[3]= {5,3,3}; int size[2]= {8,8}; time_t t; srandom((unsigned) time(&t)); char tile= wfc((char)blocks, bdims, size); if (!tile) exit(0); for (int i= 0; i<17; i++) { for (int j= 0; j<17; j++) { printf("%c ", " #"[tile[XY(i, j, 17)]]); } printf("\n"); } free(tile); exit(0); }</syntaxhighlight> Note: here we use <code>R</code> where J used <code>i</code>, because we use i as an index/loop counter (other than <code>m</code>, <code>y</code> and <code>i</code>), the comments on [[#J\|the j implementation]] should be directly relevant here. Also, when assembling the result at the end, it was convenient to treat the block overlap issue during indexing. For simplicity, we use <tt>char</tt> as our pixel datatype (and for truth values), and <tt>int</tt> for indices (C offers a variety of similar datatypes but nothing we are doing here is big enough for that to be a concern). {{out}} <pre> # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #</pre> =={{header\|J}}== Implementation:<~~lang~~syntaxhighlight Jlang="j">~~tiles~~blocks=: 0,(\|.@\|:)^:(i.4)0,1 1 1,:0 1 0 wfc=: {{ adj=.: y#.y\|"1(y#:,i.y)+"1/0,<:3 3#:1 3 5 7 horz=.: ({."1 -:"1/ {:"1) m NB. horizontal tile pairs vert=.: ({."2 -:"1/ {:"2) m NB. vertical tile pairs idnorth=.: ~~<@I.(=i.#tiles)~~1,1~\|:vert NB. ~~identity~~adj 1 constraint ~~north~~south=.: ~~<@I.~~1,~vert,1 NB. adj 17 constraint ~~south~~west=.: ~~<@I.(~~ 1,~\|:~~vert),1~~horz NB. adj 73 ~~constraint~~constrint ~~west~~east=.: ~~<@I.~~1,~horz,1 NB. adj 35 constraint ~~constrint~~ allow=: north,west,east,:south ~~east=. <@I.(\|:horz),1 NB. adj 5 constraint~~ i=: ,y$_1 ~~allow=. id,north,west,east,:south~~ i=while. (?#m)todo=: ~~(?#~~I._1=i)} i=do. ~~,y$_1~~ wave=: /"2 ((todo{adj){i){"0 2"1 3 allow ~~while. #todo=. I._1=i do.~~ entropy=: +/"1 wave ~~wave=. ([-.-.)L:0/"1 (adj{i){"0 1"1 2 allow~~ ~~entropy~~min=: <./ ~~#@>wave~~entropy ~~min=. <./ E=. todo{entropy~~ if. 0=min do. EMPTY return. end. ndx=.: ~~todo{~~~({~ ?@#) I.min=Eentropy i=.: (({~?@#)I.ndx{::wave) (ndx{todo)} i end. lap=. {{ y#~(+0=i.@#)-.;m$<n{.1 }} ~~,/"2,/0 2 1 3\|:(y$i){m~~ ({:y)lap({:$m)"1 ({.y)lap({:$m),/"2,/0 2 1 3\|:(y$i){m ~~}}</lang>~~ }}</syntaxhighlight> We work with the 3x3 partial tiles, and the larger 17x17 tile which we are randomly generating. (17x17 because every 3x3 block contributes 2x2 pixels to the result and along a horizontal and vertical edge row and column of the tile, the 3x3 blocks contribute an additional row and column of pixels.) Here, <code>m</code> is the list of tiles, and <code>i</code> represents an 8x8 list of indexes into that list, with <code>_1</code> being a placeholder for the case where the index hasn't been choosen -- initially, we pick a random location in i and assign an arbitrarily picked tile to that location. Here, <code>~~adj~~m</code> ~~indexes~~is ~~into~~the ~~<code>i</code>~~list --of ~~for~~argument ~~each~~blocks ~~item~~(which are the 3x3 blocks in ~~<code>i</code>~~this example), and <code>~~adj~~i</code> ~~selects~~represents ~~that~~an ~~item,~~8x8 ~~the~~list ~~item~~of ~~"above"~~indexes ~~it,~~into ~~the~~that ~~item~~list to(or, ~~the~~conceptually, ~~"left"~~whatever ofdimensions ~~it,~~were ~~the~~specified ~~item~~by to<code>y</code>, the "right" ofargument itto ~~and~~<code>wfc</code> ~~the~~-- ~~item~~but ~~"below"~~for itthis ~~(with scare quotes because the tile represented by~~task <code>iy</code> ~~"wraps~~will ~~around"~~always onbe ~~all~~<code>8 ~~sides~~8</code>)~~. And~~, with <code>~~allow~~_1</code> ~~lists~~being a placeholder for the ~~allowable~~case ~~tiles~~where ~~corresponding~~the toindex ~~each~~hasn't ofbeen ~~those~~choosen -- initially, we pick a random location in <code>~~adj~~i</code> ~~constraints~~and assign an arbitrarily picked tile to that location. To<code>adj</code> indexes ~~build~~into <code>~~allow~~i</code> we-- ~~first~~for ~~matched~~each ~~the~~item ~~left~~in ~~side~~<code>i</code>, of<code>adj</code> ~~each~~selects ~~tile~~that ~~with~~item, the ~~right~~item ~~side~~"above" ofit, ~~each~~the ~~tile~~item ~~(cartesian~~to ~~product)~~the ~~forming~~"left" ~~<code>horz</code>~~of ~~and~~it, ~~similarly~~the ~~matched~~item to the ~~tops~~"right" of it and ~~bottoms~~the ofitem "below" it (with scare quotes because the ~~tiles~~constructed ~~forming~~tile represented by <code>~~vert~~i</code>. ~~Then~~"wraps wearound" ~~built~~on all sides). And <code>idallow</code> ~~which~~lists ~~selects~~the ~~only~~allowable ~~the~~blocks ~~tile~~corresponding ~~itself~~to ~~(or~~each ~~all~~of ~~tiles, for~~those <code>~~i=_1~~adj</code>), constraints (there's no particular order to the items in <code>~~north~~allow</code> ~~which~~-- ~~limits~~it ~~tiles~~must ~~based~~include onall ~~the~~four ~~tile~~directions, ~~above~~but it, ~~and~~does sonot onmatter ~~for~~which ~~<code>west</code>,~~direction ~~<code>east</code>,~~we ~~and~~look ~~<code>south</code>~~at "first"). ~~Once~~To ~~we're set up, we drop into a loop:~~build <code>~~todo~~allow</code> ~~selects~~we ~~the~~first ~~unchosen~~matched ~~tile~~the ~~locations,~~left ~~<code>wave</code>lists~~side ~~for~~of each ~~location~~block with the ~~eligible~~right ~~tiles,~~side ~~and~~of each block (cartesian product) forming <code>~~entropy~~horz</code> ~~counts~~and ~~how~~similarly ~~many~~matched ~~tiles~~the ~~are~~tops ~~eligible~~and ~~for~~bottoms ~~each~~of ~~location~~the --tiles forming <code>Evert</code>. isThen ~~the~~we ~~entropy for the unchosen locations, and~~build <code>~~min~~north</code> iswhich limits tiles based on the ~~smallest~~tile ~~value~~above init, and similarly for <code>Ewest</code>., <code>~~ndx~~east</code>, ~~is a randomly picked index into~~and <code>isouth</code> ~~with~~(when ~~minimal~~the ~~entropy~~adjacent ~~and~~tile ~~for~~is ~~that location we randomly pick one of the options and update~~a <code>i_1</code> ~~with it. (When there's only one option remaining~~tile, ~~"randomly~~no ~~pick"~~limit ~~here~~is ~~means we pick that option~~imposed).) Once we're set up, we drop into a loop: <code>todo</code> selects the unchosen block locations, <code>wave</code>lists each of the unchosen block locations (for each <code>todo</code> value in <code>i</code> we select the tiles allowed by each of its adjacent locations and find the set intersection of all of those), <code>entropy</code> counts how many tiles are eligible for each of those location, and <code>min</code> is the smallest value in <code>entropy</code>. <code>ndx</code> is a randomly picked index into <code>todo</code> with minimal entropy and for that location we randomly pick one of the options and update <code>i</code> with it. (When there's only one option remaining, "randomly pick" here means we pick that option.) ~~Once we've assigned a tile to every location in i, we use those indices to assemble the result.~~ Once we've assigned a block to every location in <code>i</code>, we use those indices to assemble the result (the 3x3 blocks overlap at their borders so we introduce a mechanism to discard the redundant pixels). For task purposes here, we will use space to represent a white pixel and "#" to represent a black pixel. Also, because characters are narrow, we will insert a space between each of these "pixels" to better approximate a square aspect ratio. For task purposes, we will use space to represent a white pixel and "#" to represent a black pixel. Also, because characters are narrow, we will insert a space between each of these "pixels" to better approximate a square aspect ratio. ~~Task example (the initial tiles and two runs of wave function collapse (two, to illustrate randomness):<lang J> (<"2) 1j1#"1 ' #'{~ tiles~~ Task example: the initial blocks and three runs of wave function collapse (three, to illustrate randomness): <syntaxhighlight lang="j"> (<"2) 1j1#"1 ' #'{~ blocks ┌──────┬──────┬──────┬──────┬──────┐ │ │ │ # │ # │ # │ Line 49 ⟶ 262: └──────┴──────┴──────┴──────┴──────┘ task=: {{ 1j1#"1 ' #'{~ ~~tiles~~blocks wfc 8 8}} task&.>0 0 0 ~~# # # #~~ ┌──────────────────────────────────┬──────────────────────────────────┬──────────────────────────────────┐ ~~# # # # # # # # # # # # # # # # #~~ │ # # # # │ # # # # # # │ # # # # # │ │# # # # # # # # # # # # # # │ # # # # # # # # # # # # # # │ # # # # # # # # # # # # │ #│ # # # # # # # # # # # │ # # # # # # │ # # # # # # │ │ # # # # # # # # # # # # │ # # # # # # # # # # # # # # │# # # # # # # # # # # # # # # │ │ # # # # # # │ # # # # # # │ # # # # # # │ │# # # # # # # # # # # # # # # │# # # # # # # # # # # │# # # # # # # # # # # # # # # │ │ # # # # # # │ # # # # │ # # # # # # │ │# # # # # # # # # # # # # # # │ # # # # # # # # # # # │ # # # # # # # # # # # │ #│ # # # # # # # # │ # # # # │ # # # # # # # │ │# # # # # # # # # # # # # # # │# # # # # # # # # # # │# # # # # # # # # # # # # │ │ # # # # # # │ # # # # # # │ # # # # │ │ # # # # # # # # # # # # │# # # # # # # # # # │ # # # # # # # # │ │ # # # # # │ # # # # # # │ # # # # # │ │# # # # # # # # # # # # # # │# # # # # # # # # # # # # # # │# # # # # # # # # # # │ #│ # # # # # # # # # # │ # # # # # # │ # # # # # │ │ # # # # # # │# # # # # # # # # # # # # # # │# # # # # # # # # # # │ │ # # # # │ # # # # # # │ # # # # # │ └──────────────────────────────────┴──────────────────────────────────┴──────────────────────────────────┘</syntaxhighlight> ~~# # # # # # # # # # # # # # # # #~~ ~~# # # #~~ =={{header\|Nim}}== ~~# # # # # # #~~ {{trans\|C}} ~~# # # # # # # # # # # # # # # # # #~~ <syntaxhighlight lang="Nim">import std/[algorithm, math, random] ~~# # # # # # #~~ template XY(row, col, width: int): int = col + row width template XYZ(page, row, col, height, width: int): int = XY(XY(page, row, height), col, width) const Blocks = @[byte 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0] proc wfc(blocks: seq[byte]; bdim: (int, int, int); tdim: (int, int); ): seq[byte] = let (td0, td1) = tdim let n = td0 * td1 var adj = newSeq[int](n * 4) # Indices in R of the four adjacent blocks. for i in 0..<td0: for j in 0..<td1: adj[XYZ(i, j, 0, td1, 4)]= XY(floorMod(i-1, td0), floorMod(j, td1), td1) adj[XYZ(i, j, 1, td1, 4)]= XY(floorMod(i, td0), floorMod(j-1, td1), td1) adj[XYZ(i, j, 2, td1, 4)]= XY(floorMod(i, td0), floorMod(j+1, td1), td1) adj[XYZ(i, j, 3, td1, 4)]= XY(floorMod(i+1, td0), floorMod(j, td1), td1) let (bd0, bd1, bd2) = bdim var horz = newSeq[byte](bd0 * bd0) for i in 0..<bd0: for j in 0..<bd0: horz[XY(i, j, bd0)]= 1 for k in 0..<bd1: if blocks[XYZ(i, k, 0, bd1, bd2)] != blocks[XYZ(j, k, bd2-1, bd1, bd2)]: horz[XY(i, j, bd0)]= 0 var vert = newSeq[byte](bd0 * bd0) for i in 0..<bd0: for j in 0..<bd0: vert[XY(i, j, bd0)]= 1 for k in 0..<bd2: if blocks[XYZ(i, 0, k, bd1, bd2)] != blocks[XYZ(j, bd1-1, k, bd1, bd2)]: vert[XY(i, j, bd0)]= 0 break var allow = newSeq[byte](4 * (bd0 + 1) * bd0) allow.fill(1) for i in 0..<bd0: for j in 0..<bd0: allow[XYZ(0, i, j, bd0+1, bd0)] = vert[XY(j, i, bd0)] allow[XYZ(1, i, j, bd0+1, bd0)] = horz[XY(j, i, bd0)] allow[XYZ(2, i, j, bd0+1, bd0)] = horz[XY(i, j, bd0)] allow[XYZ(3, i, j, bd0+1, bd0)] = vert[XY(i, j, bd0)] var todo = newSeq[int](n) wave = newSeq[byte](n * bd0) entropy = newSeq[int](n) indices = newSeq[int](n) possible = newSeq[int](bd0) var r = newSeq[int](n) r.fill(bd0) while true: var c = 0 for i in 0..<n: if bd0 == r[i]: todo[c]= i inc c if c == 0: break var min = bd0 for i in 0..<c: entropy[i] = 0 for j in 0..<bd0: let val = allow[XYZ(0, r[adj[XY(todo[i],0,4)]], j, bd0+1, bd0)] and allow[XYZ(1, r[adj[XY(todo[i],1,4)]], j, bd0+1, bd0)] and allow[XYZ(2, r[adj[XY(todo[i],2,4)]], j, bd0+1, bd0)] and allow[XYZ(3, r[adj[XY(todo[i],3,4)]], j, bd0+1, bd0)] wave[XY(i, j, bd0)] = val entropy[i] += val.int if entropy[i] < min: min = entropy[i] if min == 0: r.setLen(0) break var d = 0 for i in 0..<c: if min == entropy[i]: indices[d] = i inc d var ndx = indices[rand(d - 1)] let ind = ndx * bd0 d = 0 for i in 0..<bd0: if wave[ind + i] != 0: possible[d] = i inc d r[todo[ndx]] = possible[rand(d - 1)]; if r.len == 0: return @[] result = newSeq[byte]((1 + td0 * (bd1 - 1)) * (1 + td1 * (bd2 - 1))) for i0 in 0..<td0: for i1 in 0..<bd1: for j0 in 0..<td1: for j1 in 0..<bd2: result[XY(XY(j0, j1, bd2-1), XY(i0, i1, bd1-1), 1+td1(bd2-1))] = blocks[XYZ(r[XY(i0, j0, td1)], i1, j1, bd1, bd2)] const BDims = (5, 3, 3) const Size = (8, 8) randomize() let tile = wfc(Blocks, BDims, Size) if tile.len == 0: quit QuitSuccess for i in 0..16: for j in 0..16: stdout.write " #"[tile[XY(i, j, 17)]], ' ' echo() </syntaxhighlight> {{out}} <pre> # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # </pre> =={{header\|Perl}}== {{trans\|Raku}} <syntaxhighlight lang="perl">use v5.36; use experimental 'for_list'; my @Blocks = ( [ <0 0 0>, <0 0 0>, <0 0 0> ], [ <0 0 0>, <1 1 1>, <0 1 0> ], [ <0 1 0>, <0 1 1>, <0 1 0> ], [ <0 1 0>, <1 1 1>, <0 0 0> ], [ <0 1 0>, <1 1 0>, <0 1 0> ], ); sub X($a,$b) { my @c; for my $aa (0..$a-1) { map { push @c, $aa, $_ } 0..$b-1 } @c } sub XY( $row, $col, $width) { $col + $row $width } sub XYZ($page, $row, $col, $height, $width) { XY( XY($page, $row, $height), $col, $width) } sub wfc($B, $bdim, $tdim) { my ($td0,$td1) = @$tdim; my $N = $td0 * $td1; my @blocks = map @$_, @$B; # flatten my @adj; # indices in R of the four adjacent blocks for my($i,$j) (X $td0, $td1) { $adj[XYZ($i, $j, 0, $td1, 4)] = XY(($i-1)%$td0, $j %$td1, $td1); # above (index 1) $adj[XYZ($i, $j, 1, $td1, 4)] = XY( $i %$td0, ($j-1)%$td1, $td1); # left (index 3) $adj[XYZ($i, $j, 2, $td1, 4)] = XY( $i %$td0, ($j+1)%$td1, $td1); # right (index 5) $adj[XYZ($i, $j, 3, $td1, 4)] = XY(($i+1)%$td0, $j %$td1, $td1); # below (index 7) } my ($bd0,$bd1,$bd2) = @$bdim; my @horz; # blocks which can sit next to each other horizontally for my($i,$j) (X $bd0, $bd0) { @horz[XY($i,$j,$bd0)] = 1; for my $k (0..$bd1-1) { $horz[XY($i, $j, $bd0)]= 0 if $blocks[XYZ($i, $k, 0, $bd1, $bd2)] != $blocks[XYZ($j, $k, $bd2-1, $bd1, $bd2)] } } my @vert; # blocks which can sit next to each other vertically / for my($i,$j) (X $bd0, $bd0) { $vert[XY($i,$j,$bd0)] = 1; for my $k (0..$bd2-1) { if ($blocks[XYZ($i, 0, $k, $bd1, $bd2)] != $blocks[XYZ($j, $bd1-1, $k, $bd1, $bd2)]) { $vert[XY($i, $j, $bd0)] = 0; last } } } my @allow = (1) x (4($bd0+1)$bd0); # all block constraints, based on neighbors for my($i,$j) (X $bd0, $bd0) { $allow[XYZ(0, $i, $j, $bd0+1, $bd0)] = $vert[XY($j, $i, $bd0)]; # above (north) $allow[XYZ(1, $i, $j, $bd0+1, $bd0)] = $horz[XY($j, $i, $bd0)]; # left (west) $allow[XYZ(2, $i, $j, $bd0+1, $bd0)] = $horz[XY($i, $j, $bd0)]; # right (east) $allow[XYZ(3, $i, $j, $bd0+1, $bd0)] = $vert[XY($i, $j, $bd0)]; # below (south) } my @R = ($bd0) x $N; my (@todo, @wave, @entropy, @indices, $min, @possible); while () { my $c; for (0..$N-1) { $todo[$c++] = $_ if $bd0 == $R[$_] } last unless $c; $min = $bd0; for my $i (0..$c-1) { $entropy[$i] = 0; for my $j (0..$bd0-1) { $entropy[$i] += $wave[XY($i, $j, $bd0)] = $allow[XYZ(0, $R[ $adj[XY($todo[$i],0,4)] ], $j, $bd0+1, $bd0)] & $allow[XYZ(1, $R[ $adj[XY($todo[$i],1,4)] ], $j, $bd0+1, $bd0)] & $allow[XYZ(2, $R[ $adj[XY($todo[$i],2,4)] ], $j, $bd0+1, $bd0)] & $allow[XYZ(3, $R[ $adj[XY($todo[$i],3,4)] ], $j, $bd0+1, $bd0)] } $min = $entropy[$i] if $entropy[$i] < $min } @R=[] and last unless $min; my $d = 0; for (0..$c-1) { $indices[$d++] = $_ if $min == $entropy[$_] } my $ind = $bd0 (my $ndx = $indices[ int rand $d ]); $d = 0; for (0..$bd0-1) { $possible[$d++] = $_ if $wave[$ind+$_] } $R[$todo[$ndx]] = $possible[ int rand $d ]; } return "DOES NOT COMPUTE" unless @R > 1; my @tile; for my($i0,$i1)(X $td0, $bd1) { for my($j0,$j1) (X $td1, $bd2) { $tile[XY(XY($j0, $j1, $bd2-1), XY($i0, $i1, $bd1-1), 1+$td1($bd2-1))] = (' ','#')[ $blocks[XYZ($R[XY($i0, $j0, $td1)], $i1, $j1, $bd1, $bd2)] ] } } my $width = 2 sqrt scalar @tile; join(' ', @tile) =~ s/.{$width}\K(?=.)/\n/gr; } my @bdims = (5,3,3); my @size = (8,8); say wfc(\@Blocks, \@bdims, \@size);</syntaxhighlight> {{out}} <pre> # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #</pre> =={{header\|Phix}}== {{libheader\|Phix/pGUI}} {{libheader\|Phix/online}} You can run this online [http://phix.x10.mx/p2js/wfc.htm here].<br> <!--<syntaxhighlight lang="phix">(phixonline)--> <span style="color: #000080;font-style:italic;">-- -- demo\rosetta\WaveFunctionCollapse.exw -- ===================================== --</span> <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> <span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (do until, and a switch <atom> bugfix)</span> <span style="color: #008080;">include</span> <span style="color: #000000;">pGUI</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> <span style="color: #004080;">Ihandle</span> <span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">canvas</span> <span style="color: #004080;">cdCanvas</span> <span style="color: #000000;">cddbuffer</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">bOverlap</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (debug aids)</span> <span style="color: #000000;">bSpat</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> <span style="color: #000080;font-style:italic;">-- (show space as '@')</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">8</span> <span style="color: #000080;font-style:italic;">-- board size (nb must be even)</span> <span style="color: #008080;">constant</span> <span style="color: #000000;">title</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"Wave Function Collapse"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">help_text</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""" Press 'o' to toggle overlap (see note below). Press '@' to toggle display spaces as '@'. Press '-' to decrease board size (min 2x2). Press '+' to increase board size (max 40x40). Press ' ' to start afresh. Note that it is not really possible to visually verify that a pattern is correct unless overlap is turned off. """</span> <span style="color: #000080;font-style:italic;">-- space, T, -\|, iT, \|- </span> <span style="color: #008080;">constant</span> <span style="color: #000000;">tilem</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0b0000</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b0111</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1011</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b1110</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- L, R, U, D</span> <span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">0b00101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b10001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b01001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b00011</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0b11010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b01110</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b01001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b11100</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0b11010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b10001</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b10110</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b11100</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0b11010</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b01110</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b10110</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b00011</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0b00101</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b01110</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b10110</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0b11100</span><span style="color: #0000FF;">}}</span> <span style="color: #000080;font-style:italic;">-- eg valid[1=space][4=D] means space or T can go below it, -- with bits of each valid[][] being read right-to-left.</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- -1 if unknown, else one of tilem</span> <span style="color: #000000;">allowed</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- initially 0b11111 (all possible) -> 1 bit set</span> <span style="color: #000000;">entropy</span> <span style="color: #000080;font-style:italic;">-- count matching allowed (speedwise/simplicity)</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">left</span> <span style="color: #000080;font-style:italic;">-- NN..0, with 0=finished, -1=FAIL, -2=REDO</span> <span style="color: #008080;">function</span> <span style="color: #000000;">lowest_entropy</span><span style="color: #0000FF;">()</span> <span style="color: #000080;font-style:italic;">-- returns a random tile from those with the lowest entropy</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">me</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">N</span> <span style="color: #008080;">do</span> <span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">N</span> <span style="color: #008080;">do</span> <span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- ignoring any already done</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">entropy</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">if</span> <span style="color: #000000;">e</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">me</span> <span style="color: #008080;">then</span> <span style="color: #008080;">if</span> <span style="color: #000000;">e</span><span style="color: #0000FF;"><</span><span style="color: #000000;">me</span> <span style="color: #008080;">then</span> <span style="color: #000000;">me</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">e</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">if</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">row</span><span style="color: #0000FF;">,</span><span style="color: #000000;">col</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">row</span><span style="color: #0000FF;">,</span><span style="color: #000000;">col</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #008080;">function</span> <span style="color: #000000;">pop_count</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- Kernigans bit counter:</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">while</span> <span style="color: #000000;">p</span> <span style="color: #008080;">do</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">&&=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span> <span style="color: #008080;">return</span> <span style="color: #000000;">e</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #008080;">function</span> <span style="color: #000000;">permitted</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- -- Given p, 0b00001..0b11111, a 1-5 bitmask, -- calculate the permitted tiles in direction -- d (1..4 for LRUD), eg a T(2) can have 2\|3\|4 -- on the right, and a 3 can have 1\|5, so if -- p is 0b01100 the result is 0b11111 (all), -- that is, when d is 2 (ie right). --</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">nm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">5</span> <span style="color: #008080;">do</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">nm</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">or_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">d</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">return</span> <span style="color: #000000;">nm</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #008080;">function</span> <span style="color: #000000;">propagate</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- -- Propagate the permitted tiles, given that only -- those in p (0b00001..0b11111, a 1..5 bitmask) -- are now allowed at [r][c]. Note this can fail, -- especially for some ~2x3 enclosed spaces, and -- in that case you want to undo everything, and -- clear some initial permitted bit setting. --</span> <span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span> <span style="color: #008080;">in</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}}</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">--LRUD</span> <span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">dr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dc</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dc</span> <span style="color: #008080;">if</span> <span style="color: #000000;">nr</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nr</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">N</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nc</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nc</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">N</span> <span style="color: #008080;">then</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">nm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">permitted</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">allowed</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nr</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nc</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">np</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nm</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">if</span> <span style="color: #000000;">np</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">if</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">np</span> <span style="color: #008080;">then</span> <span style="color: #000000;">allowed</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nr</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nc</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">np</span> <span style="color: #000000;">entropy</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nr</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nc</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pop_count</span><span style="color: #0000FF;">(</span><span style="color: #000000;">np</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">propagate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">np</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #008080;">procedure</span> <span style="color: #000000;">wfc</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- -- wave function collapse: (iterative/one cell at a time, because -- this was once on a timer, but now wfc_init() just loops.) -- -- There is, I guess, around a 1 in 8000 chance of this failing, -- which means 1 in 10 40x40 boards fail, presumbably because it -- has surrounded an area and none of the edges will work out. -- Setting left to -2 triggers the outer retry in wfc_init(). --</span> <span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lowest_entropy</span><span style="color: #0000FF;">(),</span> <span style="color: #000000;">g</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">allowed</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- pick a random but valid tile:</span> <span style="color: #008080;">for</span> <span style="color: #000000;">i</span> <span style="color: #008080;">in</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">do</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- in case propagation fails, make a backup</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">saveae</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">({</span><span style="color: #000000;">allowed</span><span style="color: #0000FF;">,</span><span style="color: #000000;">entropy</span><span style="color: #0000FF;">})</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tilem</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #000000;">allowed</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span> <span style="color: #000000;">entropy</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> <span style="color: #000000;">left</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">propagate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">g</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">allowed</span><span style="color: #0000FF;">,</span><span style="color: #000000;">entropy</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">saveae</span> <span style="color: #000000;">saveae</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> <span style="color: #000080;font-style:italic;">-- kill refcounts</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">m</span> <span style="color: #000080;font-style:italic;">-- don't try this again!</span> <span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- printf(1,"panic: allowed[%d][%d] := 0!\n",{r,c})</span> <span style="color: #000000;">left</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span> <span style="color: #000080;font-style:italic;">-- trigger a restart</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pop_count</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">==</span><span style="color: #000000;">entropy</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">allowed</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span> <span style="color: #000000;">entropy</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">e</span> <span style="color: #000000;">left</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> <span style="color: #008080;">procedure</span> <span style="color: #000000;">wfc_init</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">do</span> <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">),</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">allowed</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0b11111</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">),</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">entropy</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">),</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">left</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">N</span><span style="color: #0000FF;"></span><span style="color: #000000;">N</span> <span style="color: #008080;">do</span> <span style="color: #000000;">wfc</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">until</span> <span style="color: #000000;">left</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">0</span> <span style="color: #008080;">until</span> <span style="color: #000000;">left</span><span style="color: #0000FF;">!=-</span><span style="color: #000000;">2</span> <span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> <span style="color: #000080;font-style:italic;">-- (the rest of this is all fairly standard code)</span> <span style="color: #008080;">function</span> <span style="color: #000000;">redraw_cb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandle</span> <span style="color: #000000;">ih</span><span style="color: #0000FF;">)</span> <span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">cw</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupGetIntInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ih</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"DRAWSIZE"</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">N2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">N</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- (nb forces N to be even)</span> <span style="color: #000000;">N3</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">N2</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cw</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">N</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">d9</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cw</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)/(</span><span style="color: #000000;">2</span><span style="color: #0000FF;"></span><span style="color: #000000;">N</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)),</span> <span style="color: #000000;">d2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">d4</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">N2</span><span style="color: #0000FF;"></span><span style="color: #000000;">d</span> <span style="color: #000000;">cw</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cw</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">cdCanvasActivate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">cdCanvasClear</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">cdCanvasSetForeground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #004600;">CD_BLUE</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">cdCanvasSetLineWidth</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">for</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">N</span> <span style="color: #008080;">do</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">ry</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bOverlap</span><span style="color: #0000FF;">?</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">-(</span><span style="color: #000000;">row</span><span style="color: #0000FF;"></span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">N</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span><span style="color: #000000;">d9</span> <span style="color: #0000FF;">:</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">-(</span><span style="color: #000000;">row</span><span style="color: #0000FF;">-</span><span style="color: #000000;">N3</span><span style="color: #0000FF;">)</span><span style="color: #000000;">d</span><span style="color: #0000FF;">-</span><span style="color: #000000;">d2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">for</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">N</span> <span style="color: #008080;">do</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">rx</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bOverlap</span><span style="color: #0000FF;">?</span><span style="color: #000000;">cw</span><span style="color: #0000FF;">+(</span><span style="color: #000000;">col</span><span style="color: #0000FF;"></span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">N</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span><span style="color: #000000;">d9</span> <span style="color: #0000FF;">:</span><span style="color: #000000;">cw</span><span style="color: #0000FF;">+(</span><span style="color: #000000;">col</span><span style="color: #0000FF;">-</span><span style="color: #000000;">N3</span><span style="color: #0000FF;">)</span><span style="color: #000000;">d</span><span style="color: #0000FF;">+</span><span style="color: #000000;">d2</span><span style="color: #0000FF;">)</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">g</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">row</span><span style="color: #0000FF;">][</span><span style="color: #000000;">col</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">entropy</span><span style="color: #0000FF;">[</span><span style="color: #000000;">row</span><span style="color: #0000FF;">][</span><span style="color: #000000;">col</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">if</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0b1111</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">cdCanvasSetForeground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #004600;">CD_RED</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">cdCanvasSetTextAlignment</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">CD_CENTER</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">cdCanvasText</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"?"</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">cdCanvasSetForeground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #004600;">CD_BLUE</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">elsif</span> <span style="color: #000000;">bSpat</span> <span style="color: #008080;">and</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0b0000</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">cdCanvasSetTextAlignment</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">CD_CENTER</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">cdCanvasText</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"@"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">elsif</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">!=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dxy</span> <span style="color: #008080;">in</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}}</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- LURD</span> <span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">then</span> <span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">dr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dc</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dxy</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bOverlap</span><span style="color: #0000FF;">?</span><span style="color: #000000;">d9</span><span style="color: #0000FF;"></span><span style="color: #000000;">2</span><span style="color: #0000FF;">:</span><span style="color: #000000;">d2</span><span style="color: #0000FF;">))</span> <span style="color: #7060A8;">cdCanvasLine</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dr</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #7060A8;">cdCanvasFlush</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">)</span> <span style="color: #004080;">string</span> <span style="color: #000000;">o</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bOverlap</span><span style="color: #0000FF;">?</span><span style="color: #008000;">""</span><span style="color: #0000FF;">:</span><span style="color: #008000;">" (no overlap)"</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">left</span><span style="color: #0000FF;">!=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">""</span><span style="color: #0000FF;">:</span><span style="color: #008000;">" FAIL"</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">IupSetStrAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"TITLE"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s [%dx%d] %s%s"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">title</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">,</span><span style="color: #000000;">o</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">})</span> <span style="color: #008080;">return</span> <span style="color: #004600;">IUP_DEFAULT</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #008080;">function</span> <span style="color: #000000;">map_cb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandle</span> <span style="color: #000000;">ih</span><span style="color: #0000FF;">)</span> <span style="color: #004080;">cdCanvas</span> <span style="color: #000000;">cdcanvas</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">cdCreateCanvas</span><span style="color: #0000FF;">(</span><span style="color: #004600;">CD_IUP</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ih</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">cddbuffer</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">cdCreateCanvas</span><span style="color: #0000FF;">(</span><span style="color: #004600;">CD_DBUFFER</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdcanvas</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #004600;">IUP_DEFAULT</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #008080;">function</span> <span style="color: #000000;">help_cb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandln</span> <span style="color: #000080;font-style:italic;">/ih/</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">IupMessage</span><span style="color: #0000FF;">(</span><span style="color: #000000;">title</span><span style="color: #0000FF;">,</span><span style="color: #000000;">help_text</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bWrap</span><span style="color: #0000FF;">:=</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #004600;">IUP_IGNORE</span> <span style="color: #000080;font-style:italic;">-- (don't open browser help!)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #008080;">function</span> <span style="color: #000000;">key_cb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandle</span> <span style="color: #000080;font-style:italic;">/dlg/</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #004600;">K_ESC</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">IUP_CLOSE</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (standard practice for me)</span> <span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #004600;">K_F5</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">IUP_DEFAULT</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (let browser reload work)</span> <span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #004600;">K_F1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">help_cb</span><span style="color: #0000FF;">(</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">switch</span> <span style="color: #7060A8;">lower</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">case</span> <span style="color: #008000;">'c'</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">wfc</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">case</span> <span style="color: #008000;">'o'</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">bOverlap</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">not</span> <span style="color: #000000;">bOverlap</span> <span style="color: #008080;">case</span> <span style="color: #008000;">'-'</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">N</span><span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">fallthrough</span> <span style="color: #008080;">case</span> <span style="color: #008000;">'+'</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">N</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">fallthrough</span> <span style="color: #008080;">case</span> <span style="color: #008000;">' '</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">wfc_init</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">case</span> <span style="color: #008000;">'@'</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">bSpat</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">not</span> <span style="color: #000000;">bSpat</span> <span style="color: #008080;">end</span> <span style="color: #008080;">switch</span> <span style="color: #7060A8;">IupUpdate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #004600;">IUP_IGNORE</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> <span style="color: #7060A8;">IupOpen</span><span style="color: #0000FF;">()</span> <span style="color: #000000;">canvas</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupGLCanvas</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"RASTERSIZE=440x440"</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">dlg</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupDialog</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">,</span><span style="color: #008000;">`TITLE="%s"`</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">title</span><span style="color: #0000FF;">})</span> <span style="color: #7060A8;">IupSetCallbacks</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"MAP_CB"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"map_cb"</span><span style="color: #0000FF;">),</span> <span style="color: #008000;">"ACTION"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"redraw_cb"</span><span style="color: #0000FF;">)})</span> <span style="color: #7060A8;">IupSetCallback</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"KEY_CB"</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"key_cb"</span><span style="color: #0000FF;">))</span> <span style="color: #7060A8;">IupSetAttributeHandle</span><span style="color: #0000FF;">(</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"PARENTDIALOG"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">wfc_init</span><span style="color: #0000FF;">()</span> <span style="color: #7060A8;">IupShow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"RASTERSIZE"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">IupMainLoop</span><span style="color: #0000FF;">()</span> <span style="color: #7060A8;">IupClose</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> <!--</syntaxhighlight>--> === trivial ditty === Translation of the Python ditty on the talk page:<br> This trivial solution works because we're only ever adding left to right,<br> and therefore only verifying L/U vs R/D, and it is not possible to have<br> any two R/D for which no tile is valid. Were this to fill in each row/line<br> more randomly, it would soon fail with no tile matching >=3 neighbours.<br> (lowest entropy would also fail b/c it'd favour 2 no conn over 3 with) <!--<syntaxhighlight lang="phix">(phixonline)--> <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> <span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">/</span><span style="color: #000000;">unicode_console</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> <span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">unicode_console</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">with</span> <span style="color: #008080;">trace</span> <span style="color: #008080;">procedure</span> <span style="color: #000000;">make_rows</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">)</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">conn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"0000.1101.1110.0111.1011"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"."</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- RULD flags</span> <span style="color: #000000;">tiles</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" ... ╠...═╩...═╣...═╦"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"..."</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">--[...aligned]</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span> <span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">w</span> <span style="color: #008080;">do</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{}}</span> <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">w</span> <span style="color: #008080;">do</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> <span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">5</span> <span style="color: #008080;">do</span> <span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">conn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">3</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">conn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[$]][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> <span style="color: #000080;font-style:italic;">-- L=R</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">conn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">conn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">4</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- U=D</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">x</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">))]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">extract</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tiles</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">),</span><span style="color: #008000;">""</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">))</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> <span style="color: #000000;">make_rows</span><span style="color: #0000FF;">(</span><span style="color: #000000;">20</span><span style="color: #0000FF;">)</span> <!--</syntaxhighlight>--> =={{header\|Raku}}== {{trans\|C}} <syntaxhighlight lang="raku" line># 20220728 Raku programming solution my @Blocks = ( [ <0 0 0>, <0 0 0>, <0 0 0> ], [ <0 0 0>, <1 1 1>, <0 1 0> ], [ <0 1 0>, <0 1 1>, <0 1 0> ], [ <0 1 0>, <1 1 1>, <0 0 0> ], [ <0 1 0>, <1 1 0>, <0 1 0> ], ); sub XY(\row, \col, \width) { col+rowwidth } sub XYZ(\page, \row, \col, \height, \width) { XY( XY(page, row, height), col, width) } sub wfc(@blocks, @bdim, @tdim) { my \N = [] my (\td0,\td1) = @tdim[0,1]; my @adj; # indices in R of the four adjacent blocks for ^td0 X ^td1 -> (\i,\j) { # in a 3x3 grid @adj[XYZ(i,j,0,td1,4)]= XY((i-1)%td0,j%td1,td1); # above (index 1) @adj[XYZ(i,j,1,td1,4)]= XY(i%td0,(j-1)%td1,td1); # left (index 3) @adj[XYZ(i,j,2,td1,4)]= XY(i%td0,(j+1)%td1,td1); # right (index 5) @adj[XYZ(i,j,3,td1,4)]= XY((i+1)%td0,j%td1,td1); # below (index 7) } my (\bd0,\bd1,\bd2) = @bdim[0..2]; my @horz; # blocks which can sit next to each other horizontally for ^bd0 X ^bd0 -> (\i,\j) { @horz[XY(i,j,bd0)] = 1; for ^bd1 -> \k { @horz[XY(i, j, bd0)]= 0 if @blocks[XYZ(i, k, 0, bd1, bd2)] != @blocks[XYZ(j, k, bd2-1, bd1, bd2)] } } my @vert; # blocks which can sit next to each other vertically / for ^bd0 X ^bd0 -> (\i,\j) { @vert[XY(i,j,bd0)] = 1; for ^bd2 -> \k { if @blocks[XYZ(i, 0, k, bd1, bd2)] != @blocks[XYZ(j, bd1-1, k, bd1, bd2)] { @vert[XY(i, j, bd0)]= 0 andthen last; } } } my @allow = 1 xx 4(bd0+1)bd0; # all block constraints, based on neighbors for ^bd0 X ^bd0 -> (\i,\j) { @allow[XYZ(0, i, j, bd0+1, bd0)] = @vert[XY(j, i, bd0)]; # above (north) @allow[XYZ(1, i, j, bd0+1, bd0)] = @horz[XY(j, i, bd0)]; # left (west) @allow[XYZ(2, i, j, bd0+1, bd0)] = @horz[XY(i, j, bd0)]; # right (east) @allow[XYZ(3, i, j, bd0+1, bd0)] = @vert[XY(i, j, bd0)]; # below (south) } my (@R, @todo, @wave, @entropy, @indices, $min, @possible) = bd0 xx N; loop { my $c = 0; for ^N { @todo[$c++] = $_ if bd0 == @R[$_] } last unless $c; $min = bd0; for ^$c -> \i { @entropy[i]= 0; for ^bd0 -> \j { @entropy[i] += @wave[XY(i, j, bd0)] = @allow[XYZ(0, @R[@adj[XY(@todo[i],0,4)]], j, bd0+1, bd0)] +& @allow[XYZ(1, @R[@adj[XY(@todo[i],1,4)]], j, bd0+1, bd0)] +& @allow[XYZ(2, @R[@adj[XY(@todo[i],2,4)]], j, bd0+1, bd0)] +& @allow[XYZ(3, @R[@adj[XY(@todo[i],3,4)]], j, bd0+1, bd0)] } $min = @entropy[i] if @entropy[i] < $min } unless $min { @R=[] andthen last } # original behaviour #unless $min { @R = bd0 xx N andthen redo } # if failure is not an option my $d = 0; for ^$c { @indices[$d++] = $_ if $min == @entropy[$_] } my \ind = bd0 * my \ndx = @indices[ ^$d .roll ]; $d = 0; for ^bd0 { @possible[$d++] = $_ if @wave[ind+$_] } @R[@todo[ndx]] = @possible[ ^$d .roll ]; } exit unless @R.Bool; my @tile; for ^td0 X ^bd1 X ^td1 X ^bd2 -> (\i0,\i1,\j0,\j1) { @tile[XY(XY(j0, j1, bd2-1), XY(i0, i1, bd1-1), 1+td1(bd2-1))] = @blocks[XYZ(@R[XY(i0, j0, td1)], i1, j1, bd1, bd2)] } return @tile } my (@bdims,@size) := (5,3,3), (8,8); my @tile = wfc @Blocks».List.flat, @bdims, @size ; say .join.trans( [ '0', '1' ] => [ ' ', '# ' ] ) for @tile.rotor(17)</syntaxhighlight> {{out}} <pre> # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # </pre> =={{header\|Wren}}== {{trans\|C}} The following is a translation of the C version ''before'' macros were added. Wren doesn't support macros and, whilst I could use functions instead, I decided on efficiency grounds to leave it as it is. <syntaxhighlight lang="wren">import "random" for Random var rand = Random.new() var blocks = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0 ] var wfc = Fn.new { \|blocks, tdim, target\| var N = target[0] target[1] var t0 = target[0] var t1 = target[1] var adj = List.filled(4N, 0) for (i in 0...t0) { for (j in 0...t1) { var k = j + t1i var m = 4 * k adj[m ] = j + t1((t0+i-1)%t0) / above (1) / adj[m+1] = (t1+j-1)%t1 + t1 i /* left (3) / adj[m+2] = ( j+1)%t1 + t1 i /* right (5) / adj[m+3] = j + t1(( i+1)%t0) /* below (7) / } } var td0 = tdim[0] var td1 = tdim[1] var td2 = tdim[2] var horz = List.filled(td0td0, 0) for (i in 0...td0) { for (j in 0...td0) { horz[j+itd0] = 1 for (k in 0...td1) { if (blocks[0+td2(k+td1i)] != blocks[(td2-1)+td2(k+td1j)]) { horz[j+itd0] = 0 break } } } } var vert = List.filled(td0td0, 0) for (i in 0...td0) { for (j in 0...td0) { vert[j+itd0]= 1 for (k in 0...td2) { if (blocks[k+td2(0+td1i)] != blocks[k+td2((td2-1)+td1j)]) { vert[j+itd0]= 0 break } } } } var stride = (td0+1) td0 var allow = List.filled(4 * stride, 1) for (i in 0...td0) { for (j in 0...td0) { allow[ (itd0)+j] = vert[(jtd0)+i] /* above (north) / allow[ stride +(itd0)+j] = horz[(jtd0)+i] / left (west) / allow[(2stride)+(itd0)+j] = horz[(itd0)+j] /* right (east) / allow[(3stride)+(itd0)+j] = vert[(itd0)+j] /* below (south) / } } var R = List.filled(N, td0) var todo = List.filled(N, 0) var wave = List.filled(Ntd0, 0) var entropy = List.filled(N, 0) var indices = List.filled(N, 0) var min = 0 var possible = List.filled(td0, 0) while (true) { var c = 0 for (i in 0...N) { if (td0 == R[i]) { todo[c] = i c = c + 1 } } if (c == 0) break min = td0 for (i in 0...c) { entropy[i] = 0 for (j in 0...td0) { var K = 4todo[i] wave[itd0 + j] = allow[ td0R[adj[K ]]+j] & / above / allow[ stride +td0R[adj[K+1]]+j] & /* left / allow[(2stride)+td0R[adj[K+2]]+j] & / right / allow[(3stride)+td0R[adj[K+3]]+j] / below / entropy[i] = entropy[i] + wave[itd0 + j] } if (entropy[i] < min) min = entropy[i] } if (min == 0) { R = null break } var d = 0 for (i in 0...c) { if (min == entropy[i]) { indices[d] = i d = d + 1 } } var ndx = indices[rand.int(0, d)] var ind = ndx * td0 d = 0 for (i in 0...td0) { if (wave[ind+i] != 0) { possible[d] = i d = d + 1 } } R[todo[ndx]] = possible[rand.int(0, d)] } if (!R) return null var tile = List.filled((1+t0(td1-1))(1+t1(td2-1)), 0) for (i0 in 0...t0) { for (i1 in 0...td1) { for (j0 in 0...t1) { for (j1 in 0...td2) { var t = j1 + (td2-1)j0 + (1+t1(td2-1))(i1 + (td1-1)i0) tile[t] = blocks[j1 + td2(i1 + td1R[j0+t1i0])] } } } } return tile } var tdims = [5, 3, 3] var size = [8, 8] var tile = wfc.call(blocks, tdims, size) if (!tile) return for (i in 0..16) { for (j in 0..16) { System.write("%(" #"[tile[j+i*17]]) ") } System.print() }</syntaxhighlight> {{out}} ~~1j1#"1 ' #'{~ tiles wfc 8 8~~ Sample output: ~~# # # #~~ <pre> ~~# # # # # # # # # # # # # # # # # # #~~ # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ~~# #~~ # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ~~# #~~ # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # </pre> ~~# # # # # # # # # # # # # # # # #~~ ~~# # # # # #~~ ~~# # # # #~~ ~~# # # # # # # # # # # # # #~~ ~~# # # # # </lang>~~