9
\$\begingroup\$

An acyclical grid is a mapping of an acyclical graph (that is, a tree) where each node has no more than four edges onto a toroidal rectangular grid such that each cell of the grid is occupied by a node. Here is an example of an acyclical grid:

┴─┐╵╵│└┘└╴╶┴┬
╴╷╵┌┐│╷┌┬┐╶┐├
╷│╷╵│├┘│╵└╴│╵
┘└┴┐│└┬┤┌─┬┴─
╷╶─┤│╷╵├┤╶┘╶┐
│╶┐└┤└┬┤╵╷╶─┤
┤╷└─┴┬┤└┐└┬┬┴
│├──┐│├╴├─┤├╴
┘└┐┌┴┤└┐├╴╵╵┌
┌┬┘╵┌┴┐╵└─┐╶┘
┤└─┐│╷│┌┬╴╵╷╶

Some browser fonts have trouble rendering this in a properly monospaced way. If the grid looks off, please copy-paste it into a text editor of your choice.

Notice that this grid is toroidal: the left and right, as well as the top and bottom are connected preserving the axis you are moving along. For example, if you move left in the third row you eventually end up on the right of the third row and vice versa.

This grid is composed of box-drawing characters which fall into four classes:

  1. The characters , , , and denote leaves (nodes with one edge)
  2. The characters and denote nodes with two edges in a collinear arrangement
  3. The characters , , , and denote nodes with three edges
  4. The characters , , , and denote nodes with two edges in a perpendicular arrangement

The characteristic matrix of an acyclical grid is a matrix comprising for each cell in the acyclical grid the class of the node positioned there. For instance, the characteristic matrix of the aforementioned grid is this:

3241124441133
1114424232123
1211234214121
4434243342332
1123211331414
2144343311123
3142333444333
2322423131331
4444334431114
4341434142414
3424212431111

A net puzzle is an n × m matrix of integers in the range from 1 to 4 such that it is the characteristic matrix of exactly one acyclical grid.

If you want to gain an intuitive understanding about net puzzles, you can play net from Simon Tatham's puzzle collection. Make sure that “wrapping” and “ensure unique solution” are both checked and that “barrier probability” is set to 0.

The challenge

Write a function or program that given two integers n and m in the range from 3 to 1023 generates a net puzzle of dimension n × m. You may optionally receive a third integer p in the range from 1 to 1023.

If you implement the variant with two arguments (the non-deterministic variant), then your submission shall with great probability return a different puzzle each time it is called. If you implement the variant with three arguments (the deterministic variant), then the set of puzzles generated for all p for a given pair (n, m) shall contain at least four different puzzles for each pair (n, m).

There are no further restrictions with respect to input and output.

Scoring

This challenge is code golf. The solution with the least number of octets wins.

\$\endgroup\$
12
  • 2
    \$\begingroup\$ Did you choose counting characters on purpose? We usually count bytes since some languages get an easy boost from UTF-16 encoding their source and just base converting (CJam, looking at you). \$\endgroup\$ Apr 11, 2015 at 22:24
  • \$\begingroup\$ @Pietu1998 compressing source code is usually seen as a standard loophole / bad style. I count characters because it's a reasonable way to avoid the discussions about which encoding to use. \$\endgroup\$
    – FUZxxl
    Apr 11, 2015 at 22:25
  • \$\begingroup\$ @Pietu1998 There is a meta post about character count. It is assumed that either bytes or UTF-8 should be used (for counting). So if your program is 10 chars in UTF-16, that counts as 20. \$\endgroup\$
    – mbomb007
    Apr 11, 2015 at 22:29
  • 2
    \$\begingroup\$ CJam will probably win then. And no, compressing source code isn't a standard loophole. It's part of the language. \$\endgroup\$
    – mbomb007
    Apr 11, 2015 at 22:37
  • 4
    \$\begingroup\$ That is at most a non-standard loophole. You need to specify that in the question if you want to disallow it. And I'm not sure if it is objective enough. \$\endgroup\$
    – jimmy23013
    Apr 12, 2015 at 0:46

1 Answer 1

11
\$\begingroup\$

K (ngn/k), 38 bytes

{((x,y)#&(0;y;y*x-2;y-2;2))z|:/x!z+!x}

Try it online!

I can't believe that it went unanswered for, like, six and a half years?

Implements the three-argument version. It is a function that takes n m p as three separate parameters and builds a valid net puzzle deterministically.

Basically what it does is to build one asymmetric and easily constructible net puzzle of size n m, and then permute its rows based on p.

What it builds & Why it is valid for this challenge

The result for f[5;6;0] is this:

1 1 1 1 1 1
2 2 2 2 2 2
2 2 2 2 2 2
2 2 2 2 2 2
3 3 3 3 4 4

In box drawing chars:

1 1 1 1 1 1 : ╷╷╷╷╷╷
2 2 2 2 2 2 : ││││││
2 2 2 2 2 2 : ││││││
2 2 2 2 2 2 : ││││││
3 3 3 3 4 4 : ┴┴┴┴┘└

And it has a unique solution, as well as its reflections and rotations (as in APL sense; cyclically moving rows and columns).

Why unique solution? First, the solution is an unrooted tree (in graph-theoretical sense); if a configuration has a cycle, then it is not a solution because it necessarily has two or more disjoint parts. Then, the 2's must be all aligned either horizontally or vertically, but if they're horizontal then they form one or more cycles of their own. So they must be vertical. Then the orientation of 1's are fixed (downwards), and then the 3's (disconnected to the lower side). Finally the orientations for 4's are fixed in order to connect everything.

The code is easy:

&(0;y;y*x-2;y-2;2)    Create an array of:
                      m copies of 1's, m*(n-2) copies of 2's,
                      (m-2) copies of 3's, and 2 copies of 4's
(x,y)#                Reshape into n-row, m-col matrix

For "at least four distinct puzzles" part, I had to use two different permuting methods because of the 3x3 grid (single reflection gives at most 2; stepwise rotation gives at most either n or m). I went for pure row permutation because applying two separate transforms was too long.

For code, !x creates the identity permutation vector 0 1 2 ... (n-1), x!z+ rotates it by p steps, and z|:/ reverses it p times. This creates lcm(2, n) unique grids, which is always at least 4.

I know, it's likely against the original intent of the challenge, but this is not the first time I exploited "generate at least x distinct grids" :P

\$\endgroup\$
3
  • \$\begingroup\$ Since the original grid is toroidal, can those rotated permutations really be described as different? \$\endgroup\$
    – Neil
    Nov 11, 2021 at 6:55
  • \$\begingroup\$ @Neil "Different integer matrix" is my interpretation of different. If OP intended otherwise, it should've been in the challenge text. \$\endgroup\$
    – Bubbler
    Nov 11, 2021 at 7:03
  • 1
    \$\begingroup\$ @Bubbler Yes, your interpretation is correct and was intended. \$\endgroup\$
    – FUZxxl
    Nov 11, 2021 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.