24
\$\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\$
  • \$\begingroup\$ @Noodle9 The very first test case 1,3 is like that as well actually. :) \$\endgroup\$ – Kevin Cruijssen Aug 25 at 15:44
  • \$\begingroup\$ @KevinCruijssen Oops, of course - thanks! T_T \$\endgroup\$ – Noodle9 Aug 25 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 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\$ – Jonathan Allan Aug 25 at 23:10
  • \$\begingroup\$ @JonathanAllan added suggested testcases \$\endgroup\$ – Mukundan314 Aug 26 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Retina is magic. \$\endgroup\$ – null Aug 27 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.

| improve this answer | |
\$\endgroup\$
  • 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\$ – Dominic van Essen Aug 25 at 15:18
  • \$\begingroup\$ @DominicvanEssen Brilliant - thanks! :D \$\endgroup\$ – Noodle9 Aug 25 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\$ – Kevin Cruijssen Aug 25 at 15:51
  • \$\begingroup\$ @KevinCruijssen Very nice - thanks! :-) \$\endgroup\$ – Noodle9 Aug 25 at 16:09
  • \$\begingroup\$ 111 bytes by using a comprehension. \$\endgroup\$ – Neil Aug 25 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.
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can replace ʰ= by . \$\endgroup\$ – Zgarb Aug 26 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\$ – Unrelated String Aug 26 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)?
    )
  )
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ as.double is shorter than as.numeric. A pity strtoi doesn't work well with leading zeros. \$\endgroup\$ – Giuseppe Aug 25 at 13:50
  • \$\begingroup\$ Ah, and since you aren't using '[', you can alias substring to that instead of s \$\endgroup\$ – Giuseppe Aug 25 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\$ – Dominic van Essen Aug 25 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 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\$ – Dominic van Essen Aug 25 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)
| improve this answer | |
\$\endgroup\$
  • 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 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\$ – Kevin Cruijssen Aug 25 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.

| improve this answer | |
\$\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
| improve this answer | |
\$\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!

| improve this answer | |
\$\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.

| improve this answer | |
\$\endgroup\$
  • \$\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\$ – Dominic van Essen Sep 1 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!

| improve this answer | |
\$\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.