9
\$\begingroup\$

Recall from this challenge that a phat-fingered double-bit flip or phatflip is defined as follows:

Given a nonnegative integer in binary representation a phat-fingered double-bit-flip or phatflip for short replaces a pair of adjacent, equal bits with their complement.

For example given the number 0b111010010000101

0b111010010000101 -> 0b100010010000101

0b111010010000101 -> 0b111011110000101

0b111010010000101 -> 0b1010010000101

are phatflips whereas

0b111010010000101 -> 0b111000000000101 (not adjacent)

0b111010010000101 -> 0b111010001000101 (not equal)

0b111010010000101 -> 0b111010010111101 (not a pair)

are not.

Also recall that

A phat-fingered-lights-out number (or "pflon") is a nonnegative integer that can be completely erased by a finite sequence of phatflips.

We now introduce the phat-fingered double-bit flip distance or PhD:

Given two pflons a and b, PhD(a,b) is the minimum number of phatflips required to change a into b.

Your task: Using as few bytes as possible implement the function PhD

Examples:

a,b -> PhD(a,b)
possible sequence
of phatflips (you
needn't implement
this)

15 27 -> 2
01111
00011
11011

33 36 -> 2
100001
100111
100100

39 54 -> 4
100111
100100
111100
110000
110110

57 66 -> 9
0111001
0111111
0111100
0110000
0110110
0000110
0011110
0010010
1110010
1000010

417 831 -> 4
0110100001
0110100111
0110111111
0000111111
1100111111

9504 14454 -> 10
10010100100000
10010100100110
10010111100110
10010110000110
10010110110110
10010000110110
10010011110110
10011111110110
10011001110110
10000001110110
11100001110110
\$\endgroup\$

5 Answers 5

5
\$\begingroup\$

Python3, 56 bytes

p=lambda a,b,c=0:abs(c)+(a^b and p(b//2,a//2,c+a%2-b%2))

Thanks to @loopy walt for an elegant way to remove the mask completely by alternating the arguments (-50) and for golfing the result further (-19)

Now the solution is also quite fast!

Python3, 125 bytes

def p(a,b):
 m=4**(a+b)//3
 def d(a,b,c=0):
  if a==0:return 0
  c+=a%2-b%2
  return abs(c)+d(a//2,b//2,c)
 return d(a^m,b^m)

New here, I feel like this is a fun/weird solution, I'll try to explain. When using phatflips (as I do everyday) I feel more like I am moving some bits than flipping some bits (do you get what I mean ?).

With that in mind, let's define the generalized phatflip: it is the operation of flipping and swapping 2 adjacent digits. Note that if the bits are the same, it is a normal phatflip, and if the bits are different, it doesn't do anything. Trying to minimize the number of generalized phatflip is the same thing as trying to minimize the number of phatflip.

The swapping looks cooler than the flipping to me, so to get rid of the flipping part, let's use an alternate binary representation for numbers: if \$x_ny_n...x_0y_0\$ is a normal binary representation of n, the alternate representation is obtained by flipping all the \$y_i\$ , the even placed bits (e.g. 27 is normally 11011 but would be 01110 and 15 would not be 01111 but 11010). When adding leading digits with this alternate representation, make sure to alternate 0s and 1s.

With this alternate view, a phatflip just swaps adjacent bits! Now calculating the distance for swapping adjacent bits looks much easier! The distance between 27: 01110 and 15: 11010 is 2, and it is easy to know where the phatflips should be!

About the code, the variable m provides a xor-mask (1010...101) for the alternate view, and the function d calculates the distance for swapping adjacent bits. For a faster version, replace m=4**len(bin(a+b))//3 (the mask doesn't need to be that long). It can certainly be golfed further, I don't know that much about code golfing --'

\$\endgroup\$
4
  • \$\begingroup\$ Welcome to code-golf and great first post! You can get rid of the mask (-50 bytes) and then do some routine golfing (-19). \$\endgroup\$
    – loopy walt
    Feb 19 at 18:43
  • \$\begingroup\$ Oh wow getting rid of the mask is really cool, at first I thought you could just use the function d directly and I was very confused! \$\endgroup\$
    – Vincent
    Feb 20 at 8:21
  • \$\begingroup\$ You can. All that's needed are two minor modifications: stopping criterion replace a==0 with a==b (in case b is longer than a) and in the recursive call swap a and b. This keeps track of parity and allows us to dispense with the mask. \$\endgroup\$
    – loopy walt
    Feb 20 at 8:43
  • \$\begingroup\$ Yes, I understood that a bit later bit didn't spot these small modifications at first, so at first I thought you just plainly removed the mask. Thanks for these bigs improvements! \$\endgroup\$
    – Vincent
    Feb 20 at 8:46
5
\$\begingroup\$

Charcoal, 51 bytes

NθNηW⁻θη¿﹪鲫≔³ζW∧&θζ&~θζ≦⊗ζ≔⁻|θζ&θζθ→»«≧÷²θ≧÷²η»Iⅈ

Try it online! Link is to verbose version of code. Explanation: Greedy algorithm which works for the test cases at least.

NθNη

Input a and b.

W⁻θη

Repeat until a equals b.

¿﹪鲫

If exactly one of a and b is odd, then:

≔³ζW∧&θζ&~θζ≦⊗ζ

Find the rightmost possible phatflip for a.

≔⁻|θζ&θζθ

Apply that phatflip to a.

Keep count of the number of phatflips.

»«≧÷²θ≧÷²η

Otherwise, divide both a and b by 2.

»Iⅈ

Output the number of phatflips.

A port of @loopywalt's golf to @Vincent's solution is only 34 bytes:

≔E²NθW↨θ±¹«⊞υ↔ⅈM↨﹪θ²±¹→≔÷⮌θ²θ»I↨υ¹

Try it online! Link is to verbose version of code. Explanation:

≔E²Nθ

Input a and b.

W↨θ±¹«

Repeat until a==b.

⊞υ↔ⅈ

Save the absolute current offset.

M↨﹪θ²±¹→

Adjust the offset according to the difference between the bottom bits of a and b.

≔÷⮌θ²θ

Swap and halve a and b.

»I↨υ¹

Output the total number of phatflips.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 63 bytes

A port of Neil's greedy algorithm.

Expects (a)(b).

a=>g=b=>a+b&1?(h=k=>(b&k)%3?h(k*2):1+g(b^k))(3):b&&g(b>>1,a/=2)

Try it online!

Commented

a =>              // outer function taking a
g = b =>          // inner recursive function taking b
a + b & 1 ?       // if exactly one of a and b is odd:
  ( h = k =>      //   h is a recursive function taking a pattern k
    (b & k) % 3 ? //   if b AND k is neither 0b00(…) nor 0b11(…):
      h(k * 2)    //     try again with k * 2
    :             //   else:
      1 +         //     increment the final result
      g(b ^ k)    //     and do a recursive call with b XOR k
  )(3)            //   initial call to g with k = 0b11
:                 // else:
  b &&            //   stop if b = 0
    g(            //   otherwise do a recursive call with:
      b >> 1,     //     floor(b / 2)
      a /= 2      //     and a / 2
    )             //   end of recursive call
\$\endgroup\$
1
\$\begingroup\$

Python3, 256 bytes

Can certainly be golfed further.

Y=lambda x:[*map(int,bin(x)[:1]+bin(x)[2:])]
def f(a,b):
 A,B=Y(a),Y(b)
 q,s=[(A,0)],[A]
 for i,c in q:
  if i[i[0]==0:]==B[B[0]==0:]:return c
  for j in range(len(i)-1):
   if i[j]==i[j+1]and(K:=i[:j]+[int(not i[j])]*2+i[j+2:])not in s:q+=[(K,c+1)];s+=[K]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Scala 3, 137 bytes

A port of @Vincent's Python answer in Scala.


Golfed version. Attempt This Online!

(a,b)=>{val m=Math.pow(4,a+b).toInt/3;def d(a:Int,b:Int,c:Int=0):Int=if(a==0)0 else{val n=c+a%2-b%2;math.abs(n)+d(a/2,b/2,n)};d(a^m,b^m)}

Ungolfed version. Attempt This Online!

object Main {
  def f(a: Int, b: Int): Int = {
    val m = Math.pow(4, a + b).toInt / 3
    def d(a: Int, b: Int, c: Int = 0): Int = {
      if (a == 0) return 0
      val newC = c + a % 2 - b % 2
      math.abs(newC) + d(a / 2, b / 2, newC)
    }
    d(a ^ m, b ^ m)
  }

  def main(args: Array[String]): Unit = {
    println(f(15, 27) == 2)
    println(f(33, 36) == 2)
    println(f(39, 54) == 4)
    println(f(57, 66) == 9)
    println(f(417, 831) == 4)
    println(f(9504, 14454) == 10)
  }
}
\$\endgroup\$

Your Answer

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

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