DouKaku?beta

Language detail: awk

Coverage: 36.55%
number of '+' ratings
 contribution for coverage

Unsolved challenges

show all

codes

Feed

Used modules

next >>

タブ区切りデータの処理 (Nested Flatten)

はじめまして。最初awk向きなのになぜ未投稿？と思ったのですが、ソートが必要なのですね。 教科書どおりのqsortですが、整数値をソートする、ということで17行目で　+0　してから比較してみました。 #最初の投稿時、言語を指定しそこない、otherに投稿してしまいました。申し訳ありません。

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
>type data.txt
ID    Surname    Forename    Age
0    Suzuki    Taro    19
1    Sato    Hanako    18
11    Kato    Junko    40
3    Yamammoto    Shingo    46

>type  tab_sort.awk
BEGIN{FS="\t";OFS="\t"}

NR == 1{ print $1,$3,$2,$4 }
NR > 1{t=$2;$2=$3;$3=t;$4=$4+1;A[NR]=$0;}

END{qsort(A,2,NR)
     for(i=2;i<=NR;i++) print A[i]
    }

function qsort(A,left,right){
   if(left>=right) return
   swap(A,left,left+int((right-left+1)*rand()))
   last=left
   for(i=left+1;i<=right;i++)
       #if(A[i] < A[left]) swap(A,++last,i)
       if(A[i] + 0 < A[left] + 0) swap(A,++last,i)
   swap(A,left,last)
   qsort(A,left,last-1)
   qsort(A,last+1,right)
}

function swap(A,i,j){
   t=A[i];A[i]=A[j];A[j]=t
}

>mawk32 -f tab_sort.awk data.txt > kekka.txt
>type kekka.txt
ID    Forename    Surname    Age
0    Taro    Suzuki    20
1    Hanako    Sato    19
3    Shingo    Yamammoto    47
11    Junko    Kato    41
文字列の反転 (Nested Flatten)

元の文字列は別のファイルに入れておき、下のスクリプトで各行をリバースして表示します。 …mawkでも普通にjlengthとか使えますね。対応していただいた方に感謝。

1
2
3
4
5
6
7
8
>type reverse_str.awk
{print reverse_string($0)}

function reverse_string(target, str){
    for (i = 1;i<=jlength(target);i++)
        str = jsubstr(target,i,1) str
    return str
}
漢数字で九九の表 (Nested Flatten)

ベタなうえにダメな感じです。。。文字列の長さを数字代わりに使っています。

 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
28
29
30
BEGIN {
  kanjis = "〇一二三四五六七八九"

  for(i = "*"; i != "**********"; i = i "*") {
    line = ""
    for(j = "*"; j != "**********"; j = j "*") {
      num = sprintf("%d", length(i "")*length(j ""))
      while(length(num) < length("***")) {
        num = " " num
      }
      line = line kanji(num)
    }
    print line
  }
}


function kanji(s,   result, i) {
  result = ""
  for(i = length(result "*"); i <= length(s); i++) {
    c = substr(s, i, length("*"))
    if(c == " ") { 
      result = result "　"
      continue
    }
    c++
    result = result substr(kanjis, c, length("〇"))
  }
  return result
}

ごくごくベタに書きました。

 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
28
29
BEGIN {
  kanjis[" "] = "　"
  kanjis["0"] = "〇"
  kanjis["1"] = "一"
  kanjis["2"] = "二"
  kanjis["3"] = "三"
  kanjis["4"] = "四"
  kanjis["5"] = "五"
  kanjis["6"] = "六"
  kanjis["7"] = "七"
  kanjis["8"] = "八"
  kanjis["9"] = "九"

  for(i = 1; i <= 9; i++) {
    line = ""
    for(j = 1; j <= 9; j++) {
      line = line kanji(sprintf("%3d", i*j))
    }
    print line
  }
}

function kanji(s,   i) {
  result = ""
  for(i = 0; i < length(s); i++) {
    result = result kanjis[substr(s, i + 1, 1)]
  }
  return result
}
LL Golf Hole 5 - 最上位の桁を数え上げる (Nested Flatten)

old awkです。 ほぼそのままC言語のコードになっちゃいました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#!awk -f
{
max=$1
print 0
for(b=1;;b*=10) {
        n=b
        for(j=10;--j>0;n+=b) {
                if(n>max) next
                print n
        }

}
}
LL Golf Hole 4 - 文章から単語の索引を作る (Nested Flatten)
awk -f word.awk gpl.txt 
1
2
{gsub(/[^a-zA-Z0-9]/, " ");for(i=1;i<=NF;i++)t[$i]=t[$i]":"NR}
END{for(k in t)print k t[k]}

gawk 一行野郎で。文章は標準入力、出力は標準出力です。

1
gawk -F'\\W' '{ for (i=1; i<= NF; i++) { if ($i != ""){h[$i, NR] = NR; }}} END { for (k in h){split(k,s,SUBSEP);print s[1], h[k];}}'
コード中の文字の頻度分析 (Nested Flatten)

出題者です。 こちらで用意していた回答は awk を使ったものでした。一応解説すると、組み込み変数FSを空にし、１行単位の文字毎に連想配列に格納しています。

1
2
3
4
5
6
7
8
9
# １文字版
BEGIN { FS="" }
{ for (i=1; i<=NF; i++) ht[$i]++}
END { for (c in ht) print ht[c],c }

# ３文字版
BEGIN { FS="" }
{ for (i=1; i<=NF-2; i++) { ht[$i$(i+1)$(i+2)]++}}
END { for (c in ht) print ht[c],c }
BFコンパイラー (Nested Flatten) 
#3964-#3978を、optimize=2 を指定すると身も蓋もなく最適化を行うように改良(?)したもの。

- http://namazu.org/~takesako/ppencode/bpencode.html
- http://pc11.2ch.net/test/read.cgi/tech/1177988460/135
あたりのソースを通してみると面白いです。

% cat helloworld.bf
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.

% awk -v optimize=1 -f bf2awk.awk < helloworld.bf
BEGIN {
  ix = 0
  st[ix] += 10
  while (st[ix]) {
    st[++ix] += 7
    st[++ix] += 10
    st[++ix] += 3
    st[++ix]++
    ix -= 4
    st[ix]--
  }
  st[++ix] += 2
  printf("%c", st[ix])
  printf("%c", ++st[++ix])
  st[ix] += 7
  printf("%c", st[ix])
  printf("%c", st[ix])
  st[ix] += 3
  printf("%c", st[ix])
  st[++ix] += 2
  printf("%c", st[ix])
  ix -= 2
  st[ix] += 15
  printf("%c", st[ix])
  printf("%c", st[++ix])
  st[ix] += 3
  printf("%c", st[ix])
  st[ix] -= 6
  printf("%c", st[ix])
  st[ix] -= 8
  printf("%c", st[ix])
  printf("%c", ++st[++ix])
  printf("%c", st[++ix])
}

% awk -v optimize=2 -f bf2awk.awk < helloworld.bf
BEGIN {
  print "Hello World!"
}

  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
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#
# Brainf*ck to AWK compiler, written in AWK by naoya_t/
#
BEGIN {
    inst_buf = ""
    ix = 0
}
{
    gsub(/#.*$/,""); # comment
    gsub(/[^\[\]<>+\-.,]/,""); if (/^$/) next
    inst_buf = inst_buf $0
}
END {
    if (inst_buf ~ /,/) getchar_used = 1

    # compile
    if (optimize >= 1) reset_last()
    output_buf = ""

    indent = ""
    print "BEGIN {"

    indent_incr()
    if (getchar_used) indent_print("read_buf = \"\"")
    if (getchar_used || optimize < 2) indent_print("ix = 0")

    diff_value[">"] = diff_value["+"] = 1
    diff_value["<"] = diff_value["-"] = -1
    incr_decr[">"] = incr_decr["+"] = "++"
    incr_decr["<"] = incr_decr["-"] = "--"

    N = split(inst_buf, ops, "")
    eval(ops,1,N)

    if (optimize >= 1) out_last()
    flush_buf(0)

    indent_decr()
    indent_print("}")

    if (getchar_used) output_getchar_funcs()
}

function eval(ops,begin,end,  i,j,op,s,till)
{
    for (i=begin; i<=end; i++) {
        op = ops[i]
        if (op ~ /[><]/) {
            ix += diff_value[op] # emulation
            if (optimize >= 1) {
                if (last_inst == "ix") {
                    last_arg += diff_value[op]
                } else {
                    out_last()
                    set_last("ix", diff_value[op])
                }
            } else {
                if (getchar_used || optimize < 2) indent_print("ix" incr_decr[op])
            }
        } else if (op ~ /[+-]/) {
            st[ix] += diff_value[op] # emulation
            if (optimize >= 1) {
                if (last_inst ~ /^st\[/) {
                    last_arg += diff_value[op]
                } else {
                    s = set_incr_decr("st[ix]")
                    if (last_inst) out_last()
                    set_last(s, diff_value[op])
                }
            } else {
                if (getchar_used || optimize < 2) indent_print("st[ix]" incr_decr[op])
            }
        } else if (op == ".") {
            s = "printf(\"%c\", st[ix])"
            if (optimize >= 1) {
                s = set_incr_decr(s)
                if (last_inst) out_last()
            }
            if (getchar_used || optimize < 2)
                indent_print(s)
            else
                putchar(st[ix])
        } else if (op == ",") {
            s = "st[ix] = getchar()"
            if (optimize >= 1) {
                s = set_incr_decr(s)
                if (last_inst) out_last()
            }
            indent_print(s)
        } else if (op == "[") {
            nest = 1
            for (j=i+1; j<=N; j++) {
                if (ops[j] == "[") nest++
                if (ops[j] == "]") nest--
                if (nest == 0) { till = j ; break }
            }
            while_loop(ops, i+1, till-1)
            i = till
        } else {
            ;
        }
    }
}
function while_loop(ops,begin,end,  i,j,putchar_used)
{
    putchar_used = 0
    for (j=begin; j<=end; j++) if (ops[j] == ".") { putchar_used = 1; break }

    if (getchar_used || optimize < 2) {
        out_last()
        indent_print("while (st[ix]) {")
        indent_incr()

        eval(ops,begin,end)

        if (optimize >= 1) out_last()
        indent_decr()
        indent_print("}")
    } else {
        while (st[ix]) eval(ops,begin,end)
    }
}

function putchar(ch)
{
    if (ch == 10 || ch == 13) {
        flush_buf(1)
    } else {
        output_buf = output_buf sprintf("%c", st[ix])
    }
}
function flush_buf(cr)
{
    if (output_buf) {
        gsub(/\\/, "\\\\", output_buf)
        if (cr)
            indent_print("print \"" output_buf "\"")
        else
            indent_print("printf(\"%s\", \"" output_buf "\")")
        output_buf = ""
    }
}

function indent_incr()
{
    indent = "  " indent
}
function indent_decr()
{
    indent = substr(indent, 3)
}
function indent_print(line)
{
    print indent line
}
function set_last(inst,arg)
{
    last_inst = inst
    last_arg = arg
}
function reset_last()
{
    last_inst = ""
    last_arg = 0
}
function out_last(  diff)
{
    if (last_inst ~ /ix/) {
        if (last_arg > 1)
            diff = " += " last_arg
        else if (last_arg == 1)
            diff = "++"
        else if (last_arg == 0)
            diff = ""
        else if (last_arg == -1)
            diff = "--"
        else if (last_arg < -1)
            diff = " -= " (0 - last_arg)

        if (diff && (getchar_used || optimize < 2)) indent_print(last_inst diff)
    }
    last_inst = ""
}
function set_incr_decr(s)
{
    if (last_inst == "ix") {
        if (last_arg == 1) { gsub(/ix/, "++ix", s); last_inst = "" }
        else if (last_arg == -1) { gsub(/ix/, "--ix", s); last_inst = "" }
    } else if (last_inst ~ /^st\[/ && s ~ /printf/) {
        if (last_arg == 1) { gsub(/st\[ix\]/, "++" last_inst, s); last_inst = "" }
        else if (last_arg == -1) { gsub(/st\[ix\]/, "--" last_inst, s); last_inst = "" }
    }

    return s
}

function output_getchar_funcs()
{
    print "function getchar(  ch)"
    print "{"
    print "  if (read_buf ~ /^$/) {"
    print "    if (eof) return -1"
#    print "    if ((getline read_buf) < 1) { eof = 1; return -1 }"
    print "    if (getline != 1) { eof = 1; return -1 } ; read_buf = $0" # a2p
    print "  }"
    print "  ch = ord(substr(read_buf,1,1))"
    print "  read_buf = substr(read_buf,2)"
    print "  return ch"
    print "}"
    
    print "function ord(ch, ofs)"
    print "{"
    print "  if (ch == \"\\t\") return 9"
    print "  if (ch == \"\\n\") return 13"
#    print "  ofs = index(\" !\\\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~\", ch)"
    print "  if (ch == \"@\") return 64" # a2p
    print "  ofs = index(\" !\\\"#$%&'()*+,-./0123456789:;<=>?.ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~\", ch)" # a2p
    print "  return ofs ? 31 + ofs : 0"
    print "}"
}

うう駄目だ、getchar() の定義が出力されないので、#3976の ,+[-.,+] をコンパイルしても動かない。
しかも getchar() が文字コードを返すようになってない。ord() を実装。
全面書き換え。

a2pをかましても動くように getline, index 回りを微調整。
  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
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
BEGIN {
    if (optimize) reset_last()

    indent = ""
    print "BEGIN {"

    indent_incr()
    indent_print("read_buf = \"\"")
    indent_print("ix = 0")
}
{
    gsub(/#.*$/,""); # comment
    gsub(/[^\[\]<>+\-.,]/,""); if (/^$/) next

    N = split($0, op, "")
    for (i=1; i<=N; i++) {
        if (op[i] == ">") {
            if (optimize) {
                if (last_inst == "ix") {
                    last_arg++
                } else {
                    out_last()
                    set_last("ix", 1)
                }
            } else {
                indent_print("ix++")
            }
        } else if (op[i] == "<") {
            if (optimize) {
                if (last_inst == "ix") {
                    last_arg--
                } else {
                    out_last()
                    set_last("ix", -1)
                }
            } else {
                indent_print("ix--")
            }
        } else if (op[i] == "+") {
            if (optimize) {
                if (last_inst ~ /^st\[/) {
                    last_arg++
                } else {
                    s = set_incr_decr("st[ix]")
                    if (last_inst) out_last()
                    set_last(s, 1)
                }
            } else {
                indent_print("st[ix]++")
            }
        } else if (op[i] == "-") {
            if (optimize) {
                if (last_inst ~ /^st\[/) {
                    last_arg--
                } else {
                    s = set_incr_decr("st[ix]")
                    if (last_inst) out_last()
                    set_last(s, -1)
                }
            } else {
                indent_print("st[ix]--")
            }
        } else if (op[i] == ".") {
            if (optimize) {
                s = set_incr_decr("printf(\"%c\", st[ix])")
                if (last_inst) out_last()
                indent_print(s)
            } else {
                indent_print("printf(\"%c\", st[ix])")
            }
        } else if (op[i] == ",") {
            if (optimize) {
                s = set_incr_decr("st[ix] = getchar()")
                if (last_inst) out_last()
                indent_print(s)
            } else {
                indent_print("st[ix] = getchar()")
            }
        } else if (op[i] == "[") {
            if (optimize) {
                s = set_incr_decr("while (st[ix]) {")
                if (last_inst) out_last()
                indent_print(s)
                indent_incr()
            } else {
                indent_print("while (st[ix]) {")
                indent_incr()
            }
        } else if (op[i] == "]") {
            if (optimize) out_last()
            indent_decr()
            indent_print("}")
        } else {
            ;
        }
    }
}
END {
    if (optimize) out_last()
    indent_decr()
    indent_print("}")

    print "function getchar(  ch)"
    print "{"
    print "  if (read_buf ~ /^$/) {"
    print "    if (eof) return -1"
#    print "    if ((getline read_buf) < 1) { eof = 1; return -1 }"
    print "    if (getline != 1) { eof = 1; return -1 }" # a2p
    print "    read_buf = $0" # a2p
    print "  }"
    print "  ch = ord(substr(read_buf,1,1))"
    print "  read_buf = substr(read_buf,2)"
    print "  return ch"
    print "}"

    print "function ord(ch, ofs)"
    print "{"
    print "  if (ch == \"\\t\") return 9"
    print "  if (ch == \"\\n\") return 13"
#    print "  ofs = index(\" !\\\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~\", ch)"
    print "  if (ch == \"@\") return 64" # a2p
    print "  ofs = index(\" !\\\"#$%&'()*+,-./0123456789:;<=>?.ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~\", ch)" # a2p
    print "  return ofs ? 31 + ofs : 0"
    print "}"
}

function indent_incr()
{
    indent = "  " indent
}
function indent_decr()
{
    indent = substr(indent, 3)
}
function indent_print(line)
{
    print indent line
}
function set_last(inst,arg)
{
    last_inst = inst
    last_arg = arg
}
function reset_last()
{
    last_inst = ""
    last_arg = 0
}
function out_last(  diff)
{
    if (last_inst ~ /ix/) {
        if (last_arg > 1)
            diff = " += " last_arg
        else if (last_arg == 1)
            diff = "++"
        else if (last_arg == 0)
            diff = ""
        else if (last_arg == -1)
            diff = "--"
        else if (last_arg < -1)
            diff = " -= " (0 - last_arg)

        if (diff) indent_print(last_inst diff)
    }
    last_inst = ""
}
function set_incr_decr(s)
{
    if (last_inst == "ix") {
        if (last_arg == 1) { gsub(/ix/, "++ix", s); last_inst = "" }
        else if (last_arg == -1) { gsub(/ix/, "--ix", s); last_inst = "" }
    }
    return s
}

オプティマイズ時に
++ix
st[ix]++
st[ix]++
st[ix]++
が
st[++ix]++
st[ix] += 2
となっていたのを
st[++ix] += 3
のようにちゃんとまとめるように修正するパッチ
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
--- bf2awk.awk.orig    2007-11-14 00:43:07.000000000 +0900
+++ bf2awk.awk    2007-11-14 01:55:50.000000000 +0900
@@ -38,7 +38,7 @@
             }
         } else if (op[i] == "+") {
             if (optimize) {
-                if (last_inst == "st[ix]") {
+                if (last_inst ~ /^st\[/) {
                     last_arg++
                 } else {
                     s = set_incr_decr("st[ix]")
@@ -50,7 +50,7 @@
             }
         } else if (op[i] == "-") {
             if (optimize) {
-                if (last_inst == "st[ix]") {
+                if (last_inst ~ /^st\[/) {
                     last_arg--
                 } else {
                     s = set_incr_decr("st[ix]")

optimize=1 の時に while(st[ix]) の直前に ix++ や ix-- が来ると while(st[++ix]) のように誤ったオプティマイズが行われるバグを修正
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
--- bf2awk.awk.orig    2007-11-14 00:43:07.000000000 +0900
+++ bf2awk.awk    2007-11-14 01:46:46.000000000 +0900
@@ -77,15 +77,9 @@
                 indent_print("st[ix] = getchar()")
             }
         } else if (op[i] == "[") {
-            if (optimize) {
-                s = set_incr_decr("while (st[ix]) {")
-                if (last_inst) out_last()
-                indent_print(s)
-                indent_incr()
-            } else {
-                indent_print("while (st[ix]) {")
-                indent_incr()
-            }
+            if (optimize) out_last()
+            indent_print("while (st[ix]) {")
+            indent_incr()
         } else if (op[i] == "]") {
             if (optimize) out_last()
             indent_decr()

久しぶりに投稿します。
-v optimize=1 とするとオプティマイズされます（笑

helloworld.bf:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.

% awk -f bf2awk.awk helloworld.bf > helloworld.awk
% awk -f helloworld.awk 
Hello World!

helloworld.awk:
BEGIN {
  ix = 0
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  while (st[ix]) {
    ix++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    ix++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    ix++
    st[ix]++
    st[ix]++
    st[ix]++
    ix++
    st[ix]++
    ix--
    ix--
    ix--
    ix--
    st[ix]--
  }
  ix++
  st[ix]++
  st[ix]++
  printf("%c", st[ix])
  ix++
  st[ix]++
  printf("%c", st[ix])
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  printf("%c", st[ix])
  printf("%c", st[ix])
  st[ix]++
  st[ix]++
  st[ix]++
  printf("%c", st[ix])
  ix++
  st[ix]++
  st[ix]++
  printf("%c", st[ix])
  ix--
  ix--
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  printf("%c", st[ix])
  ix++
  printf("%c", st[ix])
  st[ix]++
  st[ix]++
  st[ix]++
  printf("%c", st[ix])
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  printf("%c", st[ix])
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  printf("%c", st[ix])
  ix++
  st[ix]++
  printf("%c", st[ix])
  ix++
  printf("%c", st[ix])
}

% awk -v optimize=1 -f bf2awk.awk helloworld.bf > helloworld-optimized.awk
% awk -f helloworld-optimized.awk 
Hello World!

helloworld-optimized.awk:
BEGIN {
  ix = 0
  st[ix] += 10
  while (st[ix]) {
    st[++ix]++
    st[ix] += 6
    st[++ix]++
    st[ix] += 9
    st[++ix]++
    st[ix] += 2
    st[++ix]++
    ix -= 4
    st[ix]--
  }
  st[++ix]++
  st[ix]++
  printf("%c", st[ix])
  st[++ix]++
  printf("%c", st[ix])
  st[ix] += 7
  printf("%c", st[ix])
  printf("%c", st[ix])
  st[ix] += 3
  printf("%c", st[ix])
  st[++ix]++
  st[ix]++
  printf("%c", st[ix])
  ix -= 2
  st[ix] += 15
  printf("%c", st[ix])
  printf("%c", st[++ix])
  st[ix] += 3
  printf("%c", st[ix])
  st[ix] -= 6
  printf("%c", st[ix])
  st[ix] -= 8
  printf("%c", st[ix])
  st[++ix]++
  printf("%c", st[ix])
  printf("%c", st[++ix])
}

  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
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
BEGIN {
    read_buf = ""
    if (optimize) reset_last()

    indent = ""
    indent_print("BEGIN {")

    indent_incr()
    indent_print("ix = 0")
}
{
    gsub(/#.*$/,""); # comment
    gsub(/[^\[\]<>+\-.,]/,""); if (/^$/) next

    N = split($0, op, "")
    for (i=1; i<=N; i++) {
        if (op[i] == ">") {
            if (optimize) {
                if (last_inst == "ix") {
                    last_arg++
                } else {
                    out_last()
                    set_last("ix", 1)
                }
            } else {
                indent_print("ix++")
            }
        } else if (op[i] == "<") {
            if (optimize) {
                if (last_inst == "ix") {
                    last_arg--
                } else {
                    out_last()
                    set_last("ix", -1)
                }
            } else {
                indent_print("ix--")
            }
        } else if (op[i] == "+") {
            if (optimize) {
                if (last_inst == "st[ix]") {
                    last_arg++
                } else {
                    s = set_incr_decr("st[ix]")
                    if (last_inst) out_last()
                    set_last(s, 1)
                }
            } else {
                indent_print("st[ix]++")
            }
        } else if (op[i] == "-") {
            if (optimize) {
                if (last_inst == "st[ix]") {
                    last_arg--
                } else {
                    s = set_incr_decr("st[ix]")
                    if (last_inst) out_last()
                    set_last(s, -1)
                }
            } else {
                indent_print("st[ix]--")
            }
        } else if (op[i] == ".") {
            if (optimize) {
                s = set_incr_decr("printf(\"%c\", st[ix])")
                if (last_inst) out_last()
                indent_print(s)
            } else {
                indent_print("printf(\"%c\", st[ix])")
            }
        } else if (op[i] == ",") {
            if (optimize) {
                s = set_incr_decr("st[ix] = getchar()")
                if (last_inst) out_last()
                indent_print(s)
            } else {
                indent_print("st[ix] = getchar()")
            }
        } else if (op[i] == "[") {
            if (optimize) {
                s = set_incr_decr("while (st[ix]) {")
                if (last_inst) out_last()
                indent_print(s)
                indent_incr()
            } else {
                indent_print("while (st[ix]) {")
                indent_incr()
            }
        } else if (op[i] == "]") {
            if (optimize) out_last()
            indent_decr()
            indent_print("}")
        } else {
            ;
        }
    }
}
END {
    if (optimize) out_last()
    indent_decr()
    indent_print("}")
}

function getchar(  ch)
{
    if (read_buf ~ /^$/) getline read_buf
    ch = substr(read_buf,1,1)
    read_buf = substr(read_buf,2)
    return ch
}
function indent_incr()
{
    indent = "  " indent
}
function indent_decr()
{
    indent = substr(indent, 3)
}
function indent_print(line)
{
    print indent line
}
function set_last(inst,arg)
{
    last_inst = inst
    last_arg = arg
}
function reset_last()
{
    last_inst = ""
    last_arg = 0
}
function out_last(  diff)
{
    if (last_inst ~ /ix/) {
        if (last_arg > 1)
            diff = " += " last_arg
        else if (last_arg == 1)
            diff = "++"
        else if (last_arg == 0)
            diff = ""
        else if (last_arg == -1)
            diff = "--"
        else if (last_arg < -1)
            diff = " -= " (0 - last_arg)

        if (diff) indent_print(last_inst diff)
    }
    last_inst = ""
}
function set_incr_decr(s)
{
    if (last_inst == "ix") {
        if (last_arg == 1) { gsub(/ix/, "++ix", s); last_inst = "" }
        else if (last_arg == -1) { gsub(/ix/, "--ix", s); last_inst = "" }
    }
    return s
}
変形Fizz-Buzz問題 (Nested Flatten) 
ifは全部試行するので条件6もみたしているはず。
1
2
3
4
5
6
7
8
9
BEGIN{
        for (x=1;x<=20;x++) str[x]=x ":hoge";
        for (x=1;x<=20;x++) {
         if (x%3==0) str[x]=x ":Fizz";
         if (x%5==0) str[x]=x ":Buzz";
         if (x%15==0) str[x]=x ":FizzBuzz";
        }
  for (x=1;x<=20;x++) { print str[x] }
}
重複無し乱数 (Nested Flatten) 
1〜nの要素を持つベクトルを作り，端から順に無作為に並べ替えてゆく。
ランダムさはそれで十分だろう。
スクリプト中のnへ値を渡すのは -v n=5 のように

 > awk -f p3402.awk -v n=10
 4 10 9 1 2 6 5 8 3 7
 > awk -f p3402.awk -v n=10
 4 10 9 1 2 6 5 8 3 7
 > awk -f p3402.awk -v n=10
 3 2 5 4 7 9 10 1 6 8

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
BEGIN {
    srand()
    for (i = 1; i <= n; i++) x[i] = i
    for (i = 1; i <= n; i++) {
        j = int(rand()*n)+1
        t = x[i]
        x[i] = x[j]
        x[j] = t
    }
    for (i = 1; i <= n; i++) printf " %i", x[i]
    print ""
}
文字列の反転 (Nested Flatten) 
split が文字列を分解するのは gawk に限られると思われ。。。

gawk -f p3414.awk -v string="split string array fieldsep"
pesdleif yarra gnirts tilps

スクリプト中の変数 string への値の受け渡しはgawk コマンドの -v オプションで
1
2
3
4
5
BEGIN {
        n = split(string, a, "")
        for (i = n; i >= 1; i--) printf "%s", a[i]
        print "\n"
}
exp(pi * sqrt(n))が整数に近くなるnを探す (Nested Flatten) 
やはり，awk も倍精度実数までしか使えないから
37 と 58 しか捕まえられないなあ

awk -f p3416.awk
37 : 199148647.99997794628
58 : 24591257751.999965668

1
2
3
4
5
6
7
8
9
BEGIN {
    PI = atan2(1,1)*4
    for (n = 1; n < 100; n++) {
        x = exp(PI*sqrt(n))
        if (abs(x-int(x+0.5)) < 0.0001) printf "%i : %.20g\n", n, x
    }
}

function abs(x) { return x < 0 ? -x : x }
逆転したビット列 (Nested Flatten) 
スクリプト中の変数 n に値を送り込むのは，-v オプションで，以下のようにする

awk -f p3417.awk -v n=3
0
4
2
6
1
5
3
7

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
BEGIN {
    for (i = 0; i < 2^n; i++) {
        print foo(n, i)
    }
}

function foo(n, i,     sum, j, x) {
    sum = 0
    for (j = 0; j < n; j++) {
        x = i%2
        i = int(i/2)
        sum += x*2^(n-j-1)
    }
    return sum
}
格子点の列挙 (Nested Flatten) 
ソート部分は単純なものを採用。
今はR，昔は awk を使っていたもので，R のプログラムと同様。でも，R は遙かに楽だなあ。
 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
28
29
30
31
32
33
34
BEGIN {
    n = 0
    for (i = -18; i <= 18; i++) {
        for (j = -18; j <= 18; j++) {
            x[n] = i
            y[n] = j
            d[n++] = sqrt(i^2+j^2)
        }
    }
    for (i = 0; i < n-1; i++) {
        mini = d[i]
        minp = i
        for (j = i+1; j < n; j++) {
            if (d[j] < mini) {
                mini = d[j]
                minp = j
            }
        }
        if (i != minp) {
            d[minp] = d[i]
            d[i] = mini
            t = x[i]
            x[i] = x[minp]
            x[minp] = t
            t = y[i]
            y[i] = y[minp]
            y[minp] = t
        }
    }
    printf "%4s %3s %3s %10s\n", "No.", "x", "y", "r"
    for (i = 0; i < 1000; i++) {
        printf "%4i: %3i %3i %10.6f\n", i+1, x[i], y[i], d[i]
    }
}
水の移し替えパズル (Nested Flatten) 
A<=B<=Cとしたとき、

・AとBから、Aが空になるまで汲み続け、
・BとCからAに汲み、AとBからCに汲む、を繰り返す

と、できると思ったんですが、最短なのかどうかよくわかりません。
正解はどこかにあります？
 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
{
    # A, B, C を cups[0], cups[1], cups[2] とする
    cups[0] = $1
    cups[1] = $2
    cups[2] = $3

    # A <= B <= C にそろえる
    sort(cups)

    total = 0
    # A と B からとり、C に移す。A が空になるまで
    count = cups[0]
    cups[0] = 0
    cups[1] -= count
    cups[2] += count * 2
    total += count

    # B が空になるまで、以下を繰り返す。
    # B と C から取って A に移し、A と B からとって C に移す。
    count = cups[1]
    cups[0] = count % 2
    cups[1] -= count
    cups[2] += count * 2
    total += count

    if(cups[0] != 0) {
        print "N/A"
    } else {
        print "Total :", total
    }
}


# 3要素に限定したソート
function sort(cups) {
    if(cups[0] > cups[1]) {
        swap(cups, 0, 1)
    }
    if(cups[0] > cups[2]) {
        swap(cups, 0, 2)
    }
    if(cups[1] > cups[2]) {
        swap(cups, 1, 2)
    }
}

function swap(a, i, j,   tmp) {
    tmp = a[i]
    a[i] = a[j]
    a[j] = tmp
}
next >>

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]