Alchemical Reduction

September 10, 2019

This task was solved in a blog entry by Philippe Gaultier, who explains that he started learning Scheme very recently. He gives this solution, using Chicken Scheme:

(import matchable
        clojurian.syntax
        chicken.file.posix
        chicken.io)

(define (char-case-opposite-casing? a b)
  (let* ((a-code (char->integer a))
         (b-code (char->integer b))
         (diff (- a-code b-code)))
    (= (* 32 32) (* diff diff))))

(define (chem-react acc x)
  (match acc
    [() (cons x acc)]
    [(a . arest) (if (char-case-opposite-casing? a x)
                     arest
                     (cons x acc))]))

(->> (open-input-file "/Users/pgaultier/Downloads/aoc5.txt")
     (read-line)
     (string->list)
     (foldl chem-react '())
     (length)
     (print))

Perhaps Gaultier’s purpose was to learn about pattern matching or explore the Chicken ecosystem, but he took a simple task and made it complicated. Here is my solution:

(define (chem str)
  (let loop ((cs (string->list str)) (zs (list)))
    (cond ((null? cs) (reverse zs))
          ((null? zs) (loop (cdr cs) (cons (car cs) zs)))
          ((and (char-ci=? (car cs) (car zs))
                (not (char=? (car cs) (car zs))))
            (loop (cdr cs) (cdr zs)))
          (else (loop (cdr cs) (cons (car cs) zs))))))

> (do ((str (read) (read))) ((eof-object? str))
    (display (length (chem str))) (newline))
"AabcdZZqQ"
5
"aAbxXBctTCz"
1
#!eof

With respect to Gaultier, I prefer my solution, which is written in standard RnRS and requires no imports. The do loop is a common idiom, and to my mind is easier to read than the “easy-to-read” ->> macro; quickly, why is the null list passed to chem-react in the call to foldl? (It’s the initialization of acc, which forces acc to an unnatural position as the first parameter rather than the second parameter.) And despite Gaultier’s claim, character comparisons are better than integer-to-character conversions.

You can run the program at https://ideone.com/UY0PyP.

Pages: 1 2

7 Responses to “Alchemical Reduction”

  1. Zack said

    Nifty little exercise. Not sure if it qualifies as alchemy, but it’s definitely a nice challenge. Here is my take using Julia 1.1: https://pastebin.com/DE53t8nw
    Cheers!

  2. Zack said

    There was a bug in my previous attempt (a cool exercise in itself!) so here is the refined code: https://pastebin.com/5yddm5CJ
    Cheers!

  3. chaw said

    Here’s a simple solution in R7RS Scheme, focusing on clarity. The
    imports are all trivial.

    (import (scheme base)
            (scheme write)
            (only (scheme char)
                  char-ci=?))
    
    (define (alchemical-reduction str)
      (let loop ((unseen (string->list str))
                 (seen '()))
        (if (null? unseen)
            (apply string (reverse seen))
            (loop (cdr unseen)
                  (if (and (pair? seen)
                           (pair? unseen)
                           (and (char-ci=? (car seen)
                                           (car unseen))
                                (not (char=? (car seen)
                                             (car unseen)))))
                      (cdr seen)
                      (cons (car unseen) seen))))))
    
    (display (alchemical-reduction "dabAcCaCBAcCcaDA"))
    (newline)
    

    dabCBAcaDA
    

  4. Graham said

    My Haskell solution relies mostly on a single

    foldr

    :

    module Main where
    
    import Data.Char (isLetter, toLower)
    
    react :: String -> String
    react = foldr step ""
     where
      step x (y : ys) | x /= y && toLower x == toLower y = ys
      step x ys       = x : ys
    
    part1 :: String -> Int
    part1 = length . react
    
    part2 :: String -> Int
    part2 s = minimum $ fmap (length . react . remove) ['a' .. 'z']
      where remove c = filter ((/= c) . toLower) (react s) -- save recomputation
    
    main :: IO ()
    main = do
      input <- filter isLetter <$> readFile "input"
      print . part1 $ input
      print . part2 $ input
    

    Regarding blog posts, I really like the elegance of this one, which shows this is just an exercise in group theory.

  5. matthew said

    Here’s a little C++ solution, doing in-place modification of a 0-terminated char array.

    #include <stdio.h>
    #include <string.h>
    
    char *transform(char *s) {
      int n = strlen(s);
      for (int i = 1, j = 1; i <= n; i++) {
        if (j && (s[i]^s[j-1]) == 0x20) j--;
        else s[j++] = s[i];
      }
      return s;
    }
    
    int main(int argc, char *argv[]) {
      printf("%s\n", transform(argv[1]));
    }
    
  6. Daniel said

    Here’s a solution in Python.

    def react(string):
        out = []
        for c in string:
            if out and c.lower() == out[-1].lower() and c != out[-1]:
                out.pop()
            else:
                out.append(c)
        return ''.join(out)
    
    s = 'dabAcCaCBAcCcaDA'
    print(react(s))
    

    Output:

    dabCBAcaDA
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: