Given an array where each number represent a color. After iterating each item in the array (for each item in the iteration the pointer can also point to the second-item-to-the-right), and the two colors in the iteration is the same, do the following checking:

If there is a different color between the pointed colors, the colors will "dissolve" (which is not allowed).

eg.: [1,2,1] is not allowed but [1,1,2,2] is allowed. Here is an explanation for the above test cases:

[1, 2, 1]
 ^     ^

We find that the two pointed items have the same color. We then realize that the color between the pointed items are different than the two same colors; this ensures a "dissolving".

The following is an explanation of the second example:

[1, 1, 2, 2]
 ^     ^

In this step, the atoms are different, so we don't perform the check.

[1, 1, 2, 2]
    ^     ^

In this step the atoms are still different. All colors do not "dissolve", ensuring a valid array.

We can change one color to another but the condition is if we change one color, then we have to change all of its occurrences in the array. The cost of changing color is the number of appearances of the color in the array.

eg.: if the array is [1,2,1,2,1,3,2] and we have decided to change 2 to 1, then our array will become [1,1,1,1,1,3,1] and the cost will be 3 (for changing three 2's to 1's)

We have to minimize the cost and make sure no color dissolves.

Test cases

[1,1,3,3,2,2] -> 0 (no changes are required to prevent dissolving)
[1,3,1,3,1] -> 2 (change all 3's to 1's costs 2)
[1,1,2,3,2,3]-> 2 (change color of all 2's to 3's OR change color of all 3's to 2's)
[1,2,2,2] -> 0 (This is valid; in the second iteration, the color between the pointed colors are equal to the pointed colors.)
[1,2,1,2,1,3,2] -> 3 (the 1's must be changed to make the array valid, and there's 3 of them)
  • \$\begingroup\$ Oh I get it! [1,2] is different, [1,2] is also different! \$\endgroup\$ – user85052 Nov 2 '19 at 10:07
  • \$\begingroup\$ If I am wrong, feel free to explain why. This is my understanding of your challenge. \$\endgroup\$ – user85052 Nov 2 '19 at 10:20
  • \$\begingroup\$ @A_ I didn't understood your query. can you elaborate. \$\endgroup\$ – adam Nov 2 '19 at 10:48
  • \$\begingroup\$ Done, can you understand now? \$\endgroup\$ – user85052 Nov 2 '19 at 11:12
  • 2
    \$\begingroup\$ Given [1,2,1,3,1] is the expected output 2? \$\endgroup\$ – Jonathan Allan Nov 2 '19 at 15:03

Perl 5, 92 bytes

sub f{min map{$o=$_;map{$s="@_";$c=!/$o/*$s=~s,$o,$_,g;$s=~/(.) (.) \1/&&$1-$2?9e9:$c}@_}@_}

Try it online!

sub f{                        #ungolfed:
  min                         #minimum of the yielded list of numbers (from core module List::Util)
  map{                        #map: outer loop of f()'s input args
    $o=$_;                    #keep $o (outer) loop element
    map{                      #map: inner loop of f()'s input args
      $s="@_";                #$s string are input args (input chars) concatenated with no separation
      $c=!/$o/*$s=~s,$o,$_,g; #$c becomes 0 if inner and outer loop elements are equal
                              #otherwise $c becomes the number of changes on the input
                              #$s string when swapping $o with $_ (outer and inner loop variable)
      $s=~/(.) (.) \1/&&$1-$2 #check if $s after the swapping is valid: no three consecutive chars
                              #...should exists in $s where 1st and 3rd are equal but 2nd is not
        ? 9e9                 #yield big number 9e9 if $s is invalid to make sure it wont be the minimum
        : $c                  #yield the number of swaps if $s is valid
    @_                       #input arg's
  @_                         #input arg's, outer loop
|improve this answer|||||
  • 1
    \$\begingroup\$ I think [1,2,1,3,1] should output 2 (and have asked for clarification). Also I think your edit suggestion of "[1,2,1,2,1,3,2] -> 3 (the 1's must be changed to make the array valid, and there's 3 of them)" is incorrect since if you were to change all 1s to 2s you'll have [2,2,2,2,2,3,2] which still has [2,3,2] inside. \$\endgroup\$ – Jonathan Allan Nov 3 '19 at 17:22
  • \$\begingroup\$ Your right. (And I've tried to withdraw my edit suggestion without luck) \$\endgroup\$ – Kjetil S. Nov 3 '19 at 18:38

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