24
\$\begingroup\$

Imagine you have a grid where some squares are walls, some are empty, and some are lights that shine for arbitrary distances in the four cardinal directions until they meet walls:

####.####
##..L....
####.##.#
####.##L.
##......L

In the above grid, the lights cover all the tiles. But in some cases, they may not be:

###
.#L
###

Your challenge is, given a grid like the one above, determine whether all empty tiles are lit up. You may take input as a matrix of characters or integers, a list of lines, newline-separated lines (as above) with any three distinct characters, etc.

An input may contain none of a type of cell.

You may output truthy and falsy with any of the following:

  • Values your language considers truthy or falsy (if applicable), or inverted
  • One truthy value and everything else is falsy, or vice versa
  • Two consistent values representing truthy and falsy

Testcases (Given in above format)

Truthy:

L

L.
.L

L....
..#L.
....L
.L...

#

L...L...L

#####.###
#L...L...
##.####L.
#.L..####

Falsey:

.

.#

L#.

.#.
.L.
.#.

L...
L...
L.#.
L...

L.
..
\$\endgroup\$
9
  • \$\begingroup\$ I can use any 3 char other then /n right? \$\endgroup\$
    – okie
    Dec 20, 2021 at 0:19
  • \$\begingroup\$ @okie Yep, that's correct \$\endgroup\$
    – emanresu A
    Dec 20, 2021 at 0:20
  • \$\begingroup\$ Can we take a matrix of 3 distinct integers instead of characters? \$\endgroup\$
    – pxeger
    Dec 20, 2021 at 0:20
  • \$\begingroup\$ @pxeger Sure, that's fine \$\endgroup\$
    – emanresu A
    Dec 20, 2021 at 0:21
  • \$\begingroup\$ somewhat related numberphile video: youtube.com/watch?v=xhj5er1k6GQ \$\endgroup\$ Dec 20, 2021 at 13:16

17 Answers 17

10
\$\begingroup\$

Vyxal, 29 27 25 23 bytes

2(⌈ƛƛ:×c[¶1V];Ṅ;∩vṅ)∑¶↔

Split on wall, check if any spilt contain light, replace it with 1, transpose, do it again, check sum.

outputs empty string for false, dots otherwise.

-2 by @lyxal (pog)

-2 by @lyxal again (1 minute after first one)

-2 by ... yep still @lyxal

Try it Online!

translate the input

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Nice, this is a really clever approach! \$\endgroup\$
    – emanresu A
    Dec 20, 2021 at 2:03
  • 1
    \$\begingroup\$ 27 bytes \$\endgroup\$
    – lyxal
    Dec 20, 2021 at 2:08
  • 1
    \$\begingroup\$ 25 bytes, outputs empty string for true, dots otherwise \$\endgroup\$
    – lyxal
    Dec 20, 2021 at 2:10
  • 1
    \$\begingroup\$ I swear I'm done now \$\endgroup\$
    – lyxal
    Dec 20, 2021 at 2:19
  • 2
    \$\begingroup\$ @sandra wall => split, so it got translated to "","","","",".","","","L." and then there is one string containing L so that string is replace with a mark (which was amongus here) \$\endgroup\$
    – okie
    Dec 20, 2021 at 23:42
6
\$\begingroup\$

JavaScript (ES6), 112 bytes

Expects a matrix with \$0\$ for walls, \$3\$ for lights and \$4\$ for empty squares. Returns false if the lights cover all the tiles, or true otherwise.

f=m=>m<(m=m.map((r,y)=>r.map((v,x)=>v&&[1,2,1,2].map((b,d)=>v|=(m[y+--d%2]||0)[x+~-d%2]&b)|v)))?f(m):/4/.test(m)

Try it online!

\$\endgroup\$
5
\$\begingroup\$

JavaScript (Node.js), 89 bytes

f=(a,n=4)=>n?f(a[0].map((_,x)=>a.map(c=>(t=c.at(~x))>1?p=t:t|p>>2,p=0)),n-1):!/0/.test(a)

Try it online!

Input matrix where 0 = empty, 2 = wall, 4 = light. Output true vs. false.

Rotate the matrix 90deg 4 times, fill empty cell if there is a light on its left side. Finally test if there are any empty cell left.

This function use ES2022 feature Array#at which requires a newer version of NodeJs than current TIO available. A Polyfill for Array#at is included in the header of TIO code. So it may be tested on it. You may execute it on a more recent version NodeJs without the header.

f=
  (a, // input matrix
  n=4 // rotate 4 times
)=>n?
f(
a[0].map((_,x)=>a.map(c=>(t=c.at(~x)) // rotate
/* t */>1?p=t:t|p>>2,p=0) // fill empty cell if there is a light left side
),n-1):
!/0/.test(a) // no empty cells left

JavaScript (Node.js), 95 bytes

a=>w=>a.every((c,i)=>c|[-2,-1,1,2].some(s=>a.some(_=>t=a[j+=s%2?(j%w-~s)%-~w&&s:s*w/2],j=i)&t))

Try it online!

Input flatten matrix with 0 = empty, 1 = light, 2 = wall, and its width. Output true vs. false.

a=> // the matrix; 0 = empty, 1 = light, 2 = wall
w=> // width of matrix
a.every(   // if every cell is
  (c,i)=>c| // either cell is not empty
  // or cell is lighted
  [-2,-1,1,2] // four directions; up, left, right, down
  .some(s=>   // any direction that
    a.some(_=>  // repeat enough times (we use `a` only because it is long enough)
      t=a[ // repeat move until current cell is non empty
        j+=s%2? // -2, 2 are left / right, while -1, 1 are up / down
          (j%w-~s)%-~w&&s: // if we reached end of current row, stop move
          s*w/2 // move up or down (may out of bound but we don't care)
      ],
      j=i // starting from cell `i`
    )&t // if non-empty cell exists and the cell is light
  )
)
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 254 bytes

d=>!(f=i=>i?f(i-1,d=d.replace(/(?<=a|b)[ c]|[ c](?=a|b)/g,x=>"ab"[+ 
(x<"!")]),d=(t=s=>[...s.split`
`[0]].map((_,i)=>s.split`
`.map(x=>x[i]).join``).join`
`)(t(d).replace(/(?<=a|c)[ b]|[ b](?=a|c)/g,x=>"ac"[+(x<"!")]))):d) 
(d.length+d[0].length).includes` `

Uses for empty spaces, a for lights, and any non-alphabetical and non-space character for walls.

\$\endgroup\$
1
  • \$\begingroup\$ "ac"[+(x<"!")] -> x<"!"?"c":"a" \$\endgroup\$
    – emanresu A
    Dec 20, 2021 at 1:03
4
\$\begingroup\$

C (gcc), 274 \$\cdots\$ 195 191 bytes

#define F for(y=0,i=r*c;i--;
#define J(A,B,C,D)for(y=A c;--y+B&&~-m[C*c+D];)m[C*c+D]|=m[i]*2&4;
i;y;f(m,r,c)int*m;{F){J(-i%,c,i/c,-y)J(i%,1,i/c,y)J(-i/,r,-y,i%c)J(i/,1,y,i%c)}F)y|=!m[i];i=y;}

Try it online!

Saved a whopping 45 \$\cdots\$ 55 59 bytes and got below 200 thanks to ceilingcat!!!

Inputs a pointer to an array of integers along with the room dimensions (since pointers in C carry no length info).
These integers represent a room with \$0\$ -> ., \$1\$ -> #, and \$2\$ -> L.
Returns \$0\$ if the room is lit up or \$1\$ otherwise.

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

Jelly, 19 bytes

,Z»×¥@\Ṛ$2¡€Z»¥/F’Ạ

Try It Online!

"Borrowing" the multiplication idea from Unrelated String (i.e. stealing lol). 0 for #, 1 for ., 2 for L.

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

J, 43 bytes

*-:g&.|:>.g=.**[:}:@;"1<@(#$2&e.);.2"1@,.&0

Try it online!

Based on okie's "split on walls and check if each section contains a light" idea.

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

05AB1E (legacy), 21 bytes

3xŸvTyT+:yT*y∞:ζí}SßĀ

Input as a list of lines, where .L# are 012 respectively.

Uses the legacy version of 05AB1E where the ζ and : builtin works on list of strings, which would have been €SζJ and required a map over the lines in the new 05AB1E (ending up 6 bytes longer).

Try it online or verify all test cases.

Explanation:

3          # Push a 3
 x         # Double it (without popping): 6
  Ÿ        # Pop both and push a list in this range: [3,4,5,6]
   v       # Loop over each of these digits `y`:
        :  #  Replace all:
    T      #   "10"
     yT+   #   with "1y", where `y` is the current digit
           #  (which use the implicit input-list in the first iteration)
         : #  Then infinitely replace all:
    yT*    #   "y0"
       y∞  #   with "yy", where the `y` are again the current digit
    ζí     #  Then rotate once clockwise:
    ζ      #   Zip/transpose; swapping rows/columns
     í     #   Reverse each row
   }       # After the loop, we want to check if any empty spots remain:
    S      # Convert the list of strings to a flattened list of characters
     ß     # Pop and push its minimum
      Ā    # Check if this is NOT 0
           # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

Brev, 159, no, 156 bytes:

(define (l row) (strse row "[g_]*L+[g_]*" (strse (m 0) "_" "g")))
(print (apply any (compose (strse? "_") l string) (map (o string->list l) (read-lines))))

Uses _ instead of . (shaves four bytes) and prints #f for lit up, #t for dark.

Update: remove a redundant partial applicator

\$\endgroup\$
2
\$\begingroup\$

SnakeEx, 34 bytes

m:{d<>}{d<R>}{d<L>}{d<B>}
d:,+[#$]

Uses , instead of .; to take inputs formatted as in the question, replace , on the second line with \.. Outputs one or more matches (truthy) for a room that is not fully lit, no matches (falsey) for a room that is lit. Try it here!

Explanation

Core idea: find a , which can't "see" an L in any of the four directions. If no such , exists, the room is fully lit; if such a , exists, it is not fully lit.

d:        Define a helper snake d to match
  ,+      1 or more commas
    [#$]  followed by a pound sign or the edge of the grid

m:                         Define the main snake m to match
  {d<>}                    d in the default direction (left-to-right)
       {d<R>}              and also in the direction 90 degrees clockwise (top-to-bottom)
             {d<L>}        and the direction 90 degrees counterclockwise (bottom-to-top)
                   {d<B>}  and the reverse direction (right-to-left)
\$\endgroup\$
2
\$\begingroup\$

Txr Lisp, 109 bytes

(do let((l(op mapcar(op regsub #/[. ]*L[. ]*/(op regsub #/\./" ")))))(find #\.(cat-str[l(transpose[l @1])])))

103 bytes

(op find #\.(cat-str[#1=(op mapcar(op regsub #/[. ]*L[. ]*/(op regsub #/\./" ")))(transpose[#1# @1])]))

97 bytes

Drop (cat-str X), use quasiliteral `@x`.

(op find #\.`@[#1=(op mapcar(op regsub #/[. ]*L[. ]*/(op regsub #/\./" ")))(transpose[#1# @1])]`)

This is an expression that evaluate so to a function which operates on sequence of strings, those being the lines of the grid.

The function returns #\., the dot character, to indicate that unlit areas remain. Otherwise it returns nil. A character is truthy, and nil is the only false value.

The logic is just regex. The regsub function matches regular expressions. If the replacement argument is a function, the matched text is passed to it and replaced with what the function returns. For the substitution we use another partially applied regsub which replaces dots with spaces.

So, in every string of dots or spaces that contains an L, we replace the dots with spaces, doing this in every string. Then we transpose the vector of strings and do it again.

Truthy example:

#####.###        #####.###        ####       ####
#L...L...  -->   #L   L      -->  #L#   -->  #L#
##.####L.        ##.####L         # .L       #  L
#.L..####        # L  ####        # #        # #
                                  # #        # #
                                  .L##        L##
                                  # ##       # ##
                                  # L#       # L#
                                  #  #       #  #

No dots remain, so everything is lit.

This main list-of-string processing action for replacing the Ls is a function. In the 109 byte version, it bound to the lexical variable l, which we then refer to twice separated by a transpose call.

In the 103 byte version, we get rid of the local variable and just repeat the code in two places using the Lisp circle notation. #1=OBJ means "OBJ, also associated with label 1". And #1# then means "reproduce the object from label 1, OBJ here". With this we can make a piece of data (i.e. piece of source code, of code is data) appear in two or more places.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 17 16 bytes

»×¥@\Ṛ$⁺
Ç€»ÇF1e

Try it online!

Fixed by borrowing back from hyper-neutrino lmao

-1 replacing the double transpose with a map by replacing the map with implicit vectorization

Takes a matrix of 0 for #, 1 for ., and 2 for L.

»×¥@\Ṛ$⁺    Monadic helper link: light up all columns or a row
    \       Scan by
»  @        (vectorizing) max of right and
 ×¥         (vectorizing) product,
     Ṛ      then reverse.
      $⁺    Do it again.

Ç€»ÇF1e    Monadic main link: is there anything unlit?
Ç          Light up
 €         each row,
   Ç       light up the columns,
  »        and take the maximum at each position.
    F      Flatten the result.
     1e    Does it contain 1?
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Doesn't work for #L. lol \$\endgroup\$
    – hyper-neutrino
    Dec 20, 2021 at 2:24
1
\$\begingroup\$

Charcoal, 47 bytes

WS⊞υιυFLυF⌕A§υιLF⁴«JκιM✳⊗λW﹪℅KK³⁵✳⊗λ_»≔№KA.θ⎚¬θ

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings and outputs a Charcoal boolean, i.e. - if the room is fully lit, nothing if not. Explanation:

WS⊞υιυ

Input the map and print it to the canvas.

FLυF⌕A§υιLF⁴«

Loop over the lights in all directions.

JκιM✳⊗λ

Move to a tile adjacent to a light.

W﹪℅KK³⁵

While this tile is not wall, ...

✳⊗λ_

... mark it as lit and move to the next tile. (Note: If there are two lamps, they'll light each other, but the loop above checks the original lamps, so it doesn't matter that they get removed from the canvas.)

»≔№KA.θ

Count the number of remaining unlit tiles.

⎚¬θ

Clear the canvas and output the result.

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

Retina 0.8.2, 94 91 bytes

(?!_+L|((?<=(.)*)_.*¶(?<-2>.)*(?(2)^))+L)_(?<!L_+|L((?<=(?<!.)(?(4)$)(?<-4>.)*.).*¶(.)*_)+)

Try it online! Takes input using _ as a floor tile instead of . but header converts . to _ for you for convenience. Outputs the number of unlit floor tiles, so a falsy value if the room is lit. Explanation:

(?!_+L|

Don't match a floor tile that is to the left of a light, or...

((?<=(.)*)_.*¶(?<-2>.)*(?(2)^))+L)

... that is above a light.

_

Match an unlit floor tile.

(?<!L_+|

Don't match a floor tile that is to the right of a light, or...

L((?<=(?<!.)(?(4)$)(?<-4>.)*.).*¶(.)*_)+)

... that is below a light.

.NET balancing groups are used to ensure that the light is in the same column as the tile.

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

Python3, 205 bytes:

import re
m=lambda x:re.sub('(?:\.+)*L(?:\.+)*',lambda j:'L'*len(j.group()),x)
f=lambda x:all(all(n!=('.','.')for n in zip(m(i),j)if n!=('#','#'))for i,j in zip(x,[*zip(*[m(''.join(c))for c in zip(*x)])]))

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Save a space for 204 bytes \$\endgroup\$
    – movatica
    Dec 23, 2021 at 13:11
  • \$\begingroup\$ Also, is there a testcase where the much simpler regex '\.*L\.*' would fail? \$\endgroup\$
    – movatica
    Dec 23, 2021 at 13:17
  • \$\begingroup\$ Aliasing the zip function saves two more bytes \$\endgroup\$
    – movatica
    Dec 23, 2021 at 13:20
1
\$\begingroup\$

Perl 5, 103 bytes

sub{$_=pop;while(!$h{$_}++){s/(Ll*)\./$1l/;$r=@l=();map/\s/?$r=0:$l[$r++]=~s/^/$_/,/./gs;$_="@l"}!/\./}

Try it online!

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

C (gcc), 146 141 bytes

#define F(d)for(i=r*c;i--;F&=m[i])for(j=i;m[i]>3&1u*j<r*c&m[j]<8&&j/c!=i/c^d*d;j+=d)m[j]|=1;
i;j;F;f(m,r,c)int*m;{F(1)F(-1)F(c)F=1;F(-c)i=F;}

Try it online!

Thank ceilingcat for -3 bytes

Not quite sure what Noodle9 did, and not sure why I can't F(1)(-1)... here

\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat Likely it'd fail, j/c!=i/c only returns 0 or 1 \$\endgroup\$
    – l4m2
    Jan 19 at 23:51

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.