period
문자열이 어떤 부분이 오버행 무시 자체 일치하도록 스트링의 최단 비제로 시프트된다. 예를 들어 abcabcab
period가 3
있습니다. 관례 적으로 우리는 그러한 시프트가 없다면 문자열의 길이는 길이와 같다고 말합니다. 기간 따라서 abcde
IS 5
및 기간 a
입니다 1
.
보다 공식적인 용어로, 문자열의 기간은 (에서 색인화 )가 되도록 S
최소 입니다.i > 0
S[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
. 이진 문자열은 단순히 1
s와 0
s의 문자열 이므로 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]
pi
p0 = 1
pk+1
-
pk+1 ≥ pk
문자열S
의 기간은 접두사의 기간이기도합니다S
. -
pk+1 = pk
항상 가능한 확장입니다. 동일한 기본 문자열을 두 배나 많은 문자로 반복하면됩니다. -
2k < pk+1 ≤ 2k+1
항상 가능한 확장입니다. 첫 번째 문자가 아닌 문자를 추가 하여 비 주기적 길이의 문자열을 비 주기적 길이의 문자열로 확장 할 수 있기 때문에 이를 표시하기에 충분합니다 .pk+1 = 2k+1
L
L+1
문자열을 받아
Sx
길이 2의 K 그 기간을 하고 문자열을 고려 길이 2의 K + 1 . 분명히 갖는다 기간 2 K +1있다. 기간 이 짧다고 가정하십시오 .pk
SxyS
SxyS
q
따라서 주기성에 의한 정리 는 기간이며 , 최대 제수는 인수보다 작거나 같고 가장 작은 기간이므로 2 k +1 의 적절한 인수가 되어야합니다 . 몫이 2 일 수 없으므로을 갖습니다 .
2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q)
gcd(2k+1, q)
SxyS
q
q
q ≤ (2k+1)/3
이제는 기간이므로의 기간 이어야합니다 . 그러나 의 기간은 입니다 . 우리는 두 가지 경우가 있습니다 :
q ≤ 2k
SxyS
Sx
Sx
pk
gcd(pk, q) = pk
또는 으로 정확하게 나눕니다 .pk
q
pk + q > 2k + gcd(pk, q)
주기성 정리는 더 작은주기를 강요하지 않습니다.
먼저 두 번째 경우를 고려하십시오. 의 기간으로서의 정의와 모순 됩니다. 따라서 우리 는의 요소 인 결론에 강요됩니다 .
pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2q
pk
Sx
pk
q
하지만 이후
q
의 기간Sx
과 의 기간 , 길이의 접두어는 그냥 길이의 접두사의 사본을 우리가 볼 수 있도록, 또한 기간입니다 .pk
Sx
q
q/pk
pk
pk
SxyS
따라서 기간이
SxyS
하나 인 2 K +1. 그러나 두 가지 옵션이 있습니다 ! 최대 하나의 선택 기간이주기를 제공 하므로 적어도 하나의 선택 기간은 2 k +1입니다. QED.pk
y
y
pk
-
주기성 정리를 통해 나머지 가능한 확장 중 일부를 거부 할 수 있습니다.
-
빠른 수락 또는 빠른 거부 테스트를 통과하지 못한 확장은 건설적으로 테스트해야합니다.
주기 시퀀스가 주어진 비트 스트링의 구성은 본질적으로 만족스러운 문제이지만 많은 구조를 가지고 있습니다. 거기에 내가 사용할 수 있도록, 각 접두사 기간 암시 간단한 평등 제약 노동 조합 세트 독립 클러스터로 비트를 결합하는 데이터 구조. 이것은 n = 64를 해결하기에 충분했지만 n = 128의 경우 계속 진행해야했습니다. 나는 두 가지 유용한 주장을한다 :2k - pk
- 길이 접두어
M
가 있고 길이 접두어에 마침표 가 있으면 길이 접두사 가로 끝나야합니다 . 이것은 독립적 인 클러스터가 가장 많은 경우에 가장 강력하며 편리합니다.01M-1
L > M
L
L
1M
- 길이 접두어
M
가 있고 길이 접두사 가 마침표 로 끝나고 끝나는 경우 실제로로 끝나야합니다 . 이것은주기 순서가 많은 것으로 시작될 때 반대의 극단에서 가장 강력합니다.0M
L > M
L - d
d < M
0d
10d
첫 번째 비트 (0으로 가정)를 가진 클러스터를 1로 강제하여 즉각적인 모순을 얻지 못하면 강제되지 않은 클러스터의 가능한 값에 대해 (일부 마이크로 최적화로) 강제합니다. 순서는 내림차순입니다. i
th 비트가 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^n
u64 최대 값을 초과 할 때까지 오버플로는 예상되지 않습니다 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;
}