《ジェムストリング問題》の参考プログラム

gemstring.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int ar[] = { /* 1.41421356 */
  1,
  2, 2, 2, 2,
  3,
  4, 4, 4, 4,
  5, 5,
  6,
  7, 7, 7,
};

#define MAGIC_LEN 8
int magic[MAGIC_LEN] = { 5, 1, 7, 3, 4, 6, 2, 5 }; // eagcdfbe

#define SIZE (sizeof(ar) / sizeof(ar[0]))
#undef ALL_PRINT

void print_seq(int a[], int len) {
  for (int i = 0; i < len; i++) {
    printf("%d", a[i]);
  }
}

int match_seq(int a[], int alen, int b[], int blen) {
  if (alen != blen) {
    return 0;
  }
  for (int i = 0; i < alen; i++) {
    if (a[i] != b[i]) {
      return 0;
    }
  }
  return 1;
}

int main(int argc, char *argv[]) {
  int n = SIZE;
  int a[SIZE];
  int tail = 0;
  int j, k, l;
  int t;
  time_t t1, t2, t3;
  unsigned long count = 0;

  t1 = time(NULL);
  printf("(start) %s", ctime(&t1));
  t2 = t1;

  for (int i = 0; i < SIZE; i++) {
    a[i] = ar[i];
  }
  
  while (1) {
    for (int k = tail; k < n; k++) {
      count += 1;
      if (match_seq(a, k + 1, magic, MAGIC_LEN)) {
        printf("%lu:", count);
        print_seq(a, k + 1);
        printf(" found!\n");
      }
#ifdef ALL_PRINT
      printf("%lu:", count);
      print_seq(a, k + 1);
      printf("\n");
#endif
    }
    j = n - 2;
    while (j >= 0 && a[j] >= a[j + 1]) {
      j -= 1;
    }
    if (j < 0) {
      break;
    }
    l = n - 1;
    while (l >= 0 && a[j] >= a[l]) {
      l -= 1;
    }
    t = a[j];
    a[j] = a[l];
    a[l] = t;
    tail = j;
    k = j + 1;
    l = n - 1;
    while (k < l) {
      int t = a[k];
      a[k] = a[l];
      a[l] = t;
      k += 1;
      l -= 1;
    }

    if (t2 + 10 < time(NULL)) {
      t2 = time(NULL);
      printf("%lu: %s", count, ctime(&t2));
      print_seq(a, SIZE);
      printf("\n");
    }
  }

  t3 = time(NULL);

  printf("count : %lu\n", count);
  printf("start : %s", ctime(&t1));
  printf("  end : %s", ctime(&t3));
}

gemstring1.rb

class Array
  def mpermute(&proc)
    a = self
    n = a.size
    p = 0
    loop do
      p.upto(n - 1) do |k|
        proc.call(*a[0..k])
      end
      p = n - 2
      loop do
        return if p < 0
        break if a[p] < a[p + 1]
        p -= 1
      end
      q = n - 1
      while a[p] >= a[q]
        q -= 1
      end
      a[p], a[q] = a[q], a[p]
      s = p + 1
      e = n - 1
      while s < e
        a[s], a[e] = a[e], a[s]
        s += 1
        e -= 1
      end
    end
  end
end

def find_pattern(gems, pattern)
  start = Time.now
  i = 0
  gems.split(//).mpermute do |*a|
    s = a.join
    i += 1
    if pattern == s
      puts "#{i}:#{a.join} FOUND! #{Time.now - start} sec."
      return
    end
    if i % 10_000_000 == 0
      puts "#{i}: #{Time.now - start} sec: #{i * 100.0 / 5_578_864_439}%"
    end
  end
end

find_pattern("aaabcc", "ccbaaa")
find_pattern("abbbbcddddeefggg", "eagcdfbe")

gemstring2.rb

class Hash
  # {"a"=>3,"b"=>1, "c"=>2}.gemify => "aaabcc"
  def gemify
    s = ''
    keys.sort.each do |c|
      s += c * self[c]
    end
    s
  end
end

class Array
  # ['a', 'b'].is_prefix_of(['a', 'b', 'c', 'd']) #=> true
  def is_prefix_of(a)
    size.times do |i|
      if self[i] != a[i]
        return false
      end
    end
    return true
  end
end

class GemString
  def count(h)
    counter = 0
    h.keys.sort.each do |k|
      if h[k] > 0
        @gemstack.push(k)
        @days += 1
        puts "#{@days}:#{@gemstack.join}" if $DEBUG
        if @gemstack.join == @pattern
          puts "#{@days}:#{@gemstack.join} FOUND!"
        end
        h[k] -= 1
        tail = h.gemify
        if tail == ""
          # No need to add.
        elsif @gemstack.is_prefix_of(@pattern.split(//)) or not @memo[tail]
          @memo[tail] = count(h)
          counter += @memo[tail]
          puts "Saved memo is #{tail}:#{@memo[tail]}." if $DEBUG
        else
          puts "Skip #{@memo[tail]} days." if $DEBUG
          @days += @memo[tail]
          counter += @memo[tail]
          puts "Used memo is #{tail}:#{@memo[tail]}." if $DEBUG
        end
        h[k] += 1
        @gemstack.pop
        counter += 1
      end
    end
    return counter
  end

  def gemcount
    h = Hash.new(0)
    @gems.split(//).each do |e|
      h[e] += 1
    end
    # h = {"a"=>3,"b"=>1, "c"=>2}
    @gemstack = []
    @days = 0
    @memo = {}
    return count(h)
  end

  def initialize(gems, pattern)
    @gems = gems
    @pattern = pattern
  end
end

GemString.new("aaabcc", "ccbaaa").gemcount
GemString.new("abbbbcddddeefggg", "eagcdfbe").gemcount