Block Rearrangement

Question

So your task is to take a 3x3 block where -'s mean blank spaces, and *'s mean filled spaces, for example:

-**
-*-
*-*

and rearrange the block so that the *'s form an X, like this:

*-*
-*-
*-*

Input: 3x3 squares like above, they can be 3 lines, an array, or however you want.

Output: The shortest amount of moves to rearrange into an X. Each move is flipping 2 characters that are touching, and are horizontal from each other, vertical from each other, or diagonal from each other. If it's not possible, return any impossible output, for example 999 or -4242. 5 is the smallest such number.

Test Cases:

1) Output: 1

-**
-*-
*-*

2) Output: -1

-*-
-*-
*-*

3) Output: 3

---
-**
***

4) Output: 0

*-*
-*-
*-*

You can substitute the blank and non blank characters but be sure to include which is which in your post

Code Golf

Remember this is code golf the shortest code wins!

Answer 1

Python 3, 104 78 bytes

lambda n:-(sum(n)!=5)or sum(n[1::2])+n[4]*(max(n,n[6:],n[::3],n[2::3])>=[1]*3)

Try it online!

Edit: Applied both @Jonathan Allan's and @xnor's suggestions to drastically reduce the byte count.

The input is a string list of length 9 with zeroes and ones, ones being the *s.

Here are some observations:

• We don't ever need to move the stars already on the correct cells. Any misplaced star has 5 surrounding cells which can't be blocked at once (otherwise the answer is already -1).
• The cost for each misplaced star is either 1 or 2, and it is 2 only if it is surrounded by three correctly placed stars.
• The cost for each misplaced star is independent from each other.

Therefore, we first test if the string has five ones, and then count these things:

• The number of misplaced stars (= ones at odd indices)
• The number of misplaced stars of cost 2 (= cells at 0124, 0346, 2458, 4678 being all ones)
  • Factor out n[4] being one, and then test each range extraction being '111'.
  • Since such star is at most one, we can safely use max instead of sum.

Answer 2

Jelly, 26 bytes

5ḶḤd3ạŒ!Ṁ€€ḅ1Ṃ
T’d3Ç-L=5Ɗ?

Try it online!

---

Take a flat list as input.

Too bad that Jelly doesn't have "multidimensional truthy indices"... T€ṭ€"JẎ also works but takes 1 more byte.

---

Algorithm: There are 5 current block positions and 5 targets (destinations), the algorithm tries each of the 5! matching, and output the minimum sum of [source, destination] Chebyshev distance.

Answer 3

Haskell, 176 132 126 104 bytes

w=0:1:w
m a|sum a/=5=5|1>0=sum$[a!!4|3<-sum.map(a!!)<$>[[0,1,2],[0,3,6],[2,5,8],[6,7,8]]]++zipWith(*)a w

Try it online!

---

Takes a list of integers with 1 as the non-blank character. Sums the number of non-zero even-indexed squares, then adds 1 if any of the double move patterns are found (center square and edge column/row completely filled). The last part's a bit wasteful I think, probably could be much improved over this brute-force method. Returns 5 (an impossible output) on an impossible input.

Answer 4

Python 2, 194 192 bytes

from itertools import*
f=lambda l,k=0:-(sum(l)!=5)or[1,0]*4!=l[:-1]and k<4and-~min(f(l[:a]+[l[b]]+l[a+1:b]+[l[a]]+l[b+1:],k+1)for a,b in combinations(range(9),2)if max(b/3-a/3,abs(a%3-b%3))<2)

Try it online!

Answer 5

JavaScript (ES6), 123 bytes

Takes input as a 9-bit integer. Solves the puzzle by naively applying the rules, which has been proven not to be the shortest approach.

f=(n,k=b=-1)=>n^341?k>2?b:[3,6,9,10,17,18,20,34,36].map(m=>[1,8,8].map(M=>(x=n&(m*=M))&-x^x||f(n^m,k+1)))|b:!~b|k<b?b=k+1:b

Try it online!

Commented

f = (                           // f = recursive function taking:
  n,                            //   n = input
  k =                           //   k = number of moves, initialized to -1
  b = -1                        //   b = best result so far, initialized to -1
) =>                            //
  n ^ 341 ?                     // if n does not match the target pattern:
    k > 2 ?                     //   if we've already done more than 3 moves:
      b                         //     we're not going to find a solution -> abort
    :                           //   else:
      [3,6,9,10,17,18,20,34,36] //     for each swap bitmask m
      .map(m =>                 //     and
      [1,8,8]                   //     for each multiplier M:
      .map(M =>                 //       apply the multiplier to m and
        (x = n & (m *= M))      //       apply the final bitmask to n -> this gives x
        & -x                    //       isolate the least significant bit of x
        ^ x ||                  //       if it's the only bit set,
        f(n ^ m, k + 1)         //       then swap the bits and make a recursive call
      )) | b                    //     end of both map() loops; return b
  :                             // else:
    !~b | k < b ? b = k + 1 : b //   this is a solution in k+1 moves: update b

NB: This codes performs some illegal moves beyond the top of the board when m is multiplied by 64. But they are simply ignored, as they can't possibly lead to a shorter solution than the best legal solution.

Below are the 9 base swap bitmasks and the target pattern. The top left corner is the most significant bit.

000  000  001  001  010  010  010  100  100     101
011  110  001  010  001  010  100  010  100     010 (341)
(3)  (6)  (9)  (10) (17) (18) (20) (34) (36)    101

Answer 6

Jelly, 26 bytes

“ċȤ‘ḤB;U$=a¥;Ḋm2ƊẠ€SɓSn5Nȯ

Try it online!

A monadic link.

How?

Inspired by Bubbler's Python answer; golfed to suit Jelly...

“ċȤ‘ḤB;U$=a¥;Ḋm2ƊẠ€SɓSn5Nȯ - Link: length 9 list of ones & zeros, X
“ċȤ‘                       - list of code-page indices     = [232,154]
    Ḥ                      - double                        = [464,308]
     B                     - to binary     = [[1,1,1,0,1,0,0,0,0],[1,0,0,1,1,0,1,0,0]]
        $                  - last two links as a monad:
       U                   -   upend       = [[0,0,0,0,1,0,1,1,1],[0,0,1,0,1,1,0,0,1]]
      ;                    -   concatenate = [[1,1,1,0,1,0,0,0,0],[1,0,0,1,1,0,1,0,0],[0,0,0,0,1,0,1,1,1],[0,0,1,0,1,1,0,0,1]]
           ¥               - last two links as a dyad:
          a                -   logical AND (vectorises)
         =                 -   equal? (vectorises)
                Ɗ          - last three links as a monad:
             Ḋ             -   dequeue X (remove leftmost element)
               2           -   literal two
              m            -   modulo slice (keeps the "edge-elements") 
            ;              - concatenate
                 Ạ€        - all? for €ach (edge-elements: no-op
                           -                else: 1 for any cost-2 element 0 otherwise)
                   S       - sum
                    ɓ      - new dyadic chain ^that on the right; X on the left
                     S     - sum X
                       5   - literal five
                      n    - not equal?
                        N  - negate (-1 if not exactly 5 1s, 0 otherwise)
                         ȯ - logical OR with right

Answer 7

JavaScript, 85 bytes

s=>/^0*(10*){5}$/.test(s)*s.match(/(?=1.(..)*$|^1(..)?11.1|1.11(..)?1$)|$/g).length-1

This is a regex port of Bubbler's answer.

Input as a string of 0 / 1.

f=
s=>/^0*(10*){5}$/.test(s)*s.match(/(?=1.(..)*$|^1(..)?11.1|1.11(..)?1$)|$/g).length-1

document.write('<table>'+('<tr>'+'<td><label><input type=checkbox><span></span></label>'.repeat(3)).repeat(3)+'</table>');
document.write('Answer: <output id=o></output>');
U=()=>o.value=f(ii.map(i=>i.checked?1:0).join``);
ii=[...document.querySelectorAll('input')];
ii.forEach((i,p)=>{
i.checked=!(p%2);
i.oninput=U;
});
U()

label{display:block;position:relative;overflow:hidden;width:20px;height:20px;}
input{position:absolute;top:-200%;}
input~span{width:100%;height:100%;display:block;border:1px solid black;box-sizing:border-box;}
input:focus~span{border-color:red;}
input:checked~span{background:#ace;}

Answer 8

Stax, 23 22 bytes

Ç╙╤Ü┤└åVτ┐├Y-²▼░█∩¡3ëâ

Run and debug it

This program takes an array of [0, 1] as input, and returns an integer number of moves, or an empty string if no solution is possible.

Consider this indices for the grid

0 1 2
3 4 5
6 7 8

• If there are not exactly 5 1s in the input, then there is no solution, so we produce no output.
• The centers of each side are the incorrect positions. These are indices 1, 3, 5, and 7. Summing the distance for each 1 in these positions will produce the final result.
• For each 1 in an incorrect position its distance is either 1 or 2. It will be 2 iff it's surrounded by other 1s. For example, if there are 1s at indices [0, 1, 2, 4], then the distance for the incorrect 1 is 2.

• With this in mind, consider this pseudo-code for getting the distance contributed to the result by index 1.

  1. Read 4 bits from indices [1, 0, 2, 4]. This puts the incorrect position in the most significant position.
  2. Convert these bits to a number b from 0 to 15.
  3. When 0 <= b <= 7 the distance is 0. When 8 <= b <= 14 the distance is 1. When b == 15 the distance is 2. This can be calculated using integer division by b * 2 / 15.

So the total distance can be calculated by repeating this process 4 times and rotating the grid in between.

1#5=4*  if the number of 1s is 5, then 4, else 0
D       repeat the rest of the program that many times
  x     push the value in the x register, which is initially the input
  3/    split into 3 rows
  rM    rotate 90 degrees
  $X    flatten back into single array, and save the "rotated" array in the X register
  A|2E  get the digits of 2^10 i.e. [1,0,2,4]
  @     read the bits from the current rotation at indices [1,0,2,4]
  :b    convert bits to integer
  H15/  double, then divide by 2
  +     add to running total

Run this one

Answer 9

Excel, 86 81 Bytes

=SUM(B1,A2,B3,C2)+B2*(AND(A1:A3)+AND(A1:C1)+AND(C1:C3)+AND(A3:C3))/(SUM(A1:C3)=5)

Old: When the 'impossible' output was -1

=IF(SUM(A1:C3)=5,SUM(B1,A2,B3,C2)+B2*(AND(A1:A3)+AND(A1:C1)+AND(C1:C3)+AND(A3:C3)),-1)

Uses 1 for filled and 0 for empty, input in range A1:C3. Possible to golf further if we can return values other than -1 for "impossible". Returns a #DIV/0! error on impossible grids

Operates on the same logic as Bubbler's Python answer.