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

8 Answers 8

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\$
1
  • \$\begingroup\$ You may take a flat list ("however you want") ...maybe you can even take 0-based indices and have 24? \$\endgroup\$ Apr 8, 2018 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\$
8
  • 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, 2018 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\$
    – Wheat Wizard
    Apr 9, 2018 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\$
    – Wheat Wizard
    Apr 9, 2018 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\$
    – Wheat Wizard
    Apr 9, 2018 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\$
    – Wheat Wizard
    Apr 10, 2018 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\$
2
  • 1
    \$\begingroup\$ Doesn't work with [0,1,0,1,0,1,1,1,0] (expected: 4, actual: 13). \$\endgroup\$
    – Bubbler
    Apr 8, 2018 at 16:10
  • \$\begingroup\$ @Bubbler fixed it \$\endgroup\$
    – ovs
    Apr 8, 2018 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\$
2
  • \$\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, 2018 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, 2018 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\$
2
  • \$\begingroup\$ Check the edit, any impossible value is accepted, not just -1 if that helps you \$\endgroup\$ Apr 9, 2018 at 23:57
  • \$\begingroup\$ Yes. That saved 2 bytes. \$\endgroup\$
    – recursive
    Apr 10, 2018 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\$
1
  • \$\begingroup\$ Check the edit, any impossible value is accepted, not just -1 \$\endgroup\$ Apr 9, 2018 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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