5
\$\begingroup\$

Specification

For this challenge you will:

  • Take an array of positive integers.
  • For each overlapping pair in the array, calculate the difference of it's integers. If the difference is a common divisor of the integers (they are both divisible by their difference), swap their positions in the array. The values of the next pair are affected by this swap. No integer is divisible by 0.
  • If an integer was not divisible by the difference of any of it's pairs, remove it from the array.
  • Repeat the previous two steps until the length of the array will not decrease any further.
  • Output the length of the resulting array.

Example

  • Input = [ 4, 5, 2, 4 ].
  • Difference of first pair [ ( 4, 5, ) 2, 4 ] = 1, (common divisor of 4 and 5)
    • Swap the pair and the array becomes [ 5, 4, 2, 4 ].
  • Difference of second pair [ 5, ( 4, 2, ) 4 ] = 2 (common divisor of 4 and 2)
    • Swap the pair so the array becomes [ 5, 2, 4, 4 ].
  • Difference of third pair [ 5, 2, ( 4, 4 ) ] = 0 (not a divisor of any integer)
    • Do not swap the pair so the array remains the same.
  • The final 4 was never swapped, remove it so the array becomes [ 5, 2, 4 ].
  • Repeat.
  • Difference of first pair [ ( 5, 2, ) 4 ] = 3
    • Do not swap the pair so the array remains the same.
  • Difference of second pair [ 5, ( 2, 4 ) ] = 2
    • Swap the pair so the array becomes [ 5, 4, 2 ].
  • The 5 was never swapped, remove it so the array becomes [ 4, 2 ]
  • Repeat.
  • From here the array will endlessly switch between [ 4, 2 ] and [ 2, 4 ], so output the resulting length of 2.

Rules

  • Input array will always have a length between 2 and 9 inclusive.
  • Integers will always be between 1 and 999 inclusive.
  • Input can optionally be in the form of a string delimited by a specific character.
  • This is so shortest code in bytes wins.

Test Cases

Format: [ input array ] = result (steps to get result, do not output this)

[ 1, 1 ] = 0                        ([])
[ 1, 2 ] = 2                        ([ 2, 1 ] -> [ 1, 2 ] -> ...)
[ 1, 2, 3 ] = 2                     ([ 2, 1 ] -> [ 1, 2 ] -> ...)
[ 4, 6, 8 ] = 3                     ([ 6, 8, 4 ] -> [ 8, 4, 6 ] -> [ 4, 6, 8 ] -> ...)
[ 99, 1, 3 ] = 0                    ([])
[ 4, 5, 2, 4 ] = 2                  ([ 5, 2, 4 ] -> [ 4, 2 ] -> [ 2, 4 ] -> ...)
[ 12, 4, 6, 3 ] = 3                 ([ 6, 4, 3 ] -> [ 4, 3, 6 ] -> [ 3, 6, 4 ] -> ...)
[ 9, 6, 10, 18 ] = 2                ([ 6, 10, 18, 9 ] -> [ 9, 18 ] -> [ 18, 9 ] -> ...)
[ 55, 218, 654, 703, 948, 960 ] = 2
[ 954, 973, 925, 913, 924, 996, 927, 981, 905 ] = 2
\$\endgroup\$
  • \$\begingroup\$ Are you sure of the last test case? I get 2 [924, 996, 913] -> [913, 996] \$\endgroup\$ – edc65 Apr 28 '16 at 8:28
  • \$\begingroup\$ @edc65 Oops, you're right. Fixed. \$\endgroup\$ – user81655 Apr 28 '16 at 8:46
  • \$\begingroup\$ ... and [12,4,6,3] -> [6,3,4] -> [3,4,6] -> [4,6,3] \$\endgroup\$ – edc65 Apr 28 '16 at 9:00
2
\$\begingroup\$

JavaScript (ES6), 133

Recursive function.

F=(m,k=[])=>(k[m]=m,f=m.map((x,i)=>x%(w=x-(y=m[i+1]))==0&y%w==0?m[m[i]=y,i+1]=x:0),k[m=m.filter((x,i)=>f[i-1]|f[i])]?m.length:F(m,k))

Less golfed and not recursive

F=m=>{
  for(k=[];!k[m];) // use k to find a repeated state and exit the loop
  {
    k[m]=1
    console.log(m)
    // loop for swap and mark swap position in array f
    f=m.map((x,i)=>( 
      y=m[i+1], // next element
      w=x-y,    // difference
      x%w==0&y%w==0 // if common divisor ...
        ?m[m[i+1]=x,i]=y // swap elements,mark with nonzero
        :0 // no swap, mark with 0
    ))    
    m=m.filter((x,i)=>f[i-1]|f[i]) // remove elements not swapped
  }
  return m.length
}

Test

F=(m,k=[])=>(k[m]=m,f=m.map((x,i)=>x%(w=x-(y=m[i+1]))==0&y%w==0?m[m[i]=y,i+1]=x:0),k[m=m.filter((x,i)=>f[i-1]|f[i])]?m.length:F(m,k))

console.log=x=>O.textContent+=x+'\n'

;[[1,1],[1,2],[1,2,3],[4,6,8],[99,1,3],[4,5,2,4],[12,4,6,3],[9,6,10,18]
,[ 55, 218, 654, 703, 948, 960 ],[ 954, 973, 925, 913, 924, 996, 927, 981, 905 ]]
.forEach(t=>console.log(t+' -> '+F(t)))
<pre id=O></pre>

\$\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.