第3回コードゴルフ大会 WriteUp - hakatashi/esolang-battle GitHub Wiki
与えられた8桁の2進数が、三角数かどうか判定せよ。
- 8桁の2進数が50個、改行(LF)区切りで与えられる。
- 与えられた2進数が三角数なら1を、三角数でないなら0を出力せよ。都合50個の文字が出力される。
- 0は三角数である。
- 出力に含まれる空白文字は無視される。
- 0と1と空白文字以外の文字を出力してはいけない。
- 与えられる50個の数のうち、三角数は25個含まれる。
- 含まれる25個の三角数には、255以下の三角数23個が全て含まれる。
- 重複と順序に関しては保証されない。
- 組み込み関数
-
base
,int
,parseInt
,str2nr
...
-
-
eval
- 2進数リテラルが実装されている言語の場合、
eval('0b' + input())
で短く書ける場合もある。 - 後述する8倍して1足す操作と組み合わせて、
eval('0b' + input() + '001')
ともできる。
- 2進数リテラルが実装されている言語の場合、
- 上の桁から順に2倍して足す操作を繰り返す。
- 進数という概念がない言語の場合、最悪この方法を取ることになる。
- ビットシフトと組み合わせると便利。
- 1から順番に下から足していき、目標の数に一致したら三角数とする。
- 低級な言語で有効なテクニック。
- 実際には目標の数から引いていったほうが楽な場合が多い。
- 8倍して1足した数が平方数ならば三角数。
- 今回の大会でいちばん重要な、金科玉条のテクニック。
- 平方根が扱える言語ではこちらのメソッドが非常に有利。
- ちなみに、平方根した数は必ず奇数になる。
- 全列挙
- 超低級言語の場合、最悪この方針で解ける。が、平方数23個×8桁で最低184文字を消費するのは痛い。
- 今回の大会では本当に最初の最初でしか使われなかったイメージ。
-
pow(int(sqrt(N)), 2) == N
-
sqrt
がint型を返す言語で有利。
-
- 1, 3, 5, 7 ... と順番に足していき、目標の数に一致したら平方数。
- 実際にはこれをするくらいなら三角数の判定でループしたほうがまし。
- ...
-
int(N) == N
- 基本。
- 浮動小数点数と整数を暗黙に型変換する言語では
N | 0 == N
のほうが短いこともある。
-
mod 1
テクニック-
N % 1 == 0
なら整数 - 真偽が反転するが、
N % 1 > 0
のほうが短い。 - 実際にはfloatのmodは定義されてない場合が多い。
-
int(N * 99) % 99 == 0
とするとよい(%
が整数への暗黙の型変換を行う場合に有利)
-
-
-
fmod
テクニック- libcに含まれている関数
fmod
は浮動小数点のmodを計算する。 - Vim, C, PHP など、意外といろんな言語で実装されている。
- libcに含まれている関数
-
strlen(str(N)) < 3
- 今回の問題では N < 45 なので、これで判定できる。
-
strlen
に相当する関数が暗黙の型変換を行う場合に有利。
.��8!��%�o�! ����&,-(8�=�1��v
以下はアセンブリ。
readlineloop:
; c is always zero
inc c
ld l,$0
readloop:
; accumulate input to c
call $8003 ; a = getchar()
jr c,end
and $1 ; a &= 1
sla l ; l << 1
add l ; a += l
ld l,a ; l = a
sla c ; c << 1
jr nz,readloop ; goto readloop if c != 0
call $8003 ; skip newline
xor a ; a = 0
; now l has input number
ld h,$0
; de=0
ld de,$0
loop:
; goto hlnotzero if hl!=0
inc l
dec l
jr z,printone
; de-
dec de
; hl+=de
add hl,de
jr c,loop
; print '0'
dec a
printone:
; print '1'
add a,$31
rst $38 ; the magic to call putchar()
jr readlineloop
end:
halt
xor a
を使えたので満足 (?)
https://esolang.hakatashi.com/submissions/59a11c1b89d3030742c724f6
制御文字を<>
記法で書くと以下のようになる。
qzC<C-R>=fmod(sqrt(str2nr(@@,2)*8+1),1)==0
<Esc>wq49@zZZ
str2nr
の存在に気づいてよかった。
使用している主なテクニック:
-
qz~q
でマクロ記録、49@z
で49回再生。 -
C
でデフォルトレジスタに格納、@@
で呼び出し -
<C-R>=
でexpression挿入。Vimの組み込み関数やレジスタが使える。
akouryyのテクニックを使うとさらに3bytes縮む。
qzC<C-R>=fmod(sqrt(("0b".@@)*8+1),1)==0
<Esc>wq49@zZZ
38 bytes
loop{p 2[1-(gets.to_i(2)*8+1)**0.5%1]}
- 整数
n
に対してn == 0 ? 1 : 0
は1[n]
(2進数で1の下からn桁目)と書けるが、浮動小数点数x
に対してはx
が0方向に丸められるため1[x]
も1[-x]
も使えない。2[1-x]
とするとうまくいく。 - 大抵の場合、EOFに達した後も
nil.to_i == 0
なのでエラー終了はできないが、今回は基数を指定しているのでエラーが発生する。@kurgm さんの goruby の解答を見て知った。
38 bytes
(1vn2nD*:vG2sB8nM1nA#nP1NmOnOtSsP;50bR
8+1個の変数をどう使うかが醍醐味の言語だが、今回は2+1個しか使わなかった。
( // 変数 a と f を使うことを宣言
1 vn 2 nD * // 0.5を permavar と呼ばれる変数に代入
: // ループ開始
vG 2 sB // 1行読み込んで2進数として解釈した数値を a に代入
8 nM 1 nA # nP // a に8をかけて1を足して permavar == 0.5 乗した値を a に代入
1 NmO nO // a を1で割った剰余の論理否定を a に代入
tS sP // a を文字列に変換して出力
; 50 bR // ループ終了, 50回繰り返す
981 bytes
ソースコード
入力を読み込んで各桁をa-h
に保存、それらの否定をA-H
に保存、a
とb
、c
とd
など2桁ごとの組み合わせを保存、あとは23個の三角数を全列挙して調べる。
199 bytes
WITH RECURSIVE f(x)AS(SELECT""UNION SELECT x+9 FROM f LIMIT 50)SELECT cast(substr((SELECT*FROM i),x)as R)%256 IN(0,1,11,110,242,87,117,92,4,237,31,74,150,67,201,216,104,121,19,134,218,207,189)FROM f;
まず[0,9,18,...(50個)]
というリストf
を作り、入力全体からsubstrを得る。2進数として解釈するのは諦めて、10進数と見なして256で剰余をとる(剰余は被らない)。23個の三角数の剰余を全列挙して調べる。
209 bytes
🚳🚳📲⛽🚳📱⛽450🚘📥🐣🚘⛽👥🚳📱👥⛽9🚘📥👫👥🚳📲✂⛽0b🚘🔀👫🔢🚳🚲📲⛽👥🚳🐔🚘⛽🚲📱📤👥🚲📲🌊🚘🔃🚳👬📥➡🚘🔃
スタック型の言語。Python で実装されていて、ところどころで 0
の代わりに False
が使えたりする。
// 最初に入力全体が1つの文字列としてスタックに積まれている
🚳🚳📲 // vars[False] = False (この変数は後に 9, 18, 27, ...が代入される。False は 0 の代わり)
⛽
🚳📱 // vars[False]
⛽450🚘📥 // int("450")
🐣 // 比較(vars[False] < 450)
🚘
⛽
👥 // 入力全体をdup
🚳📱 // vars[False]
👥⛽9🚘📥👫 // vars[False] + int("9")
👥🚳📲 // vars[False] = vars[False] + 9
✂ // 文字列を切り出す(入力全体[vars[False] : vars[False] + 9])
⛽0b🚘🔀👫🔢 // int("0b" + 切り出してきた文字列, 0)(2進数のパース)
🚳🚲📲 // vars[True] = False(三角数の判定で入力値から順に引く整数の初期化)
⛽
👥🚳🐔 // スタックの1番上 > False (False は 0 の代わり)
🚘
⛽
🚲📱 // vars[True]
📤 // インクリメント(本来はこの絵文字は切り上げなのだが実装がなぜか int(x + 1) なのでインクリメントできる)
👥🚲📲 // vars[True] = インクリメントの結果
🌊 // インクリメントの結果を引く
🚘🔃 // whileループ
🚳👬📥➡ // int(スタックの1番上(0 以下になるまで引かれた結果)== 0) を出力
🚘🔃 // whileループ
133 bytes
🏁🍇🔁👍🍇🍊😛0.0🚮⛷🚀➕1✖8🍺🚂🔷🔡😯🔤🔤2 1.0🍇😀🔡1 2🍉🍓🍇😀🔡0 2🍉🍉🍉
オブジェクト指向の静的型付き言語。方針としては √(8N+1)%1==0 のやつ。Optional(🍬) という概念があって、ぬるぽになりうるところがコンパイル時に分かる。以下、整形済みのコード。(👴より後ろはコメントです)
🏁🍇 👴 main() {
🔁👍🍇 👴 while (true) {
🍊 👴 if (
😛0.0 👴 (0.0).equals(
🚮 👴 (⛷〜2).mod
⛷ 👴 (🚀〜2).sqrt()
🚀 👴 (➕〜2).toFloat()
➕1 👴 (1).plus(
✖8 👴 (8).times(
🍺 👴 Optionalでない型へのキャスト。実行時に✨(要するに null)が来ると例外で死ぬ
🚂 👴 (🔷〜🔤🔤).toInt(2) (2 は基数)(失敗すると✨を返す)
🔷🔡😯🔤🔤 👴 input("")
2 👴 基数の2
1.0 👴 modの引数
🍇 👴 )))) { (ifのブロック)
😀🔡1 2 👴 (1).toString(2).print() (UTF-8 では 🔤1🔤 よりも 🔡1 2 のほうが短い)
🍉 👴 }
🍓🍇 👴 else {
😀🔡0 2 👴 (0).toString(2).print()
🍉 👴 }
🍉 👴 }
🍉 👴 }
(一般的な?言語と違ってオブジェクトよりメソッド名のほうが先にくるので少し分かりづらい)
87 bytes
for(a=java.util.Scanner(java.lang.System.in);;)print(+!(Math.sqrt(a.nextInt(2)*8+1)%1))
青チームとの激戦の末に制した言語。実質 Java。勝敗の決め手は java.util.Scanner
の前の new
の有無でした。
55 bytes
vv+1::+1$_'x-!.
0>*:b0g\`^
v^+1::0p0b$_+2*
>#@~'0-:0\`^
入力した文字から48を引いて、足した後に2倍する(最終的に入力n
の2倍が得られる):
v
0
v _+2*
> ~'0-:0\`^
2n
を'x
と書いてある1行12文字目に保存(b0p
)。i=0
とする:
'x
0p0b$_
2n
(1行12文字目のord,b0g
)とi*(i+1)
を比較し、i*(i+1)
の方が小さい間はi+=1
として繰り返す:
v+1::+1$_
>*:b0g\`^
^+1::
2n<=i*(i+1)
となったら、1行12文字目のordを'
を用いて取得し、i*(i+1)-2n
の論理否定を出力、始めに戻る:
v _'x-!.
0
v
>#@~
繰り返しは、~
がEOFで跳ね返り、@
に達することによって終了する。
49 bytes
0v0 n=0<
*>i:0(?;68*-:0(?v+2
:@-:0)?!v$2+:02.>~0
2行目で入力の2進数を解釈し、その2倍の値をスタックに保存する。3行目で各i*(i+1)
と比較し、1行目で出力する。
78 bytes
$
. v{m}2{a}s}3{<va}2{]<<
>0>{[{?{5}r @>}}s{ @1%$.
. ^{ %0<.
$
仕様が謎で、2~4行目の最後に余分な文字が必要。入力の際、ASCIIコードを5で割った剰余で分岐する(0なら改行)。入力した値から0,1,2,…を順に引いていき、0や負になるか判定する。50回の繰り返しはmain再帰とエラー終了で実現している。
739 bytes
ソースコード
安全地帯のため全列挙(ほんの少し圧縮している)。
3455 bytes
ソースコード
同じく全列挙。
57 bytes
% <{%#.< >,+86%
>2*)!<>; [#^1{_
^ +1$:86*^-2,:-*<
\
入力の2倍を保存。i=48,46,44,...,0
の順に入力の2倍から48-i
を引いていき、0や負になるか判定する。
104 bytes
$'b'{niam}ioq(i)()-@
-(!i!)(!!)()(i)g<
#{b}a1(i)s(i)()-@
$'main'
-i2mia2mia2mia2mia2mia2mia2mia0{b}
見た目がまったく Rail らしくなくなってしまった。2 進変換は 1 文字ずつ読む方式、判定は 1, 2, 3, ... を引いていって 0 になるか負になるかを見る方式。
テクとしては
- ループを環状で書くとなんだかんだで文字数を要するので、ループ展開する or 再帰呼び出しを使う とよい
- 最後に入力が取れなくてエラーで終了するので、関数の最後に書くべき
#
は省略できる - 変数名が 0 文字でも良いらしい(
(!!)
で保存して()
で呼び出せる)
など。あと、クソ仕様だったのが、文字列と整数を区別していないのはいいが、整数として使う(算術演算/大小比較)ときに -
が含まれると型エラーで落ちる。(そのくせ引き算の結果が負だと当然ながら -
が入る。)当初は大小比較の際に、文字列の一文字目が -
かどうかを見ていたが、@akouryy1 プロが引き算の前に大小比較をする技で縮めてくれた。
39 bytes
print!((1+8*oct"b$_")**.5*99%99)|0for<>
%
(剰余)が整数同士の演算で、勝手に整数に切り捨てられるので、mod 1 テクが使えない。N = 0〜255 に対して √(8N+1) の小数部分を調べたら、0 の次に小さいのは 0.011362 だったので、100 倍ぐらいして計算すればよさそうということで * 99 % 99
テクが誕生。
あと今回初めて知ったが、Perl では !
とか ==
とかが返す値は 1
か ''
(空文字列)らしくて、|0
が必要だった。それからoct関数に渡す文字列の 0b
の 0
は要らないらしい(@akouryy1 氏が縮めてくれました)。
137 bytes
using System;class _{static void Main(){for(int i=0;i++<50;Console.Write(Math.Sqrt(1+8*Convert.ToByte(Console.ReadLine(),2))%1>0?0:1));}}
いちいち長いのでコードゴルフには向いていないと思いますね。
199 bytes
↑のサイズは ZIP で固めたときのサイズです。元のフォルダ構造は:
-
if
/-
0<1)for(int i=0;i++<50;Console.Write(Math.Sqrt(1+8*Convert.ToByte(Console.ReadLine(),2))%1>0?0:1)
/
-
if
フォルダは、(アルファベット順で)最初のフォルダ名を条件式とするのだが、C# の式ならなんでも書けるので、インジェクションをした(ダメ元でやったら通ってしまった)。だいたい次のような C# のプログラムに変換されてコンパイルされる:
if(0<1)for(int i=0;i++<50;Console.Write(Math.Sqrt(1+8*Convert.ToByte(Console.ReadLine(),2))%1>0?0:1)){}
あとは ZIP でゴルフ。正直いってこれでは面白みがないのでいつかインジェクションをしないやつをやってみたい。
57 bytes
$Input|%{+!([Math]::Sqrt([Convert]::ToByte($_,2)*8+1)%1)}
C# と同じような API が使えたので、それを参考に。(入力のとり方がググってもよく分からなくてそれが一番の難関だった。)
361 bytes
あまり縮めてはいない。左シフトしつつ加算して10進法に直し、それを1から順に引いていった。
47 bytes
while 1:print(+((1+8*int(input(),2))**.5%2==1))
無限ループだがEOFまで来ると例外で停止するので問題ない。(@kurgm 案)
はじめ 0 if ... else 1
としていたが +True == 1
を利用して短縮した。
49 bytes
while 1:print+((1+8*int(raw_input(),2))**.5%2==1)
Python 3 のコードからちょっと変えただけ。 print
は関数でなく文なので括弧が要らない。Python 3 の input()
は 2 では raw_input()
になる(input()
は eval(raw_input())
に同じ)。(ちなみに `〜`
が repr(〜)
と同義なのを利用して int(`input()`, 2)
とかできないかなと思ったけど、0から始まる数値リテラルが8進数と見なされるのでダメだった。)
94 bytes
import std.stdio,std.math;void main(){int a;for(;readf(" %b",a);)write(1-(sqrt(1+a*8.)%1>0));}
readf
に %b
が指定できるのがよい。(今考えると int a;for(;
を for(int a;
にすれば 1 文字縮むなあ)
95 bytes
import std.stdio,std.math;void main(){int a;for(;readf(" %b",&a);)write(1-(sqrt(1+a*8.)%1>0));}
ほぼ D (DMD) からコピペ。DMD の方は readf(" %b",a)
で動いたのが、こっちは readf(" %b",&a)
(&
がある)でないと動かなかった(謎)(というより DMD の方で &
がいらないのが謎)。
87 bytes
module c;real d;initial while($fscanf(1<<31,"%b",d))$write($sqrt(d*8+1)%2==1);endmodule
$fscanfで入力を読み取る.
第一引数の1<<31は標準入力を表すfd的なもの.
第二引数の"%b"で入力を2進数として読み取り、第三引数で指定している変数d格納。
最後に3角数判定をして出力(true==1,false==0)
ちなみに"%b"は9570、$sqrt()は()**0.5にしても同バイト数で動く。
658 bytes
ソースコード
あまり面白い言語ではなかった。2進数は一桁ずつ読み込む。平方根(の小数点以下切り捨て)の2乗がもとの数と等しいかを調べる。
301 bytes
ソースコード
これもあまり面白くはない。2進数を一桁ずつ読み込み、0,1,2,…を順に引いていく。
186 bytes
{M[maA!sS!iI!oO!N<50>=/N<0><-1>NN*2aa.?=1J<8>=/JJJ*3aa.?=0aa.?ic.?s(sn).?<48>as.?aa.?\B1=,ic.?,J<23>=/JJ*1aa.?0J*am.?<2>ad.?EB*2ae.?=/E"1"oo.?B3=E4=\EB*2a(gt).?=/E"0"oo.?B3=E4=\J2=,,\\]}
スタック式オブジェクト指向。変数を使わずスタックを直接参照したほうが代入がない分短くなるが読みにくい。入力と23*22/2,22*21/2,21*20/2,…を順に比べていき入力の方が大きいor等しくなるときを探す。 詳細
39 bytes
\50
&&& &&& &&j
PN~|v>~*d~b
1 8 10
高階関数の記法がなかなか把握できなかった。以下のようなイメージ。&
は関数合成、~
はカリー化。
50.times{|x| puts !(sqrt(1+8* eval(gets).to_s(10).to_i(2))%1)}
50 / P N v > 8~* j(x) 10~b d 1~|
114 bytes
48$>{,<.__\=<.'.))>"*{\--.._'*._<>></*"=*1"/.|._=/=}-=.$\@~}||>*="\.=.._-"._/_\+}/.''><(*>\|.<"'_.!1=.>_*''__\~<\<
参考
六角形のコードと六角形の辺からなるメモリがある言語。2日間メモリの形を誤解していた。
4 8 $ > { , <
. _ _ \ = < . '
. ) ) > " * { \ -
- . . _ ' * . _ < >
> < / * " = * 1 " / .
| . _ = / = } - = . $ \
@ ~ } | | > * = " \ . = .
. _ - " . _ / _ \ + } /
. ' ' > < ( * > \ | .
< " ' _ . ! 1 = . >
_ * ' ' _ _ \ ~ <
\ < . . . . . .
. . . . . . .
1文字読み込み、48から入力の文字コードを引いた値の符号を調べる:
4 8 $ . { , <
. '
. -
. >
. .
. .
. .
. .
. .
< .
0や負である間は、E=(E+入力)*2
という式でメモリを更新していく。最終的にE
は入力の数値の2倍になる:
. . . > . . .
. _ _ \ = < .
. ) ) > " * { \ .
. _ _ .
> < / .
| _ .
. ~ } | .
. _ - .
. ' .
< .
途中の条件分岐は、入力が0でも1でもメモリの値を2に揃えるためのもの。
48-入力の文字コード
が正になったら、改行に到達したので三角数判定を始める。まずI=0,J=1
とする:
. / * " = * 1 " / .
. = .
. | .
. " .
. ' .
< " .
_ .
J*I
とE
を比較し、Eの方が大きいならI,J
をそれぞれ1増やす。そして比較に戻って繰り返す。
- _ ' * _ < .
. .
. / = } - = $ \
. > * = " \ = .
. \ + } /
. | .
. >
E
がJ*I
以下になったら"0"または"1"を出力し、E
を0に初期化して入力に戻る。
. . . > . . .
. .
. .
. .
. .
. .
. .
. _ _ .
. > < ( * > \ .
. ' _ ! 1 = >
. * ' ' _ _ \ ~ <
\ < .
. . . . . . .
EOFに達すると、文字コードとして0が返ってくるので、このとき終了する。
. . . > . , <
. .
. .
. .
. .
. .
@ .
13 bytes
50FEC8*>tÉn,
スタックベース言語。
-
50F
で 50 回のループ(終了の}
は最後に補われる)。 -
E
で入力を読み、C
で 2 進数をパース。 -
8*>
で 8 倍して 1 を足し、t
で平方根を得る。 - 整数かどうかを判定するコマンドが無かったが、奇数かどうかの判定をするコマンド
É
があったので、これを使った。 - これで得られるのは bool 型なので、int に変換してやる必要がある。自乗するコマンド
n
があったのでそれを使ってみた。 -
,
で出力。
34 bytes
n%{0:a\{2%+2*}/{a-a 2+:a;.0>}do!}%
スタックベース言語。
-
n%
で入力を改行ごとに区切る。(n
は改行文字を push する) -
{...}%
は配列の map。結果が実行後に出力される。-
0:a
は変数a
に 0 を代入する。スタックには 0 が残る。 -
\
はスタックの上 2 つを入れ替える。(一番上が入力された行、2 つ目が 0 になる) -
{...}/
は配列の each。-
2%
は 48 ('0'
), 49 ('1'
) を 0, 1 にする。 -
+2*
で 2 進数を整数に変換していく。base
というドンピシャなコマンドがあるのだが、名前が長く、自前でやるほうが短かった。
-
-
{...}do
は do ... while。入力値から 0, 2, 4, 6, ... を 0 以下になるまで引いていく。(↑で入力を 2 倍した値が入るので)-
a-
はa
を入力値から引く。 -
a 2+:a;
はa
に 2 を足してa
に代入し、pop する(スタックに残さない)。 -
.0>
は引いた結果が 0 より大きいかどうかを見る。(0 以下ならばループを抜ける)
-
-
!
で引いた結果が 0 になったかどうかを push する。
-
12 bytes
0V�j2'@-,q
スタックベース言語。ASCII にないバイトも使っているので短い。コンパイラがある(使わなかったけど)。sqrt があるが、結果が int で得られるので、sqrt したやつを自乗した値を sqrt する前の値と比べている。デコンパイル?するとこんな感じ。
# 入力を1行ずつ map して出力するモード
line-mode
# 文字列(48, 49の配列)を0, 1の配列にする(map の中身が1トークンなので map1 でいいのだが間違えた)
read-num
map2
# 2進数から変換
binary
# N*8+1
8 mul inc
# X == square(sqrt(X))
dup sqrt square eq
あとファイルで提出したときに末尾に改行が入ってしまったけどこれは要らないので 11 bytes でいけたはず。
21 bytes
{li10b2b8*).5#1%!o1}g
スタックベース言語。
-
{...}g
は do ... while。最後の1
があることで無限ループになっている。(最後は例外で落ちる)-
l
で入力を1行取り、i
で整数に変換する。(最後は改行文字だけの文字列になって、java.lang.NumberFormatException で落ちる) -
10b2b
で10進数表現の配列にしてから2進数表現として整数に戻す。- 入力をそのまま2進数表現として整数に戻そうとして
l2b
とやると、各桁を 48, 49 として計算されるのでおかしくなる(最初はこれでハマっていた)。
- 入力をそのまま2進数表現として整数に戻そうとして
-
8*).5#1%
で(N * 8 + 1) ** .5 % 1
を計算する。 -
!
で論理否定(結果は 0 か 1)を得てo
で出力。
-
16 bytes
qN%{2b8*)mq1%!}%
スタックベース言語。GolfScript と CJam をベースにしているらしい。
-
qN%
で入力全体を改行で区切る。 -
{...}%
は配列の map。結果が実行後に出力される。-
2b
は 2 進数のパース。 -
8*)mq1%
はsqrt(N * 8 + 1) % 1
を計算する。mq
は sqrt。 -
!
で論理否定(結果は 0 か 1)。
-
14 bytes
`jZB8*QX^1\~DT
スタックベース言語。
-
`
は while ループ。最後の]
は勝手に補われる。T
(true) が最後にあるので無限ループになる。(最後は例外で落ちる)-
j
は入力を文字列として得る。ZB
は2進数として解釈する。 -
8*QX^1\
はsqrt(N * 8 + 1) % 1
を計算する。X^
が sqrt。 -
~
で論理否定、D
で出力。
-
33 bytes
dw{p 2[1-(1+8*gt.toi(2))**0.5%1]}
golf_prelude.rb を読むと、method_missing
とか const_missing
によって、名前が長いメソッド・定数に短い名前でアクセスできるようになっている。最短の名前は
irb(main):124:0> shortest_abbreviation :gets
=> "gt"
irb(main):125:0> 1.shortest_abbreviation :to_i
=> "toi"
みたいな感じで調べられる。本来の名前で書くと
do_while{p 2[1-(1+8*gets.to_i(2))**0.5%1]}
になる。do_while
は golf_prelude.rb に定義があって、ブロックの評価結果が truthy の間ループする。残りの詳細はRubyの節を参照。
55 bytes
{ 1 "0b" :> "001" + + :i 0.5 ^ 1 % - :i :< 1 } {} while
2進数からの変換は第1回esolang陣取り大会 WriteUp に書いてあった。ありがとう過去の自分。おおよそ puts Integer(1 - Integer("0b" + gets.chomp + "001") ** 0.5 % 1)
みたいなのを無限ループにしている。
43 bytes
loop{p (1+8*read_line.to_i 2)**0.5%1>0?0:1}
Ruby みたいな雰囲気だけどコンパイルされて高速に動作する実用言語。
gets
が返す値は (String | nil)
なので、そのまま .to_i 2
とはできない。read_line
が返す値は String
(EOF にくると IO::EOFError
が送出される)なのでこれを使う。Int#[]
とかは無いので Crystal では三項演算子を使った。
17 bytes
Um_n2 *8+1 q v1}R
JavaScript にトランスパイルされて実行される言語。
本来は入力は改行ごとに区切って配列 N
に格納されるはずだが、どうも入力のまわりに "
が付いていて区切られないらしく、少しハマった。トランスパイルすると
U.m(function(Z) { return (Z.n(2) * 8 + 1).q().v(1) }, R)
になる。
-
U
は1つめの入力(今回は入力全体)。 -
String#m(f, s)
はs
で split したものをf
で map する。R
は改行文字。-
String#n(n)
は n 進数としてパース。 -
Number#q()
は sqrt。 -
Number#v(n)
は n で割り切れるかどうか(1 or 0)を返す。
-
output 系の関数を呼ばなければ自動的に最後の値が出力される。
277 bytes
x=00000000,00000001,00000011,00000110,00001010,00001111,00010101,00011100,00100100,00101101,00110111,01000010,01001110,01011011,01101001,01111000,10001000,10011001,10101011,10111110,11010010,11100111,11111101
$(foreach i,$(strip $(STDIN)),$(info $(if $(findstring $i,$x),1,0)))
素直に全列挙。
584 bytes
変数が IRC でしゃべっている感じの言語。トピックの変更がラベルとして機能し、Let's talk about 〜.
でジャンプできる。
70 bytes
while read a;do for((i=0,b=2#$a;b>0;b-=++i));do :;done;echo $[!b];done
入力値から 1, 2, 3, ... を 0 以下になるまで引いていって、0 になったかどうかを出力する。
- 初めて知ったが
2#10100101
みたいな感じで 2 進数がパースできるらしい。 - これも初めて知ったが
$((...))
は$[...]
とも書けるらしい。 -
do
とdone
の間には何かしら書かないといけないらしいので:
(何もしないコマンド)を置いた。(これはごく普通に使われているテクらしいですね)
86 bytes
f={x->if(x>0)f(int(x/10))*2+x%2else 0}
stdin|{x->int(1-sqrt(f(number(x))*8+1)%1)}|puts
ストリームベース?の言語。諸関数の仕様とかが(まだ)文書化されていないので、サンプルコードを見たり実装から探す必要がある。
2 進数を 10 進数として解釈した整数から元の数を(再帰的に)復元する関数を f
に定義している。1 - sqrt(X * 8 + 1) % 1
は、X
が三角数であれば 1 に等しく、三角数でなければ 0 と 1 の間にあるので、int に渡してやると答えが得られる。
61 bytes
<?php while($_=readline())echo+!(sqrt(1+8*bindec($_))*99%99);
Perl で発明した *99%99
テクを利用。fmod
を使って +!fmod(sqrt(...),1)
としても文字数的には同じ。
87 bytes
console.log((""+require("fs").readFileSync(0)).replace(/.+/g,q=>+!(`0b${q}001`**.5%1)))
標準入力のとり方がややめんどくさい。fs モジュールの readFileSync(0)
を呼ぶと標準入力が同期的に得られる(0 はファイルディスクリプタ)。readFileSync
の第 2 引数にはエンコーディング('0'と'1'と改行しかないので実質どれでもいい)を指定できて、指定すると文字列が返ってくるが、これを省略すると Buffer のインスタンスが返ってきてしまう。Buffer#replace なんて無いので、空文字列を繋げることで文字列に変換してやる。
JavaScript の正規表現の .
は改行以外の任意の文字にマッチするので今回は 50 個の数字列がアロー関数によって置換される。2 進数数値リテラル 0b〜
とか、テンプレートリテラル `〜${hoge}〜`
とか、べき乗の演算子 **
とか新しめの文法をふんだんに(?)使っている。!
は論理否定(真偽値)、単項演算子 +
は数値への変換。(そしてreplaceによって暗黙に文字列へ変換される)
50 bytes
do disp(!rem((1+8*bin2dec(fgetl(0)))^.5,1))until 0
do 〜 until 0
で無限ループ。√(8N + 1) mod 1 が 0 かどうかをみている。rem
は余りを求める。
183 bytes
begin integer a,b,r,i;while i<50do begin a:=inint;b:=0;r:=1;while a>0do begin b:=b+r*(a-a//2*2);r:=r*2;a:=a/10;end;a:=sqrt(b*8+1);r:=0;if a*a=b*8+1then r:=1;outint(r,0);i:=i+1;end;end
50 年の歴史を持つ言語。最初期のオブジェクト指向言語らしい。仕様を探してもなかなか出てこなくて、やっと出てきたのが紙にタイプライタ体で印刷されたのをスキャンした PDF で、ページ内検索ができなくてしんどかった(あとで探したら HTML 版が見つかった)。
整形すると
begin
integer a, b, r, i;
while i < 50 do begin
a := inint;
b := 0;
r := 1;
while a > 0 do begin
b := b + r * (a - a // 2 * 2);
r := r * 2;
a := a / 10;
end;
a := sqrt(b * 8 + 1);
r := 0;
if a * a = b * 8 + 1 then r := 1;
outint(r, 0);
i := i + 1;
end;
end
inint
で 10 進数として入力を得て、outint
で結果を出力する。剰余の演算子がないので、a - a // 2 * 2
としている(あとで調べたら mod(x, y)
があった)。sqrt(b * 8 + 1)
の結果を integer 型の a
に代入しているので、a * a = b * 8 + 1
で平方根が整数だったか否かが判定できる。
90 bytes
:$<;
(.+?)\n(.*);: ,$($1) $2;
.*,:"1"
(.*),\1(.*):a$1,$2
1:"a"
.:
(\d+)(.):$1 $1 $2
.*:"0"
正規表現のマッチで制御する言語。 マッチの優先順位の都合で、コードが入り乱れている。
:$<;
(.+?)\n(.*);: ,$($1) $2;
で入力を改行ごとに区切って処理する。 ( ;を消すと縮みそうなのだが、なぜかマッチが無限ループするので入れた)
(\d+)(.):$1 $1 $2
1:"a"
.:
で二進->一進変換する。たとえば 101 は aaaaa になる。 (入力で $($1)と呼び出しているので、出力をまた正規表現にマッチさせるようになる)
(.*),\1(.*):a$1,$2
.*,:"1"
.*:"0"
で、三角数かどうか判定する。(前方参照(\1)が存在するのでできる)
1から順に数を引いてって、丁度0になれば三角数、という判定法。
X,Y は、値Xまでインクリメントして残りがYの意味。
たとえば、6は、 ,aaaaaa -> a,aaaaaa -> aa,aaaaa -> aaa,aaa -> aaaa, とマッチして三角数と判定される。
274 bytes
https://kimiyuki.net/blog/2016/09/20/about-emmental-language/
http://moraprogramming.hateblo.jp/entry/2017/04/05/194303
などを参考にした。
手元ではWikiの記法(ただし'[abc]は'a'b'cの意)で書いた。
; '[:+] #40!
; '[:+#1+] #41!
; #!
; '[~#8+~#3-] #9!
; '[ : v+^ v^- #9? v+^:-? #1+: #23-#9?#9?? ] #1!
; '[ #^?^:-^ #1? vv+:-? v#48+.#] #2!
; '[,#8-?#4?] #4!
##4?
これを展開するとこうなる。
入力文字を8だけ減らして対応する関数を呼ぶ、を無限ループさせた。(関数'0'などは上書きできないため)
'0'(40),'1'(41)のときは、スタックトップを2倍してよしなにする。
'\n'(2)のときは判定。初期化したあと(1)を呼ぶ。
(1)は、カウンタが23以下なら再帰呼び出しして値判定するやつ。
(9)はnot。kimiyukiさんの記事にあったのを使用。
211 bytes
以下、ソースコードを生成したpythonコード。 メモリの状態などは、コメントからなんとなく察してください。
s = "" #st :: 0
s += ">,+[-" #st :: 0
s += "[" #st :: 1
s += ">[>++<-]>[<+>-]<<" #二倍
s += "[-->+<-[+>-<[<+>-]]<[>+<-]>]" # mod 2 でやっていく
s += "," + "-" * 10 + "]" # endif
# ... | s# | ....
bo = ">>++++[>++++++<-]>-"
# ... | s | 0 | 23#
bo += "["
# 50 | sum | 0 | i | 0 ...
bo += "[<+>>>+<<-]>>-"
# 50 | sum | i | 0 | 0 | i-1# | ans
bo += "[[<+<+>>-]<<[>>+<<-]>>-]"
# 50 | sum | i | 0 | i * (i-1)/2 | 0# | ans
bo += "<<<[>>+>-<<<-]"
# 50 | 0# | i | sum | i * (i-1)/2 - sum | 0 | ans
bo += ">>[<<+>>-]"
# 50 | sum | i | 0# | i * (i-1)/2 - sum | 0 | ans
bo += ">>>+<<[>>-<<[-]]"
# 50 | sum | i | 0 | 0# | 0 | ans_
bo += "<<[>+<-]>-"
# 50 | sum | 0 | i-1# | 0 ...
bo += "]"
# 50 | sum | 0 | 0# | 0 | 0 | 0 | ans
bo += ">>>++++++++[>++++++<-]>"
# 50 | sum | 0 | 0 | 0 | 0 | 0 | chr#
bo += ".[-]<<<<<<[-]<"
s += bo
s += ",+]"
print s
入力文字に対してmod2を取ることによって文字数を減らすとかやってみたけどあんまり縮まらずに苦労するだけだった。
191 bytes
>++=t+=:# d# d# d# d# d# d#d=*v
+ M M M M M M M
% ) ) ) ) ) ) )
0vvj<~0~*u~*=*u~*=*u~*=*u~*=*u~*=*u~*=*u~ <
A
. J
^0< ~
+' +
^<>~^
Active value と inactive value を持ったポインターが 2 次元グリッド上を同時に複数動く言語。
まず %
から 4 方向にポインターが動き始める。下向きは A
(上から来たポインターを除去する)にぶつかって除去される。左右向きはプログラムの外へ行って消滅する。上向きのポインターは 3 × 3 + 1 = 10 を inactive に持って、入力された整数を active に持つ:
>++=t+=:
+
%
#
は入ってきた向き以外の 3 方向にポインターをコピーする。上向きはプログラム外へ行って消滅し、下向きは active % inactive
(10で割った余り)を計算、右向きは active // inactive
(10で割った商)を計算していく:
# d# d# d# d# d# d#d
M M M M M M M
10で割った余りは )
によって )
の右のマスに("\x00"
や "\x01"
として)置かれる。その後ポインターは下に進みプログラム外へ消滅する。置いた余りを下のマスの u
を通ったポインターが読み取っていく。2 倍しながら足していって 2 進数を整数に変換していく:
=*v
) ) ) ) ) ) )
*u~*=*u~*=*u~*=*u~*=*u~*=*u~*=*u~ <
Inactive を 0 にしておく(~
は active と inactive をスワップするコマンド)(この後 inactive を 0, 1, 2, 3, ... と変化させながら active から引いていく):
~0~
Active が 0 ならば、j
のすぐ次の v
がスキップされて、その次の v
で下向きになる。0+
により active に 1 が格納され、.
で出力される。もし 0 より小さいならば、j
のすぐ次の v
で下向きに、J
の次の <
で左向きになり、0
により active に 0 が格納され、.
で出力される。
vvj<
. J
^0<
+
^<
もし active が 0 より大きいならば J
の次の <
もスキップされる。Active から inactive を引き ('
)、inactive をインクリメント (~+~
) するループ:
<
J
< ~
' +
>~^
ループを抜けて .
で結果を出力した後は、0
で active を 0 に戻してから最初の %
に戻る(%
は通過しても何も起こらない)。
%
0
A
.
230 bytes
밯빠바쟈희차박라박따밯박라다박따밯박라다박따밯박라다박따붛
투서써뻐버석떠벅더러벅벟떠벅더러벅벟떠벅더러벅벟떠벅더러벅
뿌 박도셕
차빠바자초북벅
무어벟멍버녀
プログラムをハングルで記述する言語。スタックが複数ある。1 つのカーソルが 2 次元グリッド上を動く。普段ハングルを打つ機会が無いので、Google 翻訳でキーボードを表示してポチポチ打っていた。
ハングルは子音字母と母音字母を組み合わせた文字であり、Aheui では母音字母がカーソルの移動方向と移動量を指定して(ㅏは右に 1 マス、ㅕは左に 2 マス、など)、子音字母が操作の内容を指定する。
実行はプログラムの左上から始まる。入力 1 文字の Unicode コードポイント(EOF だと -1)をスタックに入れて(밯
)、0 以上かどうかを見る(빠바쟈
(duplicate, push 0, compare))。쟈
の母音はㅑ(右に 2 マス)なので、次のマス 희
は一旦スキップされる。ㅊ はスタックから取り出した値が 0 以外ならば母音字母が示す向きに進み、0 ならばその逆向きに進む。すなわち EOF ならば 차
で左へ進み 희
(実行終了)にあたる。違えば右へ進む。박라박따
(push 2, modulo, push 2, multiply) は 2 で割った余りを求めて(48, 49 が 0, 1 になる)、2 を掛ける:
밯빠바쟈희차박라박따
その後に、밯박라다박따
(input char, push 2, modulo, add, push 2, multiply) の並びが 7 回続く(2進数をパース):
밯박라다박따밯박라다박따밯박라다박따붛
떠벅더러벅벟떠벅더러벅벟떠벅더러벅벟떠벅더러벅
この状態で、スタックの一番上には入力値の 2 倍が入っている。スタックをㄱに切り替えて(석
)、0 を push する(버
)(スタックㄱの一番上はこの後 0, 2, 4, 6, ... と変化させていく):
버석
スタックㄱの一番上を複製して(뻐
)最初のスタックに移動させる(써
)。最初のスタックに切り替えて(서
)、引き算をする(투
)。引いた結果を複製して(뿌
)これが 0 ならば左へ、そうでなければ右へ進む(차
)(左端より左へ行くと右端から出て来る):
투서써뻐
뿌
차
引いた結果が 0 でなければ、0 以上かどうかを見る(빠바자
(duplicate, push 0, compare))。0 以上であれば上へ、そうでなければ下へ進む(초
):
빠바자초
0 以上であれば、スタックをㄱに切り替えて(셕
)、2 を(push 박
して)足す(도
)。スタックㄱの一番上を複製するところに戻ってループする:
뻐
박도셕
0 以上でなければ、0 を push して(버
)、出力して(멍
)、標準入力から 1 文字(改行)読んで(벟
)pop する(무
)。(어
は カーソルが移動するだけで何もしない。)下端より下へ行くと上端から出てきて最初の場所に戻る:
무어벟멍버
(引いた結果が)0 であれば、(1 は push できないので)2 を 2 回 push(벅
, 북
)して割り算をし(녀
)、あとは同様に、出力して(멍
)標準入力から 1 文字(改行)読んで(벟
)pop して(무
)最初に戻る:
북벅
무어벟멍버녀
116 bytes
(@ 1(pn(: A 0)(: N(#(l)))(: R 1)(@ N(pn(: A(+ A(* R(% N 2))))(: R(* R 2))(: N(#/ N 10))))(p(+ 0(/?(^(+ 1(* 8 A)).5)1
LISP 風の関数型言語。コメントを入れて書くと
(@ 1 ; while(1)(無限ループ)
(pn ; 複数の式を評価して最後の値を返す
(: A 0) ; A = 0 (最終的に 2 進数をパースした値が入る)
(: N (#(l))) ; N = int(入力)
(: R 1) ; R = 1 (1, 2, 4, 8, ...)
(@ N ; while(N)(N が 0 でない間ループ)
(pn
(: A (+ A (* R (% N 2)))) ; A = A + R * (N % 2) (意味的には N % 10 だが文字数削減のため N % 2 に)
(: R (* R 2)) ; R = R * 2
(: N (#/ N 10)) ; N = N // 10
)
)
(p ; print
(+ 0 ; 0 + X (真偽値型から数値型へのキャスト)
(/? ; 1 で割れるか?(整数判定)
(^ (+ 1 (* 8 A)) .5) ; (1 + 8 * A) ** .5
1
)
)
)
)
)
最初 2 進数をパースするところを再帰関数で実装したのだが何故かうまく行かなかったので、再帰を諦めて while ループで書いた。今になって調べてみると、変数スコープの実装がアレで、再帰関数を作ると再帰呼び出しから帰ってきたときには引数が消されているっぽい(クソ)。ということは再帰呼び出しをする前なら引数が見えるはずなので、そうすればもっと短く書けるかも。
1245 bytes
'
と "
しか使えない。I/O とインクリメントとデクリメントと if, while, 変数読み書きくらいしか無い言語。さすがに直には書けないので TypeScript で書いた。(TypeScript にしたのは引数の数が違ったりするとエディタが怒ってくれるので。)方針としては 0, 1, 2, 3, ... を引いていった。
引っかかったのは、while ('"""""XY
:X
が 0 でない間 Y
を実行し、最後の Y
の値を返す)は、X
が最初から 0 を返す(Y
が一度も実行されない)とインタープリターが Python の NameError で落ちるので、最低でも 1 回は実行しないといけないという点。
11 bytes
|vyC8*>tÉ?
今回の大会で最も短いコード(gs2も11バイトになるらしいのでそれを考慮すると同着)。だけどまだ言語設計に冗長性を感じるので、もっと短くなる言語を作れる気がする。
文字数は10文字だが、UTF-8ではÉ
が2バイトなので11バイトである。
| # 入力を改行で区切り配列としてpushする
v # for-each
y # ループの現在の要素(8桁の2進数)をpushする
C # int(N, 2)
8* # 8倍
> # インクリメント
t # 平方根
É # 奇数かどうか判定
? # 改行なしで出力