Arc Forumnew | comments | leaders | submitlogin
2 points by zck 4374 days ago | link | parent

Generally, I'll try to show it to some of my programmer friends, or to people at work.

I had actually come up with an interview question: take two strings and return the index of the first difference. I posted some arc code, and wanted to have people run it.

My code:

  (def first-difference (seq1 seq2 (o comparer is))
       "Returns the index of the first difference between seq1 and seq2, or nil if
        they are the same. This function uses 'comparer as the function to compare
        elements of the sequences."
       (withs (len1 (len seq1) ;; 'withs ([var1 val1]* ) binds each var to its val
               len2 (len seq2)
               helper (afn (seq1 seq2 pos) ;; 'afn makes an anonymous function that
                                           ;; can recurse by calling 'self
                           (if (is len1
                                   len2
                                   pos) ;; at end of both sequences
                               nil
                             (or (is len1
                                     pos)
                                 (is len2
                                     pos)) ;; at end of only one sequence
                             pos
                             (~comparer seq1.pos
                                        seq2.pos) ;; found a difference
                             pos
                             (self seq1 seq2 (+ pos 1)))))
               (helper seq1 seq2 0)))


2 points by akkartik 4374 days ago | link

Nice example. For exposition is it useful to simplify the problem by focusing on lists?

  (def first-difference(seq1 seq2)
    (if (or no.seq1 no.seq2
            (~iso car.seq1 car.seq2))
      0
      (+ 1 (first-difference cdr.seq1 cdr.seq2))))
Edit: no, that's not right, because it doesn't return nil on identical sequences. Here are two variants with and without the accumulator. Which is easier for noobs?

  (def first-difference(seq1 seq2 (o pos 0))
    (if
      (and no.seq1 no.seq2)
        nil
      (or no.seq1 no.seq2 (~iso car.seq1 car.seq2))
        pos
      'else
        (first-difference cdr.seq1 cdr.seq2 (+ pos 1))))

  (def first-difference(seq1 seq2)
    (if
      (and no.seq1 no.seq2)
        nil
      (or no.seq1 no.seq2 (~iso car.seq1 car.seq2))
        0
      'else
        (only.+ (first-difference cdr.seq1 cdr.seq2) 1)))
 
  (test-iso "" 0 (first-difference nil '(34)))
  (test-iso "" nil (first-difference '(1) '(1)))
  (test-iso "" 1 (first-difference '(1) '(1 2)))
  (test-iso "" 3 (first-difference '(1 2 3 4) '(1 2 3)))

-----

1 point by jsgrahamus 4373 days ago | link

  arc> (def 1st-diff (str1 str2 i)
    (if (or (is str1 "") (is str2 ""))
      0
      (or (> i (- (len str1) 1)) (> i (- (len str2) 1)))
      i
      (no (is (str1 i) (str2 i)))
      i
      (1st-diff str1 str2 (+ i 1))))
  #<procedure: 1st-diff>
  arc> (1st-diff "" "" 0)
  0
  arc> (1st-diff "" "" 0)
  0
  arc> (= astring "abcde")
  "abcde"
  arc> (= bstring "abced")
  "abced"
  arc> (1st-diff "" "" 0)
  0
  arc> (1st-diff astring "" 0)
  0
  arc> (1st-diff "" astring 0)
  0
  arc> (1st-diff astring bstring 0)
  3
  arc> (1st-diff bstring astring 0)
  3
  arc> (1st-diff astring "abcdef" 0)
  5
  arc> (1st-diff "abcdef" astring 0)
  5
  arc>

-----

1 point by jsgrahamus 4373 days ago | link

It's interesting to compare this to the solution in my workday language. One of the reasons that M is shorter is because its functions are more tolerant. For arc, I had to make sure that the index to the string was not too large. In M, it simply returns an empty string if you attempt to access a string position beyond the length. And I used iteration with M. Perhaps the arc solution would have been shorter had I done the same there.

Interesting exercise for this newbie.

-----

2 points by akkartik 4373 days ago | link

Yeah you can index past the end in my arc variant (http://github.com/akkartik/wart). But it currently returns nil. What should it be?

I'd love to see the M version expanded into english.

-----

2 points by jsgrahamus 4373 days ago | link

Great.

I'm used to seeing it as the empty string

Here is the expanded M version (! = LF):

  IF X=Y WRITE !,0 ; No difference
  ELSE  FOR I=1:1 IF $EXTRACT(X,I)'=$EXTRACT(Y,I) WRITE !,I QUIT

-----

1 point by akkartik 4372 days ago | link

I still don't know enough MUMPS to follow it :)

Are you concatenating strings? Is that where returning "" is useful? In wart concatenating strings is tolerant of non-strings, so I think returning nil should be ok.

-----

2 points by jsgrahamus 4371 days ago | link

If the string X = the string Y, print 0 (to indicate there are no differences / MUMPS uses 1-based indexing of strings)

Otherwise, go through each character of the strings and at the point where they differ, print that index and quit looping.

MUMPS does not error out on attempting to extract a character beyond the string's length. So in that event, 1 string's extract will return the empty string, which will differ from the other string's extract and will cause you to print the index and quit. Not generating such an error, of course, cuts down on the code needed.

-----

2 points by zck 4371 days ago | link

So if we enter the for loop, we know there is a difference between the two sequences.

So we just need to find an index position i where (isnt seq1.i seq2.i) is true. If indexing off the end of a string causes an error, we need to put in code to prevent that. If indexing off the end of a string returns anything that can't be an element of the string, we can compare each index i until we find a difference, knowing that we'll eventually find one.

-----

1 point by jsgrahamus 4371 days ago | link

Correct.

-----

1 point by jsgrahamus 4373 days ago | link

test-iso?

-----

1 point by akkartik 4373 days ago | link

https://github.com/nex3/arc/blob/ec47676f99af11b6fa8935a3cb0...

-----

3 points by jsgrahamus 4374 days ago | link

In my work language:

  I X=Y W !,0 ; No difference
  E  F I=1:1 I $E(X,I)'=$E(Y,I) W !,I Q
A challenge for me is arc/lisp/scheme's verboseness.

-----

1 point by akkartik 4374 days ago | link

What is that, J?

-----

1 point by rocketnia 4373 days ago | link

I think you may already have an inkling somewhere in the back of your mind.... http://arclanguage.org/item?id=15341

-----

1 point by akkartik 4373 days ago | link

Lol.

-----

1 point by jsgrahamus 4373 days ago | link

MUMPS / M / Caché - Used it for most of 30 years. In the U.S. mostly used on medical information systems, however it is also used in banks, credit unions, Ameritrade, etc.

-----