14
\$\begingroup\$

Inspired by Is this Flow Free puzzle trivial? by @Bubbler. Lengthy chunks of this challenge are borrowed from there. This may be one step of a solution for the linked challenge, depending on chosen strategy.

Background

Flow Free is a series of puzzle games whose objective is to connect all the same-colored pairs of dots on the grid. In this challenge, we consider the original game on a rectangular grid (no variations like bridges, warps, or hexagonal grids).

A puzzle in Flow Free might look like this:

Puzzle   Solution
....1    11111
.....    13333
..24.    13243
1....    13243
23...    23243
...43    22243

Challenge

Given a solved Flow Free puzzle, output the unsolved puzzle.

The input can be taken as a single string/array or a list of lines. You may also take the dimensions of the array as input.

You may assume only the digits 1-9 are used and the numbers used in the solved puzzle will be a strict prefix of these (i.e. no need to handle there being 2s but no 1s in the input). Also, each line represented by each digit is a valid polystrip of length 3 or higher.

Unsolving means identifying the ends of the polystrips and keeping them in place, while replacing other cells with a 0 or any consistent non-digit character.

Output the string/array in any convenient manner.

This is , the shortest code per language wins!

Test cases

Inputs Outputs
11111
12221

11113
33333
32222

11111
13333
13243
13243
23243
22243

11121
13121
13121
13111

11122
13121
13121
33111

13333
13443
13343
11243
21243
22244

1116777
1226666
1125555
5555344
8888334
9998444
.....
12.21

1..13
.....
32..2

....1
.....
..24.
1....
23...
...43

...21
.3...
...2.
13...

....2
.3..1
1..2.
3....

1....
..4..
..3..
..2..
21..3
....4

..167.7
.2....6
.12...5
5...34.
8....3.
9.984..
\$\endgroup\$
3
  • \$\begingroup\$ "You may assume only the digits 1-9 are used", I would imagine we may assume that the numbers used in the solved puzzle will be a strict prefix of these (i.e. we do not need to handle there being 2s but no 1s in the input etc.), is that correct? \$\endgroup\$ Oct 8 at 19:18
  • 1
    \$\begingroup\$ @JonathanAllan I didn't mean that there, but you may assume that, if that fits you. \$\endgroup\$
    – pajonk
    Oct 8 at 19:46
  • \$\begingroup\$ I did not believe you meant that, but that if I asked you would say OK. I don't think I'd need it though, but it could be a useful allowance for some. \$\endgroup\$ Oct 8 at 19:56

11 Answers 11

5
\$\begingroup\$

JavaScript (ES6),  87 84 83  82 bytes

Saved 1 byte thanks to @tsh

Expects a matrix of integers. Returns another matrix where empty cells are set to 0.

m=>m.map((r,y)=>r.map((v,x)=>v*-(g=d=>d+2?((m[y+d--%2]||0)[x+d%2]==v)+g(d):d)(2)))

Try it online!

Or 79 bytes with optional chaining:

m=>m.map((r,y)=>r.map((v,x)=>v*-(g=d=>d+2?(m[y+d--%2]?.[x+d%2]==v)+g(d):d)(2)))

(not supported by TIO)

Commented

m =>                       // m[] = input matrix
m.map((r, y) =>            // for each row r[] at position y in m[]:
  r.map((v, x) =>          //   for each value v at position x in r[]:
    v * -(                 //     set v to 0 if the result of g() is 0
                           //     or leave it unchanged if it's -1
      g =                  //     g is a recursive function taking
      d =>                 //     a direction d in [-1, 0, 1, 2]
      d + 2 ?              //       if d is not equal to -2:
        (                  //         we test whether the adjacent cell
          (                //         at (x', y') with:
            m[y + d-- % 2] //           y' = y + (d % 2)
            || 0           //
          )                //
          [x + d % 2]      //           x' = x + ((d - 1) % 2)
          == v             //         is equal to v
        )                  //         and increment the result if it is
        + g(d)             //         recursive call
      :                    //       else:
        d                  //         stop the recursion and subtract 2
    )(2)                   //     initial call to g with d = 2
  )                        //   end of inner map()
)                          // end of outer map()
\$\endgroup\$
2
  • \$\begingroup\$ m=>m.map((r,y)=>r.map((v,x)=>v*-(g=d=>d+2?((m[y+d--%2]||0)[x+d%2]==v)+g(d):d)(2))) \$\endgroup\$
    – tsh
    Oct 11 at 3:50
  • \$\begingroup\$ @tsh Oh I see. I overlooked the part valid polystrip of length 3 or higher, which implies that there will never be more than 2 neighbors. Thank you. \$\endgroup\$
    – Arnauld
    Oct 11 at 7:21
4
\$\begingroup\$

Wolfram Language (Mathematica), 106 bytes

ArrayFilter[Count[Extract[#,{{1,2},{2,1},{2,3},{3,2}}],#[[2,2]]]/.{1->#[[2,2]],_->0}&,#,{1,1},Padding->0]&

Try it online!

ArrayFilter[                       -apply to each 3x3 block, padded with 0s
  Count[                           -count the
    Extract[#,                     -occurrences at
      {{1,2},{2,1},{2,3},{3,2}}    -positions up, down, left, right
    ],
    #[[2,2]]                       -of the center element
  ]
  /.{1->#[[2,2]],_->0}&,           -replace with center element if count is 1, otherwise 0
#,{1,1},Padding->0]&
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 51 bytes

WS⊞υιυUMυ⪪ι¹FLυ«J⁰ιFL§υι«F⊖№KVKK§≔§υικ.→»»J⁰¦⁰Eυ⪫ιω

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

WS⊞υιυ

Input the strings and print them to the canvas.

UMυ⪪ι¹

Split the strings into character lists so that they can be replaced.

FLυ«

Loop over each of the lists.

J⁰ι

Jump to the start of its line.

FL§υι«

Loop over the cells of the list.

F⊖№KVKK§≔§υικ.

Count the number of times the cell appears in its Von Neumann neighbourhood. If it's more than once then replace the state with a ..

Move to the next cell.

»»J⁰¦⁰Eυ⪫ιω

Overwrite the canvas with the new states.

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

Retina 0.8.2, 125 bytes

(.)(?<=(\1).)?(?=(?<2>\1))?(?<=(?<!.)(?(3)$)(?<-3>.)*(?<2>\1).*¶(.)*.)?(?=(?<=(.)*.).*¶(?<-4>.)*(?(4)$)(?<2>\1))?(?<-2>){2}
.

Try it online! Link includes test suite that splits on double-spaced tests and double-spaces the results. Explanation:

(.)

Match a character...

(?<=(\1).)?

... that might be preceded by a copy of that character, ...

(?=(?<2>\1))?

... that might be followed by a copy of that character, reusing capture group 2 for the count of copies, ...

(?<=(?<!.)(?(3)$)(?<-3>.)*(?<2>\1).*¶(.)*.)?

... that might be below a copy of that character, using a .NET balancing group to ensure both characters are in the same column, ...

(?=(?<=(.)*.).*¶(?<-4>.)*(?(4)$)(?<2>\1))?

... or that might be above a copy of that character, ...

(?<-2>){2}

... where two copies exist.

.

Replace it with a dot.

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

R, 112 bytes

function(m)m*(apply(which(m|1,T),1,function(j)sum(m[t((j+rbind(o<-c(1:-1,0),rev(o)))%%(dim(m)+1))]==m[t(j)]))<2)

Try it online!

unsolved=function(m)                # get unsolved puzzle for matrix m:                 
 m*                                 # m multiplied by...
  (apply(which(m|1,T),1,function(j) # function applied to all coordinates of m:
    sum(m[                          #  sum of elements of m...
     t((j                           #  at each coordinate...
      +rbind(o<-c(1:-1,0),rev(o)))  #  plus (1,0),(0,-1),(-1,0) & (0,1)...
     %%(dim(m)+1))                  #  modulo dimensions of m +1...
                                    #  (prevents offset coordinates becoming too big)
    ]==m[t(j)]))                    #  that are equal to the value at this coordinate
  <2)                               # is less than 2 
                                    # (so, is equal to 1, since there are no 'lonely' 
                                    # digits without any equal neighbours as each line 
                                    # is guaranteed to be length 3 or longer)
\$\endgroup\$
2
\$\begingroup\$

Jelly, 18 bytes

ŒĠạⱮ§ỊSʋÐṀ⁸$€ẎŒṬ¬a

A monadic Link that accepts a list of list of positive integers and yields a list of lists of non-negative integers (0 representing the unclued cells).

Try it online! Or see the test-suite.

How?

ŒĠạⱮ§ỊSʋÐṀ⁸$€ẎŒṬ¬a - Link: list of lists, A
ŒĠ                 - group multi-dimensional indices by their values
            €      - for each group (a list of coordinates, G, where one of the values are):
           $       -   last two links as a monad, f(G):
          ⁸        -     using G as the right argument...
        ÐṀ         -     filter G keeping those [a,b] which are maximal under:
       ʋ           -       last four links as a dyad, f([a,b], G)
   Ɱ               -         map across G with:
  ạ                -           absolute difference (vectorises)
    §              -           sums (-> Manhatten distances)
     Ị             -           insignificant? (0 or 1?)
      S            -           sum
             Ẏ     - tighten to a list of coordinates (of the blanks in the puzzle)
              ŒṬ   - multi-dimensional untruth
                ¬  - logical NOT (vectorises)
                 a - logical AND with A (vectorises)
\$\endgroup\$
3
  • \$\begingroup\$ If the tightened list of coordinates doesn't include the last row or column, does 'multi-dimensional untruth' fill a big-enough matrix? For instance, this seems to fail... \$\endgroup\$ Oct 8 at 22:41
  • \$\begingroup\$ Huh, I thought it would be OK... will delete/fix \$\endgroup\$ Oct 8 at 22:45
  • \$\begingroup\$ Thanks, fixed it up now! \$\endgroup\$ Oct 8 at 23:00
2
\$\begingroup\$

BQN, 41 bytes

4⊸⊑⊸(⊣×1=·+´1‿3‿5‿7⊏=)∘⥊⎉2 3‿3↕⊢↑˝·≍⟜¬2+≢

Try it here.

It is a tacit function which takes input as an integer array and returns an integer array. The function can be split into three parts:

Pad the input with 0s on all sides.

⊢↑˝·≍⟜¬2+≢ #
       2+≢ # Add 2 to each dimension of the shape
⊢↑˝·≍⟜¬    # and use that to over-take from the input in each direction

Make a rank 4 array of the 3 by 3 windows.

3‿3↕
 

Replace each window with it's center element if it is an endpoint, otherwise replace with 0.

4⊸⊑⊸(⊣×1=·+´1‿3‿5‿7⊏=)∘⥊⎉2 # 
                        ⎉2 # On the rank 2 subarrays:
                      ∘⥊   # flatten
4⊸⊑                        # get the center element,
   ⊸(                )     # and pass as the left argument into the train:
                    =      # compare equality of flattened window with center
            1‿3‿5‿7⊏       # pick out only the Manhattan neighbors
         ·+´               # sum the true values
       1=                  # test if equals 1,
     ⊣×                    # and multiply bool result by the center element
\$\endgroup\$
2
\$\begingroup\$

Python 3, 111 bytes

lambda k:[c*(sum('0'<c==(k+" "*d)[n+q]for d in(1,k.find('\n')+1)for q in(d,-d))<2)or'.'for n,c in enumerate(k)]

Try it online!

Returns a list of characters.

-1 byte thanks to ovs

Thanks to PertinentDetail for fixing a bug for only +3 bytes

\$\endgroup\$
4
  • 2
    \$\begingroup\$ 108 bytes as a lambda function \$\endgroup\$
    – ovs
    Oct 8 at 16:01
  • 2
    \$\begingroup\$ This fails on the fourth test case. The failure is more obvious on "123\n123\n123\n". I can fix it at the cost of growing to 111 characters. \$\endgroup\$ Oct 9 at 23:43
  • \$\begingroup\$ @ovs Great find, thanks! \$\endgroup\$
    – Jitse
    Oct 11 at 7:26
  • \$\begingroup\$ @PertinentDetail Ah, I missed that. Thanks for the fix! \$\endgroup\$
    – Jitse
    Oct 11 at 7:27
2
\$\begingroup\$

PHP, 177 Bytes

$s=array_fill(0,$h,[]);foreach($a as $j=>$r)foreach($r as $i=>$e)$s[$j][$i]=($a[$j][$i-1]==$e)+($a[$j][$i+1]==$e)+($j>0&&$a[$j-1][$i]==$e)+($j<$h-1&&$a[$j+1][$i]==$e)<2?$e:'.';

Assumes that the input $a is supplied as a multi-dimensional array, $h is the total number of rows and $w is the total number of columns. These can also be derived using simple explode, split and count functions:

$a=array_map(str_split,explode("\n",$argn));
$h=count($a);
$w=count($a[0]);

The output can also be converted back to a string, although in true golf fashion, there may be less bytes if we skipped saving the output as an array.

$o=implode("\n",array_map(implode,$s));
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf! Taking input with variables isn't usually allowed (typical rules), although this answer looks pretty cool! \$\endgroup\$ Oct 13 at 3:41
1
\$\begingroup\$

Ruby, 170 bytes

->m{(0...R=m.size).map{|y|(0...C=m[0].size).map{|x|[[y-1,x],[y,x-1],[y+1,x],[y,x+1]].reject{|a,b|a<0||a>=R||b<0||b>=C}.map{|a,b|m[y][x]==m[a][b]?1:0}.sum<2?m[y][x]:'.'}}}

Try it online!

  • Straightforward approach : we cross check every element against the 4 adjacent elements and we keep it if there are only 1, we put a dot instead.
  • to check adjacent elements we build an array of [y,x] indexes and we reject pairs out of bounds, this costs so many bytes!
\$\endgroup\$
1
\$\begingroup\$

Matlab, 102 90 bytes

function a=f(a)
for i=1:9
b=a==i
a=a-b.*(conv2(b,[0 1 0;1 0 1;0 1 0],'same')~=1)*i
end
end

The input is a and the output is also a. This goes through all the values in the grid (1 to 9). For each value it finds cells that have more than one neighbor of that value. This is done using the 4-directional 2D convolution conv2. It then sets those cells to 0. What is left is the required grid. Note this will also work if there are multiple paths with the same digit. It also works for the case when digit 1 is missing, but digit 2 exists.

-12 bytes by removing unnecessary white space. Thanks to @MarcMush!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I haven't golfed (or used even) Matlab in like 5 years, but you may have a look at the Matlab tips question: codegolf.stackexchange.com/questions/12974/… \$\endgroup\$
    – pajonk
    Oct 12 at 7:13
  • 1
    \$\begingroup\$ Assuming input in a variable is not allowed, so you need to wrap it into a function (taking a as a parameter and returning the modified a at the end; linking a valid example answer because I don't actually know matlab). \$\endgroup\$
    – Bubbler
    Oct 12 at 7:30
  • \$\begingroup\$ Thank you both. I will try to fix it. \$\endgroup\$ Oct 12 at 8:42
  • \$\begingroup\$ I wrapped it in a function, so this submission is legal now. Still shorter than most non-golfing languages :) \$\endgroup\$ Oct 13 at 2:20
  • 1
    \$\begingroup\$ you can save at least 15 bytes by removing all the useless spaces \$\endgroup\$
    – MarcMush
    Oct 21 at 9:38

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.