Number Chaining Predicate

Question 1

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.

Question 2

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

Question 3

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.

Question 4

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)

Question 5

That's cool. Seems... declarative? Reads like you're just telling the language the specification.

Question 6

@Carcigenicate Brachylog is indeed declarative, it is based on the declarative logic programming language Prolog.

Question 7

Prologs actually on my (increasingly) long list of languages to learn when I attain unlimited free time. There's too many cool languages!

Question 8

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

Question 9

Does `[${p}]` not work?

Question 10

@Neil Not for the first item of each array.

Question 11

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

Question 12

Perhaps you can remove the p&& if you set p=1/19?

Question 13

The 1/19 trick is really cool. However, a simpler '^x' would work just as well (same size, though).

Question 14

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.

Question 15

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

Question 16

€Sü.å - I wish this worked like I thought it would.

Question 17

@carusocomputing: Yeah that would have been great. Or just ü.å or €Süå.

Question 18

Why doesn't pairwise work with dot commands again?

Question 19

@carusocomputing: It's only implemented to take the next byte as command. It doesn't take the dot into account.

Question 20

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.

Question 21

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

Question 22

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.

Question 23

44 bytes: and.(zipWith(any.flip elem)=<<tail).map show

Question 24

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.

Question 25

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.

Question 26

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

Question 27

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

Question 28

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)

Question 29

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

Question 30

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

Question 31

Thanks to both of you. I think the only way to improve this by a meaningful amount now is to look at the regex.

Question 32

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

Question 33

Python 3, 48 bytes

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

Try it online!

Question 34

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

Question 35

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

Question 36

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?

Question 37

@carusocomputing Hmmm, what is the R for then? :p

Question 38

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.

Question 39

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!

Question 40

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?

Question 41

I'm not sure what "the signs" means, but you can assume all numbers will be positive.

Question 42

@Carcigenicate they can be zero too.

Question 43

Yes, sorry. "Non-negative".

Question 44

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

Question 45

A big Sorry. for the given testcases your solution works. ["filename",1,11,414] works not.

Question 46

@JörgHülsermann sure trim only works for the leading and trailing chars. Fixed it.

Question 47

For PHP<7.1, you can use a& instead of null!== (-5 bytes).

Question 48

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

Question 49

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

Question 50

PHP, 77 Bytes

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

Question 51

Alternative: foreach($argv as$k=>$v)$t=$k--?$t*preg_match("#[{$argv[$k]}]#",$v)):1;echo$t;, 77 bytes (untested).

Question 52

@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

Question 53

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.

Question 54

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.

Question 55

@IsmaelMiguel You forget that the first parameter in the is the filename.

Question 56

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

Question 57

You can save a byte replacing 1)VG by 1&) (and this avoids repeating the first number)

Question 58

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

Question 59

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

Question 60

@LuisMendo Clever. They should hire you MATL guys to improve MATLAB...

Question 61

Haha. I do miss some of these features in MATLAB sometimes

Question 62

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

Question 63

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}

Question 64

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.

Rod 18.6k4 gold badges32 silver badges89 bronze badges · Accepted Answer · 2017-03-15 14:36:34Z

13

\$\begingroup\$

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

Share

Improve this answer

edited Mar 15, 2017 at 14:41

answered Mar 15, 2017 at 14:36

Rod's user avatar

Rod

18.6k4 gold badges32 silver badges89 bronze badges

\$\endgroup\$

Add a comment |

Number Chaining Predicate

Problem:

Input:

Output:

Test Cases:

29 Answers 29

Python 2, 48 bytes

Retina, (削除) 25 (削除ここまで) 20 bytes

Brachylog, 9 bytes

Explanation

JavaScript (ES6), (削除) 47 (削除ここまで) (削除) 44* (削除ここまで) 43 bytes

Test snippet

Jelly, (削除) 5 (削除ここまで) 4 bytes

How it works

05AB1E, 10 bytes

CJam, (削除) 18 (削除ここまで) (削除) 15 (削除ここまで) 14 bytes

Haskell, (削除) 51 (削除ここまで) (削除) 48 (削除ここまで) 35 Bytes

Ruby, (削除) 49 (削除ここまで) 48 bytes

Mathematica (削除) 62 47 (削除ここまで) 35 bytes

Java 8, (削除) 94 (削除ここまで) (削除) 90 (削除ここまで) 87 bytes

Jelly, 6 bytes

Explanation

Python 3, 48 bytes

Jelly, 8 bytes

How?

05AB1E, 5 bytes

PowerShell, 87 bytes

Perl 5, 31 bytes

APL (Dyalog APL), 9 bytes

PHP, (削除) 65 (削除ここまで) 68

PHP, 75 bytes

PHP, 77 Bytes

MATL, 14 bytes

Clojure, 71 bytes

SimpleTemplate, 124 bytes

JavaScript (ES6), 37 bytes

Pip, (削除) 12 (削除ここまで) 10 bytes

Explanation

Röda, (削除) 45 (削除ここまで) 35 bytes

Bash + Unix utilities, (削除) 71 (削除ここまで) 69 bytes

Q, 57 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Linked

Related

Hot Network Questions

JavaScript (ES6), (削除) 47 (削除ここまで) (削除) 44^_* (削除ここまで) 43 bytes