Распечатать пересечение последовательностей

9

Последовательности

Вам даны четыре числовые последовательности, пронумерованные до 1конца 4.

  1. OEIS Местоположение 0's, когда натуральные числа перечислены в двоичном виде. Вот пример того, как рассчитать последовательность:

     0,1,10,11,100,101,110,111
     ^    ^     ^^  ^    ^
     0    3     78  10   14
    

    Начало последовательности выглядит так: 0, 3, 7, 8, 10, 14, 19, 20, 21, 23, 24, 27, 29, 31, 36, 37, 40, 45, 51, ...


  1. OEIS Эта последовательность включает в себя первое натуральное число, пропускает следующие два, затем включает следующие три, затем пропускает следующие четыре и продолжает.

     0, 3, 4, 5, 10, 11, 12, 13, 14, 21, 22, 23, 24, 25, 26, 27, 36, ...
    

  1. OEIS Положительные целые числа, где как число 0's, так и число 1' s в двоичном представлении числа являются степенями 2.

    2, 4, 5, 6, 9, 10, 12, 16, 23, 27, 29, 30, 33, 34, 36, 39,
    

  1. OEIS Q последовательность Хофштадтера .

    а (1) = а (2) = 1;
    a (n) = a (na (n-1)) + a (na (n-2)) для n> 2.

    1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, 12, 12, 12, 16, 14, ...
    

    Мало что строго доказано об этой последовательности, но существует много эмпирических результатов. Один из них особенно важен, и вы можете предположить, что он действителен для всей серии:

    В этой статье отмечается, что элементы ряда могут быть сгруппированы в поколения. Если мы нумеруем их, начиная с 1, то k- е поколение содержит ровно 2 k элементов. Соответствующим свойством является то, что все числа в поколении k получаются суммированием двух чисел из поколений k-1. и / или k-2 , но никогда из предыдущих поколений. Вы можете использовать это (и только это) наблюдение, чтобы установить нижнюю границу для оставшихся элементов в последовательности.


Вызов

Ваша задача - напечатать первые xчисла на пересечении заданных входных последовательностей.

Ввод: два числа, разделенные пробелом STDIN. Первое число представляет собой целое число от 1до 15включительно, где каждый бит соответствует последовательности. Самый младший бит соответствует последовательности 1, а самый старший - последовательности 4. Второе количество цифр,x , на которое нужно вывести STDIN.

Выход: первые xчисла, которые пересекаются с заданными входными последовательностями. Распечатать цифры наSTDOUT с любым свободным пробелом или пунктуацией в качестве разделителя (пробелы, символы табуляции, новые строки, запятые, двоеточия, точки и т. Д.).


Примеры

1. Напечатайте первые 3числа в каждой последовательности.

Входные данные: 15 3

Вывод: 10,23,40


2. Напечатайте первые 12числа в порядковом номере1 и 4.

Входные данные: 9 12

Вывод: 3,8,10,14,19,20,21,23,24,31,37,40


3. Распечатайте первый10 числа в последовательности 2.

Входные данные: 2 10

Вывод: 0,3,4,5,10,11,12,13,14,21


4. Напечатайте первые 6числа в последовательностях 3и4 .

Входные данные: 12 6

Вывод: 2,4,5,6,9,10


подробности

  • Вы можете распечатать вывод на ходу или все сразу в конце.

Огромное спасибо всем, кто помог с этим в чате! Этот вопрос получил большую выгоду от того, чтобы быть в песочнице .

hmatt1
источник
@chilemagic: На самом деле, как вы определяете «первые X чисел» на пересечении? Если вы возьмете обе последовательности в 12 5примере до одного и того же индекса, то 10действительно ли это будет раньше 9на пересечении ... например, как бы вы, просматривая последовательности, решили, пропустить ли вход 9№3 как возможное пересечение? Например, если бы в нем было № 3, 7вам нужно было бы пропустить его, так как этого нет в № 4
Claudiu
@Claudiu Ваши выведенные числа должны всегда увеличиваться, и каждое число будет появляться только один раз в вашем выводе.
hmatt1
Есть ли максимальный предел x?
Ypnypn
@ypnypn не кодирует ограничение жестко, но если ваш алгоритм очень медленный или не завершится для очень больших входных данных, это нормально. Это код гольф, так что вы можете быть неэффективны, чтобы сохранить байты.
hmatt1

Ответы:

2

Хаскелл, 495 442 402

import Data.List
d=1:1:1%2
f=filter
p 0="0"
p 1="1"
p n=p(div n 2)++p(mod n 2)
l=length
u z[a,b]=sort.head.dropWhile((<b).l)$m(nub.foldl1 intersect.y(tail.p$31-a).(`m`[d,f(v.group.sort.p)[1..],z#1,y(z>>=p)z]).take)z
w=(=='0')
v[a]=1>2
v x=all(all w.tail.p.l)x
y x=m snd.f(w.fst).zip x
x#n=n`take`x++drop(n+n+1)x#(n+2)
n%m=d!!(m-d!!n)+d!!(m-d!!(n-1)):m%(m+1)
main=interact$show.u[0..].m read.words
m=map

Работает достаточно хорошо. Вот пара примеров OP:

Flonk@home:~>echo 15 10 | codegolf
[10,23,40,57,58,139,147,149,212,228]
Flonk@home:~>echo 9 12 | codegolf
[3,8,10,14,19,20,21,23,24,31,37,40]
Flonk@home:~>echo 2 10 | codegolf
[0,3,4,5,10,11,12,13,14,21]
Flonk@home:~>echo 12 6 | codegolf
[2,4,5,6,9,10]
Flonk
источник
4

Python 3, 590 639 символов

from itertools import count as C
D=lambda n,t='1':bin(n).count(t)
Y=range
def O():
 for n in C(0):yield from bin(n)[2:]
def B():
 s=i=0
 while 1:
  i+=s
  for j in Y(i,i+s+1):yield j
  s+=2;i+=s-1
def s(i):return D(i)==1
def F():
 a=[1]*3
 for n in C(3):a+=[a[n-a[n-1]]+a[n-a[n-2]]];yield a[-1]
L,R=input().split()
J=[x for x,U in zip([F(),(n for n in C(0)if s(D(n,'0')-1)and s(D(n))),B(),(i for i,c in enumerate(O())if'1'>c)],"{0:04b}".format(int(L)))if U>'0']
X=[set()for _ in J]
M=[]
Z=int(R);K=1
while len(M)<Z:
 for x,j in zip(X,J):x.add(next(j))
 for _ in Y(K):X[0].add(next(J[0]));K+=1
 M=X[0]
 for x in X:M=M&x
print(sorted(M)[:Z])

Это простое решение: используйте генераторы для определения каждой из бесконечных последовательностей, и, пока пересечение недостаточно велико, добавьте шаг к каждой последовательности.

Чтобы учесть немонотонно увеличивающуюся последовательность Хофштадтера: на каждом шаге я генерирую вдвое больше для этой последовательности, например, 1, затем 2, 4, 8, 16, 32 и т. Д. Я думаю, что удовлетворяет границе, указанной в вопросе и это все еще достаточно быстро для всех тестовых случаев, представленных там.

Клаудиу
источник
2
Гольф: from itertools import count as C-> from itertools import* C=count, def s(i):return D(i)==1-> s=lambda i:D(i)==1(я даже не думаю, что эта функция делает его короче ...), "{0:04b}".format(int(L)))if U>'0'->"{0:04b}".format(int(L)))if'0'<U
Джастин
3

С # 1923

Это, вероятно, не самая короткая программа, но я нашел задачу интересной, так что вот мое решение.

Выполнение всех 4 с 35 номерами (15 35) занимает около 5 секунд.

Вы можете проверить это здесь , но обратите внимание, что если вы хотите OEIS4, количество цифр, которое вы хотите, должно быть маленьким, или netfiddle исчерпает память.

Golfed

using System;using System.Collections;using System.Collections.Generic;using System.Linq;class p{public static void Main(string[] args){int b=0;IEnumerable<int>a=null;foreach(char c in Convert.ToString(int.Parse(args[0]),2).Reverse()){++b;if(c=='0')continue;switch(b){case 1: a=d(a,e());break;case 2: a=d(a,f());break;case 3: a=d(a,g());break;case 4: a=d(a,h(),true);break;}}if(a==null)return;bool j=true;foreach(int i in a.Take(int.Parse(args[1]))){if(j)j=false;else Console.Write(",");Console.Write(i);}}static IEnumerable<int>d(IEnumerable<int>k,IEnumerable<int>l,bool m=false){if(k==null)foreach(int n in l)yield return n;int o=0;int p=1;foreach(int i in k){Dictionary<int,HashSet<int>>q=m ? new Dictionary<int,HashSet<int>>(): null;int s=0;foreach(int n in l){if(!m){if(i<n)break;}else{if(!q.ContainsKey(o))q.Add(o,new HashSet<int>());q[o].Add(n);if(q.Count==1){int r=q[o].OrderBy(gi =>gi).Take(2).Sum();if(i<r)break;}else{int r=q[o].Concat(q[o-1]).OrderBy(gi =>gi).Take(2).Sum();if(i<r)break;}if(++s==p){o++;p=(int)Math.Pow(2,o);}}if(i==n){yield return i;break;}}}}static IEnumerable<int>e(){int t=0;for(int i=0;i<int.MaxValue;i++)foreach(char c in Convert.ToString(i,2)){if(c=='0')yield return t;t++;}}static IEnumerable<int>f(){int t=1;int u=0;bool v=true;using(IEnumerator<int>w=Enumerable.Range(0,int.MaxValue).GetEnumerator()){while(w.MoveNext()){if(v){if(u==0)u=t+1;yield return w.Current;if(--t==0)v=false;}else{if(t==0)t=u+1;if(--u==0)v=true;}}}}static IEnumerable<int>g(){for(int i=0;i<int.MaxValue;i++){string s=Convert.ToString(i,2);if(x(s.Count(c =>c=='0'))&& x(s.Count(c =>c=='1')))yield return i;}}static bool x(int y){return(y != 0)&&((y &(y-1))==0);}static IEnumerable<int>h(){return Enumerable.Range(1,int.MaxValue).Select(z);}static Dictionary<int,int>_=new Dictionary<int,int>();static int z(int n){int a;if(!_.TryGetValue(n,out a)){if(n<3)a=1;else a=z(n-z(n-1))+z(n-z(n-2));_.Add(n,a);}return a;}}

Удобочитаемый

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

class Programm
{
    public static void Main(string[] args)
    {
        int index = 0;

        IEnumerable<int> intersection = null;

        foreach (char c in Convert.ToString(int.Parse(args[0]), 2).Reverse())
        {
            ++index;
            if (c == '0')
                continue;

            switch (index)
            {
                case 1: intersection = _join(intersection, OEIS1()); break;
                case 2: intersection = _join(intersection, OEIS2()); break;
                case 3: intersection = _join(intersection, OEIS3()); break;
                case 4: intersection = _join(intersection, OEIS4(), true); break;

                default: throw new ArgumentException();
            }
        }
        if (intersection == null)
            return;

        bool first = true;
        foreach (int i in intersection.Take(int.Parse(args[1])))
        {
            if (first) first = false;
            else Console.Write(",");

            Console.Write(i);
        }

        Console.ReadKey();
    }

    private static IEnumerable<int> _join(IEnumerable<int> intersection, IEnumerable<int> newSequence, bool hof = false)
    {
        if (intersection == null)
            foreach (int n in newSequence) yield return n;



        int generation = 0;
        int generationMax = 1;
        foreach (int i in intersection)
        {
            Dictionary<int, HashSet<int>> generationCache = hof ? new Dictionary<int, HashSet<int>>() : null;
            int count = 0;
            foreach (int n in newSequence)
            {
                if (!hof)
                {
                    if (i < n)
                        break;
                }
                else
                {
                    if (!generationCache.ContainsKey(generation))
                        generationCache.Add(generation, new HashSet<int>());

                    generationCache[generation].Add(n);

                    if (generationCache.Count == 1)
                    {
                        int lowerBound = generationCache[generation].OrderBy(gi => gi).Take(2).Sum();
                        if (i < lowerBound)
                            break;
                    }
                    else
                    {
                        int lowerBound = generationCache[generation].Concat(generationCache[generation - 1]).OrderBy(gi => gi).Take(2).Sum();
                        if (i < lowerBound)
                            break;
                    }

                    if (++count == generationMax)
                    {
                        generation++;
                        generationMax = (int)Math.Pow(2, generation);
                    }
                }

                if (i == n)
                {
                    yield return i;
                    break;
                }
            }
        }
    }


    static IEnumerable<int> OEIS1()
    {
        int position = 0;
        for (int i = 0; i < int.MaxValue; i++)
            foreach (char c in Convert.ToString(i, 2))
            {
                if (c == '0')
                    yield return position;
                position++;
            }
    }

    static IEnumerable<int> OEIS2()
    {
        int take = 1;
        int skip = 0;
        bool doTake = true;
        using (IEnumerator<int> enumerator = Enumerable.Range(0, int.MaxValue).GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                if (doTake)
                {
                    if (skip == 0)
                        skip = take + 1;
                    yield return enumerator.Current;
                    if (--take == 0)
                        doTake = false;
                }
                else
                {
                    if (take == 0)
                        take = skip + 1;
                    if (--skip == 0)
                        doTake = true;
                }
            }
        }
    }

    static IEnumerable<int> OEIS3()
    {
        for (int i = 0; i < int.MaxValue; i++)
        {
            string s = Convert.ToString(i, 2);
            if (_isPowerOfTwo(s.Count(c => c == '0')) && _isPowerOfTwo(s.Count(c => c == '1')))
                yield return i;
        }
    }

    static bool _isPowerOfTwo(int number)
    {
        return (number != 0) && ((number & (number - 1)) == 0);
    }

    static IEnumerable<int> OEIS4()
    {
        return Enumerable.Range(1, int.MaxValue).Select(HofstadterQ);
    }

    static Dictionary<int, int> _hofstadterQCache = new Dictionary<int, int>();

    static int HofstadterQ(int n)
    {
        int result;
        if (!_hofstadterQCache.TryGetValue(n, out result))
        {
            if (n < 3)
                result = 1;
            else
                result = HofstadterQ(n - HofstadterQ(n - 1)) + HofstadterQ(n - HofstadterQ(n - 2));

            _hofstadterQCache.Add(n, result);
        }
        return result;
    }
}

объяснение

Это использует ленивую оценку, что делает ее претенциозно быстрой, я верю. Также мне было лениво делать какие-либо «битлогические», используя метод Convert.ToString (число, 2). Это превращает любое число в его представление binray в виде строки.

Мне пришлось написать свой собственный метод для пересечения последовательностей, так как пересечение Linq-Method вычисляет пересечение полной последовательности, и это было буквально невозможно.

CSharpie
источник