7
\$\begingroup\$

This challenge was inspired by the game Flood.

Challenge

Given a grid of colors, determine the optimal list of moves to take to convert the whole grid to the same color.

First of all, let us say that a pixel is in the "top left chunk" if and only if it is either the top left pixel or it shares an edge with a pixel of the same color in the top left chunk. Then, a move is defined as changing the color of all pixels in the top left chunk to a specific color.

If you change the color of the top left chunk to match the color of one of the pixels adjacent to the top left chunk, then that pixel joins the top left chunk.

The input will be given as a matrix of positive integers with each integer representing a distinct color. A move is defined by the color to which you change the top left chunk; thus, a move is represented as an integer,

The output should be a list of integers representing which moves to take to convert the entire grid to one color in as few moves as possible. If multiple methods are possible, outputting all of them or any one of them is allowed.

Example

Let's take this as an example:

123
132
223

In this case, both [2, 3, 2] and [3, 2, 3] work. We observe the following for [2, 3, 2]:

123    223    333    222
132 -> 232 -> 332 -> 222
223    223    333    222

and the following for [3, 2, 3]:

123    323    223    333
132 -> 332 -> 222 -> 333
223    223    223    333

Test Cases

123
132 -> 2 3 2 OR 3 2 3
223

111
111 -> []
111

123
231 -> 2 3 1 2
312

123
312 -> 2 1 3 1 2 OR 2 1 3 2 1 OR 2 3 2 1 3 OR 2 3 2 3 1 OR 3 1 2 1 3 OR 3 1 2 3 1 OR 3 2 3 1 2 OR 3 2 3 2 1 (Thanks @JonathanAllan)
231

Rules

  • This is so the shortest valid submission is determined as the winner, tiebreak by earlier submission winning
  • The input and output can be in any reasonable format for matrices and lists
  • The input is not necessarily square but is necessarily rectangular
  • Your program must be able to handle at least 128 x 128
  • Your program must be able to handle at least 16384 colors
  • You may also take the number of distinct colors as an input

Please correct my test cases if they are wrong. Thanks!

Note:

I believe that this is different enough from Create A Flood AI to warrant its own post because the winning criteria are very different; that one mainly asks to find a small number of steps to solve all of the test cases; this one requires one of the shortest solutions and is a code-golf. However, if you disagree, please close-vote as duplicate and then the community can decide.

\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – rahnema1 Jun 9 '17 at 4:46
  • \$\begingroup\$ @rahnema1 Oh that's what it's called. Interesting, thanks. \$\endgroup\$ – HyperNeutrino Jun 9 '17 at 4:47
  • \$\begingroup\$ Any limit on the size of the matrix? Any limit on the number of distinct 'colors'? Also, can we take the number of colors as an additional input or are we supposed to figure this out by scanning the matrix? \$\endgroup\$ – Arnauld Jun 9 '17 at 6:50
  • 1
    \$\begingroup\$ Near duplicate \$\endgroup\$ – user1502040 Jun 9 '17 at 10:13
  • 1
    \$\begingroup\$ @user1502040 On second thought, that one asks to find the shortest solutions for a lot of grids; this one wants the shortest code to get it, so the winning criteria are a bit different. Thanks anyway :) \$\endgroup\$ – HyperNeutrino Jun 9 '17 at 12:19
1
\$\begingroup\$

CJam (77 bytes)

{Ma+a{():B;:A:|{A((:C;0\+a\+_e_,2*{[0C]f/[0_]f*z}*{0Der}%BD+a+a+}fDAe_(-}g;B}

Online demo. This is an anonymous block (function) which takes the input as a 2D array and provides the output as a 1D array.

\$\endgroup\$

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.