current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 13 down vote favorite
1

Recursive Binary Description

Recently, I made my very first contribution to OEIS by extending and adding a b-file to sequence A049064. The sequence starts with 0, and then the next values are derived from giving a "binary description" of the last item.

For example, the second term would be 10, because there was one 0 in the first element. The third term would be 1110, because there was one 1 and one 0. The fourth would be 11110. because there are three (11 in binary!) 1s and one 0. Below is a breakdown of the fifth term to make this process clear:

> 11110
> 1111 0    (split into groups of each number)
> 4*1 1*0   (get count of each number in each group)
> 100*1 1*0 (convert counts to binary)
> 100110    (join each group back together)

And here's an example for going from the 6th to the 7th term:

> 1110010110
> 111 00 1 0 11 0
> 3*1 2*0 1*1 1*0 2*1 1*0
> 11*1 10*0 1*1 1*0 10*1 1*0
> 111100111010110

You can check out a reference programφ I made to calculate the terms.

Your Job

You need to create a program or function which takes in a number n via standard input or function arguments, and prints out the sequence from the 1st term to the (n+1)th term, separated by a newline. If you would like a look at the lower numbers, you may refer to the b-file from the OEIS page. However, your program/function should support 0 <= n <= 30, i.e. up to the 31st term. This is no small feat, as A049064(30) is over 140,000 digits longδ. If you would like to see what the 31st term should be, I've put it on Pastebin.

Example I/O

func(10)
0
10
1110
11110
100110
1110010110
111100111010110
100110011110111010110
1110010110010011011110111010110
1111001110101100111001011010011011110111010110
1001100111101110101100111100111010110111001011010011011110111010110

func(0)
0

func(3)
0
10
1110
11110

There is only one rule: No standard loopholes!

This is , so the lowest byte count wins.

φ - Gist can be found here, and an ideone demo is here.

δ - Just in case you were wondering, my estimates at the length of the 100th term put it at approximately 3.28x10250 characters long, which would be quite a lot for anyone to calculate.

share|improve this question
    
Output as list allowed? Like [0]\n[1, 0]\n[1, 1, 1, 0]\n... –  Jakube yesterday
    
@Jakube No, you'll need to do a string join on it. –  Vioz- yesterday
4  
Congrats on making a contribution to OEIS! –  Alex A. yesterday

7 Answers 7

up vote 8 down vote

CJam, 18 17 bytes

0{sN1$e`2af.b}ri*

Thanks to @MartinBüttner for golfing off one byte!

Try it online in the CJam interpreter.

How it works

0                 e# Push 0.
 {           }ri* e# Repeat int(input)) times:
  s               e#   Stringify the element on top of the stack.
                       EXAMPLE: [[[1 1] '1] [[1] '0]] -> "11110"
   N              e#   Push a linefeed.
    1$            e#   Copy the last stack.
      e`          e#   Perform run-length encoding.
                  e#   EXAMPLE: "100110" -> [[1 '1] [2 '0] [2 '1] [1 '0]]
        2a        e#   Push [2].
          f.b     e#   For each pair [x 'y], execute: [x 'y][2].b
                  e#   This pushes [x2b 'y], where b is base conversion.
share|improve this answer
up vote 4 down vote

Pyth, 18 bytes

jbjLk.usjR2srN8Q]0

Try it online: Demonstration

Explanation:

                     implicit: Q = input number
     .u        Q]0   applying the following expression Q times to N, starting
                     with N = [0], and saving all intermediate states of N
            rN8         run-length-encoding of N
           s            unflatten lists 
        jR2             convert each number to base 2
       s                unflatten lists
  jLk                convert each list to a string
jb                   join them by newlines and print

This uses the fact, that 0 and 1 in binary are also 0 and 1.

share|improve this answer
up vote 2 down vote

Python 2, 125 116 110 bytes

from itertools import*
v='0'
exec"print v;v=''.join(bin(len(list(g)))[2:]+k for k,g in groupby(v));"*-~input()

Saved 1 byte thanks to @Sp3000 and 5 bytes by removing a redundant int call.

Older version:

import itertools as t
v='0'
exec"print v;v=''.join(bin(int(len(list(g))))[2:]+k for k,g in t.groupby(v));"*-~input()

Saved many, many bytes thanks to @Vioz-!

Original version:

import itertools as t
v='0'
for n in range(input()+1):print v;v=''.join(bin(int(len(list(g))))[2:]+k for k,g in t.groupby(v))
share|improve this answer
up vote 1 down vote

Ruby, 80 72 69 bytes

As a function:

f=->m{l=?0;0.upto(m){puts l;l.gsub!(/1+|0+/){$&.size.to_s(2)+$&[0]}}}

Call it for example with: f[6]

share|improve this answer
    
You could save a few bytes if you take input as a function argument: ->m{l=?0;0.upto(m){puts l;l.gsub!(/1+|0+/){$&.size.to_s(2)+$&[0]}}} –  blutorange yesterday
    
@blutorange Nice! Totally forgot about upto and ! -- Thanks :) –  daniero yesterday
up vote 1 down vote

Python 2, 102 bytes

import re
o='0'
exec"print o;o=''.join(bin(len(x))[2:]+x[0]for x in re.findall('0+|1+',o));"*-~input()

Somehow the combination of itertools being longer than re and groupby returning grouper objects means that using regex is a bit shorter...

share|improve this answer
up vote 0 down vote

Cobra - 128

do(i)=if(i-=1,(r=RegularExpressions).Regex.replace(f(i),'1+|0+',do(m=r.Match())=Convert.toString('[m]'.length,2)+'[m]'[:1]),'0')
share|improve this answer
up vote 0 down vote

Haskell, 136 130 Bytes

import Text.Printf
import Data.List
f n=putStr.unlines.take(n+1).iterate(concatMap(\n->(printf"%b"$length n)++[head n]).group)$"0"
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.