LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 September 27 2012

Joe
Member

[Exercise]Is this list a sublist?

In your language of choice, pick a simple ordered container of objects (arrays, list, vectors, strings, you-name-it ...). Let C1 and C2 be two instances of this container. The goal of this exercise is to write a function that takes C1 and C2 as paramters and returns a boolean whose value is True if C1 is a subset subsequence subword of C2 and False otherwise.

Here are some examples you could use to validate your code:

C1=(2, 39) C2=(3, 20, 2, 39, 93, 2) -> True
C1=(10, 0) C2=(5, 10, 3, 0, 9) -> False
C1=(4, 50, 3) C2=(3, 87, 4, 50) -> False

Remarks
• Most languages implement this functionality either natively (like the in operator in Python on strings) or through specialized libraries (like <string.h> in C). It goes without saying that you shouldn't use those.

• This exercise is a bit easier than the ones I usually post. It can be a good entry point for members looking to start participating in our Programming Exercises series but don't know where to start.

• If anyone feels the exercise is not challenging enough, answer the question in your weakest language (or a language you're trying to learn).

#2 September 27 2012

geek
Member

Re: [Exercise]Is this list a sublist?

Subsequence instead of subset, based on the examples you have given.

#3 September 27 2012

Joe
Member

Re: [Exercise]Is this list a sublist?

Corrected. Are you posting some code this time?
EDIT: Well my examples do not follow exactly the definition of Subsequence as the sub-element has to be a consecutive sequence found inside the element (look at my second example).

This paragraph seems to show that the word I'm looking for is substring, or subword. I'm using the latter because string has a very localized connotation for programmers and I want the function to take any type of sequence as input.

Anyway, thanks for helping me get my (badly needed) formalism straight in formulating my problems.

#4 September 27 2012

Joe
Member

Re: [Exercise]Is this list a sublist?

My answer in Scheme (clearly our syntax coloring system is not familiar with this language):

``````(define nil '()) ;;'# This whole line is a hack to improve syntax coloring.

(define (pattern-matcher pattern)
;; #Returns a function lambda (target) that returns #t if pattern is found
;; #in the beggining of target, and #f otherwise.
(lambda (target)
(cond ((and (eq? target nil) (not (eq? pattern nil))) #f)
((eq? pattern nil) #t)
((not (= (car target) (car pattern))) #f)
(else ((pattern-matcher (cdr pattern)) (cdr target))))))

(define (sublist? C1 C2)
;; #iterates over C2 until it finds a substring that matches C1
;; #returns #t if match is found, and #f if nothing is.
(cond ((eq? C2 nil) #f)
(((pattern-matcher C1) C2) #t)
(else (sublist? C1 (cdr C2)))))``````

#5 September 27 2012

geek
Member

Re: [Exercise]Is this list a sublist?

``````subword :: (Eq a) => [a] -> [a] -> Bool -> Bool
subword [] _ _ = True
subword _ [] _ = False
subword (x:xs) (y:ys) b = ((x == y) && (subword xs ys False)) || (b && (subword (x:xs) ys True))``````
``````> subword [1,2,3] [1,1,2,2,3,3] True
False
> subword [1,2,3] [1,1,2,3,3] True
True``````

Last edited by geek (September 27 2012)

#6 September 27 2012

arithma
Member

Re: [Exercise]Is this list a sublist?

@geek: I didn't get this subexpression:

``subword (x:xs) ys``

x:xs is equivalent to tail(xs) if "tail" exists..?

Last edited by arithma (September 27 2012)

#7 September 27 2012

geek
Member

Re: [Exercise]Is this list a sublist?

@arithma: The last line can be written alternatively as:

``subword xs ys b = (((head xs) == (head y)) && (subword (tail xs) (tail ys) False)) || (b && (subword xs (tail ys) True))``

[inlinecode]x:xs[/inlinecode] is equivalent to [inlinecode]head:tail[/inlinecode] with [inlinecode]head = x[/inlinecode] and [inlinecode]tail = xs[/inlinecode]

#8 September 27 2012

Ayman
Member

Re: [Exercise]Is this list a sublist?

My first python one liner ^^

``````checkSub = lambda seq,subq: len(['t' for i,val in enumerate(seq) if cmp(seq[i:(len(subq)+i)],subq) == 0]) > 0

print checkSub((3, 20, 2, 39, 93, 2),(93,2))``````

Last edited by Ayman (September 27 2012)

#9 September 28 2012

Joe
Member

Re: [Exercise]Is this list a sublist?

Nice one Ayman!

For the record, you don't need to [inlinecode]enumerate[/inlinecode] the sequence since you're only using the index. Enumerating can be costly in case of very large sequences (although Python does deal with it lazily). I would write something more like this:

``checkSub = lambda seq,subq: len(['t' for i in xrange(len(seq)) if cmp(seq[i:(len(subq)+i)],subq) == 0]) > 0``

#10 September 28 2012

Ayman
Member

Re: [Exercise]Is this list a sublist?

@rahmu ah I see you're right, thanks for the tip! :)