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

{⊇m=∧?t}l

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

{ }l Left fold on the input:
 ⊇m= 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)

• Carcigenicate: That's cool. Seems... declarative? Reads like you're just telling the language the specification.
• Fatalize: @Carcigenicate Brachylog is indeed declarative, it is based on the declarative logic programming language Prolog.
• Carcigenicate: Prologs actually on my (increasingly) long list of languages to learn when I attain unlimited free time. There's too many cool languages!

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)}

• Neil: Does `[${p}]` not work?
• ETHproductions: @Neil Not for the first item of each array.
• Neil: Ah, I see you found a workaround. I had got as far as a=>a.reduce((l,r)=>`${l}`.match(`[${r}]`)&&r) (which also works for numeric input).
• Neil: Perhaps you can remove the p&& if you set p=1/19?
• Arnauld: The 1/19 trick is really cool. However, a simpler '^x' would work just as well (same size, though).

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

• Magic Octopus Urn: €Sü.å - I wish this worked like I thought it would.
• Emigna: @carusocomputing: Yeah that would have been great. Or just ü.å or €Süå.
• Magic Octopus Urn: Why doesn't pairwise work with dot commands again?
• Emigna: @carusocomputing: It's only implemented to take the next byte as command. It doesn't take the dot into account.

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

• Nick Hansen: I was able to shave a byte by using zip and some (->) monad trickery: f(x,y)=any('elem'x)y;g=all f.(zip=<<tail).map show . edit: elem should [hopefully obviously] be in backticks but that isn't possible with the comment formatter.
• Laikoni: 44 bytes: and.(zipWith(any.flip elem)=<<tail).map show
• nimi: It's allowed to take the input as a list of strings, e.g. ["1234567890", "19", "95", "5012", "23"], so you can drop the .map show.

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);
 }
}

• Kevin Cruijssen: Nice! A lot shorter than I was about to post.. Anyway, you can golf some more: a->{for(int i=1;i<a.length;)if(!a[i].matches(".*["+a[i++-1]+"].*"))return 0>1;return 1>0;} (90 bytes)
• Business Cat: I also golfed it to 90, but in a different way: a->{int r=1;for(int i=0;++i<a.length;)r*=a[i].matches(".*["+a[i-1]+"].*")?1:0;return r>0;}
• Business Cat: Nevermind, got it to 87: a->{int r=1,i=0;for(;++i<a.length;)r*=a[i].matches(".*["+a[i-1]+"].*")?1:0;return r>0;}
• user18932: Thanks to both of you. I think the only way to improve this by a meaningful amount now is to look at the regex.

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œ&L2円\Ạ

Try it online!

How?

Dœ&L2円\Ạ - 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

• Magic Octopus Urn: Oh man it DOES work! RüÃõå_ was what I came up with on my own. I'm honored to have been so close to your best answer, deleting mine. Why do you not need the R though?
• Adnan: @carusocomputing Hmmm, what is the R for then? :p

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?

• Carcigenicate: I'm not sure what "the signs" means, but you can assume all numbers will be positive.
• Adám: @Carcigenicate they can be zero too.
• Carcigenicate: Yes, sorry. "Non-negative".

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

• Jörg Hülsermann: A big Sorry. for the given testcases your solution works. ["filename",1,11,414] works not.
• Christoph: @JörgHülsermann sure trim only works for the leading and trailing chars. Fixed it.
• Titus: For PHP<7.1, you can use a& instead of null!== (-5 bytes).
• Titus: ... but this will only work for the first digit in $argv[$i], because "If from and to have different lengths, the extra characters in the longer of the two are ignored." (from the manual)

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;

• Ismael Miguel: Alternative: foreach($argv as$k=>$v)$t=$k--?$t*preg_match("#[{$argv[$k]}]#",$v)):1;echo$t;, 77 bytes (untested).
• Jörg Hülsermann: @IsmaelMiguel Heavy alternative First you must change $k-- to --$k and drop one ) after that your approach should work and you must add a @ for the warning
• Ismael Miguel: Oh, yes, didn't notice the useless parenthesys that causss syntax errors. And I disagree about the $k--. I specifically used it so that $k is still 0 on the first run. And warnings are ignorable. That means the code now is 76 bytes, but still untested.
• Ismael Miguel: After the edit, I can confirm that foreach($argv as$k=>$v)$t=$k--?$t*preg_match("#[{$argv[$k]}]#",$v):1;echo$t; is working as it should. Testing with $argv = array(1, 12, 123, 3, 34, 45, 5, 5); displays 1 and testing with $argv = array(1, 12, 123, 3, 34, 45, 5, 6); displays 0, as expected.
• Jörg Hülsermann: @IsmaelMiguel You forget that the first parameter in the is the filename.

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

• Luis Mendo: You can save a byte replacing 1)VG by 1&) (and this avoids repeating the first number)
• Sanchises: @LuisMendo Of course! I vaguely remembered that MATL had this functionality, but searching for "pop" (like in a queue or stack) in the spec didn't yield any results, so I thought I was mistaken.
• Luis Mendo: Yes, actually it's a particular case of reference indexing. With two outputs, a reference indexing operation like ) gives the selected values as first output, and then the remaining values as second output
• Sanchises: @LuisMendo Clever. They should hire you MATL guys to improve MATLAB...
• Luis Mendo: Haha. I do miss some of these features in MATLAB sometimes

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

• Neil: Would it help to have a single regexp that does the whole test in one go? Something like ^(\S*(\S)\S* (?=\S*2円))+\S+$.
• fergusq: @Neil That seems to work. Thanks!

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.

• Carcigenicate: The file restriction is fine, although that's certainly an odd limitation.

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.

• Carcigenicate: This looks like a similar approach to my Clojure answer. Neat looking language.