Skip to content

Instantly share code, notes, and snippets.

@hyuki0000
Created February 13, 2014 23:43
Embed
What would you like to do?
《ジェムストリング問題》の参考プログラム
#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));
}
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")
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment