# Secret “>” Stacking Challenge: grading

## Background

Tetris Grand Master 3 has a hidden grading system based on the shape of the stack at the end of the game, which is called Secret ">" Stacking Challenge. It consists of entirely filling the lowest rows except for the zigzag pattern which starts at the left bottom cell and spans the entire width:

#
.#########
#.########
##.#######
###.######
####.#####
#####.####
######.###
#######.##
########.#
#########.
########.#
#######.##
######.###
#####.####
####.#####
###.######
##.#######
#.########
.#########


The board is graded by how many lines follow this exact pattern from the bottom line. Note that the topmost hole in the pattern must be blocked by an extra piece of block. If you consider the #s and .s as the mandatory pattern (blanks can be anything), you can get the score of 19 only if the exact pattern above is matched from the bottom line. Analogously, if the board matches this pattern

   #
###.######
##.#######
#.########
.#########


but not

    #
####.#####
###.######
##.#######
#.########
.#########


then the score is 4.

For this challenge, consider a board of arbitrary size (other than 20 cells high and 10 cells wide). We can grade the board for the same pattern: for example, if the board has width 4, this is the pattern for score 3:

  #
##.#
#.##
.###


and this is the pattern for score 10:

   #
###.
##.#
#.##
.###
#.##
##.#
###.
##.#
#.##
.###


## Challenge

Given the final state of the Tetris board of arbitrary size, grade the board using the system above.

You can take the board using any sensible format for a rectangular matrix, where every cell contains one of two distinct values (for empty and filled respectively). You can assume the grid is a valid Tetris board (no row is entirely filled). Also, the width of the grid is at least 2.

Standard rules apply. The shortest code in bytes wins.

## Test cases

In order to prevent possible confusion, the test cases here use O for the blocks and . for empty spaces.

Input:
..O.O
OOOO.
OOO..
OO.OO
O.OOO
.OOOO
Output: 3

Input:
..
O.
.O
.O
O.
.O
O.
.O
Output: 4

Input:
.OOO
O.OO
OO.O
OO.O
OO.O
O.OO
.OOO
Output: 2 (any lines above the first non-conforming line are ignored;
doesn't get 3 because 3rd line's hole is not capped)

Input:
OOO.
.OOO
O.OO
OO.O
OOO.
OO.O
O.OO
Output: 0 (Wrong starting hole)

Input:
.OOO
O.OO
OO.O
OOO.
Output: 0 (Wrong starting hole)

Input:
.OOO
.OOO
Output: 0 (Hole is not covered)

Input:
OOO...O..O
.OOOOOOOOO
O.OOOOOOOO
OO.OOOOOOO
OOO.OOOOOO
OOOO.OOOOO
OOOOO.OOOO
OOOOOO.OOO
OOOOOOO.OO
OOOOOOOO.O
OOOOOOOOO.
OOOOOOOO.O
OOOOOOO.OO
OOOOOO.OOO
OOOOO.OOOO
OOOO.OOOOO
OOO.OOOOOO
OO.OOOOOOO
O.OOOOOOOO
.OOOOOOOOO
Output: 19

• How about a test case, where the entire board is in a zig-zag pattern, but as the top row is not blocked, its score is height - 1? – xash Aug 18 '20 at 12:22
• No, it doesn't match the pattern for score 5 (or 4) since the rightmost cell on line 4 is empty, but it is required to be filled for score 4 or higher. – Bubbler Aug 18 '20 at 12:24
• @xash Yes, exactly. – Bubbler Aug 18 '20 at 12:24
• Do conforming lines only ever contain one hole? – Shaggy Aug 18 '20 at 12:39
• @Shaggy Yes. Each line in the pattern must have only one hole at the specific position. – Bubbler Aug 18 '20 at 13:31

# JavaScript (ES6), 84 bytes

Expects a list of strings, with 1 for empty spaces and 0 for blocks.

f=(a,i=j=1<<a[k=0].length)=>(v='0b'+a.pop()+0)^i?v&i/k&&-1:1+f(a,i*=k=i&j?.5:i&2||k)


Try it online!

### How?

Each string in the input array is padded with an extra 0 and interpreted as a binary number. The variable j is initialized to 2**W, where W is the width of the board. We use a bit mask i initialized to j to keep track of the expected position of the hole in the pattern.

After each iteration, i is multiplied by k. We update the value of k whenever (i & j) != 0 (bouncing on the leftmost side) or (i & 2) != 0 (bouncing on the rightmost side).

Example for W = 5:

j = 0b100000

i = 0b100000 // -> set k to 1/2
i = 0b010000 // \
i = 0b001000 //  }-> leave k unchanged
i = 0b000100 // /
i = 0b000010 // -> set k to 2
i = 0b000100 // \
i = 0b001000 //  }-> leave k unchanged
i = 0b010000 // /
i = 0b100000 // -> set k to 1/2
...


### Commented

f = (                // f is a recursive function taking:
a,                 //   a[] = input array
i = j =            //   i = hole bit mask, initialized to ...
1 << a[k = 0]    //   ... j = 2 ** W, where W is the width of the board
.length     //   k = bit mask multiplier, initialized to 0
) =>                 //
( v =                // pop the last value from a[], append a '0' and interpret
'0b' + a.pop() + 0 // it as a binary number saved in v
) ^ i ?              // if v is not equal to i:
v & i / k          //   use the previous bit mask i / k to test whether there's
&& -1              //   a hole in v above the last hole of the pattern, in
//   which case we subtract 1 from the final result
:                    // else:
1 +                //   add 1 to the final result
f(                 //   do a recursive call:
a,               //     pass a[] unchanged
i *=             //     multiply i by:
k =            //       the new value of k:
i & j ?      //         if we've reached the leftmost side:
.5         //           set k to 1/2
:            //         else:
i & 2      //           set k to 2 if we've reached the rightmost side,
|| k       //           or leave k unchanged otherwise
)                  //   end of recursive call


# Husk, 18 bytes

Lδ↑€…¢ŀT¹↑εΨ↑-↔m¥0


Try it online!

Takes a 0-1 matrix.

## Explanation

There are three occurrences of ↑ in this program, and they all work differently thanks to the modifier functions δ and Ψ. By default, ↑α expects α to be a unary function, takes a list and returns the longest prefix of elements for which α returns a truthy value. Ψ↑α expects α to be binary, and returns the longest prefix of elements x for which α x y is truthy, where y is the next element. δ↑α expects α to be binary and takes two lists instead of one. It returns the longest prefix of the second list whose elements y satisfy α x y, where x is the corresponding element of the first list.

Input is a list of lists of integers.
Example: [[0,1,1],[1,0,1],[1,1,0],[1,0,1],[1,1,0],[0,0,1],[0,1,1]]

m     Map
¥0   indices where 0 occurs:
[[1],[1,2],[3],[2],[3],[2],[1]]
↔     Reverse:
[[1],[2],[3],[2],[3],[1,2],[1]]

↑    Take while
Ψ     this element and the next
-   have nonempty set difference:
[[1],[2],[3],[2],[3],[1,2]]

↑     Take while
ε    this element is a singleton:
[[1],[2],[3],[2],[3]]
Call this list X.

ŀT¹   Indices of input transposed:
[1,2,3]
¢     Cycle infinitely:
[1,2,3,1,2,3,..]
…     Rangify:
[1,2,3,2,1,2,3,2,1,..]
↑    Take from X while
δ     the corresponding integer in this list
€   is an element of it:
[[1],[2],[3],[2]]
L     Length: 4


# Charcoal, 52 bytes

ＷＳ⊞υι≔⮌υυＰ⪫υ¶Ｗ∧⁼.O⪫ＫＤ²↓ω⁼¹№§υⅉ.Ｍ✳⁻⁷⊗÷﹪ⅉ⊗⊖Ｌθ⊖Ｌθ≔ⅉθ⎚Ｉθ


Try it online! Link is to verbose version of code. Takes input as a newline-terminated list of strings of . and O characters. Explanation:

ＷＳ⊞υι


Input the list.

≔⮌υυ


Reverse the list.

Ｐ⪫υ¶


Print the list without moving the cursor.

Ｗ∧


Repeat while both...

⁼.O⪫ＫＤ²↓ω


... the character under the cursor is a . and the character below (because the list was reversed) is an O, and...

⁼¹№§υⅉ.


... the current list line contains exactly one .:

Ｍ✳⁻⁷⊗÷﹪ⅉ⊗⊖Ｌθ⊖Ｌθ


Move the cursor diagonally down and either right or left depending on the row.

≔ⅉθ⎚Ｉθ


Capture the first invalid row index (0-indexed, so equal to the number of valid rows), clear the canvas, and print it as a string.

# J, 57 42 bytes

Takes in 0 for blocked, 1 for empty.

[:#.~(|.@$2^|@}:@i:@<:)/@$=2#.[*[+_1|.!.2]


Try it online!

### How it works

[*[+_1|.!.2]


Shift the board down by one (2 gets pushed in at the top to make sure the top spots don't count.) Then it adds to the original board and multiplies with itself. This basically boils down to: a valid open spot stays 1, while invalid ones become 2.

 (|.@$2^|@}:@i:@<:)/@$


Given the dimensions, get the exclusive range -x … x - 1 for the width, for e.g. 4: _3 _2 _1 0 1 2, and get their absolute values 3 2 1 0 1 2. Resize that list to the height of the board, rotate it so the starting 3 aligns to the last row, and 2^x the list: 8 4 2 1 2 4 8 4 2…

 =2#.


Interpret the rows as a base 2 number and compare it to the zig-zag list.

 [:#.~


And by reflexive base conversion we can count the leading 1's, so the leading rows that are valid.

# Jelly, 25 bytes

ZJŒḄṖṁLW€⁻"ⱮṚT€,Ḋ$ƊZḄCTḢ’  A monadic Link accepting a list of lines where each line is a list of 1s (empty) and 0s (filled) which yields a non-negative integer (the score). Try it online! Or see the test-suite. ### How? Builds a list of the expected empty indices for each line from the bottom and compares it to each of two lists, (a) the actual empty indices and (b) the actual empty indices dequeued. The results of this comparison are then processed to find the score. ZJŒḄṖṁLW€⁻"ⱮṚT€,Ḋ$ƊZḄCTḢ’ - Link: list of lines, A
Z                         - transpose
J                        - range of length     -> [1,2,...,w=#Columns]
ŒḄ                      - bounce              -> [1,2,...,w-1,w,w-1,...,2,1]
Ṗ                     - pop                 -> [1,2,...,w-1,w,w-1,...,2]
L                   - length (A)          -> h=#Lines
ṁ                    - mould like (repeat Ṗ result such that it is length h)
W€                 - wrap each of these integers in a list (call this x)
Ɗ       - last three links as a monad - i.e. f(A):
Ṛ             -   reverse (A)
T€           -   for each (line) get the list of truthy ("empty") indices
\$        -   last two links as a monad - i.e. f(z=that):
Ḋ         -     dequeue (drop the leftmost)
,          -     (z) pair (that)
Ɱ              - map across (the two results of f(A)) applying:
"               -   (x) zip with (result) applying:
⁻                -     not equal?
Z      - transpose - now we have leading [0,1]'s for valid rows
from the bottom up
Ḅ     - convert from binary - now leading 1s for valid rows
C    - complement (subtract (each) from one)
T   - truthy indices
’ - decrement


# 05AB1E, 32 bytes

R©εDgÝ¨û¨NèDU._ƶO®N>èX.__н*Θ}γнO


Input as a matrix of 1s and 0s, where the 1s are empty spaces and 0s are filled cells.

Explanation:

R             # Reverse the rows of the (implicit) input-matrix
©            # Store it in variable ® (without popping)
ε           # Map over each row:
Dg         #  Get the width of the matrix
Ý        #  Push a list in the range [0,width]
¨       #  Remove the last element to change the range to [0,width-1]
û      #  Palindromize it: [0,1,2,...,w-2,w-1,w-2,...,2,1,0]
¨     #  Remove the last value: [0,1,2,...,w-2,w-1,w-2,...,2,1]
Nè   #  Index the map-index into this list
DU #  Store a copy in variable X
._        #  Rotate the current row that many times to the left
ƶ       #  Multiply each value by its 1-based index
O      #  And sum this list
®          #  Push the reversed input-matrix again from variable ®
N>è       #  Index the map-index + 1 into this to get the next row
X._    #  Also rotate it X amount of times towards the left
_   #  Invert all booleans (1s becomes 0s, and vice-versa)
н  #  And only leave the first value
*          #  Multiply both together
Θ         #  And check that it's equal to 1 (1 if 1; 0 otherwise)
}γ          # After the map: split the list into groups of adjacent equivalent values
н         # Only leave the first group
O        # And take the sum of that
# (after which it is output implicitly as result)