Number Chaining Predicate

Question

Problem:

Your task is to decide if in a sequence of numbers, every number contains at least one of the digits of the number that preceded it.

For example, the following should return truthy:

[1, 12, 203, 0, 30]
             ^   ^ Contains a 0
        ^ Contains a 2
    ^ Contains a 1
    

The following should return falsey:

[1, 32, 23, 34]
    ^ Doesn't contain a 1, therefore false
    

Your submission can be a function or full program.

Input:

Input can be any reasonable type of sequence. An array of numbers, an array of strings, a delimited string of numbers, etc.

Order matters however, so whatever structure you choose to accept as input obviously must have a definite ordering.

Input can be taken via the stdin or as an argument.

You can assume:

• all numbers will be non-negative integers

• input will always contain at least 2 numbers

• input numbers will not start with a 0

Output:

Output will be a truthy or falsey value (as defined by your language), representing whether or not the above specification is met.

Truthy/falsey values don't need to be consistent between tests.

It can either be output to the stdout or returned.

Test Cases:

True cases:
[1, 1, 1, 11, 111, 11, 1]
[12, 23, 34, 45, 56]
[65, 54, 43, 32, 21]
[123, 29, 9, 59, 55, 52, 2017, 2]
[1234567890, 19, 95, 5012, 23]

False cases:
[1, 2, 3, 4, 5, 1, 11] (2 doesn't contain a 1)
[12, 23, 33, 45] (45 doesn't contain a 3)
[98, 87, 76, 11, 12, 23] (11 doesn't contain a 7 or 6)

This is code-golf, so the least number of bytes wins.

Answer 1

Python 2, 48 bytes

lambda x:reduce(lambda a,b:set(a)&set(b)and b,x)

Try it online!

Print a empty set for False and the last element for True

Answer 2

Retina, 25 20 bytes

(.).*¶(?=.*\1)

^.+$

Try it online!

Whenever we find a digit that also occurs in the next number, we remove the separator between those numbers (along with the digits in the former number, starting from the shared one, but that's irrelevant). The input is valid, if all separators have been remove in the process, which we check by making sure that the string can be matched as a single line.

Answer 3

Brachylog, 9 bytes

{⊇ᵐ=∧?t}ˡ

Try it online!

Note that this not only works with a list of integers, but also with a list of strings or a list of lists.

Explanation

{      }ˡ       Left fold on the input:
 ⊇ᵐ=              It is possible to find a number which is a subset of both input numbers
    ∧             (and)
     ?t           The output is the second number (to continue the fold)

Answer 4

JavaScript (ES6), 47 44^_* 43 bytes

Saved a byte thanks to @Neil

x=>x.every(y=>y.match(`[${p}]`,p=y),p=1/19)

Takes input as a list of strings.

Test snippet

let f =
x=>x.every(y=>y.match(`[${p}]`,p=y),p=1/19)

let g = x => console.log("f([%s]): %s", x.join(", "), f(x.map(String)))

g([1, 1, 1, 11, 111, 11, 1])
g([12, 23, 34, 45, 56])
g([65, 54, 43, 32, 21])
g([123, 29, 9, 59, 55, 52, 2017, 2])
g([123456789, 19, 95, 5012, 23])

g([1, 2, 3, 4, 5, 1, 11])
g([12, 23, 33, 45])
g([98, 87, 76, 11, 12, 23])

*_{(crossed out 44 is still regular 44)}

Answer 5

Jelly, 5 4 bytes

f2\Ạ

Input is an array of strings.

Try it online!

How it works

f2\Ạ  Main link. Argument: A (array of strings)

 2\   Pairwise reduce by:
f       Filter, yielding all chars in the left string that appear in the right one.
   Ạ  All; yield 1 if all strings are non-empty, 0 if not.

Answer 6

05AB1E, 10 bytes

ü‚vy`Så1åP

Try it online! or as a Test suite

Explanation

ü‚          # map pairing over each pair in input
  v         # for each pair
   y`       # push as 2 separate elements on stack
     Så     # check each digit in 2nd number for membership in first
       1å   # check if any 1 exists in the resulting list
         P  # product of stack

Answer 7

CJam, 18 15 14 bytes

Saved 4 bytes thanks to Martin Ender

l~Afb_1>.&:,:*

Try it online!

Explanation

l~              e# Read and eval the input
  Afb           e# Convert each number to a list of digits
     _          e# Duplicate the array
      1>        e# Slice it after the first element
        .&      e# Vectorized set intersection; take the set intersection of corresponding 
                e#  elements of the two arrays
          :,    e# Get the length of each intersection
            :*  e# Take the product of the whole array. 
                e#  Will be 0 if any intersection was empty.

Answer 8

Haskell, 51 48 35 Bytes

-3 bytes thanks to @NickHansen! I really need to get better with those monad operators

-4 and -9 bytes thanks to @Laikoni and @nimi respectively!

and.(zipWith(any.flip elem)=<<tail)

This version takes the input as an array of strings, eliminating the need for show, but as far as I can see it works in largely the same way as the older version:

all(\(x,y)->any(`elem`x)y).(zip=<<tail).map show

(I'm fairly certain I'm allowed to submit an anonymous function like this, but I'll fix it if necessary)

First the numbers are converted to strings. Then the monad magic zip=<<tail creates a function that zips the list with itself which pairs each entry with its neighbor(s). Then all maps a lambda to each pair that checks whether one string contains any chars from the other and finally checks that they all come out True.

Old version that works basically the same way:

f a=and$zipWith(\b->any(`elem`show b).show)a$tail a

Answer 9

Ruby, 49 48 bytes

->x{x.each_cons(2){|z|x&&=z*' '=~/(.).* .*\1/};x}

Output is nil for false and a "random" integer for true.

Answer 10

Mathematica 62 47 35 bytes

With 12 bytes saved thanks to MartinE.

FreeQ[#⋂#2&@@@Partition[#,2,1],{}]&

---

FreeQ[#⋂#2&@@@Partition[#,2,1],{}]&[{{1},{1,2},{2,0,3},{0},{3,1}}]

False

FreeQ[#⋂#2&@@@Partition[#,2,1],{}]&[{{1},{1,2},{2,0,3},{0},{3,0}}]

True

Answer 11

Java 8, 94 90 87 bytes

Input is an array of strings representing the numbers. Starting with the second string, it performs a regular expression comparison against each previous string to see if it contains any of its characters: .*[previous string].*.

Golfed:

a->{int r=1,i=0;while(++i<a.length)r*=a[i].matches(".*["+a[i-1]+"].*")?1:0;return r>0;}

Ungolfed:

public class NumberChainingPredicate {

  public static void main(String[] args) {
    System.out.println("Expect true:");
    for (String[] input : new String[][] { { "1", "1", "1", "11", "111", "11", "1" }, { "12", "23", "34", "45", "56" },
        { "65", "54", "43", "32", "21" }, { "123", "29", "9", "59", "55", "52", "2017", "2" },
        { "1234567890", "19", "95", "5012", "23" } }) {
      System.out.println(java.util.Arrays.toString(input) + " = " + exec(f(), input));
    }

    System.out.println();
    System.out.println("Expect false:");
    for (String[] input : new String[][] { { "1", "2", "3", "4", "5", "1", "11" }, { "12", "23", "33", "45" },
        { "98", "87", "76", "11", "12", "23" } }) {
      System.out.println(java.util.Arrays.toString(input) + " = " + exec(f(), input));
    }
  }

  private static java.util.function.Function<String[], Boolean> f() {
    return a -> {
      int r = 1, i = 0;
      while (++i < a.length) {
        r *= a[i].matches(".*[" + a[i - 1] + "].*") ? 1 : 0;
      }
      return r > 0;
    };
  }

  private static boolean exec(java.util.function.Function<String[], Boolean> function, String[] input) {
    return function.apply(input);
  }

}

Answer 12

Jelly, 6 bytes

Dµf"ḊẠ

Try it online!

Explanation

Dµf"ḊẠ
Dµ        Treat the first (i.e. only) input as a list of decimal digits
   "      For each pair of corresponding elements in {the input digits} and
    Ḋ     {the input digits} with the first element removed
  f       take all elements common to both sides
     Ạ    then return true if the result has no empty lists, false otherwise

It's most obvious to try to use 2/ here, but that runs a unary function on all slices of size 2. "Ḋ effectively runs a binary function on all pairs of adjacent elements, which means we can use f directly (rather than needing to convert it to a unary function as f/). This does end up leaving the last element of the input in place, but luckily not even an input of 0 becomes an empty list when converted to decimal, so it has no effect on the Ạ.

Answer 13

Python 3, 48 bytes

f=lambda x:x==x[:1]or{*x[0]}&{*x[1]}and f(x[1:])

Try it online!

Answer 14

Jelly, 8 bytes

Dœ&L¥2\Ạ

Try it online!

How?

Dœ&L¥2\Ạ - Main link: the list of integers            e.g. [3, 13, 351, 73, 82]
D        - convert all the integers to decimal lists       [[3],[1,3],[3,5,1],[7,3],[8,2]]
     2\  - 2-slice cumulative reduce with:
    ¥    -     last two links as a dyad:
 œ&      -         multiset intersection                   [[3],[1,3],[3],[]]
         -         length                                  [1,2,1,0]
       Ạ - all truthy?                                     0

Answer 15

05AB1E, 5 bytes

Code:

üÃõå_

Uses the CP-1252 encoding. Try it online! or Verify all test cases!.

Explanation:

üà         # Intersection on each pair
  õå       # Check if the empty string exists
    _      # Boolean negate

Answer 16

PowerShell, 87 bytes

param($n)(1..($a=$n.length-1)|?{[char[]]$n[($i=$_)-1]|?{$n[$i]-like"*$_*"}}).count-eq$a

Try it online!

Not the shortest by any measure, but a slightly different approach than others are using, and shows off the nifty |?{} functionality.

This takes the input as an array of strings into $n, then loops from 1 up to the length-1. We use Where-Object (the |?{...}) to pull out those indices that are truthy for a particular condition. You can think of this like a combination for loop with an if clause.

The clause here is [char[]]$n[($i=$_)-1]|?{$n[$i]-like"*$_*"}. That is, we're taking the current index $_, setting it to $i, and subtracting 1, and using that to index into $n (i.e., so we get the previous element in our input array). That is then cast as a char-array and sent through another Where-Object procedure.

The inner clause $n[$i]-like"*$_*" specifies that the string at the current index $i is -like the current character $_ from the previous index. This will therefore output any characters that are in common between the two array elements. Thus, the outer clause will only be truthy if there is a character in common (since an empty array is falsey in PowerShell), and so the index will only be selected if there are characters in common.

Then, we gather up all of the indices that matched the criteria, and verify that the .count thereof is -equal to the length of the input array. That Boolean result is left on the pipeline, and output is implicit.

Answer 17

Perl 5, 31 bytes

A port of Martin Ender's beautiful answer.

30 bytes of code + -p flag.

s/(\S)\S* (?=\S*\1)//g;$_=!/ /

Try it online!

Answer 18

APL (Dyalog APL), 9 bytes

∧/×≢¨2∩/⎕

Try it online!

∧/ are all ones in the list of

× the signs

≢ of the tally of

¨ each of

2∩/ the pair-wise intersections of

⎕ the input?

Answer 19

PHP, 65 68

for(;null!==$a=$argv[++$i+1];)$r+=$a==strtr($a,$argv[$i],_);echo!$r;

iterate over all numbers and remove all digits that appeared in the previous. Count how often it equals the number itself (no digit removed). If at least one equaled we didn't have a match in one of the pairs.

---

Fixed a mistake using trim insted of strtr. Thanks to @JörgHülsermann

Answer 20

PHP, 75 bytes

for($b=3**39;--$argc;)preg_replace("#[$b]#","",$b=$argv[$argc])<$b?:die(1);

takes numbers from command line arguments; exits with 1 for falsy, with 0 for truthy.
Run with -r or test it online.

• start with $b = a number containing all digits
• loop down through the arguments
  • remove all digits of $b from the argument
  • copy argument to $b
  • if no digit was removed, exit with 1
• implicit: exit with 0

Answer 21

PHP, 77 Bytes

for($i=$t=1;++$i<$argc;)$t*=preg_match("#[{$argv[$i-1]}]#",$argv[$i]);echo$t;

Answer 22

MATL, 14 bytes

1&)"V@VX&nv@]x

Try it online!

Thanks @LuisMendo for saving a byte. Explanation:

1&)            % 'Pop' the first item from the input and push it on the stack.
   "       ]   % Main 'for' loop, to loop over the rest of the input.
    V            % Stringify previous (or first) iten from the input.
     @V          % Push current number, convert to string
       X&        % Intersect with stringified number already on the stack.
         nv      % Count the size of the intersection, and add it to the existing list of sizes.
           @     % Push the current number again for the intersection in the next loop. 
             x % Remove the number pushed by the last loop.
               % Else the program would end with the result on the second instead of the first position in the stack

Answer 23

Clojure, 71 bytes

(fn[n](every?(fn[[q w]](some q w))(partition 2 1(map #(set(str %))n))))

An anonymous function that accepts a sequence of numbers. Returns true/false.

I like how it reads. There's definitely a few areas that can be improved upon here. My function being passed to map can't easily be changed so that it doesn't require the function macro, which means the entire function can't make use of the macro, which likely added some bytes. It would also be nice if I could figure out a better way of unpacking the values in the every? predicate.

(defn number-chain? [nums]
  (let [; Turn each number into a set of characters
        set-nums (map #(set (str %)) nums)

        ; Partition the sets into lists of neighbors
        ; [1 2 3 4] -> [[1 2] [2 3] [3 4]]
        partitioned (partition 2 1 set-nums)]

    ; Does every second neighbor contain some element of the first?
    (every?
      (fn [[l1 l2]]
        (some l1 l2))
      partitioned)))

Answer 24

SimpleTemplate, 124 bytes

Wow, this was a workout!

{@eachargv asA keyK}{@ifK}{@setR"/[",O,"]/"}{@calljoin intoR"",R}{@ifA is notmatchesR}{@return}{@/}{@/}{@setO A}{@/}{@echo1}

This "simply" makes a regex using the old element, showing 1 as a truthy value, or nothing otherwise.

---

Ungolfed:

{@each argv as number key K}
    {@if K}
        {@set regex "/[", old, "]/"}
        {@call join into regex "", regex}
        {@if number is not matches regex}
            {@return false}
        {@/}
    {@/}
    {@set old number}
{@/}
{@echo 1}

Answer 25

JavaScript (ES6), 37 bytes

s=>/^(.*(.).*\n(?=.*\2))+.+$/.test(s)

Accepts input as a string of newline-separated numbers. Based on @MartinEnder♦'s excellent Retina answer, but doing the entire test in a single regexp because it's shorter in JavaScript that way.

Answer 26

Pip, 12 10 bytes

$&B@X^_MPg

Takes input as a series of command-line arguments. Output is a nonempty list for truthy and an empty list for falsey. Try it online or verify all test cases.

Explanation

         g  List of all cmdline args
       MP   Map this function to consecutive pairs of items from that list:
     ^_      Split 1st item of pair into list of characters
    X        Convert to regex that matches any of those characters
  B@         Find all matches in 2nd item of pair
$&          Fold on logical AND--truthy if all items are truthy, falsey if one is falsey
            Print (implicit)

Answer 27

Röda, 45 35 bytes

{[_=~`(\S*(\S)\S* (?=\S*\2))+\S+`]}

Try it online!

This is similar to the Perl 5 solution, which is a port of the Retina solution by Martin Ender. -10 bytes thanks to @Neil.

Here's a different solution (73 72 bytes):

{[_/""]|{|x|{x|[0]()unless[not(_ in y)]else[1]}if tryPeek y}_|sum|[_=0]}

It's an anonymous function that pulls strings from the stream and checks that the consecutive strings contain same characters. Explanation:

{
    [_/""]|    /* split strings -> creates arrays of characters */
    {|x|       /* begin for loop over character arrays */
        {      /* begin if tryPeek(y) -> peeks the second item from the stream */
               /* x and y are now two consecutive character arrays */
            x| /* push characters in x to the stream */
            [0]()unless[not(_ in y)]else[1] /* pushes 0 to the stream */
                                            /* if y contains the character */
                                            /* in the stream, otherwise 1 */
        }if tryPeek y
    }_|        /* end for loop */
    sum|       /* sum all numbers in the stream */
    [_=0]      /* return true if the sum is zero */
}

It could possibly be golfed more...

Answer 28

Bash + Unix utilities, 71 69 bytes

sed "s/\(.*\)/<<<\1 \&\&grepx[\1]/;1s/.*g/g/;\$s/ .*//"|tr 'x
' \ |sh

Try it online!

Input is on stdin, one number per line.

Output is in the exit code: 0 for truthy, 1 for falsey.

This can probably be golfed more.

For the code above to work, there cannot be any file in the current directory whose name is a single digit. If this isn't acceptable, replace [\1] in the program with '[\1]' (at a cost of 2 additional bytes).

Sample run (the last test case provided in the challenge):

$ echo '98
> 87
> 76
> 11
> 12
> 23' | ./digittest > /dev/null; echo $?
1

(1 here is falsey.)

---

How it works:

I'll demonstrate on the sample run above.

The sed command converts the input into:

grepx[98]
<<<87 &&grepx[87]
<<<76 &&grepx[76]
<<<11 &&grepx[11]
<<<12 &&grepx[12]
<<<23

The tr command then converts this to the string:

grep [98] <<<87 &&grep [87] <<<76 &&grep [76] <<<11 &&grep [11] <<<12 &&grep [12] <<<23

This string is a shell command for doing the desired operation, so I pipe that into sh and I'm done.

Answer 29

Q, 57 bytes

{r::();({r,::any(last x)in y;x,enlist y}\)($)0,x;all 1_r}

1. Initialises global r.
2. Converts input to array of strings.
3. Scans array checking that some character in last string is in current string.
4. Appends each result to r.
5. Returns 1 if all strings satisfy step 3 else returns 0.

Note: 0 appended to start of input array within function. This was done so that the comparison of the first element would be done enlisted. Otherwise, the last character of the first element is grabbed for comparison. Could do a type check however that adds 7 bytes over the current count.