25
\$\begingroup\$

Background

Two numbers, \$a\$ and \$b\$, are said to be connected by a Brussels choice operation* if \$b\$ can be reached from \$a\$ by doubling or halving (if even) a substring (the substring must not be empty and may not contain any leading 0s but it can be 0) in the base-10 representation of \$a\$

*This operation is slightly different from the one defined on this paper mainly that the operation defined in the paper allows empty substrings and does not allow choosing the substring "0"

For example, all the number that can be reached from 5016:

508     (50[16] half   -> 50[8])
2508    ([5016] half   -> [2508])
2516    ([50]16 half   -> [25]16)
5013    (501[6] half   -> 501[3])
5016    (5[0]16 half   -> 5[0]16)
        (5[0]16 double -> 5[0]16)
5026    (50[1]6 double -> 50[2]6)
5032    (50[16] double -> 50[32])
10016   ([5]016 double -> [10]016)
        ([50]16 double -> [100]16)
10026   ([501]6 double -> [1002]6)
10032   ([5016] double -> [10032])
50112   (501[6] double -> 501[12])

Task

Write a program/function that when given two positive integers as input outputs a truthy value if they can reach each other with a single Brussels choice operation and a falsey value otherwise.

Scoring

This is so shortest bytes wins.

Sample Testcases

2, 4       -> Truthy
4, 2       -> Truthy
101, 101   -> Truthy
516, 58    -> Truthy
58, 516    -> Truthy
516, 5112  -> Truthy
5112, 516  -> Truthy

1, 3       -> Falsey
123, 123   -> Falsey
151, 252   -> Falsey
112, 221   -> Falsey
101, 999   -> Falsey
999, 1001  -> Falsey
101, 1001  -> Falsey

Inspired by The Brussels Choice - Numberphile

\$\endgroup\$
5
  • \$\begingroup\$ @Noodle9 The very first test case 1,3 is like that as well actually. :) \$\endgroup\$ Aug 25, 2020 at 15:44
  • \$\begingroup\$ @KevinCruijssen Oops, of course - thanks! T_T \$\endgroup\$
    – Noodle9
    Aug 25, 2020 at 15:48
  • \$\begingroup\$ At first, I thought this was uninteresting since it reduces to a last digit check, but then I realized it's not about full connectivity, but single-step connectivity. \$\endgroup\$
    – Beefster
    Aug 25, 2020 at 19:43
  • 1
    \$\begingroup\$ I suggest adding falsey test-cases for which either one or both numbers are connected to themselves: (101,999), (999, 1001), and (101,1001). \$\endgroup\$ Aug 25, 2020 at 23:10
  • \$\begingroup\$ @JonathanAllan added suggested testcases \$\endgroup\$ Aug 26, 2020 at 3:09

10 Answers 10

6
\$\begingroup\$

Retina, 38 bytes

L$w`0|[1-9]\d*
$`$.(*2*)$'
m`^(.+),\1$

Try it online! Link includes test cases. Outputs 0 for Falsey, non-zero for Truthy. Explanation:

L$w`0|[1-9]\d*

Match all integer substrings of both inputs, including 0 but not integers beginning with 0.

$`$.(*2*)$'

List the result of doubling that substring only.

m`^(.+),\1$

Check to see whether this produces any pairs of equal integers.

\$\endgroup\$
1
  • \$\begingroup\$ Retina is magic. \$\endgroup\$
    – null
    Aug 27, 2020 at 6:20
6
\$\begingroup\$

Python 2, 180 \$\cdots\$ 121 111 bytes

Saved 2 bytes thanks to Mukundan314!!!
Saved a whopping 16 bytes thanks to an idea from Dominic van Essen!!!
Saved 7 bytes thanks to Kevin Cruijssen!!!
Saved 10 bytes thanks to Neil!!!

def f(*p):a=`min(p)`;return max(a[:i]+`2*int(a[i:j])`+a[j:]==`max(p)`for j in range(len(a)+1)for i in range(j))

Try it online!

Returns either True or False.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Surely it's shorter to first check whether a>b and only do the 'brussels' transformation one way around? I can't write in Python, so you'll certainly be able to improve this... \$\endgroup\$ Aug 25, 2020 at 15:18
  • \$\begingroup\$ @DominicvanEssen Brilliant - thanks! :D \$\endgroup\$
    – Noodle9
    Aug 25, 2020 at 15:27
  • \$\begingroup\$ 127 bytes by using a mixture of spaces and tabs for indentations since you're using Python 2, and removing variable b since you only use it once. \$\endgroup\$ Aug 25, 2020 at 15:51
  • \$\begingroup\$ @KevinCruijssen Very nice - thanks! :-) \$\endgroup\$
    – Noodle9
    Aug 25, 2020 at 16:09
  • \$\begingroup\$ 111 bytes by using a comprehension. \$\endgroup\$
    – Neil
    Aug 25, 2020 at 18:50
5
\$\begingroup\$

Brachylog, 13 12 bytes

p{~c↺×₂ʰ↻c}ᵈ

Try it online!

-1 byte thanks to Zgarb

Takes input as a list [a, b] through the input variable and outputs through success or failure.

p               Permute the input.
 {        }ᵈ    For the first element of the input:
  ~c            take some partition of it,
     ×₂         double
    ↺  ʰ↻       the second element of the partition,
         c      and re-concatenate it.
 {        }ᵈ    It's possible for the result to be the second element of the input.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I think you can replace ʰ= by . \$\endgroup\$
    – Zgarb
    Aug 26, 2020 at 18:56
  • \$\begingroup\$ Can't believe I thought to use it for the testing header in earlier versions, but not in the solution itself... thanks! \$\endgroup\$ Aug 26, 2020 at 19:30
3
\$\begingroup\$

R, 120 117 112 106 bytes

Edit: -5 bytes thanks to Giuseppe (again)

Edit2: -6 bytes by using vectorized arguments to substring and paste and so avoiding any loops

function(v,m=min(v),`[`=substring,b=rep(1:m,e=m))max(v)%in%paste0(m[0,b-1],as.double(m[1:m,b])*2,m[1:m+1])

Try it online!

How?

is_brussels=
function(v,             # v is vector of 2 input values
 m=min(v),              # m is smaller input value
 s=substring)           # s is alias to substring function.
 max(v) %in%            # Main function : Is larger input value present in ...
  sapply(1:m,           # the results of applying all combinations of 1..m ...
   function(b)          # to the 'brussels' function with beginning b ...
    paste0(s(m,0,b-1),  # which pastes together m (up to b)...
     as.numeric(s(m,b,1:m))*2,
                        # onto 2x m (from b to all values of e from 1:m) ... 
     s(m,2:m)           # onto m (from e onwards)?
    )
  )
\$\endgroup\$
5
  • \$\begingroup\$ as.double is shorter than as.numeric. A pity strtoi doesn't work well with leading zeros. \$\endgroup\$
    – Giuseppe
    Aug 25, 2020 at 13:50
  • \$\begingroup\$ Ah, and since you aren't using '[', you can alias substring to that instead of s \$\endgroup\$
    – Giuseppe
    Aug 25, 2020 at 13:51
  • \$\begingroup\$ Thanks & thanks! I was quite frustrated about the need for as.numeric, so a byte saved is particularly welcome there! \$\endgroup\$ Aug 25, 2020 at 14:53
  • \$\begingroup\$ Ah, I was trying to figure out how to get rid of sapply with mapply, but completely overlooked that paste0 is already vectorized! \$\endgroup\$
    – Giuseppe
    Aug 25, 2020 at 18:07
  • \$\begingroup\$ Yes! I got something similar to work with outer(...,...,Vectorize(...)), but turns out to be much shorter to do the work of outer 'by hand' using rep... \$\endgroup\$ Aug 25, 2020 at 19:08
3
\$\begingroup\$

05AB1E, 31 27 23 bytes

{R`.œv3FyDNè·Nyg%ǝ])Jćå

-4 bytes as bug-fix - thanks to @ovs for noticing. (Decreasing the bytes as bug-fix doesn't happen often, haha. :D)

Input as a pair of integers.

Try it online or verify all test cases.

Explanation:

{R                 # Sort the (implicit) input-pair from highest to lowest
  `                # Pop and push both values separated to the stack
   .œ              # Get all partitions of the top lowest integer
     v             # Loop over each partition `y`:
      3F           #  Inner loop `N` in the range [0, 3):
        yD         #   Push partition `y` twice
          Nè       #   Get the `N`'th item of the partition (modulair 0-based)
            ·      #   Double it
             N     #   Push index `N` again
              yg%  #   Modulo the length of the current partition `y`
                   #   (since builtin `ǝ` doesn't index modulair)
                 ǝ #   Insert the doubled substring back into the partition at that index
     ]             # Close both loops
      )            # Wrap all values on the stack into a list
       J           # Join each partition back to a single string
        ć          # Extract the head; pop and push the remainder-list and first item
                   # separated to the stack (which is the highest value that was still on
                   # the stack)
         å         # Check if the list contains this highest integer
                   # (after which the result is output implicitly)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ This fails on [123,134], which should be false. The problem is with the partition builtin, which also includes partition of permutations for some reason: tio.run/##yy9OTMpM/f9fydDIWEnBWEHv6KT//wE \$\endgroup\$
    – ovs
    Aug 25, 2020 at 16:07
  • 1
    \$\begingroup\$ @ovs Thanks for noticing! Fixed by using the other partition builtin , which actually opened up a way to golf 4 bytes in the process. :D \$\endgroup\$ Aug 25, 2020 at 18:11
2
\$\begingroup\$

Raku, 48 bytes

{;*eq[|] m:ex/.+/>>.&{.replace-with($_/(2|.5))}}

Try it online! Oops, TIO doesn't have an up to date version of Raku, which means it doesn't have replace-with. I guess we'll have to go with repl.it online! instead.

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

JavaScript (ES9), 102 bytes

Returns either false or 1.

f=(a,b,i)=>(g=r=>a.replace(o=RegExp('(?<='+r),n=>o=n*2)==b&++o||o&&g('.'+r)|g(r+'.'))`)`||!i&&f(b,a,1)

Try it online!

How?

We recursively build all possible regular expressions matching the first occurrence of \$p\$ digits preceded by \$q\$ digits, using a lookbehind assertion. The matched string is coerced to an integer, doubled and coerced back to a string.

Example:

"123456".replace(/(?<=..).../, n => n * 2) // -> "12[345]6" -> "12[690]6"

We stop the recursion when no replacement occured (failure) or the result is equal to the other number (success). We try to turn either a into b or b into a.

Commented

f = (                     // f is a recursive function taking:
  a, b,                   //   the input numbers a and b
  i                       //   a flag i telling if the numbers were already swapped
) => (                    //
  g = r =>                // g is a recursive function taking a pattern r
    a.replace(            // replace in a:
      o =                 //   initialize o to a non-numeric value
      RegExp('(?<=' + r), //   turn r into a regular expression of the form /(?<=..)../
      n =>                //   if something is matched: replace the substring n with
        o = n * 2         //   2 * n and assign the result to o
    ) == b                // end of replace(); success if the result is equal to b
    & ++o                 // and o is an even number, which becomes odd when incremented
    || o &&               // otherwise, if o is not equal to NaN:
      g('.' + r) |        //   try again with 1) another leading '.' in r
      g(r + '.')          //   and 2) with another trailing '.' in r
)`)`                      // initial call to g with r = ')'
|| !i && f(b, a, 1)       // if i is not set, try again with a and b exchanged
\$\endgroup\$
1
\$\begingroup\$

Python 3.8 (pre-release), 115 bytes

lambda*x:(a:=str(min(x)))and{str(max(x))}&{a[:i]+str(2*int(a[i:j]))+a[j:]for j in range(len(a)+1)for i in range(j)}

Try it online!


Python 3, 139 116 bytes

A golf of Noodle9's answer. Outputs a set containing b if there is a Brussels choice, an empty set otherwise.

def f(*x):a,b=map(str,sorted(x));return{b}&{a[:i]+str(2*int(a[i:j]))+a[j:]for j in range(len(a)+1)for i in range(j)}

Try it online!

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

perl -Mfeature=say -na, 68 bytes

($_,$n)=@F;m[.+(?{say$=if$n eq$`.($&/2).$'||$n eq$`.($&*2).$'})(?!)]

Try it online!

Reads two numbers from the input, and prints 60 if there's a way to connect the numbers, and nothing otherwise.

How does it work?

We take every possible, non-empty, substring of the first number; this will be in available in $&. The part of the first number which proceeds the current substring is in $` , the part after it is in $'. We then create two new strings, by either multiplying the substring by 2, or dividing it by 2, and sandwiching it between $` and $'. We then compare this with the second number, and print $= if there is a match ($= by default contains 60). Note that if the substring is odd, the resulting string will contain a decimal point, and hence, will not match with the second number.

\$\endgroup\$
1
  • \$\begingroup\$ I'm still working through this bit-by-bit to try to understand it, but I think it could be shorter by first sorting & then only checking the 'brussels' transformation one way round... \$\endgroup\$ Sep 1, 2020 at 15:35
0
\$\begingroup\$

Perl 5 -pl, 122 bytes

$t=<>;for$a(1..y///c){for$b(0..y///c){$z||=/(.{$b})(.{$a})/&&$2!~/^0./&&grep$t==$_,$2%2==0&&$1.$2/2 .$',$1.$2*2 .$'}}$_=$z

Try it online!

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