Код Гольф: Моррис Последовательность

Задача

Самый короткий код по количеству символов, который выведет Morris Number Sequence. Последовательность номеров Morris, также известная как последовательность Look-and-say, представляет собой последовательность чисел, которая начинается следующим образом:

1, 11, 21, 1211, 111221, 312211, ...

Вы можете генерировать последовательность бесконечно (т.е. вам не нужно создавать определенный номер).

Ожидания ввода/вывода

Программе не нужно принимать какие-либо входные данные (но бонусные баллы за прием ввода и тем самым предоставить возможность начать с любой произвольной начальной точки или числа). По крайней мере, ваша программа должна начинаться с 1.

Выход по крайней мере ожидается как последовательность:

Дополнительный кредит

Если вы собираетесь получить дополнительный кредит, вам нужно будет сделать что-то вроде этого:

$ morris 1
1
11
21
1211
111221
312211
...

$ morris 3
3
13
1113
3113
132113
...

Ответ 1

GolfScript - 41 (дополнительный кредит: 40)

1{.p`n+0:c:P;{:|P=c{c`P|:P!}if):c;}%~1}do
{~.p`n+0:c:P;{:|P=c{c`P|:P!}if):c;}%1}do

Что?
Процедура получения следующего числа в последовательности: Преобразование текущего числа в строку, добавление новой строки и цикл над символами. Для каждой цифры, если предыдущая цифра P одинакова, увеличьте счетчик c. В противном случае добавьте c и P к тому, что будет следующим числом, а затем обновите эти переменные. Новая строка, которую мы добавляем, позволяет добавить последнюю цифру к следующему номеру.

Подробные сведения можно получить, ознакомившись с документацией GolfScript. (Обратите внимание, что | используется как переменная.)

Ответ 2

Haskell: 115 88 85

import List
m x=do a:b<-group x;show(length b+1)++[a]
main=mapM putStrLn$iterate m"1"

Это бесконечная последовательность. Я знаю, что это может быть улучшено много - я довольно новичок в Haskell.

Бит короче, вставка mapM и итерация:

import List
m(a:b)=show(length b+1)++[a]
f x=putStrLn x>>f(group x>>=m)
main=f"1"

Ответ 3

Perl (46 символов)

$_="1$/";s/(.)\1*/length($&).$1/eg while print

Дополнительный кредит (52 символа)

$_=(pop||1).$/;s/(.)\1*/length($&).$1/eg while print

Ответ 4

Perl, 46 символов

$_=1;s/(.)\1*/$&=~y!!!c.$1/ge while print$_,$/

Дополнительный кредит, 51 символ:

$_=pop||1;s/(.)\1*/$&=~y!!!c.$1/ge while print$_,$/

Ответ 5

Javascript 100 97

for(x=prompt();confirm(y=x);)for(x="";y;){for(c=0;y[c++]&&y[c]==y[0];);x+=c+y[0];y=y.substr(c--)}

Позволяет прервать последовательность (нажав "Отмена" ), чтобы мы не блокировали пользовательский агент и привязывали CPU. Он также позволяет начинать с любого положительного целого (дополнительный кредит).

Live Пример: http://jsbin.com/izeqo/2

Ответ 6

Mathematica - 62 53 50 символов - Дополнительный кредит

Изменить: 40 символов... но справа налево:(

Любопытно, если мы читаем последовательность справа налево (то есть 1,11,12,1121,..), достаточно 40 символов

NestList[Flatten[Tally /@ [email protected]#] &, #2, #] &

Это потому, что Tally генерирует список {elem, counter}!

Изменить: 50 символов

NestList[[email protected][Tally /@ [email protected]#, 3] &, #2, #] &

Рассечение: (читать комментарии вверх)

NestList[               // 5-Recursively get the first N iterations
    [email protected]            // 4-Convert to one big list
       Reverse          // 3-Reverse to get {counter,element}
          [Tally /@     // 2-Count each run (generates {element,counter})
               [email protected]#, // 1-Split list in runs of equal elements
                 3] &,
                     #2,// Input param: Starting Number 
                     #] // Input param: Number of iterations

Изменить: реорганизован

NestList[Flatten[{[email protected]#, #[[1]]} & /@ [email protected]#, 1] &, #2, #1] &

Конец редактирования ///

NestList[[email protected][Length /@ (c = [email protected]#), First /@ c] &, #2, #1] &

Пространства, которые не нужны/добавлены для ясности

Вызвать

%[NumberOfRuns,{Seed}]

Мой первый раз, используя "Riffle", объединить {1,2,3} и {a, b, c} в {1, a, 2, b, 3, c}:)

Ответ 7

Python, 97 102 115

Пробелы должны быть табуляциями:

x='1'
while 1:
    print x;y=d=''
    for c in x+'_':
        if c!=d:
            if d:y+=`n`+d
            n,d=0,c
        n+=1
    x=y

например:.

$ python morris.py | head
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211

Ответ 8

Здесь мой С# пытается использовать LINQ и сначала попытаться использовать Code Golf:

С# - 205 194 211 198 байтов с дополнительным кредитом (включая шаблон С#)

using System.Linq;class C{static void Main(string[]a){var v=a[0];for(;;){var r="";while(v!=""){int i=v.TakeWhile(d=>d==v[0]).Count();r+=i;r+=v[0];v=v.Remove(0,i);}System.Console.WriteLine(r);v=r;}}}

Считываемая версия:

static void Main(string[] args)
{
    string value = args[0];
    for (;;)
    {
        string result = "";
        while (value != "")
        {
            int i = value.TakeWhile(d => d == value[0]).Count();
            result += i;
            result += value[0];
            value = value.Remove(0, i);
        }
        Console.WriteLine(result);
        value = result;
    }
}

Пример вывода:

Ответ 9

Здесь идет моя реализация (в Prolog):

Пролог с DCG (174 символа):

m(D):-write(D),nl,m(1,write(D),T,[nl|T],_).
m(C,D,T)-->[D],{succ(C,N)},!,m(N,D,T).
m(C,D,[G,D|T])-->[N],{G=write(C),G,D,(N=nl->(M-T-O=0-[N|R]-_,N);M-T-O=1-R-N)},!,m(M,O,R).

Простой ванильный пролог, код гораздо более прозрачный (225 символов):

m(D):-
  ((D=1->write(D),nl);true),
  m([], [1,D]).

m([], [C,D|M]):-
  write(C), write(D),nl,
  reverse([D,C|M],[N|X]),
  !,
  m([N|X],[0,N]).
m([D|T], [C,D|M]):-
  succ(C,N),
  !,
  m(T,[N,D|M]).
m([Y|T],[C,D|M]):-
  write(C), write(D),
  !,
  m(T,[1,Y,D,C|M]).

Чтобы вывести последовательность Морриса: м (Д). где D - "стартовая" цифра.

Ответ 10

Perl, 67 символов

включая флаг -l.

sub f{$_=pop;print;my$n;$n.=$+[0].$1while(s/(.)\1*//);f($n)}f(1)

Perl, 72 символа с дополнительным кредитом

sub f{$_=pop;print;my$n;$n.=$+[0].$1while(s/(.)\1*//);f($n)}f(pop||1)

Ответ 11

Ruby - 52

s=?1;loop{puts s;s.gsub!(/(.)\1*/){"#{$&.size}"+$1}}

Задача слишком проста и слишком perlish...

Ответ 12

C, 128 символов

использует статический буфер, гарантированный причиной сбоя сегментации

main(){char*c,v[4096],*o,*b,d[4096]="1";for(;o=v,puts(d);strcpy(d,v))for(c=d;*c;o+=sprintf(o,"%d%c",c-b,*b))for(b=c;*++c==*b;);}

Ответ 13

Вызвать строку "Morris-ish", если она содержит только цифры 1-3 и не содержит пробегов более трех цифр. Если исходной строкой является Morris-ish, все строки, итеративно созданные из нее, также будут Morris-ish. Аналогично, если исходная строка не является Morris-ish, тогда никакая сгенерированная строка не будет Morris-ish, если числа больше десяти считаются комбинациями цифр (например, если 11111111111 считается рушащимся на три, а не "одиннадцать" и один).

Учитывая это наблюдение, каждая итерация, начинающаяся с семени Morris-ish, может быть выполнена в виде следующей последовательности операций поиска/замены:

111 -> CA
11 -> BA
1 -> AA
222 -> CB
22 -> BB
2 -> AB
333 -> CC
33 -> BC
3 -> AC
A -> 1
B -> 2
C -> 3

Обратите внимание, что последовательность является Morris-ish перед указанной заменой, второй символ каждой сгенерированной пары будет отличаться от второго символа предыдущей и следующих пар; таким образом, невозможно иметь более трех одинаковых символов в последовательности.

Интересно, сколько там непересекающихся последовательностей Морриса-Иш?

Ответ 14

Perl (дополнительный кредит), 47 символов

$_=pop.$/;{print;s/(.)\1*/$&=~y|||c.$1/ge;redo}

Ответ 15

Java

Моя первая попытка "Code-Golf" Я просто бросил это вместе во время части моего класса IB CS:

238 конденсированных

Сгущенное:

String a="1",b="1",z;int i,c;while(true){System.out.println(b);for(c=0,i=0,b="",z=a.substring(0,1);i<a.length();i++){if(z.equals(a.substring(i,i+1)))c++;else{b+=Integer.toString(c)+z;z=a.substring(i,i+1);c=1;}}b+=Integer.toString(c)+z;a=b;}

Правильно отформатирован:

    String a = "1", b = "1", z;
    int i, c;

    while (true) {      
      System.out.println(b);

      for (c = 0, i = 0, b = "", z = a.substring(0, 1); i < a.length(); i++) {
        if (z.equals(a.substring(i, i + 1))) c++;
        else {
          b += Integer.toString(c) + z;
          z = a.substring(i, i + 1);
          c = 1;
        }
      }

      b += Integer.toString(c) + z;
      a = b;
    }

Ответ 16

J, 44 символа с дополнительным кредитом

(([:,#;[email protected]{:,.{:#{.)@(,:0<1,[:|2-/\]))^:(<9)

К сожалению, это генерирует только 9 итераций, но число итераций <9 может быть изменено как угодно. Установка его на a: создает бесконечную последовательность, но, очевидно, это невозможно напечатать.

Использование:

   (([:,#;[email protected]{:,.{:#{.)@(,:0<1,[:|2-/\]))^:(<9) 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0 0 0 0 0 0 0
1 2 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 2 2 1 0 0 0 0 0 0 0 0
3 1 2 2 1 1 0 0 0 0 0 0 0 0
1 3 1 1 2 2 2 1 0 0 0 0 0 0
1 1 1 3 2 1 3 2 1 1 0 0 0 0
3 1 1 3 1 2 1 1 1 3 1 2 2 1

   (([:,#;[email protected]{:,.{:#{.)@(,:0<1,[:|2-/\]))^:(<11) 4
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 3 2 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 3 1 2 2 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 1 1 3 1 1 2 2 2 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 3 2 1 1 3 2 1 3 2 2 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 3 1 2 2 1 1 3 1 2 1 1 1 3 2 2 2 1 1 4 0 0 0 0 0 0 0 0
3 1 1 3 1 1 2 2 2 1 1 3 1 1 1 2 3 1 1 3 3 2 2 1 1 4 0 0 0 0
1 3 2 1 1 3 2 1 3 2 2 1 1 3 3 1 1 2 1 3 2 1 2 3 2 2 2 1 1 4

Ответ 17

Java - 167 символов (с кредитом)

_{(122 без класса/основного шаблона)}

class M{public static void main(String[]a){for(String i=a[0],o="";;System.out.println(i=o),o="")for(String p:i.split("(?<=(.)(?!\\1))"))o+=p.length()+""+p.charAt(0);}}

С символами новой строки:

class M{
 public static void main(String[]a){
  for(String i=a[0],o="";;System.out.println(i=o),o="")
   for(String p:i.split("(?<=(.)(?!\\1))"))
    o+=p.length()+""+p.charAt(0);
 }
}

Ответ 18

Здесь моя самая первая попытка кодового гольфа, поэтому, пожалуйста, не слишком сильно меня беспокоишь!

PHP, 128 122 112 байт с открывающим тегом

~~122~~ ~~116~~ 106 байтов без открытия тега и пропущенных пробелов.

<?php for($a="1";!$c="";print"$a\n",$a=$c)for($j=0,$x=1;$a[$j];++$j)$a[$j]==$a[$j+1]?$x++:($c.=$x.$a[$j])&&$x=1;

(Очень жаль, что я должен инициализировать $a как строку, хотя и стоил мне 2 дополнительных байта, иначе я не могу использовать нотацию индекса.)

Выход

$ php morris.php
1
11
21
1211
111221
312211
...

PHP (дополнительный кредит), 133 127 117 байт с открывающим тегом

~~127~~ ~~121~~ 111 байт, не открывая тег <?php и ведущие пробелы.

<?php for($a=$argv[1];!$c="";print"$a\n",$a=$c)for($j=0,$x=1;$a[$j];++$j)$a[$j]==$a[$j+1]?$x++:($c.=$x.$a[$j])&&$x=1;

Выход

$ php morris.php 3
3
13
1113
3113
132113
1113122113
...
^C
$ php morris.php 614
614
161114
11163114
3116132114
1321161113122114
1113122116311311222114
...

PHP (дополнительный кредит), не расплывчатый с открытием и закрытием тегов

<?php

for ($a = $argv[1]; !$c = ""; print "$a\n", $a = $c)
{
    for ($j = 0, $x = 1; $a[$j]; ++$j)
    {
        // NB: this was golfed using ternary and logical AND operators:
        // $a[$j] == $a[$j + 1] ? $x++ : ($c .= $x . $a[$j]) && $x = 1;
        if ($a[$j] == $a[$j + 1])
        {
            $x++;
        }
        else
        {
            $c .= $x . $a[$j];
            $x = 1;
        }
    }
}

?>

Ответ 19

Delphi

Delphi - ужасный язык игры в гольф, но все же:

var i,n:Int32;s,t,k:string;u:char;label l;begin s:='1';l:writeln(s);t:='';u:=s[1
];n:=1;for i:=2to length(s)do if s[i]=u then inc(n)else begin str(n,k);t:=t+k+u;
u:=s[i];n:=1;end;str(n,k);t:=t+k+u;s:=t;goto l;end.

Это 211 байт (и он компилируется, как он есть).

Ответ 20

PHP: 111

Моя первая попытка когда-либо появляться в кодовом гольф-поле, вполне доволен результатом.

for($x=1;;){echo$y=$x,"\n";for($x="";$y;){for($c=0;$y[$c++]&&$y[$c]==$y[0];);$x.=$c.$y[0];$y=substr($y,$c--);}}

дает:

> php htdocs/golf.php
1
11
21
... (endless loop)

PHP с дополнительным кредитом: 118

for($x=$argv[1];;){echo$y=$x,"\n";for($x="";$y;){for($c=0;$y[$c++]&&$y[$c]==$y[0];);$x.=$c.$y[0];$y=substr($y,$c--);}}

дает:

> php htdocs/golf.php 4
4
14
1114
3114
... (to infinity and beyond)

Ответ 21

Python - 98 символов

from itertools import *
L='1'
while 1:print L;L=''.join('%s'%len(list(y))+x for x,y in groupby(L))

106 символов для бонуса

from itertools import *
L=raw_input()
while 1:print L;L=''.join('%s'%len(list(y))+x for x,y in groupby(L))

Ответ 22

С++, 310 символов.

#include <iostream>
#include <list>
using namespace std;
int main(){list<int> l(1,1);cout<<1<<endl;while(1){list<int> t;for(list<int>::iterator i=l.begin();i!=l.end();){list<int>::iterator p=i;++i;while((i!=l.end())&&(*i==*p)){++i;}int c=distance(p,i);cout<<c<<*p;t.push_back(c);t.push_back(*p);}cout<<'\n';l=t;}}

Корректно с отступом:

#include <iostream>
#include <list>
using namespace std;

int main() {
    list <int> l(1,1);
    cout << 1 << endl;
    while(1) {
        list <int> t;
        for (list <int>::iterator i = l.begin(); i != l.end();) {
            const list <int>::iterator p = i;
            ++i;
            while ((i != l.end()) && (*i == *p)) {
                ++i;
            }
            int c = distance(p, i);
            cout << c << *p;
            t.push_back(c);
            t.push_back(*p);
        }
        cout << '\n';
        l = t;
    }
}

Ответ 23

C w/Дополнительный кредит, 242 (или 184)

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define s malloc(1<<20)
main(int z,char**v){char*j=s,*k=s;strcpy(k,*++v);for(;;){strcpy(j,k);z=1;*k=0;while(*j){if(*j-*++j)sprintf(k+strlen(k),"%d%c",z,*(j-1)),z=1;else++z;}puts(k);}}

Вы можете сохранить еще ~ 60 символов, если вы опустите включенные, gcc все равно будет компилироваться с предупреждениями.

$ ./a.out 11111111 | head
81
1811
111821
31181211
132118111221
1113122118312211
31131122211813112221
132113213221181113213211
111312211312111322211831131211131221
3113112221131112311332211813211311123113112211

Ответ 24

Python - 117

Мой python-fu не силен, поэтому я много сделал для этого.:)

a='1'
while 1:
 print a
 a=''.join([`len(s)`+s[0]for s in''.join([x+' '*(x!=y)for x,y in zip(a,(2*a)[1:])]).split()])

Идея состоит в том, чтобы использовать zip для создания списка пар (a [i], a [i + 1]), использовать внутреннее понимание для вставки пробела, когда [i]!= a [i + 1], присоедините полученный список к строке и разделите на пробелы, используйте другое понимание в этом списке разделов, чтобы заменить каждый элемент длиной выполнения элемента и первым символом и, наконец, присоединиться, чтобы получить следующее значение в последовательности.

Ответ 25

С#, 204 байта (256 с дополнительным кредитом)

Моя первая попытка кодового гольфа

static void Main(){var v="1";for(;;){Console.Write(v + "\n");var r=v.Aggregate("", (x, y) => x.LastOrDefault()==y?x.Remove(0, x.Length-2)+(int.Parse(x[x.Length-2].ToString())+1).ToString()+y:x+="1"+y);v=r;}}

Читаемая версия, отличие от других заключается в том, что я использую функцию Linq Aggregate

static void Main(){
    var value="1";
    for(;;)
    {
        Console.Write(value + "\n");
        var result = value.Aggregate("", (seed, character) => 
                        seed.LastOrDefault() == character ? 
                            seed.Remove(seed.Length-2) + (int.Parse(seed[seed.Length-2].ToString())+1).ToString() + character
                            : seed += "1" + character
                    );
        value = result;
    }
}

Ответ 26

Python - 92 символа

^{98 с дополнительным кредитом}

Выводится бесконечно. Я рекомендую перенаправить вывод в файл и быстро нажать Ctrl + C.

x=`1`;t=''
while 1:
 print x
 while x:c=x[0];n=len(x);x=x.lstrip(c);t+=`n-len(x)`+c
 x,t=t,x

Для дополнительной кредитной версии замените

x=`1`

x=`input()`

Ответ 27

C - 120 символов

^{129 с дополнительным кредитом}

main(){char*p,*s,*r,x[99]="1",t[99];for(;r=t,puts(p=x);strcpy(x,t))
for(;*p;*r++=p-s+48,*r++=*s,*r=0)for(s=p;*++p==*s;);}

^{Новая строка доступна только для удобства чтения.}

Это прекращается, когда происходит segfault (после как минимум 15 итераций). Если ваши библиотеки C используют буферизованный ввод-вывод, вы можете не видеть никаких результатов перед segfault. Если да, проверьте с помощью этого кода:

#include<stdio.h>
main(){char*p,*s,*r,x[99]="1",t[99];for(;r=t,puts(p=x),fflush(stdout),1;
strcpy(x,t))for(;*p;*r++=p-s+48,*r++=*s,*r=0)for(s=p;*++p==*s;);}

Это добавляет fflush после каждого выхода.

Ungolfed, он выглядел бы примерно так:

int main(){
    char *p, *start, *result, number[99] = "1", temp[99];

    while(1){ /* loop forever */
        puts(number);

        result = temp; /* we'll be incrementing this pointer as we write */
        p = number;    /* we'll be incrementing this pointer as we read */

        while(*p){ /* loop till end of string */
            start = p; /* keep track of where we started */

            while(*p == *start) /* find all occurrences of this character */
                p++;

            *result++ = '0' + p - start; /* write the count of characters, */
            *result++ = *start;          /* the character just counted, */
            *result   = 0;               /* and a terminating null */
        }

        strcpy(number, temp); /* copy the result back to our working buffer */
    }
}

Вы можете увидеть его в действии на ideone.

С дополнительным кредитом код выглядит следующим образом:

main(){char*p,*s,*r,x[99],t[99];for(scanf("%s",x);r=t,puts(p=x);strcpy(x,t))
for(;*p;*r++=p-s+48,*r++=*s,*r=0)for(s=p;*++p==*s;);}

Ответ 28

Общий Lisp - 124 122 115 Chars

(do((l'(1)(do(a r)((not l)r)(setf a(1+(mismatch(cdr l)l))r(,@r,a,(car l))l(nthcdr a l)))))((format t"~{~s~}~%"l)))

С форматированием:

(do ((l '(1) (do (a r) ((not l) r) (setf a (1+ (mismatch (cdr l) l))
                                         r `(,@r ,a ,(car l)) l (nthcdr a l)))))
    ((format t "~{~s~}~%" l)))

Ответ 29

F # - 135

let rec m l=Seq.iter(printf "%i")l;printfn"";m(List.foldBack(fun x s->match s with|c::v::t when x=v->(c+1)::v::t|_->1::x::s)l [])
m[1]

Отформатированный код

let rec m l=
    Seq.iter(printf "%i")l;printfn"";
    m (List.foldBack(fun x s->
        match s with
        |c::v::t when x=v->(c+1)::v::t
        |_->1::x::s) l [])
m[1]

По-прежнему надеюсь, что я смогу найти лучший способ распечатать список или использовать string/bigint.

Ответ 30

PHP 72 байта

<?for(;;)echo$a=preg_filter('#(.)\1*#e','strlen("$0"). $1',$a)?:5554,~õ;

Этот script может быть дополнительно оптимизирован. Но так как у нас есть PHPGolf ({http://www.phpgolf.org/?p=challenges&challenge_id=28}) точно такая же последовательность, я сохраняю его таким образом.