5
\$\begingroup\$

Given a mine map of minesweeper, output how many left clicks at least needed to win the game.

Each left click reveals a cell, and if there's no mine in the 3x3 range, recursively reveal nearby 3x3 cells. Your goal is reveal all safe cells.

Test cases: (1 is mine, 0 is safe)

100
000 => 1
000

100
000 => 2
001

101
000 => 5
101

1000
0000 => 2
0001

10000
00000 => 1
00001

1000
0000
0000 => 1
0001

000
101 => 7 # You can't click outside of the board
000

Shortest code wins.

Notes

  • Last time I asked a similar question(but considering distance), and someone closed as unclear because "what would happen if step on a mine". Yet, if you know where mines are, still stepping on them is just silly.
\$\endgroup\$
3
  • 3
    \$\begingroup\$ I don't understand what the challenge is about, specifically "Each left click reveals a cell, and if there's no mine in the 3x3 range, recursively reveal nearby 3x3 cells". What does "reveal" mean exactly, and how is it "recursive"? Ideally, you should explain what should be done in the challenge without relying on people knowing the Minesweeper game \$\endgroup\$
    – Luis Mendo
    Commented Jun 7 at 8:23
  • \$\begingroup\$ @LuisMendo Reveal is a verb whose meaning doesn't matter in this question. Definition of recursion doesn't base on minesweeper. \$\endgroup\$
    – l4m2
    Commented Jun 7 at 8:45
  • \$\begingroup\$ Duplication verified \$\endgroup\$
    – l4m2
    Commented Jun 7 at 19:34

3 Answers 3

2
\$\begingroup\$

Charcoal, 79 bytes

WS⊞υιυFLυFL⌊υ«Jκι¿¬№⊞OKMKK1«UMΦKM⁼0λ2ψ»»≔№KA0ηUBψ⟲¹FLυFL⌊υ«J⁺ικ⁻ικ≧⁺¬℅KKη¤2»⎚Iη

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

WS⊞υιυ

Input the strings and write them to the canvas.

FLυFL⌊υ«Jκι

Loop through every cell.

¿¬№⊞OKMKK1«

If it and its neighbours are empty then...

UMΦKM⁼0λ2

... mark adjacent unrevealed safe cells as being auto-revealed, and...

ψ

... mark this cell as being recursively revealed.

»»≔№KA0η

The remaining unrevealed safe cells need one click each.

UBψ⟲¹

Rotate the canvas by 45°. (I have to set the background to null to work around a bug in Rotate in TIO; this costs me three bytes.)

FLυFL⌊υ«J⁺ικ⁻ικ

Loop through the cells again.

≧⁺¬℅KKη

If this cell was marked as recursively revealed then click on it.

¤2

Flood fill from this cell if possible, recursively revealing nearby cells as part of the same click.

»⎚Iη

Output the final click count.

\$\endgroup\$
4
  • \$\begingroup\$ Fail 1000 0000 0000 0001(expect 1, get 2). Do you only considered LRUD, not 8 directions? \$\endgroup\$
    – l4m2
    Commented Jun 7 at 8:09
  • \$\begingroup\$ Oh yeah, Charcoal's fill is only LRUD, sigh... I'll have to think about this. \$\endgroup\$
    – Neil
    Commented Jun 7 at 8:33
  • \$\begingroup\$ @l4m2 I think this fixes it. \$\endgroup\$
    – Neil
    Commented Jun 7 at 12:20
  • \$\begingroup\$ Rotation bug has been fixed on ATO, so it's now 76 bytes there. \$\endgroup\$
    – Neil
    Commented Jun 12 at 11:31
1
\$\begingroup\$

05AB1E, 58 bytes

"2Fø0δ.ø}2Fø€ü3}"DU.VOO_©˜ƶIgäΔX.V®*€€à}D˜ÙsX.V€€àI+_˜«0Kg

Input as a bit-matrix.

Try it online or verify all test cases.

Explanation:

Step 1: Add a border of 0s around the input, and convert it to overlapping 3x3 blocks:

"..."       # Push the string explained below
     DU     # Store a copy in variable `X`
       .V   # Pop and evaluate it as 05AB1E code

2Fø0δ.ø}    # Add a border of 0s around the (implicit) input-matrix:
2F     }    #  Loop 2 times:
  ø         #   Zip/transpose; swapping rows/columns
            #   (which will use the implicit input-matrix in the first iteration)
    δ       #   Map over each row:
   0 .ø     #    Add a leading/trailing 0
2Fø€ü3}     # Convert it into overlapping 3x3 blocks: 
2F    }     #  Loop 2 times again:
  ø         #   Zip/transpose; swapping rows/columns
   €        #   Map over each inner list:
    ü3      #    Convert it to a list of overlapping triplets

Try just this first step online.

Step 2: Sum each overlapping 3x3 block, and check whether it's 0:

OO          # Sum all overlapping 3x3 blocks
  _         # Check for each sum whether it's 0 (1 if 0; 0 if ≥1)

Try just the first two steps online.

Step 3: Flood-fill, and check how many islands of 1s there are:

©           # Store the current matrix in variable `®` (without popping)
 ˜          # Flatten it
  ƶ         # Multiply each value by its 1-based index
   Ig       # Push the amount of rows in the input-matrix
     Ì      # Increase it by 2 to account for the two borders of 0s
      ä     # Convert the list back to a matrix of that many rows
Δ           # Loop until the result no longer changes to flood-fill:
 X.V        #  Pop and evaluate string `X` as 05AB1E code (repeat step 1)
 ®*         #  Multiply each 3x3 block by the value in matrix `®`
            #  (so the 0s remain 0s)
 €€         #  Nested map over each 3x3 block:
   à        #    Pop and leave its flattened maximum
}           # Close the changes-loop
 D          # Duplicate this matrix (to use in a later step)
  ˜         # Pop and flatten it to a list
   Ù        # Uniquify the remaining digits, to get all islands (and 0)

Try just the first three steps online.

Step 4: Identify all single cell edge cases, that haven't been flood-filled yet:

s           # Swap so the duplicated matrix of islands is at the top again
 X.V        # Pop and evaluate string `X` as 05AB1E code (repeat step 1 yet again)
    €€      # Nested map over each 3x3 block:
      à     #   Pop and leave its flattened maximum
       Y+   # Add the values of the input-matrix
         _  # Check which cells are (still) 0s

Try just the first four steps online.

Step 5: Combine the results of steps 3 and 4, and output the result:

˜           # Flatten the matrix of 1s/0s of the previous step to a list
 «          # Merge the two lists together (the unique islands,
            # as well as the 0-cells that haven't been flood-filled)
  0K        # Remove all 0s
    g       # Pop and push the combined length
            # (which is output implicitly as result)
\$\endgroup\$
4
  • \$\begingroup\$ Why the last two are 3? \$\endgroup\$
    – l4m2
    Commented Jun 7 at 10:58
  • \$\begingroup\$ @l4m2 one and two (similar as your third test case)? \$\endgroup\$ Commented Jun 7 at 11:28
  • 1
    \$\begingroup\$ No cell there, can't click \$\endgroup\$
    – l4m2
    Commented Jun 7 at 11:32
  • \$\begingroup\$ @l4m2 Should be fixed now (I hope). \$\endgroup\$ Commented Jun 7 at 12:23
1
\$\begingroup\$

Uiua SBCS, 54 bytes

/+⊂⊙♭⊙≠◰⍥(⊞(/↥↧).)⧻.<3⊞(/+×.-).⊚:⍥(¬⍥(≡/↥◫3⊂:0⊂0⍉)2.)2

Try it!

Finds all clear spots with no mine in a 3x3, counts the connected components, then adds the number of empty spots that are not adjacent to any clear spots.

\$\endgroup\$

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