Instantly share code, notes, and snippets.

# hyuki0000/gemstring.c

Created February 13, 2014 23:43
Show Gist options
• Save hyuki0000/8986369 to your computer and use it in GitHub Desktop.
《ジェムストリング問題》の参考プログラム
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #include #include #include 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)); }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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")
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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