9
\$\begingroup\$

Consider the following 9 "row patterns", using 0s to represent empty cells and 1s to represent a full cell. Each pattern is associated with an integer \$n\$, such that \$0 \le n \le 8\$ (multiple [1,1,1,1,1,1]s exist as there's some difference that we don't care about):

\$n\$ Pattern
0 [0,0,0,0,0,0]
1 [1,1,1,1,1,1]
2 [1,1,1,1,1,1][1]
3 [1,1,1,1,1,1][1]
4 [1,1,0,1,1,1]
5 [0,1,1,0,1,0]
6 [1,0,0,1,0,1]
7 [0,1,0,0,0,0]
8 [0,0,0,0,1,0]

Given 6 integers, each of which is between \$0\$ and \$8\$ inclusive, we can use these rows to build a 6x6 square matrix. For example, consider an input of [1,4,6,6,0,0]. We'll start with 1 being the bottom row and the 0s being the top 2, giving:

[0,0,0,0,0,0]
[0,0,0,0,0,0]
[1,0,0,1,0,1]
[1,0,0,1,0,1]
[1,1,0,1,1,1]
[1,1,1,1,1,1]

For each column in this matrix, we can see that every non-zero element has a "support" down to the base, i.e. no 1 has a 0 below it. However, this isn't the case for [2,3,4,5,0,0]:

[0,0,0,0,0,0]
[0,0,0,0,0,0]
[0,1,1,0,1,0]
[1,1,0,1,1,1]
[1,1,1,1,1,1]
[1,1,1,1,1,1]

As the third column from the left has a 0 below the top 1, meaning that it is "unsupported".

Given 6 integers between 0 and 8 inclusive, in any reasonable format, you should output a truthy value if, in the matrix represented by these numbers, all non-zero values are supported; and a falsey value if not.

This is , so the shortest code in bytes wins.

Test cases:

[1,4,6,6,0,0] => valid
[2,1,2,4,7,7] => valid
[5,8,8,0,0,0] => valid
[2,0,2,0,0,0] => invalid
[2,3,4,5,0,0] => invalid
\$\endgroup\$
6
  • 2
    \$\begingroup\$ I've done some editing (removed the image and replaced it with a table), added some explanations and worked examples. Feel free to change anything I've gotten wrong/you dislike \$\endgroup\$ Sep 16, 2021 at 21:19
  • 1
    \$\begingroup\$ I would have liked to see a version of this with just the binary matrix as input. The 6 numbers don't seem to add anything to the challenge. \$\endgroup\$
    – user
    Sep 16, 2021 at 22:28
  • 5
    \$\begingroup\$ @user I actually think the 6 numbers are a good addition. Without that, my Jelly answer is 3 bytes (maximum of 4, depending on I/O format/order). That said, the "vanilla" version of this, with just the matrix, would also be a good, simple challenge. \$\endgroup\$ Sep 16, 2021 at 22:36
  • 2
    \$\begingroup\$ I think both challenges are interesting in different ways. There are ways to solve this that are completely ignorant of the binary matrix and just rely on the numbers. \$\endgroup\$
    – Wheat Wizard
    Sep 16, 2021 at 22:37
  • 3
    \$\begingroup\$ @user most of us have AND and OR as a builtin, right? just convert the number to binary and either do top&=bottom or bottom|=top. if the number doesn't change the top row is supported. \$\endgroup\$ Sep 16, 2021 at 23:40

9 Answers 9

6
\$\begingroup\$

Jelly, 20 15 bytes

ị“???7ȷ%Ñ£¡‘&\Ƒ

Try it online!

-5 bytes thanks to Lynn!

How it works

ị“???7ȷ%Ñ£¡‘&\Ƒ - Main link. Takes a list of integers on the left
 “???7ȷ%Ñ£¡‘    - Integer list; [63, 63, 63, 55, 26, 37, 16, 2, 0]
ị               - For each i in the input, get the ith element of the list
              Ƒ - Is the list of numbers unchanged when doing:
             \  -   Scan by:
            &   -     Bitwise AND

We can avoid having to convert to binary by using bitwise AND instead of logical AND. By scanning a column (treating the numbers as binary) with a zero bit "hole" with AND, it'll overwrite it as a 1, thus changing the number represented. If there are no holes, none of the numbers will change.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ There really should be a built-in for converting to fixed-width binary… \$\endgroup\$
    – xigoi
    Sep 16, 2021 at 22:41
  • 1
    \$\begingroup\$ 15 bytes: ị“???7ȷ%Ñ£¡‘&\Ƒ :) \$\endgroup\$
    – Lynn
    Sep 17, 2021 at 17:04
  • \$\begingroup\$ @Lynn Nice, very clever! \$\endgroup\$ Sep 17, 2021 at 17:07
4
\$\begingroup\$

JavaScript (ES6),  45  43 bytes

Returns false for valid or true for invalid.

a=>a.some(n=>a!=n&n<'900067999'[a]&(a=n)>0)

Try it online!

How?

When trying to actually process the patterns, my best attempt was 49 bytes. It turns out that looking for invalid consecutive indices is shorter (at least in JS).

For each index \$0\le p\le 8\$, we generate the list of indices \$n\$ that cannot appear right after \$p\$:

0 → [ 1, 2, 3, 4, 5, 6, 7, 8 ]
1 → []
2 → []
3 → []
4 → [ 1, 2, 3, 5 ]
5 → [ 1, 2, 3, 4, 6 ]
6 → [ 1, 2, 3, 4, 5, 7, 8 ]
7 → [ 1, 2, 3, 4, 5, 6, 8 ]
8 → [ 1, 2, 3, 4, 5, 6, 7 ]

It follows that \$n\$ is invalid iff all the following conditions are met:

  • \$p\$ is defined
  • \$n\neq p\$
  • \$n\neq 0\$
  • \$n<A_p\$, with \$A=[9,0,0,0,6,7,9,9,9]\$

JavaScript (ES6), 58 bytes

This is a straightforward implementation of the results described above as a regex.

Expects a string of digits. Returns false for valid or true for invalid.

s=>/0[^0]|4[1235]|5[1-46]|6[1-578]|7[1-68]|8[1-7]/.test(s)

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Python 3, 73 64 bytes

Thanks to ovs for pointing what I should have seen.

lambda x:all(2**i&ord("ǿ.^¾ľ"[j])for i,j in zip(x,x[1:]))

Try it online!

First time goling in Python a while. We store a binary matrix as a string.

This represents

\$ M= \left[\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ \end{matrix}\right] \$

Where \$M_{i,j}\$ is whether \$i\$ can be placed on top of \$j\$. Basically its the adjacency matrix of the underlying lattice. Then with this matrix we check all the pairs of indices and see if anything is adjacent to something it can't be.

\$\endgroup\$
2
  • \$\begingroup\$ Iterating over zip(x,x[1:]) instead of the range saves a few bytes. \$\endgroup\$
    – ovs
    Sep 17, 2021 at 6:44
  • \$\begingroup\$ @ovs I was sitting around thinking "Man I wish python had some sort of zip", without actually even bothering to check if I was correct. \$\endgroup\$
    – Wheat Wizard
    Sep 17, 2021 at 7:42
1
\$\begingroup\$

JavaScript (Node.js), 44 bytes

n=>/^[123]*(4*6*|(4*|5*)(7*|8*))0*$/.test(n)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 20 bytes

3LÛ0ÜÔ•€Â¦ŠôY∞•59вså

Input as a string of digits.

Port of @tsh's JavaScript regex answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

3L                   # Push list [1,2,3]
  Û                  # Remove all leading 1s, 2s, and/or 3s from the (implicit) input
   0Ü                # Also remove all trailing 0s
     Ô               # Connected uniquify the remaining digits
      •€Â¦ŠôY∞•      # Push compressed integer 35401368921902082
               59в   # Convert it to base-59 as list: [4,5,6,7,8,46,47,48,57,58]
                  så # Check if the earlier integer is in this list
                     # (after which the result is output implicitly)

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand why •€Â¦ŠôY∞• is 35401368921902082 and •€Â¦ŠôY∞•59в is [4,5,6,7,8,46,47,48,57,58].

\$\endgroup\$
1
\$\begingroup\$

MATL, 22 bytes

63tt55' :_o'd2Ovi)Bd1<

Outputs a matrix containing only ones (which is truthy) or containing at least a zero (which is falsy). The footer contains a truthy/falsy test.

Try it online! Or verify all test cases.

Explanation

The code generates the binary matrix, without any leading column of zeros (which doesn't affect the result), and computes consecutive differences vertically. The differences can be 0, 1 or −1. The input is valid if no difference equals 1.

63       % Push this number
tt       % Duplicate twice
55       % Push this number
' :_o'   % Push this string
d        % Consecutive differences (of ASCII codes). Gives [26 37 16]
2        % Push this number
O        % Push 0
v        % Concatenate everything into a column vector. (*)
i        % Input: numeric vector
)        % Index into (*). Indexing is 1-based and modular, so index 0
         % corresponds to the last entry
B        % Convert to binary. Gives a matrix, each original number corresponding
         % to a row. The number of columns is determined by the longest binary
         % expansion
d        % Consecutive differences, vertically
1        % Push 1
<        % Less than? Element-wise. For a valid input this gives a matrix with
         % all entries equal to true, or equivalently to 1
         % Implicit display
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 86 83 75 bytes

i;r;*m=L"???7%";f(int*l){for(r=i=0;i++<5;)r|=m[*l++]&m[*l]^m[*l];i=!r;}

Try it online!

Saved 8 bytes thanks to ceilingcat!!!

Inputs a list of \$6\$ integers in \$\left[ 0,8 \right]\$.
Returns \$1\$ if valid or \$0\$ for invalid.

\$\endgroup\$
4
  • \$\begingroup\$ Can you save bytes by using the literal chars instead of escape sequences? I know TIO can't handle null bytes, but \x1a and such should be fine \$\endgroup\$ Sep 18, 2021 at 1:00
  • \$\begingroup\$ 75 bytes as suggested by caird coinheringaahing \$\endgroup\$
    – tsh
    Sep 18, 2021 at 3:39
  • \$\begingroup\$ @cairdcoinheringaahing Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Sep 18, 2021 at 7:08
  • \$\begingroup\$ @tsh Thanks for the help! :D \$\endgroup\$
    – Noodle9
    Sep 18, 2021 at 9:50
0
\$\begingroup\$

Charcoal, 30 bytes

≔ES℅§O@@@ABMGKIιθ⬤θ∨¬κ⁼ι|ι§θ⊖κ

Try it online! Link is to verbose version of code. Takes input as a string of digits and outputs a Charcoal boolean, i.e. - for supported, nothing for unsupported. Explanation:

≔ES℅§O@@@ABMGKIιθ

Translate each digit to a custom bitmask, given by the bottom 4 bits of the ASCII codes of each character (the upper bits are the same for each character so they don't affect the final result).

⬤θ∨¬κ⁼ι|ι§θ⊖κ

Check that the bitmasks represent a supported matrix.

The custom bitmasks are as follows:

0   1111
1   0000
2   0000
3   0000
4   0001
5   0010
6   1101
7   0111
8   1011

Calculation of the adjacency matrix will result in the same matrix as the original bitmasks. Note that these masks are inverted so the code uses a bitwise OR check to compensate.

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 93 bytes

Here it is, not extensively tested but I think it should work!

Input is a string of 6 digits, no spaces or separators. Exit code 1 means invalid, 0 means valid

Uses (lower|upper)>lower to test for unsupported bits.

Thanks to ceilingcat for -8 bytes!

b=63;char*a,d[9];main(c){for(scanf("%s",a=d);*a;b=c)(b|(c="%7???"[56-*a++]))>b?exit(1):0;}

Try it online!

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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