# CGAC2022 Day 4: Can Santa fit down the chimney?

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.

Christmas is coming up, and Santa hasn't kept to his diet very well this year. Due to his size, he is getting the elves to collect a list of all the chimneys he will be able to fit down. Unfortunately, chimneys these days are a bit of a maze, and he can't just drop straight down like he used to.

Task: Given Santas width as an integer and a binary matrix representing the chimney, output whether or not Santa will be able to fit down the chimney.

Rules

• Santa is able to "fit" down the chimney if he can enter it at the top and exit at the bottom, while only moving downwards or sideways through the cavity sections of the chimney.
• Santa cannot move up
• Assume Santa's height is always 1
• There will only be one entrance to the chimney, and one exit from the chimney
• The matrix representing the chimney should consist of two values, one for brick (which Santa can't move through) and one for cavities (which Santa can move through). These can be of type integer, string, float or any other type, as long as a distinction can be made between the two.
• The format of the matrix is flexible - any standard subsitution for a matrix (list of strings, list of lists etc) is allowed
• The output can be any valid truthy/falsy output, or two values/states chosen to represent the truthy falsy output (i.e output 1/None, 1/Error)

Standard rules apply. The shortest code in bytes wins.

## Test Cases

Truthy

Width = 1

Chimney=[
"101",
"101",
"101"
]

Width = 2

Chimney = [
"110011",
"110011",
"100011",
"100111",
"100001",
"110001",
"111001",
"111001",
]


Falsy

Width = 1

Chimney=[
"101",
"010",
"101"
]

Width = 2

Chimney = [
"100111"
"100110"
"100110"
"100010"
"111010"
"111010"
"111010"
"111010"
]

Width = 1

Chimney = [
"0111",
"1110",
"1110",
]

Width = 1

Chimney = [
"1011111",
"1011111",
"1010001",
"1000101",
"1111101",
"1111101",
"1111101",
"1111101",
]

• I just noticed the "can't move up" constraint. My understanding is that would mean this is falsy assuming width 1? Dec 4, 2022 at 1:13
• @Jonah yes that is falsy Dec 4, 2022 at 2:05
• What is the actual task? What is the format of the matrices and what shape is Santa? I just don't get what this is asking me to do, at all. Are the numbers always either 0 or 1? What do those mean? Does a 2-wide Santa have a height of 1 or 2? What if my language doesn't have a concept of truthy/falsy (and shouldn't this be tagged with decision-problem? Dec 4, 2022 at 17:25
• @RadvylfPrograms all good questions, I've edited the question to hopefully address these all. The height is always 1. Initially I had both height and width as input, but feedback in the sandbox (linked post) suggested just using width. Let me know if you think I should make any further changes to clarify and tidy up the question Dec 4, 2022 at 19:09
• @jezza_99 Looks much better, thanks for clarifying those things Dec 5, 2022 at 14:16

# Vyxal, 18 16 bytes

vlvṠλĠ~•vA⋎f;RA¬


Takes input as width and a matrix of 0's and 1's, in either order.

## Explanation

Since Santa cannot move up the chimney, we can iterate through each chimney's row until we arrive into a result. To check if we can move down then sideways to the 0's: (Assuming width 1)

[1 0] [0 1 1] [1] [1] [1] => previous (molded to current)
0      0     1   1   1  =>   are all of them true?
OR     OR    OR  OR  OR  (bitwise)
[1 1] [0 0 0] [1] [0] [1] => current
=      =     =   =   =
[1 1] [0 0 0] [1] [1] [1] => new


#### Commented code

vl               # cumulative groups (vectorise)
vṠ             # sum (doubly vectorise)
# - this is "any?" as truthy/falsy only matters in this case
R   # reduce by
λ       ;    # a lambda taking two elements:
Ġ           #   group the current consecutively
•         #   mold the previous
~          #   do not pop the items
vA       #   all? (vectorise)
⋎      #   bitwise or (vectorises)
f     #   flatten
A¬ # is not all true?


# JavaScript (ES7), 105 bytes

Expects (width)(chimney).

w=>g=([v,...a],m=2**w-1,c,r='0b1'+v,h=(k,M=m,q=r&M)=>M%1||M>r|c*q?0:g(a,M,1)&!q|h(k,M*k))=>v?h(2)|h(.5):1


Try it online!

### Commented

w =>              // outer function taking the width w
g = (             // inner recursive function taking:
[ v,            //   v = next row of the chimney
...a          //   a[] = array of remaining rows
],              //
m = 2 ** w - 1, // m = bit mask for Santa
c,              // c = flag telling if horizontal collisions
//     must be taken into account
r = '0b1' + v,  // r = the row with the binary prefix and an
h = (           // h = recursive search function taking:
k,            //   k = direction as a multiplier (2 or 1/2)
M = m,        //   M = copy of m
q = r & M     //   q = collision mask of Santa with the chimney
) =>            //
M % 1 ||        //   if Santa is too far to the right
M > r |         //   or too far to the left
c * q ?         //   or c is set and there's a collision:
0             //     abort
:               //   else:
g(a, M, 1)    //     do a recursive call to g with the
//     collision flag enabled
& !q          //     ignore the result if q was not 0
| h(k, M * k) //     do a recursive call to h with M updated
) =>              //
v ?               // if v is defined:
h(2) |          //   try to move Santa to the left
h(.5)           //   try to move Santa to the right
:                 // else:
1               //   success


# 05AB1E, 18 bytes

Å»γD€gŠr£P~˜}θJÎ×å


Port of @u-ndefined's Vyxal answer, so make sure to upvote him/her as well!

Chimney as first input as an integer-matrix, width as second input-integer.

Explanation:

Å»           # Cumulative left-reduce the rows of the first (implicit) input-matrix,
# keeping all intermediate steps (unfortunately)
γ          #  Split the row into groups of the same adjacent values
D         #  Duplicate this list of groups of 1s/0s
€g       #  Pop the copy, and get the length of each group
Šr     #  Change the stack order from a,b,c, to b,a,c (triple-swap and reverse stack)
£    #  Split the previous rows into groups of those lengths
P   #  Get the product of each inner group to check if all are truthy
~  #  Bitwise-OR these values with the groups of the current row
˜ #  Flatten it for the next iteration
}θ          # After the cumulative left-reduce with intermediate steps: keep the last result
J         # Join this list of 0s/1s together to a string
Î        # Push 0 and the second input-integer
×       # Repeat the "0" that many times as string
å      # Check if it's a substring in the left-reduced result
# (after which this is output implicitly)


# J, 67 47 bytes

1 e.[([*&;]<@(##+./);.1~2~:/\_,[)/@|.@E.~0$~1,]  Try it online! -20 based on approach from u-ndefined's answer ## original graph theory approach, 67 bytes */@(0{+./ .*^:_~)@(1&~:*1>:|)@([:-/~$j./@#:I.@,)@(1,~1,])@E.~1&,\$0:


Try it online!

Convert to adjacency matrix, transitive closure, check if first row is all ones.

# Python3, 274 bytes:

V=lambda b,w,X,Y:0<=Y and Y+w<len(b[0])and sum(b[X][Y:Y+w])==0
def f(b,w):
q,S=[(0,i)for i,a in enumerate(b[0])if V(b,w,0,i)],[]
while q:
x,y=q.pop(0)
if x==len(b)-1:return 1
for X,Y in[(x,y+1),(x,y-1),(x+1,y)]:
if V(b,w,X,Y)and(X,Y)not in S:q+=[(X,Y)];S+=[(X,Y)]


Try it online!

• -1 byte with if~-len(b)==b instead of if x==len(b)-1 -2 bytes with for X,Y in(x,y+1),(x,y-1),(x+1,y) instead of for X,Y in[(x,y+1),(x,y-1),(x+1,y)] Dec 5, 2022 at 1:02
• -1 byte 0<=Y and --> Y>=0and Dec 5, 2022 at 4:39

# Charcoal, 65 bytes

Ｎθ≔⪫11Ｓη≔⌕Ａη×0θζＷＳ«≔⪫11ιι≔Φζ¬Σ✂ικ⁺κθ¹ζＦζＦ⁻⟦⊖κ⊕κ⟧ζ¿¬Σ✂ιλ⁺λθ¹⊞ζλ»¬ζ


Try it online! Link is to verbose version of code. Takes input as an integer followed by a list of newline-terminated binary strings and outputs a Charcoal boolean, i.e. - if Santa sets stuck, nothing if he can drop down. Explanation:

Ｎθ


Input Santa's width.

≔⪫11Ｓη


Input the top of the chimney, but ensure that the edges are solid.

≔⌕Ａη×0θζ


Find all of the places where Santa could start lowering himself down.

ＷＳ«


Loop through the rest of the chimney.

≔⪫11ιι


Ensure that the edges are solid.

≔Φζ¬Σ✂ικ⁺κθ¹ζ


Keep only the positions that are wide enough in the new row.

ＦζＦ⁻⟦⊖κ⊕κ⟧ζ


Loop through the neighbours of the found positions, without repeating a position.

¿¬Σ✂ιλ⁺λθ¹⊞ζλ


If Santa can move sideways then add this position.

»¬ζ


Output whether Santa got stuck.

# APL(Dyalog Unicode), 30 bytes SBCS

{0∊↑(∊∨(∧/¨∧⊢)⍤⊂⍨1,2≠/⊣)/↓⍵}∨/


Try it on APLgolf!

Input width on the left and a binary matrix representing the chimney on the right.

# Python NumPy, 133 bytes

def f(w,A):
while w>1:A=A[:,1:]|A[:,:-1];w-=1
p=~A.T@~A
for a in A:b=p^p;b[range(len(p)),-a.cumsum()]=~a;p=p@[email protected]
return p.any()


Attempt This Online!

# PARI/GP, 101 bytes

f(c,w)=a=[1..#c-w--];[while(j=0;b-a=[[s,j&&a[j],j++<#a&&a[j+1]]&&!r[j..j+w]|s<-t],b=a)|r<-c~,t=b=a];a


Attempt This Online!