21
\$\begingroup\$

BCD difference

Given an integer n, convert it to BCD (binary-coded decimal) by replacing each decimal digit with its 4-digit binary representation

 234 -> 0 0 1 0 0 0 1 1 0 1 0 0

Then rotate the list of binary digits in order to find the largest and smallest numbers, representable by this list without other rearrangements.

max: 1 1 0 1 0 0 0 0 1 0 0 0  (the entire list rotated left 6 times)
min: 0 0 0 0 1 0 0 0 1 1 0 1 (the entire list rotated right 2 times)

Convert these numbers back to decimal, treating the list of bits as regular binary and subtract the smallest from the largest:

1 1 0 1 0 0 0 0 1 0 0 0 -> 3336
0 0 0 0 1 0 0 0 1 1 0 1 -> 141

3336 - 141 -> 3195

The output is the difference of the largest and smallest numbers found.

Test cases:

234 -> 3195
1234 -> 52155
12 -> 135
975831 -> 14996295
4390742 -> 235954919
9752348061 -> 1002931578825
\$\endgroup\$
0

23 Answers 23

7
\$\begingroup\$

Wolfram Language (Mathematica), 89 88 bytes

Thanks to Jenny_mathy for saving 1 byte.

i=IntegerDigits;Max@#-Min@#&[#~FromDigits~2&/@NestList[RotateRight,Join@@i[i@#,2,4],#]]&

Try it online!

This is terribly inefficient, because it generates n rotations of the BCD of n, which is way more than we need. We can make this is a bit more efficient by saving the result of the Join@@ in k and replacing the # at the end with Length@k. That lets us generate a scatterplot quite easily:

enter image description here

I'm really intrigued by the contrast of local structure and overall chaos.

\$\endgroup\$
6
  • \$\begingroup\$ Max@#-Min@#& saves a byte. right? \$\endgroup\$
    – ZaMoC
    Nov 16, 2017 at 12:32
  • \$\begingroup\$ @Jenny_mathy Yeah, thanks! :) \$\endgroup\$ Nov 16, 2017 at 12:33
  • 1
    \$\begingroup\$ I made this from our solutions Max@#-Min@#&[#~FromDigits~2&/@Partition[s=Join@@(i=IntegerDigits)[i@#,2,4],Tr[1^s],1,1]]& 89 bytes AND efficient. damn that byte! \$\endgroup\$
    – ZaMoC
    Nov 16, 2017 at 13:00
  • \$\begingroup\$ Actually the plot is a repeated patern.Those "chaotic clouds" happen every 10^n (the plot "jumps" and create a new one): 1-9,10-99,100-999... here are some different zooms: imgur.com/RXLMkco \$\endgroup\$
    – ZaMoC
    Nov 16, 2017 at 17:27
  • \$\begingroup\$ @Jenny_mathy sure, but the structure within these intervals appears very chaotic (with structures only at much smaller scales). \$\endgroup\$ Nov 16, 2017 at 17:33
6
\$\begingroup\$

Jelly, 13 bytes

Dd4d2FṙJ$ḄṢIS

Try it online!

How it works

Dd4d2FṙJ$ḄṢIS  Main link. Argument: n

D              Decimal; convert n to base 10 (digit array).
 d4            Divmod 4; map each digit d to [d/4, d%4].
   d2          Divmod 2; map each [d/4, d%4] to [[d/8, d/4%2], [d%4/2, d%2]].
     F         Flatten the resulting 3D binary array.
      ṙJ$      Take all possible rotations.
         Ḅ     Convert each rotation from binary to integer.
          Ṣ    Sort the resulting integer array.
           I   Take the forward differences.
            S  Take the sum.
\$\endgroup\$
4
\$\begingroup\$

Python 3, 115 108 bytes

thanks to Jonathan Frech for -7 bytes

k=''.join(f'{int(i):04b}'for i in input())
v=[int(k[i:]+k[:i],2)for i in range(len(k))]
print(max(v)-min(v))

Try it online!

\$\endgroup\$
0
4
\$\begingroup\$

PowerShell, 153 bytes

$b=[char[]]-join([char[]]"$args"|%{[convert]::toString(+"$_",2).PadLeft(4,'0')})
($c=$b|%{$x,$y=$b;[convert]::ToInt64(-join($b=$y+$x),2)}|sort)[-1]-$c[0]

Try it online!

Stupid lengthy .NET calls to convert to/from binary really bloats the length here. ;-)

We take input as $args, wrap it in a string, then cast it as a char-array. We loop over each digit, converting the digit toString in base 2 (i.e., turning the digit into a binary number), then .padLeft to make it a four-digit binary number. That resulting array of strings is then -joined into a single string and re-cast as a char-array before being saved into $b.

Next, we loop over $b, which just makes sure we loop enough times to account for every rotation. Each iteration, we peel off the first character into $x and the remaining characters into $y using multiple assignment. Then, we merge them back together into $b=$y+$x to move the first element to the end, i.e., effectively rotating the array by one. That's -joined into a string, which is used as the input to the convert call to turn the string from binary base 2 into an Int64. We then sort all of those resultant numbers and store them into $c. Finally, we take the biggest [-1] and subtract the smallest [0]. That's left on the pipeline and output is implicit.

\$\endgroup\$
4
\$\begingroup\$

Ohm v2, 15 bytes

€b4Ü. 0\;Jγó↕]a

Try it online!

Explanation:

€b4Ü. 0\;Jγó↕]a  Main wire, arguments: a (integer)

€       ;        Map the following over each digit of a...
 b                 Convert to binary
  4Ü               Right-justify w/ spaces to length 4
    . 0\           Replace all spaces with zeroes
         J       Join together binary digits
          γó     Get all possible rotations and convert back to decimal
            ↕    Find the minimum *and* maximum rotation
             ]a  Flatten onto stack and get the absolute difference
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 118 100 99 bytes

f=
n=>(g=m=>Math[m](...[...s=(`0x1`+n-0).toString(2)].map(_=>`0b${s=0+s.slice(2)+s[1]}`)))`max`-g`min`
<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>

Edit: Saved 11 bytes thanks to @RickHitchcock. Saved 1 byte thanks to @ETHproductions. Explanation: The 0x1 prefix causes the input to get reparsed as a hexadecimal number, whose binary is the same as the BCD of the original number with a 1 prefix (I think this is golfier than any other way of padding to a multiple of 4 digits). Excluding the prefix, which is changed from 1 to 0, the resulting string is then rotated at each possible position and converted from binary back to decimal. Finally the maximum and minimum are subtracted.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ @RickHitchcock Wrap the string in double backticks... unless you want to write something like .join`` in which case you need triple backticks etc. \$\endgroup\$
    – Neil
    Nov 15, 2017 at 22:40
  • \$\begingroup\$ Good idea to use hexadecimal. Save 11 bytes like this: n=>(g=m=>Math[m](...[...s=(+`0x1${n}`).toString(2).slice(1)]‌​.map(_=>`0b${s=s.sli‌​ce(1)+s[0]}`)))`max`‌​-g`min` \$\endgroup\$ Nov 15, 2017 at 22:44
  • 1
    \$\begingroup\$ @RickHitchcock Thanks, that helped me... slice... off another 7 bytes by removing another slice too! \$\endgroup\$
    – Neil
    Nov 15, 2017 at 22:48
  • 1
    \$\begingroup\$ The m=>Math[m] trick is great. Perhaps change (+`0x1${n}`) to ('0x1'+n-0) or similar? \$\endgroup\$ Nov 16, 2017 at 3:47
3
\$\begingroup\$

Python 2, 115 113 bytes

  • Saved some bytes thanks to ovs.
  • Saved two bytes thanks to Mr. Xcoder.
b="".join(format(int(n),"04b")for n in`input()`)
b=[int(b[s:]+b[:s],2)for s in range(len(b))]
print max(b)-min(b)

Try it online!

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

Pyth, 29 bytes

Ksm.[\04.Bsd`Q-eJSmi.<Kd2lKhJ

Try it here! or Check out the test suite.

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

Husk, 18 bytes

§-▼▲mḋUMṙNṁȯtḋ+16d

Try it online!

There should be a shorter way to convert a digit into its 4-bit binary representation...

Explanation

§-▼▲mḋUMṙNṁȯtḋ+16d
                 d    Get the list of digits of the input
          ṁȯ          For each digit...
              +16      add 16
             ḋ         convert to binary
            t          drop the first digit
       MṙN            Rotate the list by all possible (infinite) numbers
      U               Get all rotations before the first duplicated one
    mḋ                Convert each rotation from binary to int
§-▼▲                  Subtract the minimum from the maximum value
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog), 31 bytes

Full program body. Prompts for number from STDIN. Prints result to STDOUT.

(⌈/-⌊/)2⊥¨(⍳≢b)⌽¨⊂b←,⍉(4/2)⊤⍎¨⍞

Try it online!

 prompt for line of text from STDIN

⍎¨ execute (evaluate) each (character)

()⊤ encode (anti-base) in the following number system:

4/2 four binary bits

 transpose

, ravel (flatten)

b← store in b (for binary)

 enclose (so that we will use this entire list for each rotation)

()⌽¨ rotate (left) by each of the following amounts:

≢b length of b

indices of that

2⊥¨ decode each from base-2.

() apply the following tacit function to that

⌈/ the max(-reduction)

- minus

⌊/ the min(-reduction)

\$\endgroup\$
2
  • \$\begingroup\$ you could easily trainify this bit: (⍳≢b)⌽¨⊂b← \$\endgroup\$
    – ngn
    Nov 18, 2017 at 18:59
  • \$\begingroup\$ or even better - use (≢,/,⍨) instead of the obvious (⍳∘≢⌽¨⊂) \$\endgroup\$
    – ngn
    Nov 18, 2017 at 19:10
3
\$\begingroup\$

APL (Dyalog), 37 34 bytes

{(⌈/-⌊/)2⊥¨(⍳⍵)∘.⌽⊂,↑(4⍴2)∘⊤¨⍎¨⍕⍵}

Try it online!

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

Jelly, 21 bytes

DB0;$4¡€ṫ€-3FṙJ$ḄµṀ_Ṃ

Try it online!

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

Ruby, 96 91 bytes

->n{r=""
n.digits.map{|d|r="%04b"%d+r}
s=r.chars.map{(r=r[1..-1]+r[0]).to_i 2}
s.max-s.min}

Try it online!

  • Saved 5 bytes thanks to displayname
\$\endgroup\$
2
  • \$\begingroup\$ ->n{r="" n.digits.map{|d|r="%04b"%d+r} s=r.chars.map{(r=r[1..-1]+r[0]).to_i 2} s.max-s.min} should be 91 bytes \$\endgroup\$ Nov 15, 2017 at 22:50
  • \$\begingroup\$ @displayname Ha, yeah, you're right. Thank you \$\endgroup\$ Nov 15, 2017 at 22:55
2
\$\begingroup\$

Mathematica, 110 99 bytes

Max@#-Min@#&[#~FromDigits~2&/@Partition[s=Join@@Tuples[{0,1},4][[IntegerDigits@#+1]],Tr[1^s],1,1]]&


Try it online!

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

Python 3, 141 bytes

def f(a):a=''.join([format(int(i),'#010b')[-4:]for i in str(a)]);b=[int(''.join(a[-i:]+a[:-i]),2)for i in range(len(a))];return max(b)-min(b)

Try it online

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

Retina, 96 89 bytes

.
@@@$&
@(?=@@[89]|@[4-7]|[2367])
_
T`E`@
\d
_
.
$&$'$`¶
O`
_
@_
+`_@
@__
s`(_+).*\W\1

_

Try it online! Somewhat slow, so link only includes a small test case. Edit: Saved 7 bytes thanks to @MartinEnder. Explanation:

.
@@@$&

Prefix three @s to each digit. (These represent the 0s of the BCD, but are golfier.)

@(?=@@[89]|@[4-7]|[2367])
_

Change the @s to _s (representing the 1s of the BCD) where appropriate.

T`E`@
\d
_

Fix up the last digit of the BCD.

.
$&$'$`¶

Generate all of the rotations.

O`

Sort them into ascending order.

_
@_
+`_@
@__

Convert them to unary.

s`(_+).*\W\1

_

Subtract the first from the last number, ignoring intermediate numbers, and convert to decimal.

\$\endgroup\$
2
  • \$\begingroup\$ There's no need to use % for the binary to unary conversion and you can save a few more bytes by using other characters than 0 and 1 for binary: tio.run/##K0otycxL/… \$\endgroup\$ Nov 16, 2017 at 21:41
  • \$\begingroup\$ @MartinEnder Oh, I think that dated from when I was trying and failing to use one of your binary conversion routines... \$\endgroup\$
    – Neil
    Nov 16, 2017 at 22:11
2
\$\begingroup\$

Haskell, 130 bytes

r=foldl1
f x=max#x-min#x
f#x|s<-show x=r((+).(2*)).r f.take(sum$4<$s).iterate(drop<>take$1)$do d<-s;mapM(pure[0,1])[1..4]!!read[d]

Try it online!

Explanation / Ungolfed

Since we're going to use foldl1((+).(2*)) to convert from binary to decimal, we might as well not use maximum and minimum but rather foldl1 max (or same with min respectively) and use a short r = foldr1.

Now, let us define an operator f#x which converts x to BCD, generates all rotations, reduce these using f and convert it to decimal:

f # xs
  | s <- show xs
  = foldr1 ((+).(2*))                             -- convert from binary to decimal
  . foldr1 f                                      -- reduce by either max or min
  . take (4 * length s)                           -- only keep 4*length s (ie. all "distinct" rotations)
  . iterate (drop<>take $ 1)                      -- generate infinite list of rotations
  $ do d<-s; mapM (pure[0,1]) [1..4] !! read [d]  -- convert to BCD

Now it's only a matter of using this operator once with max and once with min and subtracting their results:

f x = max#x - min#x
\$\endgroup\$
2
\$\begingroup\$

PHP, 156 153 bytes

<?foreach(str_split($argv[1])as$n)$s.=str_pad(decbin($n),4,0,0);for(;$i<$a=strlen($s);)$r[]=bindec(substr($s,$i).substr($s,0,$i++));echo max($r)-min($r);

Try it online!

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

Japt -x, 20 bytes

®¤ùT4쬣ZéY ì2Ãn äa

Try it online!

Input as an array of digits.

Explanation:

®¤                      #Map each digit to base 2
  ùT4Ã                  #Pad each one to 4 places
      ¬                 #Join them to a single binary string
       ¬                #Split them to an array of single characters
        £      Ã        #For each index Y in that array:
         ZéY            # Get the array rotated Y times
             ì2         # Convert the array from binary to decimal
                n       #Sort the results
                  äa    #Get the absolute difference between each element
                        #Implicitly output the sum
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can use the -x flag to save 2 bytes. \$\endgroup\$
    – Oliver
    Dec 14, 2018 at 0:23
  • 1
    \$\begingroup\$ 20 bytes. \$\endgroup\$
    – Oliver
    Dec 17, 2018 at 20:27
1
\$\begingroup\$

Pyth, 24/26 bytes

s.+Smi.>Gd2l=Gsm.[\04.Bs

Takes input as a quoted string. 26 bytes if it needs to take input as an integer; append dz in that case.

Test Cases (input as strings, 24 bytes)

Test Cases (input as numbers, 26 bytes)

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

J, 43 bytes

3 :'(>./-<./)#.(i.@#|."0 1]),}.#:8,"."0":y'

Try it online!

Sometimes tacit style makes things difficult. But there's probably a way to do it tacit style that's a lot more concise than this. I think I remember a better way to split a number to digits other than "."0@": but I can't seem to recall it...

Explanation

3 :'(>./-<./)#.(i.@#|."0 1]),}.#:8,"."0":y'
                                         y  the input (integer)
                                       ":   convert to string
                                   "."0     evaluate each char (split to digits)
                                 8,         prepend 8
                               #:           debase 2
                             }.             behead (remove the 8)
                            ,               ravel (flatten)
               (i.@#|."0 1])                create a list of rotations
                    |.    ]                   rotate the list
                      "0 1                    for each number on the left
                i.@#                          range 0 ... length - 1
             #.                             convert rotations back to base 10
    (>./-<./)                               max minus min

The prepending and removing 8 is to ensure that the right number of zeroes are present (J will reshape its arrays to be the size of their maximum length element, and 8 is 4 digits in binary so it is used).

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

APL(NARS), 34 chars, 68 bytes

{(⌈/-⌊/)2⊥¨{⍵⌽a}¨⍳≢a←∊⍉(4⍴2)⊤⍎¨⍕⍵}

some little test:

  h←{(⌈/-⌊/)2⊥¨{⍵⌽a}¨⍳≢a←∊⍉(4⍴2)⊤⍎¨⍕⍵}
  h 9752348061
1002931578825
  h 0
0
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 97 91 89 + 2 (-F) = 99 93 91 bytes

$a=sprintf"%04b"x@F,@F;@r=sort{$b<=>$a}map{oct"0b".($a=(chop$a).$a)}(@F)x4;say$r[0]-pop@r

Try it online!

\$\endgroup\$

Your Answer

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

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