period문자열이 어떤 부분이 오버행 무시 자체 일치하도록 스트링의 최단 비제로 시프트된다. 예를 들어 abcabcabperiod가 3있습니다. 관례 적으로 우리는 그러한 시프트가 없다면 문자열의 길이는 길이와 같다고 말합니다. 기간 따라서 abcdeIS 5및 기간 a입니다 1.
보다 공식적인 용어로, 문자열의 기간은 (에서 색인화 )가 되도록 S최소 입니다.i > 0S[1,n-i] == S[i+1,n]1
두 길이의 거듭 제곱의 주어진 문자열 S에 대해, 우리는 두 길이의 거듭 제곱의 모든 접두사의주기를 계산합니다. 예를 들어을 고려하십시오 S = abcabcab. 우리가 계산할 기간은 다음과 같습니다.
'a', 1
'ab', 2
'abca', 3
'abcabcab', 3
실제로 마침표 배열을 출력합니다 [1, 2, 3, 3].
주어진 양의 2의 제곱에 n대해 가능한 모든 이진 문자열을 고려하십시오 S. 이진 문자열은 단순히 1s와 0s의 문자열 이므로 2^n이러한 문자열 (즉 2, 거듭 제곱 n)이 있습니다. 각각에 대해이 기간 배열을 계산할 수 있습니다.
문제는
n입력으로 (2의 거듭 제곱) 코드를 작성 하고 그러한 배열이 얼마나 많은지를 계산하는 것입니다.
이에 대한 답변 n = 1, 2, 4, 8, 16, 32, 64, 128은 다음과 같습니다.
1, 2, 6, 32, 320, 6025, 216854, 15128807
고유 한 기간 배열의 전체 세트 n = 4는 다음과 같습니다.
1, 1, 1
1, 1, 3
1, 1, 4
1, 2, 2
1, 2, 3
1, 2, 4
점수
Ubuntu를 실행하는 컴퓨터에서 10 분 동안 코드를 실행합니다. 귀하의 점수는 n해당 시간에 코드가 종료되는 최대 점수입니다 . 동점 인 경우, 가장 큰 공동으로 가장 n빠른 답이 이깁니다. 타이밍이 1 초 이내에 동점 인 경우 첫 번째 답변이 승리합니다.
언어와 라이브러리
원하는 언어와 라이브러리를 사용할 수 있습니다. 가능하다면 리눅스에서 코드를 실행 / 컴파일하는 방법에 대한 자세한 설명을 포함하십시오 .`
코드는 실제로 미리 계산 된 값만 출력하는 것이 아니라 답변을 계산해야합니다.
주요 항목
- 2 분 21초 대한 N = 128 의 C 번호 피터 테일러
- isaacg의 Rust 에서 n = 32 에 대해 9 초
답변
약 2:40에서 C #, n = 128
using System;
using System.Collections.Generic;
using System.Linq;
namespace Sandbox
{
class PPCG137436
{
public static void Main(string[] args)
{
if (args.Length == 0) args = new string[] { "1", "2", "4", "8", "16", "32", "64", "128" };
foreach (string arg in args)
{
Console.WriteLine(Count(new int[(int)(0.5 + Math.Log(int.Parse(arg)) / Math.Log(2))], 0));
}
}
static int Count(int[] periods, int idx)
{
if (idx == periods.Length)
{
//Console.WriteLine(string.Join(", ", periods));
return 1;
}
int count = 0;
int p = idx == 0 ? 1 : periods[idx - 1];
for (int q = p; q <= 1 << (idx + 1); q++)
{
periods[idx] = q;
if (q == p || q > 1 << idx || p + q - Gcd(p, q) > 1 << idx && UnificationPasses(periods, idx, q)) count += Count(periods, idx + 1);
}
return count;
}
private static int Gcd(int a, int b)
{
while (a > 0) { int tmp = a; a = b % a; b = tmp; }
return b;
}
private static bool UnificationPasses(int[] periods, int idx, int q)
{
UnionSet union = new UnionSet(1 << idx);
for (int i = 0; i <= idx; i++)
{
for (int j = 0; j + periods[i] < Math.Min(2 << i, 1 << idx); j++) union.Unify(j, j + periods[i]);
}
IDictionary<int, long> rev = new Dictionary<int, long>();
for (int k = 0; k < 1 << idx; k++) rev[union.Find(k)] = 0L;
for (int k = 0; k < 1 << idx; k++) rev[union.Find(k)] |= 1L << k;
long zeroes = rev[union.Find(0)]; // wlog the value at position 0 is 0
ISet<int> onesIndex = new HashSet<int>();
// This can be seen as the special case of the next loop where j == -1.
for (int i = 0; i < idx; i++)
{
if (periods[i] == 2 << i) onesIndex.Add((2 << i) - 1);
}
for (int j = 0; j < idx - 1 && periods[j] == 2 << j; j++)
{
for (int i = j + 1; i < idx; i++)
{
if (periods[i] == 2 << i)
{
for (int k = (1 << j) + 1; k <= 2 << j; k++) onesIndex.Add((2 << i) - k);
}
}
}
for (int i = 1; i < idx; i++)
{
if (periods[i] == 1) continue;
int d = (2 << i) - periods[i];
long dmask = (1L << d) - 1;
if (((zeroes >> 1) & (zeroes >> periods[i]) & dmask) == dmask) onesIndex.Add(periods[i] - 1);
}
long ones = 0L;
foreach (var key in onesIndex) ones |= rev[union.Find(key)];
if ((zeroes & ones) != 0) return false; // Definite contradiction!
rev.Remove(union.Find(0));
foreach (var key in onesIndex) rev.Remove(key);
long[] masks = System.Linq.Enumerable.ToArray(rev.Values);
int numFilteredMasks = 0;
long set = 0;
long M = 0;
for (int i = 1; i <= idx; i++)
{
if (periods[i - 1] == 1) continue;
// Sort the relevant masks to the start
if (i == idx) numFilteredMasks = masks.Length; // Minor optimisation: skip the filter because we know we need all the masks
long filter = (1L << (1 << i)) - 1;
for (int j = numFilteredMasks; j < masks.Length; j++)
{
if ((masks[j] & filter) != 0)
{
var tmp = masks[j];
masks[j] = masks[numFilteredMasks];
masks[numFilteredMasks++] = tmp;
}
}
// Search for a successful assignment, using the information from the previous search to skip a few initial values in this one.
set |= (1L << numFilteredMasks) - 1 - M;
M = (1L << numFilteredMasks) - 1;
while (true)
{
if (TestAssignment(periods, i, ones, masks, set)) break;
if (set == 0) return false; // No suitable assignment found
// Gosper's hack with variant to reduce the number of bits on overflow
long c = set & -set;
long r = set + c;
set = (((r ^ set) >> 2) / c) | (r & M);
}
}
return true;
}
private static bool TestAssignment(int[] periods, int idx, long ones, long[] masks, long assignment)
{
for (int j = 0; j < masks.Length; j++, assignment >>= 1) ones |= masks[j] & -(assignment & 1);
for (int i = idx - 1; i > 0; i--) // i == 0 is already handled in the unification process.
{
if (Period(ones, 2 << i, periods[i - 1]) < periods[i]) return false;
}
return true;
}
private static int Period(long arr, int n, int min)
{
for (int p = min; p <= n; p++)
{
// If the bottom n bits have period p then the bottom (n-p) bits equal the bottom (n-p) bits of the integer shifted right p
long mask = (1L << (n - p)) - 1L;
if ((arr & mask) == ((arr >> p) & mask)) return p;
}
throw new Exception("Unreachable");
}
class UnionSet
{
private int[] _Lookup;
public UnionSet(int size)
{
_Lookup = new int[size];
for (int k = 0; k < size; k++) _Lookup[k] = k;
}
public int Find(int key)
{
var l = _Lookup[key];
if (l != key) _Lookup[key] = l = Find(l);
return l;
}
public void Unify(int key1, int key2)
{
int root1 = Find(key1);
int root2 = Find(key2);
if (root1 < root2) _Lookup[root2] = root1;
else _Lookup[root1] = root2;
}
}
}
}n = 256으로 확장하려면 BigInteger마스크 로 전환해야합니다.이 경우 n = 256은 물론 새로운 아이디어없이 n = 128이 통과하기에는 성능이 너무 많이 저하 될 수 있습니다.
Linux에서는로 컴파일 mono-csc하고로 실행하십시오 mono.
기본 설명
나는 한 줄씩 해부하지 않고 개념에 대한 개요를 할 것입니다.
경험상, 나는 무차별 조합 프로그램에서 2 ~ 50 개의 요소 를 반복해서 기쁘다 . 따라서 n = 128이 되려면 모든 비트 열을 분석하지 않는 접근 방식을 사용해야합니다. 따라서 비트 문자열에서 기간 시퀀스로 진행하는 대신 역순으로 작업합니다.주기 시퀀스가 주어지면 그것을 인식하는 비트 문자열이 있습니까? n = 2 x 의 경우 2 x (x + 1) / 2 주기 시퀀스 의 쉬운 상한이 있습니다 (vs 2 2 x 비트 스트링).
일부 인수는 문자열 주기성 정리를 사용합니다 .
하자
p및q길이의 문자열의 두 기간 수n. 경우p + q ≤ n + gcd(p, q)한 다음gcd(p, q)또한 문자열의 기간입니다.
Wlog 고려중인 모든 비트 문자열이로 시작한다고 가정합니다 0.
길이 2 i 의 접두어주기 ( 항상) 인주기 순서 가 주어지면 가능한 값에 대해 쉽게 관찰 할 수 있습니다 .[p1 p2 ... pk]pip0 = 1pk+1
-
pk+1 ≥ pk문자열S의 기간은 접두사의 기간이기도합니다S. -
pk+1 = pk항상 가능한 확장입니다. 동일한 기본 문자열을 두 배나 많은 문자로 반복하면됩니다. -
2k < pk+1 ≤ 2k+1항상 가능한 확장입니다. 첫 번째 문자가 아닌 문자를 추가 하여 비 주기적 길이의 문자열을 비 주기적 길이의 문자열로 확장 할 수 있기 때문에 이를 표시하기에 충분합니다 .pk+1 = 2k+1LL+1문자열을 받아
Sx길이 2의 K 그 기간을 하고 문자열을 고려 길이 2의 K + 1 . 분명히 갖는다 기간 2 K +1있다. 기간 이 짧다고 가정하십시오 .pkSxySSxySq따라서 주기성에 의한 정리 는 기간이며 , 최대 제수는 인수보다 작거나 같고 가장 작은 기간이므로 2 k +1 의 적절한 인수가 되어야합니다 . 몫이 2 일 수 없으므로을 갖습니다 .
2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q)gcd(2k+1, q)SxySqqq ≤ (2k+1)/3이제는 기간이므로의 기간 이어야합니다 . 그러나 의 기간은 입니다 . 우리는 두 가지 경우가 있습니다 :
q ≤ 2kSxySSxSxpkgcd(pk, q) = pk또는 으로 정확하게 나눕니다 .pkqpk + q > 2k + gcd(pk, q)주기성 정리는 더 작은주기를 강요하지 않습니다.
먼저 두 번째 경우를 고려하십시오. 의 기간으로서의 정의와 모순 됩니다. 따라서 우리 는의 요소 인 결론에 강요됩니다 .
pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2qpkSxpkq하지만 이후
q의 기간Sx과 의 기간 , 길이의 접두어는 그냥 길이의 접두사의 사본을 우리가 볼 수 있도록, 또한 기간입니다 .pkSxqq/pkpkpkSxyS따라서 기간이
SxyS하나 인 2 K +1. 그러나 두 가지 옵션이 있습니다 ! 최대 하나의 선택 기간이주기를 제공 하므로 적어도 하나의 선택 기간은 2 k +1입니다. QED.pkyypk -
주기성 정리를 통해 나머지 가능한 확장 중 일부를 거부 할 수 있습니다.
-
빠른 수락 또는 빠른 거부 테스트를 통과하지 못한 확장은 건설적으로 테스트해야합니다.
주기 시퀀스가 주어진 비트 스트링의 구성은 본질적으로 만족스러운 문제이지만 많은 구조를 가지고 있습니다. 거기에 내가 사용할 수 있도록, 각 접두사 기간 암시 간단한 평등 제약 노동 조합 세트 독립 클러스터로 비트를 결합하는 데이터 구조. 이것은 n = 64를 해결하기에 충분했지만 n = 128의 경우 계속 진행해야했습니다. 나는 두 가지 유용한 주장을한다 :2k - pk
- 길이 접두어
M가 있고 길이 접두어에 마침표 가 있으면 길이 접두사 가로 끝나야합니다 . 이것은 독립적 인 클러스터가 가장 많은 경우에 가장 강력하며 편리합니다.01M-1L > MLL1M - 길이 접두어
M가 있고 길이 접두사 가 마침표 로 끝나고 끝나는 경우 실제로로 끝나야합니다 . 이것은주기 순서가 많은 것으로 시작될 때 반대의 극단에서 가장 강력합니다.0ML > ML - dd < M0d10d
첫 번째 비트 (0으로 가정)를 가진 클러스터를 1로 강제하여 즉각적인 모순을 얻지 못하면 강제되지 않은 클러스터의 가능한 값에 대해 (일부 마이크로 최적화로) 강제합니다. 순서는 내림차순입니다. ith 비트가 1이면 마침표가 될 수 없으며 i클러스터링에 의해 이미 시행 된 마침표보다 짧은 마침표를 피하려고합니다. 내려 가면 유효한 과제를 조기에 찾을 가능성이 높아집니다.
답변
Rust, 32, 10s 11s 29s 내 노트북에서
비트 라인을 명령 행 인수로 사용하여 호출하십시오.
영리한 기술 : 비트 스트링을 숫자로 직접 표시하고 비트 트래들 링을 사용하여주기를 확인하십시오. 비트 스트링의 기간 배열과 그 역수 (1은 1로 교체 됨)가 동일하므로 비트 스트링의 첫 절반 만 0으로 시작하는 문자열 만 검색하십시오. 최종 위치에 대한 모든 가능성이 이미 발생한 경우 검색하지 않습니다.
더 영리한 것들 :
각 블록 (비트의 전반이 동일한 문자열)을 중복 제거하려면 최종 사이클 길이에 해시가 필요하지 않기 때문에 비트 벡터를 사용합니다. 해시 세트보다 훨씬 빠릅니다.
또한 마지막 사이클이 두 번째에서 마지막 사이클보다 짧을 수 없다는 것을 알고 있기 때문에 사이클 검사의 첫 번째 단계를 건너 뜁니다.
프로파일 링을 많이 한 후에는 거의 모든 시간이 생산적으로 사용되고 있음을 알 수 있으므로 여기에서 알고리즘 개선이 필요하다고 생각합니다. 또한 시간을 조금 더 절약하기 위해 32 비트 정수로 전환했습니다.
//extern crate cpuprofiler;
//use cpuprofiler::PROFILER;
extern crate bit_vec;
use bit_vec::BitVec;
use std::collections::HashSet;
fn cycle_len(num: u32, mask: u32, skip_steps: usize) -> usize {
let mut left = num >> skip_steps;
let mut mask = mask >> skip_steps;
let mut steps = skip_steps;
loop {
left >>= 1;
if left == (num & mask) {
return steps;
}
mask >>= 1;
steps += 1;
}
}
fn all_cycles(size_log: usize) -> HashSet<Vec<usize>> {
let mut set = HashSet::new();
if size_log == 0 {
set.insert(vec![]);
return set;
} else if size_log == 1 {
set.insert(vec![0]);
set.insert(vec![1]);
return set;
}
let size: usize = 1 << size_log;
let half_size: usize = 1 << size_log - 1;
let shift_and_mask: Vec<(usize, u32)> = (1..size_log)
.map(|subsize_log| {
let subsize = 1 << subsize_log;
(size - subsize, (1 << (subsize - 1)) - 1)
})
.collect();
let size_mask = (1 << (size - 1)) - 1;
for block in 0..(1 << (half_size - 1)) as u32 {
let start: u32 = block << half_size;
if block % 1024 == 0 {
eprintln!(
"{} ({:.2}%): {}",
start,
start as f64 / (1u64 << size - 1) as f64 * 100f64,
set.len()
);
}
let leader = {
let mut cycles = Vec::new();
for &(shift, mask) in &shift_and_mask {
let subnum = start >> shift;
cycles.push(cycle_len(subnum, mask, 0));
}
cycles
};
let &end = leader.last().unwrap();
if (end..size).all(|count| {
let mut new = leader.clone();
new.push(count);
set.contains(&new)
})
{
continue;
}
let mut subset = BitVec::from_elem(size, false);
for num in start..start + (1 << half_size) {
subset.set(cycle_len(num, size_mask, end), true);
}
for (unique_cycle_len, _) in subset.into_iter().enumerate().filter(|x| x.1) {
let mut new_l = leader.clone();
new_l.push(unique_cycle_len);
set.insert(new_l);
}
}
set
}
fn main() {
let size: f32 = std::env::args().nth(1).unwrap().parse().unwrap();
let size_log = size.log2() as usize;
//PROFILER.lock().unwrap().start("./my-prof.profile").unwrap();
let cycles = all_cycles(size_log);
//PROFILER.lock().unwrap().stop().unwrap();
println!(
"Number of distinct arrays of periods of bitstrings of length {} is {}",
1 << size_log,
cycles.len()
);
}
bit-vec = "0.4.4"당신의 Cargo.toml에 넣으십시오
이것을 실행하려면 github.com/isaacg1/cycle을 복제 한 다음 Cargo build --release빌드 Cargo run --release 32하고 실행하십시오.
답변
녹 , 16
use std::collections::HashSet;
use std::io;
fn main() {
print!("Enter a pow of two:");
let mut input_text = String::new();
io::stdin()
.read_line(&mut input_text)
.expect("failed to read from stdin");
let n_as_string = input_text.trim();
match n_as_string.parse::<usize>() {
Ok(n) => {
let log2 = (n as f64).log(2_f64) as usize;
if n != 1 << log2 {
panic!("{} is not a power of two", n);
}
let count = compute_count_array(log2, n);
println!("n = {} -> count = {}", n, count);
}
Err(_) => { panic!("{} is not a number", n_as_string); }
}
}
fn compute_count_array(log2:usize, n: usize) -> usize {
let mut z = HashSet::new();
let mut s:Vec<bool> = vec!(false; n);
loop {
let mut y:Vec<usize> = vec!();
for j in 0..log2+1 {
let p = find_period(&s[0..1<<j]);
y.push(p);
}
z.insert(y);
if !next(&mut s) {
break;
}
}
z.len()
}
#[inline]
fn find_period(s: &[bool]) -> usize {
let n=s.len();
let mut j=1;
while j<n {
if s[0..n-j] == s[j..n] {
return j;
}
j+=1;
}
n
}
#[inline]
fn next(s:&mut Vec<bool>) -> bool {
if s[0] {
s[0] = false;
for i in 1..s.len() {
if s[i] {
s[i] = false;
} else {
s[i] = true;
return true;
}
}
return false
} else {
s[0] = true;
}
true
}편집: rustc -O <name>.rs
문자열은 Bool 벡터로 구현됩니다.
-
next조합을 통한 기능으로 반복; -
는
find_period부울 슬라이스 소요 기간을 반환 -
이
compute_count_array작업은 Bool의 각 조합에 대한 “2의 거듭 제곱”하위 시퀀스에 대한 작업을 수행합니다.
이론적으로 2^nu64 최대 값을 초과 할 때까지 오버플로는 예상되지 않습니다 n > 64. 이 한계는 s = [true, true, …, true]에서 값 비싼 테스트를 통해 도달 할 수 있습니다.
나쁜 소식은 n = 16에 대해 317을 반환하지만 이유를 모르겠습니다. n = 32에 대해 10 분 안에 만들지 모르겠습니다 Vec<bool>. 왜냐하면이 종류의 계산에 최적화되어 있지 않기 때문 입니다.
편집하다
-
에 대한 한도 인 64 개를 제거했습니다
n. 이제n최대 사용 정수보다 클 때까지 충돌하지 않습니다 . -
이전 코드가에 대해 317을 반환 한 이유를 찾았습니다
n=32. 나는 계산 된 세트 기간과하지의 배열 기간을. 동일한 요소를 가진 3 개의 배열이있었습니다 :
[1, 2, 3, 3, 8] -> {1, 2, 3, 8} [1, 2, 3, 8, 8] -> {1, 2, 3, 8} [1, 1, 3, 3, 7] -> {1, 3, 7} [1, 1, 3, 7, 7] -> {1, 3, 7} [1, 1, 3, 3, 8] -> {1, 3, 8} [1, 1, 3, 8, 8] -> {1, 3, 8}
이제 작동합니다. 여전히 느리지 만 작동합니다.
답변
C-16
오버 플로우의 16 cuz보다 큰 값에서는 실패합니다.
나는 이것이 repl.it에서 그것을 실행하는 크롬 북에서 얼마나 빨리 cuz im을 실행하는지 전혀 모른다.
읽은대로 질문을 구현하고 모든 비트 문자열을 거치며 기간 배열을 계산하고 이미 계산되었는지 확인합니다.
#include "stdio.h"
#include <stdbool.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
int per(int s[], int l) {
int period = 0;
while (1) {
period++;
bool check = 1;
int i;
for (i=0; i<l-period; i++) {
if (s[i]!=s[i+period]) {
check = 0;
break;
}
}
if (check) {
return period;
}
}
}
bool perar(int* s, int l, int* b, int i) {
int n = 1;
int j=0;
while (n<=l) {
b[i*l+j] = per(s, n);
n=n<<1;
j++;
}
for (j=0;j<i;j++) {
int k;
bool check = 1;
for(k=0; k<l; k++) {
if (b[j*l+k] != b[i*l+k]) {
check = 0;
break;
}
}
if (check) {
return 0;
}
}
return 1;
}
int main(int argc, char* argv[]) {
int n;
scanf("%d", &n);
puts("Running...");
int i;
int c = 0;
int* a = malloc(n*sizeof(int));
int m=pow(2, n);
int* b = malloc(m*n*sizeof(int));
for (i=0; i<m; i++) {
int j;
for (j=0; j<n; j++) {
a[j] = (i>>j)&1;
}
c+=perar(a, n, b, i);
}
printf("Answer: %d\n", c);
return 0;
}
gcc 등으로 컴파일하십시오.
답변
하스켈
import qualified Data.Set as S
import Data.Bits
period :: Int -> Int -> Int
period num bits = go (bits-2) (div prefix 2) (clearBit prefix $ bits-1)
where
prefix = (2^bits-1) .&. num
go p x y
| x == y = p
| otherwise = go (p-1) (div x 2) (clearBit y p)
allPeriods :: Int -> [[Int]]
allPeriods n = map periods [0..div(2^n)2-1]
where
periods num = map (period num) powers
powers = takeWhile (<=n) $ iterate (*2) 2
main = readLn >>= print . S.size . S.fromList . allPeriods
로 컴파일하십시오 ghc -O2. 온라인으로 사용해보십시오!
에 대한 내 6 년 된 랩톱 하드웨어에서 0.1 초 이내에 실행됩니다 n=16. 99 92 분이 n=32걸리므로 9 또는 10을 배제합니다. 룩업 테이블에서 기간을 캐싱하려고 시도하여 반복해서 다시 계산할 필요가 없지만 4GB 시스템의 메모리가 빨리 소모됩니다.
답변
파이썬 2 (PyPy), 16
import sys
import math
def do(n):
masks=[]
for i in range(n):
masks+=[(1<<((2<<i)-1))-1]
s=set()
bits=1<<n
for i in xrange(1<<bits):
r=[0,]*n
for j in range(len(masks)):
mask=masks[j]
k,c=i>>bits-(2<<j),1
d=k>>1
while k&mask^d:
d>>=1
mask>>=1
c+=1
r[j]=c
s|={tuple(r)}
return len(s)
print do(int(math.log(int(sys.argv[1]),2)))
답변
[C ++], 32 분, 4 분
#include <iostream>
#include <vector>
typedef unsigned int u;
template<typename T, typename U>
u Min(T a, U b) {
return a < b ? a : b;
}
template<typename T, typename U>
u Max(T a, U b) {
return a > b ? a : b;
}
u Mask(int n) {
if (n < 0) n = 0;
return ~((u)(-1) << n);
}
u MASKS[32];
inline u Rshift(u v, int n) {
return n < 0 ? v >> (-1*n)
: n > 0 ? v << n
: n;
}
int GetNextPeriodId(u pattern, int pattern_width, int prior_id) {
int period = (prior_id % (pattern_width>>1)) + 1;
int retval = prior_id * pattern_width;
for (; period < pattern_width; period+=1) {
u shift = pattern >> period;
int remainder = pattern_width-period;
u mask = MASKS[period];
for (;remainder >= period && !((pattern ^ shift) & mask);
shift >>= period, remainder -= period);
if (remainder > period) continue;
if (remainder == 0 || !((pattern ^ shift) & MASKS[remainder])) {
retval += (period-1);
break;
}
}
if (period == pattern_width) {
retval += pattern_width-1;
}
return retval;
}
int ParseInput(int argc, char** argv) {
if (argc > 1) {
switch(atoi(argv[1])) {
case 1:
return 1;
case 2:
return 2;
case 4:
return 4;
case 8:
return 8;
case 16:
return 16;
case 32:
return 32;
default:
return 0;
}
}
return 0;
}
void PrintId(u id, int patternWidth) {
for(;patternWidth > 0; id /= patternWidth, patternWidth >>= 1) {
std::cout << (id % patternWidth)+1 << ",";
}
std::cout << std::endl;
}
int TestAndSet(std::vector<bool>& v, int i) {
int retval = v[i] ? 0 : 1;
v[i] = true;
return retval;
}
std::vector<bool> uniques(1<<15);
int uniqueCount = 0;
void FillUniques(u i, int id, int target_width, int final_width) {
int half_size = target_width / 2;
u end = 1u<<(half_size-1);
u mask = MASKS[half_size];
u lowers[] = { i, (~i)&mask };
for (u j = 0ul; j < end; j++) {
u upper = j << half_size;
u patterns[] = { (upper|lowers[0]), (upper|lowers[1]) };
for (int k=0; k < sizeof(patterns)/sizeof(patterns[0]); k+=1) {
int fid = GetNextPeriodId(patterns[k], target_width, id);
if (target_width != final_width) {
FillUniques(patterns[k], fid, target_width*2, final_width);
} else {
if (TestAndSet(uniques, fid)) {
uniqueCount += 1;
}
}
}
}
}
int main(int argc, char** argv) {
for (int i = 0; i < 32; i++) {
MASKS[i] = Mask(i);
}
int target_width = 32; // ParseInput(argc, argv);
if (!target_width) {
std::cout << "Usage: " << argv[0] << " [1|2|4|8|16|32]" << std::endl;
return 0;
}
if (target_width == 1) {
std::cout << 1 << std::endl;
return 0;
}
FillUniques(0, 0, 2, target_width);
std::cout << uniqueCount << std::endl;
return 0;
}