14
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ By flipping 2 characters, did you mean flip from space to * and vice versa, or exchange them? \$\endgroup\$ – user202729 Apr 8 '18 at 14:57
  • \$\begingroup\$ What if there are more than five *? Can you add some more test cases? \$\endgroup\$ – Stewie Griffin Apr 8 '18 at 14:58
  • \$\begingroup\$ @user202729 for example abc would be acb if you flipped the last 2 characters. \$\endgroup\$ – Noah Cristino Apr 8 '18 at 15:08
  • \$\begingroup\$ @StewieGriffin "if it's not possible return a -1" more than 5 * or less than 5 makes it impossible. \$\endgroup\$ – Noah Cristino Apr 8 '18 at 15:08
  • 6
    \$\begingroup\$ May we use something other than -1? For example 5 (impossible otherwise), or throwing an error? \$\endgroup\$ – Jonathan Allan Apr 8 '18 at 18:38
12
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Save 17 bytes by accepting a list instead of a string (replacing counts with sums and '111' with [1]*3) TIO (I've been trying to be clever with a n[i::j]>=[1]*3 loop but have not found shorter). \$\endgroup\$ – Jonathan Allan Apr 8 '18 at 20:30
  • \$\begingroup\$ Since there can only be one cost-2 star, it looks like you can do max(n,n[6:],n[::3],n[2::3])>='1'*3. \$\endgroup\$ – xnor Apr 8 '18 at 21:33
  • \$\begingroup\$ There are other arrangements that have a cost-2 star. I think [0,1,1,1,1,0,1,0,0] should return 3 instead of 2. \$\endgroup\$ – RootTwo Apr 11 '18 at 20:56
  • \$\begingroup\$ Also, [1,1,1,1,0,0,1,0,0] should be 3 instead of 2. \$\endgroup\$ – RootTwo Apr 11 '18 at 21:29
  • \$\begingroup\$ Also, [1,1,1,1,0,0,1,0,0] should be 3 instead of 2. \$\endgroup\$ – RootTwo Apr 11 '18 at 21:29
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You may take a flat list ("however you want") ...maybe you can even take 0-based indices and have 24? \$\endgroup\$ – Jonathan Allan Apr 8 '18 at 22:26
4
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Some tips: the length test can be shortened to sum[1|1<-a]. Function s to :(1-e,n+sum[1|b>e]) which you can inline to save another byte. You can use the otherwise guard in m to save pair of (). Finally, && on top level in a guard can be replaced by ,. ... \$\endgroup\$ – nimi Apr 9 '18 at 15:26
  • 2
    \$\begingroup\$ You can save another byte by using a sum on a list comprehension to cast a Boolean to int. Try it online! \$\endgroup\$ – Sriotchilism O'Zaic Apr 9 '18 at 21:03
  • 2
    \$\begingroup\$ Actually you can save quite a few bytes because once the pattern guards are gone you can just move the whole thing up into m. Try it online! \$\endgroup\$ – Sriotchilism O'Zaic Apr 9 '18 at 21:14
  • 2
    \$\begingroup\$ Also since every non-1 element of a must be 0 can't you use sum a instead of sum[1|1<-a]? Try it online! \$\endgroup\$ – Sriotchilism O'Zaic Apr 9 '18 at 21:19
  • 1
    \$\begingroup\$ I just realized since there can't be more than 1 side with all 1s unless the center is 0, you can do 3<- instead of elem 3$. Also you can use sum.map(a!!) instead of sum<$>map(a!!). \$\endgroup\$ – Sriotchilism O'Zaic Apr 10 '18 at 20:40
3
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Doesn't work with [0,1,0,1,0,1,1,1,0] (expected: 4, actual: 13). \$\endgroup\$ – Bubbler Apr 8 '18 at 16:10
  • \$\begingroup\$ @Bubbler fixed it \$\endgroup\$ – ovs Apr 8 '18 at 16:46
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Can you link a hexdump for testing? Also, I didn’t know 9 bit integers were possible in JS \$\endgroup\$ – Stan Strum Apr 9 '18 at 6:15
  • \$\begingroup\$ @StanStrum Updated to a shorter version with a more straightforward encoding. (And yes: JS supports bitwise operations for up to 32 bits.) \$\endgroup\$ – Arnauld Apr 9 '18 at 6:33
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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;}

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

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

\$\endgroup\$
  • \$\begingroup\$ Check the edit, any impossible value is accepted, not just -1 if that helps you \$\endgroup\$ – Noah Cristino Apr 9 '18 at 23:57
  • \$\begingroup\$ Yes. That saved 2 bytes. \$\endgroup\$ – recursive Apr 10 '18 at 0:54
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Check the edit, any impossible value is accepted, not just -1 \$\endgroup\$ – Noah Cristino Apr 9 '18 at 23:57

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.