CGAC2022 Day 4: Can Santa fit down the chimney?

Question

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 code-golf 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",
]

Answer 1

Vyxal, 18 16 bytes

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

Try it online! or Test suite.

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?

Answer 2

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
                  //     extra leading '1'
  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

Answer 3

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.

Try it online or verify all test cases.

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)

Answer 4

J, ⁶⁷ 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.

Answer 5

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!

Answer 6

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.

Answer 7

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.

Answer 8

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!

Answer 9

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!