33
\$\begingroup\$

Introduction

In this challenge you should split an integer into two pieces. Since nobody likes getting the smaller piece of cake, your goal is to be as fair as possible. For example if you wanted to split the integer 7129 into two pieces, there are 3 possible ways of doing so.

7,129, 71,29 and 712,9 are all possibilities, but 71,29 is the fairest way of splitting it into two pieces because it minimizes the difference between the two:

7 129 -> |7-129| = 122
71 29 -> |71-29| = 42
712 9 -> |712-9| = 703

Challenge

Given an integer determine the best possible way of partitioning it as described above and report the resulting difference.

Rules

  • Splitting only makes sense for integers of length at least two, the input will always be ≥ 10
  • Input can be either an integer, list of digits or a string
  • You don't have to handle invalid input

Testcases

You only need to report the resulting difference, the partitioning is only here for illustration:

10 -> 1,0 -> 1
11 -> 1,1 -> 0
12 -> 1,2 -> 1
13 -> 1,3 -> 2
101 -> 1,01 -> 0
128 -> 12,8 -> 4
313 -> 3,13 -> 10
1003 -> 1,003 -> 2
7129 -> 71,29 -> 42
81128 -> 81,128 -> 47
999999 -> 999,999 -> 0
9999999 -> 999,9999 or 9999,999 -> 9000
\$\endgroup\$

33 Answers 33

11
\$\begingroup\$

Brachylog, 12 11 bytes

My first Brachylog answer

Take input as a string

{~cĊịᵐ-ȧ}ᶠ⌋

Try it online!

Explanation:

will find all possible outputs for the predicate in {…} and store them in a list. ~c says that the output is a list that, when concatenated, is equal to the input. Next Ċ asserts that the the output of ~c has length 2.

ịᵐ converts both elements of the output into integers (this gets rid of leading 0s), takes the absolute difference of the two elements.

Once we have our list of all possible outputs, we get the minimum element with

\$\endgroup\$
10
\$\begingroup\$

Haskell, 48 bytes

f n=minimum[abs$n`div`10^k-n`mod`10^k|k<-[1..n]]

[1..n] makes this too slow for the larger test cases.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Nice job! I got so blind sided by using strings that I forgot that I could use arithmetic. \$\endgroup\$ – Sriotchilism O'Zaic Dec 18 '17 at 5:20
9
\$\begingroup\$

05AB1E, 9 bytes

Code:

ā¤âε£ÆÄ}W

Uses the 05AB1E encoding. Try it online!

Explanation

ā            # Get the array [1, 2, .., len(input)]
 ¤â          # Cartesian product with the last element, (e.g. for input 12345:
               [[1, 5], [2, 5], [3, 5], [4, 5], [5, 5]])
   ε   }     # For each element:
    £        #   Get the substrings (12345 [3, 5] £ --> [123, 45])
     Æ       #   Reduce by subtraction
      Ä      #   Get the absolute value
        W    # Take the minimum of all results
\$\endgroup\$
  • 1
    \$\begingroup\$ If you replace £ with °‰ you won't need ¤â anymore. \$\endgroup\$ – Emigna Dec 18 '17 at 12:22
8
\$\begingroup\$

Python 2, 64 bytes

lambda n:min(abs(int(n[i:])-int(n[:i]))for i in range(1,len(n)))

Try it online!

\$\endgroup\$
7
\$\begingroup\$

Perl 6, 40 bytes

{min map {abs [-] @$_},m:ex/^(.+)(.+)$/}

Test it

Expanded:

{  # bare block lambda with implicit parameter 「$_」

  min
    map
      {
        abs
          [-]    # reduce with &infix:«-»
            @$_  # the input of this inner block as a Positional
      },

      # split 「$_」 into 2 in every possible way
      m
      :exhaustive
      /^ (.+) (.+) $/
}
\$\endgroup\$
6
\$\begingroup\$

C, 94 bytes

c,r,d,a;f(n){for(c=1,r=0,d=n<11?1:n;n;r+=n%10*c,c*=10,n/=10)a=abs(r-n),d=r&&a<d?a:d;return d;}

Try it online!

\$\endgroup\$
6
\$\begingroup\$

Python 2, 51 bytes

f=lambda n,k=1:min(abs(n/k-n%k),k/n*n or f(n,10*k))

Try it online!

\$\endgroup\$
6
\$\begingroup\$

Prolog (SWI), 195 189 154 117 112 bytes

35 bytes saved thanks to Eminga

A*H:-findall(X,(between(0,A,I),r(A,I,X)),L),sort(L,[H|_]),!.
r(A,B,C):-Z is 10**B,divmod(A,Z,X,Y),C is abs(X-Y).

Try it online!

This is my first try at prolog golfing so it may be a bit horrendous. Here is how it works.

At the highest level we have *. * takes A and H, and determines if H is the smallest way to split A.

    A*H:-
      findall(X,(between(0,A,I),call(r,A,I,X)),L),
      sort(L,[H|_]),
      !.

The first line here uses a technique from this SO post, to essentially perform a map of the predicate r(A) over the integers from 0 to A. Since r confirms the values of each partitions this will give us the values of all possible partitions, plus a whole load of extra junk. All these partitions will be stored in L in no particular order. Once that is done we sort the list to find the smallest element. We then use a cut to prevent backtracing.

Next we have the definition of r. First r calculates the two results of the split naming them X and Y.

r(A,B,C):-
  Z is 10**B,
  divmod(A,Z,X,Y),
  C is abs(X-Y).

Then we assert that C is the difference of them and is positive.

  C is abs(X-Y).
\$\endgroup\$
  • \$\begingroup\$ There seem to be a misstake here as X is div(A,10**B),Y is div(A,10**B) will always give C=0 (meaning H will always be 0 as well). Should be Y is mod(A,10**B) I presume. \$\endgroup\$ – Emigna Dec 18 '17 at 11:50
  • \$\begingroup\$ The second row could also be r(A,B,C):-Z is 10**B,divmod(A,Z,X,Y),C is abs(X-Y). saving 32 bytes (If you're using SWI prolog at least, not sure about other versions). \$\endgroup\$ – Emigna Dec 18 '17 at 11:56
  • \$\begingroup\$ The first row could start with for example A*H instead of l(A,H) saving another 3. And if you are using SWI, you could add a TIO link \$\endgroup\$ – Emigna Dec 18 '17 at 12:07
  • \$\begingroup\$ Also, I don't think you need the ,! do you? There shouldn't be any backtracking at that point. \$\endgroup\$ – Emigna Dec 18 '17 at 12:45
  • \$\begingroup\$ @Emigna Thanks for the tips, I'll be implementing them shortly. I also thought ,! would not be necessary but when I test the program it does backtrace. It seems to try every possible ordering of L and then sorts them all. Meaning it will give the same answer A! times. \$\endgroup\$ – Sriotchilism O'Zaic Dec 18 '17 at 19:20
5
\$\begingroup\$

Haskell, 68 65 bytes

f x=minimum[abs$read(take i x)-read(drop i x)|i<-[1..length x-1]]

Try it online!

Explanation

minimum              -- Minimum of ...
 [abs$               -- The absolute value of ...
  read(take i x)     -- The first i characters of x
  -                  -- Minus ...
   read(drop i x)    -- The last i characters of x
 |i<-[1..length x-1] -- From i=1 to i=length x - 1
 ]
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 14 bytes

I⌊Eθ↔⁻I…θκI✂θκ

Try it online! Link is to verbose version of code. Conveniently I get to use the 2-arg variant of Slice. Explanation:

   θ            Input string
  E             Map over characters
        θ   θ   Input string
         κ   κ  Current map index
       …        Mold to length (i.e. head)
           ✂    Slice (i.e. tail)
      I   I     Cast to integer
     ⁻          Subtract
    ↔           Absolute value
 ⌊              Minimum
I               Cast to string
                Implicitly print
\$\endgroup\$
4
\$\begingroup\$

Jelly, 9 8 bytes

ḌÐƤḊạḌƤṂ

Try it online!

-1 byte thanks to Dennis. Input is a list of digits.

Explanation

ḌÐƤḊạḌƤṂ
ḌÐƤ          Convert to integer from decimal for all Ƥostfixes. [1,2,3]->[123,23,3]
   Ḋ         Remove the first element ->[23,3]
     ḌƤ      Convert to integer from decimal for all Ƥrefixes [1,2,3]->[1,12,123]
    ạ        Absolute difference. [23,3]ạ[1,12,123]->[22,9,123]
       Ṃ     Minimum
\$\endgroup\$
  • \$\begingroup\$ Hm, your explanation doesn't seem to reflect what your code actually does. \$\endgroup\$ – Erik the Outgolfer Dec 23 '17 at 16:39
  • \$\begingroup\$ @EriktheOutgolfer Is it the “remove the last element” part when it should say “remove the first element”? I’ll fix that, thanks for pointing it out \$\endgroup\$ – dylnan Dec 23 '17 at 16:48
3
\$\begingroup\$

Funky, 159 134 99 bytes

s=>{S={}fori=1i<#s i++{S[#S]=(((v=s::sublist)(0,i)::reduce@..-v(i)::reduce@..)^2)^.5};math.min...S}

Actually fitting the spec is shorter it seems.

Try it online!

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

Retina, 36 bytes

\B
,$'¶$`
\d+
$*
(1*),\1

Om`^.*
\G1

Try it online!

Explanation

\B
,$'¶$`

This generates all possible partitions on separate lines, as well as a trailing line with the original input.

\d+
$*

Convert each number in each partition to unary.

(1*),\1

Remove a maximal and equal amount of 1s from both parts of each partition (i.e. remove the minimum, and subtract it from the maximum, which gives the absolute difference).

Om`^.*

Sort the lines.

\G1

Count the 1s on the first line, which gives the minimal absolute difference.

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

J, 32, 27 23 bytes

-5 bytes thanks to FrownyFrog! -4 bytes if input is a string.

[:<./}:@(".\)|@-1}.".\.

Try it online!

Original: Takes a number as input

(".\(}:@[([:<./|@-)}.@])".\.)@":

How it works:

                             @": - convert the number to list of chars and
(".\                    ".\.)    - form all prefixes/suffixes and convert them to numbers
    (}:@[          }.@])         - drop the last prefix / first suffix
         (     |@-)              - find the absolute differences
          [:<./                  - find the minimum

Try it online!

\$\endgroup\$
  • \$\begingroup\$ @FrownyFrog - Thanks! \$\endgroup\$ – Galen Ivanov Dec 18 '17 at 9:49
3
\$\begingroup\$

JavaScript (ES6), 64 bytes

Takes input as a string.

f=([c,...s],l=0)=>c?Math.min(Math.abs((l+=c)-s.join``),f(s,l)):l

Test cases

f=([c,...s],l=0)=>c?Math.min(Math.abs((l+=c)-s.join``),f(s,l)):l

console.log(f("10"     )) // -> 1
console.log(f("11"     )) // -> 0
console.log(f("12"     )) // -> 1
console.log(f("13"     )) // -> 2
console.log(f("101"    )) // -> 0
console.log(f("128"    )) // -> 4
console.log(f("313"    )) // -> 10
console.log(f("1003"   )) // -> 2
console.log(f("7129"   )) // -> 42
console.log(f("81128"  )) // -> 47
console.log(f("999999" )) // -> 0
console.log(f("9999999")) // -> 9000

Commented

f = ([c, ...s],           // c = current character, s = array of remaining characters
                l = 0) => // l = left part of the integer, initialized to 0 (see footnote)
  c ?                     // if c is defined:
    Math.min(             //   return the minimum of:
      Math.abs(           //     1) the absolute value of:
        (l += c) -        //       the updated left part
        s.join``          //       minus the right part
      ),                  //     end of Math.abs()
      f(s, l)             //     2) the result of a recursive call
    )                     //   end of Math.min()
  :                       // else:
    l                     //   stop the recursion by returning l (now equal to the input)

Non-recursive (ES7), 65 bytes

Takes input as a string.

s=>Math.min(...[...s].map(c=>((l+=c)-s.slice(++i))**2,i=l=0))**.5

Test cases

let f =

s=>Math.min(...[...s].map(c=>((l+=c)-s.slice(++i))**2,i=l=0))**.5

console.log(f("10"     )) // -> 1
console.log(f("11"     )) // -> 0
console.log(f("12"     )) // -> 1
console.log(f("13"     )) // -> 2
console.log(f("101"    )) // -> 0
console.log(f("128"    )) // -> 4
console.log(f("313"    )) // -> 10
console.log(f("1003"   )) // -> 2
console.log(f("7129"   )) // -> 42
console.log(f("81128"  )) // -> 47
console.log(f("999999" )) // -> 0
console.log(f("9999999")) // -> 9000

Commented

s =>                            // given s
  Math.min(...                  // get the minimum value in the result of this map():
    [...s].map(c =>             //   for each character c in s:
      ((l += c)                 //     append c to l (the left part)
                - s.slice(++i)) //     and subtract the right part from it
      ** 2,                     //     square the result
      i =                       //     start with i = 0 (split position)
      l = 0                     //     and l = 0 (left part, see footnote)
    )                           //   end of map()
  )                             // end of Math.min()
  ** .5                         // return the square root of the smallest square

Note: In both versions, l is coerced to a string on the first iteration. Normally, we should be careful about leading zeros in a numeric literal: 0123 - 10 === 73 because 0123 is parsed as an octal value (this is now deprecated, but still valid in non-strict mode). But '0123' - '10' === 113, the leading zero being this time ignored. So, it's sound to do so.

From the specification of the abstract operation ToNumber applied to a string:

A StringNumericLiteral that is decimal may have any number of leading 0 digits

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

APL (Dyalog), 27 bytes

{⌊/|-/⍎¨↑⊂∘⍵¨↓1,∘.=⍨⍳¯1+≢⍵}

Try it online!

How?

¯1+≢⍵ - length of n minus 1

∘.=⍨⍳ - identity matrix

      1,∘.=⍨⍳3
1 1 0 0
1 0 1 0
1 0 0 1

1, - prepend 1 for each row

- split by rows

⊂∘⍵¨ - for each, partition the string by it

      1 0 1 0 ⊂ '7129'
┌──┬──┐
│71│29│
└──┴──┘

- flatten

-/ - reduce each pair with subtraction

| - take absolute values

⌊/ - minimum


APL (Dyalog), 35 bytes

{⌊/|-/⍎¨(⊂∘⍵⍤1)1,∘.=⍨⍳¯1+≢⍵}

Try it online!

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

Jelly, 11 bytes

ŒṖṖLÐṂḌạ/€Ṃ

Try it online!

-3 bytes thanks to dylnan

How it works

ŒṖṖLÐṂḌạ/€Ṃ - Main link. Argument: n (integer)    e.g    7129
ŒṖ          - Partitions of n's digits;                  [[7, 1, 2, 9], [7, 1, [2, 9]], [7, [1, 2], 9], [7, [1, 2, 9]], [[7, 1], 2, 9], [[7, 1], [2, 9]], [[7, 1, 2], 9], [7, 1, 2, 9]]
  Ṗ         - Remove the final element                   [[7, 1, 2, 9], [7, 1, [2, 9]], [7, [1, 2], 9], [7, [1, 2, 9]], [[7, 1], 2, 9], [[7, 1], [2, 9]], [[7, 1, 2], 9]]
    ÐṂ      - Keep the lists with the minimum...         [[7, [1, 2, 9]], [[7, 1], [2, 9]], [[7, 1, 2], 9]]
   L        -   length
      Ḍ     - From digits                                [[7, 129], [71, 29], [712, 9]]
        /   - Reduce...
         €  - ...each...
       ạ    - ...by absolute difference                  [122, 42, 703]
          Ṃ - Take the minimum                           42
\$\endgroup\$
  • \$\begingroup\$ You can change L=2$$Ðf to ṖLÐṂ in this case \$\endgroup\$ – dylnan Dec 18 '17 at 2:43
2
\$\begingroup\$

Python 2, 58 bytes

lambda n:min(abs(n%10**i-n/10**i)for i in range(len(`n`)))

Try it online!

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

Pyth, 15 bytes

hSmaFvMdfqlT2./

Try it online!

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

MATL, 15 bytes

"GX@:&)UwU-|vX<

Input is a string representing the integer.

Try it online! Or verify all test cases.

Explanation

"         % Implicit input. Do the following as many times as input length
  G       %   Push input
  X@      %   Push iteration index (1-based), k
  :       %   Range: gives [1 2 ... k]
  &)      %   Two-ouput reference indexing: gives a substring with the first
          %   k characters in the input and then a substring with the rest
  U       %   Convert to number
  wU      %   Swap, convert to number
  -|      %   Absolute difference
  v       %   Vertically concatenate stack. This concatenates the obtained
          %   absolute difference with the minimum so far; does nothing in 
          %   the first iteration
  X<      %   Minimum of array
          % Implicit end. Implicit display
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 66 bytes

Min@Abs[#-#2&@@FromDigits/@#&/@ReplaceList[#,{a__,b__}:>{a}|{b}]]&

Takes a list of digits.

Try it online!

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

Clean, 106 83 bytes

import StdEnv
@n#f=toInt o(%)n
=hd(sort[abs(f(0,i)-f(i+1,size n))\\i<-[0..size n]])

Defines the function @, taking a string.

Mostly self-evident, the only tricky bit is f=toInt o(%)n: This takes the toInt class of functions, and composes it (o) with the curried slice operator class (%) already supplied with the first argument (n). Since there is only one type (String, equivalent to {#Char}) which has overloads for both % and toInt the line actually compiles, whereas normally it's hard to compose functions when golfing due to the lack of contextual information given to the compiler.

Try it online!

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

Jelly, 12 bytes

JṬ€œṗ€⁸Ḍạ/€Ṃ

A monadic link taking a list of digits and returning the integer.

Try it online!

How?

JṬ€œṗ€⁸Ḍạ/€Ṃ - Link: list of digits     e.g. [7,1,2,9]
J            - range of length               [1,2,3,4]
 Ṭ€          - untruth €ach                  [[1],[0,1],[0,0,1],[0,0,0,1]]
      ⁸      - chain's left argument         [7,1,2,9]
   œṗ€       - partition at truthy for €ach  [[[],[7,1,2,9]],[7,[1,2,9]],[[7,1],[2,9]],[[7,1,2],9]]
       Ḍ     - undecimal (vectorises)        [[0,7129],[7,129],[71,29],[712,9]]
         /€  - reduce €ach by:
        ạ    - absolute difference           [7129,122,42,703]
           Ṃ - minimum                       42
\$\endgroup\$
1
\$\begingroup\$

Pyth, 10 bytes

hSaMv<./Ql

Test suite

Takes input as a string.

This uses one of Pyth's more recent features, which is that applying a function to a list defaults to mapping the function over the list, if no other behavior is defined. This means that v applied to a list of list of strings evaluates all of the strings.

hSaMv<./Ql
hSaMv<./QlQ    Implicit variable
      ./Q      Form all partitions of the input string.
               Split it in all possible ways, maintaining the order.
               Partitions are ordered from shortest to longest.
     <   lQ    Take the prefix as long as the input string.
               This keeps just the splits into one and two pieces.
    v          Evaluate. All strings are converted to numbers.
  aM           Map the absolute difference function.
hS             Minimum

Note that the list of splits allows the split into 1 piece, but the value of this will always be larger than the minimum, so it is safely ignored.

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

Tcl, 116 bytes

foreach d [split [set b [set R $argv]] {}] {append L $d
regexp .(.+) $R - R
set b [expr min($b,abs($L-$R))]}
puts $b

Try it online!

Explanation

b ← R ← input number
for each digit (d) in the input number:
  L += d
  strip first digit off of R using a regular expression
  b ← min( b, distance between L and R )
print b

It works by using a regex trick allowing a degenerate final case that will always compute to greater than the minimum difference. For “12345” the values are:

1 2345 → 2344
12 345 → 333
123 45 → 78
1234 5 → 1229
12345 5 → 12340 (degenerate case)
\$\endgroup\$
1
\$\begingroup\$

Ruby, 44 bytes

->a{((w=1)..a).map{((a%w*=10)-a/w).abs}.min}

Try it online!

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

Java 8, 88 82 bytes

n->{int r=-1,t,p=1;for(;n>=p;p*=10)if(r<0|(t=Math.abs(n/p-n%p))<r)r‌​=t;return r;}

Try it online.

\$\endgroup\$
  • 1
    \$\begingroup\$ n->{int r=-1,d,p=1;for(;n>=p;p*=10){d=Math.abs(n/p-n%p);if(r<0|d<r)r=d;}return r;} 82 bytes \$\endgroup\$ – Nahuel Fouilleul Dec 18 '17 at 10:21
  • \$\begingroup\$ @NahuelFouilleul Thanks! Should have known it would be possible to combine both methods.. \$\endgroup\$ – Kevin Cruijssen Dec 18 '17 at 12:09
1
\$\begingroup\$

APL+WIN, 31 bytes

⌊/|(⍎¨m↓¨⊂n)-⍎¨(m←⍳¯1+⍴n)↑¨⊂n←⎕

Prompts for screen input of integer as a string.

Explanation:

m←⍳¯1+⍴n Create a list of numbers from 1 to length of string - 1

↑¨⊂n←⎕ Using m create a nested vector taking successively characters from the front of the string defined by m

⍎¨ Convert from character to integer

(⍎¨m↓¨⊂n) Using m create a nested vector dropping successively characters from the front of the string defined by m 

⌊/| take the minimum absolute value after subtracting the two vectors of integers
\$\endgroup\$
  • \$\begingroup\$ I don't know APL, is there a way to test this? \$\endgroup\$ – ბიმო Dec 18 '17 at 17:07
  • \$\begingroup\$ Unfortunately APL+WIN is not in TIO. If you want to play with APL you can download a copy of APLX from the Dyalog website for free and my code works with it. It does not work in Dyalog's Try APL on-line. dyalog.com/aplx.htm \$\endgroup\$ – Graham Dec 18 '17 at 17:42
1
\$\begingroup\$

Perl 5, 51 41 + 1 (-p) = 42 bytes

$\=$_;$\=$\>($"=abs$'-$`)?$":$\while//g}{

Try it online!

inspired by @Nahuel-Fouilleul's comment

\$\endgroup\$
  • \$\begingroup\$ 46 bytes $\--;$d=abs$``-$',$\=$\<0|$d<$\?$d:$\while//g}{ \$\endgroup\$ – Nahuel Fouilleul Dec 18 '17 at 10:37
1
\$\begingroup\$

C# (.NET Core), 112 107 + 18 = 125 bytes

n=>Enumerable.Range(1,n.Length-1).Min(i=>System.Math.Abs(int.Parse(n.Remove(i))-int.Parse(n.Substring(i))))

Try it online!

The count includes the 18 bytes in using System.Linq;. Takes input as a string.

  • 5 bytes saved by Caius Jard!
\$\endgroup\$
  • \$\begingroup\$ string.Remove might save you a few bytes \$\endgroup\$ – Caius Jard Dec 18 '17 at 17:02

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.