Limiting consecutive identical elements with match

[Joel Dueck]

(This is related to the problem for this year’s Advent of Code day 4, so...SPOILERS.)

(I did solve both parts of today's problem, so this is more for my own edification.)

The problem involves finding lists of numbers, one of the criteria for which is that the list has at least two consecutive identical numbers. I was able to solve this part of the problem easily with `match`:

    (define (cool? lst)
      (match lst
        [(list _ ... a a _ ...) #t]
        [_ #f]))

    > (cool? '(1 2 3 4 5 6))
    #f
    > (cool? '(1 2 1 4 5 6))
    #f
    > (cool? '(1 1 1 4 5 6))
    #t

The second part (SPOILER) involves finding lists containing **exactly two** consecutive identical numbers.

I was trying to find a way to use pattern matching for this problem and could not.

As a simple case:

 

    (define (super-cool? lst)

      (match lst

        [(list a b b c) #t]

        [_ #f]))

    > (super-cool? '(1 1 1 4))
    #t                       ; I want it to be #f!

Using `b b` in the middle of the pattern allows me to require that those two elements be identical. But there is no requirement that the outside elements be not identical despite my giving them different ids. I also can't do (list (not a) a a (not a)) because, as the docs say[1], "instances of an `id` in different `or` and `not` sub-patterns are independent. The binding for `id` is not available in other parts of the same pattern."

So it seems easy to match "at least N identical elements".

But is there a method for matching "no more than N identical elements"?

[1]: https://docs.racket-lang.org/reference/match.html

[Matthew Butterick]

On Dec 4, 2019, at 2:39 PM, 'Joel Dueck' via Racket Users <racket...@googlegroups.com> wrote:

So it seems easy to match "at least N identical elements".

But is there a method for matching "no more than N identical elements"?

?

#lang racket

(require rackunit)

(define (super-cool? lst)

  (match lst

    [(and (list* _ ... a a _)

          (not (list* _ ... a a a _))) #t]

    [_ #f]))

(check-true (super-cool? '(1 1 4)))

(check-false (super-cool? '(1 1 1 4)))

[Sorawee Porncharoenwase]

This is super cool indeed. Now I feel stupid.

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/1734093C-0C39-4289-9747-41CAFB35851F%40mbtype.com.

[Joel Dueck]

I feel stupid too!

I like the trick of using list* to match _ on any number of trailing elements. The grammar given in the docs doesn't seem to include it; I'm curious by what rule is it "allowed" as a pattern?

On Wednesday, December 4, 2019 at 5:02:48 PM UTC-6, Sorawee Porncharoenwase wrote:

This is super cool indeed. Now I feel stupid.

On Wed, Dec 4, 2019 at 2:56 PM Matthew Butterick <m...@mbtype.com> wrote:

On Dec 4, 2019, at 2:39 PM, 'Joel Dueck' via Racket Users <racket...@googlegroups.com> wrote:

So it seems easy to match "at least N identical elements".

But is there a method for matching "no more than N identical elements"?

?

#lang racket

(require rackunit)

(define (super-cool? lst)

  (match lst

    [(and (list* _ ... a a _)

          (not (list* _ ... a a a _))) #t]

    [_ #f]))

(check-true (super-cool? '(1 1 4)))

(check-false (super-cool? '(1 1 1 4)))

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to racket...@googlegroups.com.

[Matthew Butterick]

On Dec 4, 2019, at 3:26 PM, 'Joel Dueck' via Racket Users <racket...@googlegroups.com> wrote:

I like the trick of using list* to match _ on any number of trailing elements. The grammar given in the docs doesn't seem to include it; I'm curious by what rule is it "allowed" as a pattern?

It's a synonym for the `list-rest` match pattern.

[Laurent]

I don't know what the exact specs are, but what should be the return values for '(a a a b b c) and '(a a b b b c) ?

(I can't test right now but I suspect the match approach might miss one)

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/B5F3E54D-B800-481D-8FE3-A03C6B4F565E%40mbtype.com.

[Daniel Prager]

While playing around with this I came across an error message in match that could perhaps stand some improvement ...

> (define (super-cool?/flawed ds)
    (match ds
      [(list _ ... a a ... _) #t]
      [_ #f]))
a59: unbound identifier;
 also, no #%top syntax transformer is bound in: a59

Dan