challenge LL Golf Hole 5 - 最上位の桁を数え上げる

与えられた自然数までの数え上げを行います。ただし、繰り上がりが起こったときは最上位の桁のみを数え上げます。また、与えられる自然数には0以外の桁が2回以上登場してはいけません。たとえば、300を入力として与えられた場合は以下のような出力となります。

0
1
2
3
4
5
6
7
8
9
10
20
30
40
50
60
70
80
90
100
200
300

与える自然数についてはリテラルで与える、標準入力で与える、引数で与えるなどは自由とします。

※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。

1
2
3
4
5
6
#!/usr/bin/env ruby
def f(n, m = 0)
    puts m    
    n == m ? return : f(n, m + 10 ** (m.to_s.size - 1) )
end
f(300)

Posted feedbacks - Flatten

Nested Hidden

ちょっと不格好かなぁ…。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>

void count(int n)
{
    int d = 1;
    int i = 0;
    while(i <= n)
    {
        std::cout << i << std::endl;
        i += d;
        if((i / (d * 10) > 0))
        {
            d *= 10;
        }
    }
}

int main(int, char* [])
{
    count(300);

    return 0;
}

引数。

1
2
3
4
5
6
7
8
echo 0
while :;do
  for ((i=1;i<10;i++));do
    echo $i$m
    [ $i$m = $1 ]&&exit
  done
  m=${m}0
done

SWI-Prologで。

1
2
3
4
count(N) :- writeln(0), sub_atom(N,1,_,_,Y), between(1,9,X), 
    atom_concat(X,Y,XY), writeln(XY), atom_number(XY,N), !.

:- count(300).

コマンドを呼ぶと28B。

1
seq 0 300|grep '^[1-9]\?0*$'

問題例のスクリプト f(300)の場合は、うまくいくけど f(310)とか一般的な場合にうまくいかないと思うけど。


1
2
3
count n = takeWhile (<= n) (0:[x*n | n <- [10^n|n<-[0..]], x <- [1..9]])

main = mapM_ print $ count 300

Squeak Smalltalk で。

1
2
3
4
5
6
7
| n m |
n := 300.
m := 0.
World findATranscript: nil.
[m <= n] whileTrue: [
    Transcript cr; show: m.
    m := m + (10 raisedTo: m asString size - 1)]

標準入力から
1
(do((a 1)(e(read)))((< e(incf a(expt 10(floor(log(print a)10)))))))

grepが一番シンプルかもですね。

1
count <- function(n) grep("^[0-9]0*$", 0:n, value=T)

perl countup.pl 300 
1
2
3
4
5
6
7
while($ARGV[0]>=($x=$n++ . '0' x $c)){
    print "$x\n";
    if($n == 10){
        $n=1;
        $c++;
    }
}

たしかに。grepを使ったらシンプルに。

1
ruby -e 'p (0..300).collect{|i| i.to_s}.grep(/^[1-9]?0*$/)'

("0".."300")という書き方ができるんですね。そうすればcollectの部分も不要。投稿してから気がつきました。


Javaだとこんなもんでしょうか?

1
2
3
4
5
6
7
8
class LL_Golf_Hole_5 {
    public static void main(String[] args) {
        for(int i=0; i<=Integer.parseInt(args[0]); i++) {
            if(String.valueOf(i).charAt(0) != String.valueOf(i-1).charAt(0) )
                System.out.println(i);
        }
    }
}


	
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
module Main where

import Control.Arrow
import System.Environment

funcA = arr ((head >>> read >>> (>=) >>> takeWhile) &&& const lst)
          >>> arr (app >>> (:) 0)
          >>> Kleisli (mapM_ print)
  where lst = concat $ iterate (map (10*)) [1..9]

main = getArgs >>= runKleisli funcA

標準入力。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#!/bin/sed -nf
x
:a
s/$/0/
:b
p
G
/^\(.*\)\n\1$/b
s/\n.*//
/^9/{s//1/;ba}
y/12345678/23456789/
s/^0/1/
bb

1
2
3
4
5
6
7
#!/usr/bin/env python
# -*- coding: utf8 -*-
def f(n, m=0):
    print m
    return (n == m) and True or f(n, m + 10 ** (len(str(m)) - 1))

f(300)

 余り面白く無いかも知れませんが,範囲演算子とgrepを使って書いてみました。

1
print join("\n",grep{/^\d0*$/}0..$ARGV[0])

数値に限定されるのでもう少し簡単な正規表現で書けます。

1
seq 0 300|grep '^.0*$'

1
2
3
4
5
6
7
8
9
function f(n) {
  var m = 0, r = [];
  while (n >= m) {
    r.push(m);
    m += Math.pow(10, (("" + m).length - 1));
  }
  return r;
}
alert(f(300).join("\n"));

while文を1行にした。

1
2
3
4
5
6
function f(n) {
  var m = 0, r = [m];
  while (n >= (m += Math.pow(10, (("" + m).length - 1)))) r.push(m);
  return r;
}
alert(f(300).join("\n"));

コマンドラインからで67バイト。

1
puts z=0;while 1.upto(9){|i|puts((t=i*10**z)<=300?t:exit)};z+=1;end

標準入力に対応させてみました

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstdlib>
#include <cstring>

void func(int m, int n = 0)
{
    char buf[BUFSIZ];
    int i = 1;
    int size = ::strlen(::itoa(n, buf, 10)) - 1;

    std::cout << n << std::endl;
    while(size--) i *= 10;
    if(m > n) return func(m, n+i);
}

int main(int argc, char* argv[])
{
    argc == 2 ? func(::atoi(argv[1])) : func(300);
}

取り敢えずパッと思い付いたのを。

1
2
import Data.List
main=readLn>>=print.(\n->fst$span(<=n)$nub$concat$iterate(map(*10))[0..9])

 余り短く出来ませんでしたが...。

1
2
3
4
object M{
    def c(d:Int,f:Int,m:Int):Unit=if(d*f<=m){printf("%d\n",d*f);c(d%9+1,f*(1+9*(d/9)),m)}
    def main(a:Array[String])=c(0,1,Integer.parseInt(a(0)))
}

1
2
3
4
5
6
7
class Program {
    static void Main(string[] args) {
        for (int i = 0; i <= int.Parse(args[0]); i++)
            if (System.Text.RegularExpressions.Regex.IsMatch(i.ToString(), "^.0*$"))
                System.Console.WriteLine("{0}", i);
    }
}

たしかに、数値しか入力されないから"."で十分なのですね。シンプルすぎる・・・

1
grep("^.0*$",0:300)-1

こんな感じで。
1
using System;class P{static void Main(string[]a){for(int i=0;i<=int.Parse(a[0]);i++)if(i%Math.Pow(10,i.ToString().Length-1)==0)Console.WriteLine(i);}}

nubだと遅いので。。。

1
main=readLn>>=print.(0:).fst.flip span(concat$iterate(map(10*))[1..9]).(>=)

皆さんのご意見を元に改良。

コマンドラインから上限を得ます。

1
puts ("0"..ARGV[0]).grep(/^.?0*$/)

> また、与えられる自然数には0以外の桁が2回以上登場してはいけません。

という条件付です~。


XPath の conditional expressions(if then else) など使ってみる。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet version="2.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  xmlns:xs="http://www.w3.org/2001/XMLSchema"
  xmlns:fn="http://www.w3.org/2005/xpath-functions"
  >

  <xsl:output method="text" />

  <xsl:variable name="goal" as="xs:string" select="'300'" />

  <xsl:template match="/" >
    <xsl:variable name="digit" as="xs:integer" select="fn:string-length($goal)" />
    <xsl:for-each select="1 to $digit">
      <xsl:variable name="d" as="xs:integer" select="." />
      <xsl:for-each select="(if (.=1) then 0 else 1)
                            to
                            (if (.=$digit) then xs:integer(fn:substring($goal,1,1)) else 9)" >
        <xsl:value-of select="." />
        <xsl:for-each select="2 to $d">
          <xsl:value-of select="0" />
        </xsl:for-each>
        <xsl:text>&#xA;</xsl:text>
      </xsl:for-each>
    </xsl:for-each>
  </xsl:template>
</xsl:stylesheet>

#7156さんのをもうちょっと短く。68bytes
1
while($ARGV[0]>=($x=$n++.0 x$c)){print"$x\n";$n==10&&($n=1)&&$c++}

Javaで頑張って縮めてみました。 改行・タブを消して 146B

1
2
3
4
5
6
7
8
class LL_Golf_Hole_5{
    public static void main(String[]s){
        for(int i=0,t=1;i<=Integer.parseInt(s[0]);i+=t){
            System.out.println(i);
            if(i==t*10)t*=10;
        }
    }
}

grepでもやってみる。40bytes
1
$,="\n";print grep/^\d0*$/,0..$ARGV[0]

1
2
3
4
5
def max = args[0].toInteger()
(0..max).collect{
    def num = it.toString()
    num[0] + "0" * (num.size()-1)
}.unique().each{ println it }

mattsanさんの#7145を参考に標準入力に対応しつつgolf化.
164bytes. 改行5,空白4省略可で実質155bytes
本当はoperator<()を定義してcout<cin とかやりたかったけど、短さを優先しました。
1
2
3
4
5
6
7
#include<iostream>
using namespace std;
void f(ostream&o,istream&i){
  int c=0,d=1,n;i>>n;
  while(c<=n)o<<c<<"\n"&&(c+=d)&&c/d/10&&(d*=10);
}
main(){f(cout,cin);}

別関数に分けずにベタでmain内に書いたほうがよっぽど短かった orz
というわけで元コードは自分で-1.
116btyes.実質109bytes
1
2
3
4
5
#include<iostream>
main(){
  int c=0,d=1,n;std::cin>>n;
  while(c<=n)std::cout<<c<<"\n"&&(c+=d)&&c/d/10&&(d*=10);
}

データは標準入力から。
1
exit wd"0(a&>:#])0,,(10x^i.#":a=.".}:1!:1[3)*/>:i.9

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
(use srfi-1)
(define (main args)
  (let ((n (string->number (cadr args))))
    (print 0)
    (let loop ((i 1))
      (receive (xs ys) (partition (cut <= <> n)
                                  (map (cut * i <>) '(1 2 3 4 5 6 7 8 9)))
        (for-each print xs)
        (if (pair? ys)
            0
            (loop (* i 10)))))))

ループより再帰の方がきれいに書けるかも?と思ったので試してみました。

もう少しうまく書けそうですが・・・

1
2
3
4
count <- function(n=300){
  if(n!=0) Recall(n - 10^(nchar(n-1)-1))
  print(n)
}

80byte

1
2
<?$m=fgets(STDIN);for($a=0;$a<=$m;eval('$a+=1e'.(strlen($a)-1).';'))echo$a,'
';

素直に書いた方が短いんですけどね。71byte

1
2
<?$m=fgets(STDIN);for($a=0;$a<=$m;$a+=pow(10,strlen($a)-print$a.'
'));

正規表現をお借りして、43バイト。

1
iで0から尋(i)まで繰返,RE(i,"^.0*$")なら表示

正規表現を使って短かく。 80 bytes。

1
(use srfi-1)(for-each print(filter(compose #/^.0*$/ x->string)(iota(+(read)1))))

1
x=[1..9]++(map(10*)x);main=readLn>>=print.fst.(`span`(0:x)).(>=)

C++に対抗意識を燃やしてみたけどかてなかったorz
うーん、atoi()をstrcmp()にすればもう少し短くなる気がするんだけどうまく動かない。。
strcmp()って短い文字列は小さいと判断されると思ったのだけど気のせいかなー?

// gcc -Wall doukaku200.c

ちなみに圧縮すると↓のような感じ(113バイト?)
char s[9]={48},*t=s;
main(int ac, char* av[]){for(;atoi(s)<atoi(av[1]);(*s)++)
{puts(s);if(*s==59)*s=*(++t)=48;}}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>
char s[9]={0x30},*t=s;
int main(int ac, char* av[])
{
    for(;atoi(s)<=atoi(av[1]);(*s)++)
    {
        puts(s);
        if(*s==0x39)
        {
            t++;
            *s = *t = 0x30;
        }
    }
    return 0;
}
/* EOF */