HHeLiBeXの日記 正道編

日々の記憶の記録とメモ‥

各言語で日時文字列の解析

手元にある各言語で、標準入力から日時文字列を読み込んで、標準出力にUNIX TIME値を吐き出すプログラムを書いてみようと思ったメモ。

要件は以下の通り。

  • 入力される日時文字列は1つのみ
    • 不正入力のチェックは不要とする
  • OS等のタイムゾーンJST
  • 対応するUNIX TIME値を出力
    • 例えば、「2017/12/31 12:34:56 +0900」が入力されたら「1514723696」を出力

環境

手元にあるものということで、環境は以下のものに限定する。

入力ファイルの例

  • 001.txt
2017/12/31 12:34:56 +0900

期待される出力の例

  • 001.txt
1514723696

Java

import java.io.PrintWriter;
import java.text.DateFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Scanner;
import java.util.Date;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in);
            PrintWriter out = new PrintWriter(System.out)
        ) {
            String str = in.nextLine();

            DateFormat df = new SimpleDateFormat("yyyy/MM/dd HH:mm:ss ZZZZZ");
            Date date = df.parse(str);

            out.println(date.getTime() / 1000);
        } catch (ParseException e) {
            e.printStackTrace();
        }
    }
}

C

#define _XOPEN_SOURCE
#include <stdio.h>
#include <time.h>

int main(int argc, char** argv) {
    char str[32];
    fgets(str, sizeof(str) - 1, stdin);

    struct tm timeinfo;
    strptime(str, "%Y/%m/%d %H:%M:%S %z", &timeinfo);
    long second = mktime(&timeinfo);

    printf("%d\n", second);

    return 0;
}

strptimeを使ったソースを警告も出さないようにコンパイルするためには、マクロ定数を定義してやる必要がある。

上記を見ると、%zについては、「glibc での注意」として書いてあるが、「サポートさせようとしているが、多くの場合、tmフィールドは変更されない」らしい、つまり無視される、と。 実際、「+0000」を与えて試してみたら、見事に無視されて、tmフィールドのタイムゾーン情報には"JST"が入っていた・・・

C++

#include <ctime>
#include <iostream>

using namespace std;

int main(int argc, char** argv) {
    char str[32];
    cin.getline(str, sizeof(str));

    struct tm timeinfo;
    strptime(str, "%Y/%m/%d %H:%M:%S %z", &timeinfo);
    long second = mktime(&timeinfo);

    cout << second << endl;

    return EXIT_SUCCESS;
}

上記を見ると、%zについては、「glibc での注意」として書いてあるが、「サポートさせようとしているが、多くの場合、tmフィールドは変更されない」らしい、つまり無視される、と。 実際、「+0000」を与えて試してみたら、見事に無視されて、tmフィールドのタイムゾーン情報には"JST"が入っていた・・・

PHP

<?php

$lines = file('php://stdin');
$str = $lines[0];

date_default_timezone_set("Asia/Tokyo");
$second = strtotime($str);

printf("%d\n", $second);

Python 2

import sys
import re
from datetime import datetime
import time

str = sys.stdin.readline()
str = re.sub(r' [+][0-9][0-9][0-9][0-9][\r]*\n', "", str)

dt = datetime.strptime(str, "%Y/%m/%d %H:%M:%S")
second = int(time.mktime(dt.timetuple()))

print second

最初、%zを入れたら、ValueError: 'z' is a bad directive in format '%Y/%m/%d %H:%M:%S %z'って怒られた‥

次に、%zを外したら、ValueError: unconverted data remains: +0900って怒られた‥

なので、時差を指定している部分を正規表現による文字列置換で削除‥当然、JST扱いされるので、「+0000」を与えたテストケースは通らない‥

Python 3

import sys
import re
from datetime import datetime
import time

str = sys.stdin.readline()
str = re.sub(r'[\r]*\n', "", str)

dt = datetime.strptime(str, "%Y/%m/%d %H:%M:%S %z")
second = int(dt.timestamp())

print(second)

Ruby

require 'time'

str = STDIN.gets

second = Time.parse(str).to_i

print second,"\n"

Perl

DateTime::Format::Strptime版

use DateTime::Format::Strptime;

my $str = readline(STDIN);

my $strp = DateTime::Format::Strptime->new(
    pattern => "%Y/%m/%d %H:%M:%S %z"
);
my $second = $strp->parse_datetime($str)->epoch;

print $second,"\n";

これをやるには、「yum install perl-DateTime-Format-Strptime」をしておく必要がある。

Time::Piece版

use Time::Piece;

my $str = readline(STDIN);
chomp($str);

my $dt = Time::Piece->strptime($str, "%Y/%m/%d %H:%M:%S %z");
my $second = $dt->epoch;

print $second,"\n";

これをやるには、「yum install perl-Time-Piece」をしておく必要がある。

Go

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "time"
)

func main() {
    stdin := bufio.NewReader(os.Stdin)
    buf := make([]byte, 0, 1024)
    str := ""
    for {
        line, prefix, err := stdin.ReadLine()
        if err == io.EOF {
            break
        }
        buf = append(buf, line...)
        if prefix {
            continue
        }
        str = string(buf)
        break
    }

    t, err := time.Parse("2006/01/02 15:04:05 -0700", str)
    if err != nil {
        panic(err)
    }

    fmt.Println(t.Unix())
}

Go言語の日時のフォーマット指定子の仕様は何度見ても謎だ‥

bash

#! /bin/bash

IFS=$'\n' read str

date -d "${str}" +"%s"
  • man date(ぉ

各言語でdate format

手元にある各言語で、標準入力からUNIX TIME値を読み込んで、標準出力にフォーマットされた日時文字列を吐き出すプログラムを書いてみようと思ったメモ。

要件は以下の通り。

  • 入力されるUNIX TIME値は1つのみ
    • 不正入力のチェックは不要とする
  • タイムゾーンJST
  • 対応する日時文字列を出力
    • 例えば、「1514723696」が入力されたら「2017/12/31 12:34:56 +0900」を出力

環境

手元にあるものということで、環境は以下のものに限定する。

入力ファイルの例

  • 001.txt
1514723696

期待される出力の例

  • 001.txt
2017/12/31 12:34:56 +0900

Java

import java.io.PrintWriter;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in);
            PrintWriter out = new PrintWriter(System.out)
        ) {
            long millisecond = in.nextLong() * 1000L;

            DateFormat df = new SimpleDateFormat("yyyy/MM/dd HH:mm:ss ZZZZZ");
            String str = df.format(millisecond);

            out.println(str);
        }
    }
}

C

#include <stdio.h>
#include <time.h>

int main(int argc, char** argv) {
    time_t second;
    scanf("%ld", &second);

    char str[32];
    struct tm* timeinfo;
    timeinfo = localtime(&second);
    strftime(str, sizeof(str), "%Y/%m/%d %H:%M:%S %z", timeinfo);

    printf("%s\n", str);

    return 0;
}

C++

#include <ctime>
#include <iostream>

using namespace std;

int main(int argc, char** argv) {
    time_t second;

    cin >> second;

    char str[32];
    struct tm* timeinfo;
    timeinfo = localtime(&second);
    strftime(str, sizeof(str), "%Y/%m/%d %H:%M:%S %z", timeinfo);

    cout << str << endl;

    return EXIT_SUCCESS;
}

PHP

<?php

$lines = file('php://stdin');
$second = (int)$lines[0];

date_default_timezone_set("Asia/Tokyo");
printf("%s\n", date("Y/m/d H:i:s O", $second));

Python 2

import sys
import pytz
from datetime import datetime

line = sys.stdin.readline()
second = int(line)

dt = datetime.fromtimestamp(second)
dt = pytz.timezone('Asia/Tokyo').localize(dt)
str = dt.strftime("%Y/%m/%d %H:%M:%S %z")

print str

これをやるには、「yum pytz」でpytzモジュールをインストールしておく必要がある。

Python 3

import sys
import pytz
from datetime import datetime

line = sys.stdin.readline()
second = int(line)

dt = datetime.fromtimestamp(second)
dt = pytz.timezone('Asia/Tokyo').localize(dt)
str = dt.strftime("%Y/%m/%d %H:%M:%S %z")

print(str)

これをやるには、(自前ビルドしたPythonなので)「pip3 install pytz」でpytzモジュールをインストールしておく必要がある。

Ruby

line = STDIN.gets
second = line.to_i

t = Time.at(second)
str = t.strftime("%Y/%m/%d %H:%M:%S %z")

print str,"\n"

Perl

use POSIX 'strftime';

my $line = readline(STDIN);
my $second = $line + 0;

my $str = strftime "%Y/%m/%d %H:%M:%S %z", localtime($second);

print $str,"\n";

Go

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "time"
)

func main() {
    stdin := bufio.NewReader(os.Stdin)
    buf := make([]byte, 0, 1024)
    second := int64(0)
    for {
        line, prefix, err := stdin.ReadLine()
        if err == io.EOF {
            break
        }
        buf = append(buf, line...)
        if prefix {
            continue
        }
        s := string(buf)
        tmpSec, err2 := strconv.Atoi(s)
        if err2 != nil {
            panic(err2)
        }
        second = int64(tmpSec)
        break
    }

    t := time.Unix(second, 0)

    fmt.Println(t.Format("2006/01/02 15:04:05 -0700"))
}

Go言語の日時のフォーマット指定子の仕様は謎だ‥

bash

#! /bin/bash

IFS=$'\n' read line
second=$(echo ${line} | sed -e 's/^\([+-]*[0-9][0-9]*\).*/\1/')
second=$((second+0))

date -d "@${second}" +"%Y/%m/%d %H:%M:%S %z"
  • man date(ぉ

各言語でQueue

手元にある各言語で、標準入力からの数値列をQueueに放り込んで、入力と同順になるように標準出力に吐き出すプログラムを書いてみようと思ったメモ。

標準入力から入力される数値列の要件は以下の通り。

  • 1行に1つの数値が書かれている
    • 不正入力のチェックは不要とする
  • いくつの数値が入力されるかは不明(ただし、メモリがあふれることが無い程度に手加減する)
  • 入力される数値は符号付32ビット整数とする

入力をそのまま標準出力に放り出せばいいじゃないかという突っ込みもあるだろうが、Queue構造を扱ってみようというのが今回の目的。

環境

手元にあるものということで、環境は以下のものに限定する。

入力ファイルの例

  • 001.txt
0
1
-1
256
-256
32768
-32768
2147483647
-2147483648

期待される出力の例

  • 001.txt
0
1
-1
256
-256
32768
-32768
2147483647
-2147483648

Java

import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in);
            PrintWriter out = new PrintWriter(System.out)
        ) {
            Queue<Integer> queue = new ArrayDeque<>();

            while (in.hasNextInt()) {
                queue.offer(in.nextInt());
            }

            while (queue.peek() != null) {
                out.println(queue.poll());
            }
        }
    }
}

Javaには、Queueとして使えるjava.util.Queueの実装クラスがあるので、それを使って簡単に書ける。

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int capacity;
    int lastIndex;
    int curIndex;
    int* elemData;
} IntQueue;

IntQueue* IntQueue_new(int capacity) {
    IntQueue* queue = (IntQueue*)calloc(sizeof(IntQueue), 1);
    queue->elemData = (int*)calloc(sizeof(int), capacity);
    queue->capacity = capacity;
    queue->lastIndex = 0;
    queue->curIndex = 0;
    return queue;
}
void IntQueue_destroy(IntQueue* queue) {
    free(queue->elemData);
    free(queue);
}
int IntQueue_isEmpty(IntQueue* queue) {
    return queue->curIndex >= queue->lastIndex;
}
void IntQueue_push(IntQueue* queue, int elem) {
    // 先頭の方の使わなくなった領域をつぶして再利用。
    if (queue->lastIndex + 1 >= queue->capacity && queue->curIndex > 0) {
        if (queue->lastIndex - queue->curIndex > 0) {
            memmove(queue->elemData, &(queue->elemData[queue->curIndex]), sizeof(int) * (queue->lastIndex - queue->curIndex));
        }
        queue->lastIndex -= queue->curIndex;
        queue->curIndex = 0;
    }
    // それでも領域が足りない場合は増やす。
    if (queue->lastIndex + 1 >= queue->capacity) {
        int newCapacity = queue->capacity * 2;
        int* newElemData = (int*)calloc(sizeof(int), newCapacity);
        memcpy(newElemData, &(queue->elemData[queue->curIndex]), sizeof(int) * (queue->lastIndex - queue->curIndex));
        free(queue->elemData);
        queue->elemData = newElemData;
        queue->capacity = newCapacity;
        queue->lastIndex -= queue->curIndex;
        queue->curIndex = 0;
    }

    queue->elemData[(queue->lastIndex)++] = elem;
}
int IntQueue_pop(IntQueue* queue) {
    return queue->elemData[(queue->curIndex)++];
}

int main(int argc, char** argv) {
    IntQueue* queue = IntQueue_new(256);

    int num;
    while (scanf("%ld", &num) == 1) {
        IntQueue_push(queue, num);
    }

    while (!IntQueue_isEmpty(queue)) {
        printf("%d\n", IntQueue_pop(queue));
    }

    IntQueue_destroy(queue);

    return 0;
}

C言語は当然自前実装。

C++

#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

int main(int argc, char** argv) {
    queue<int> queue;
    int num;

    while (cin >> num) {
        queue.push(num);
    }

    while (!queue.empty()) {
        cout << queue.front() << endl;
        queue.pop();
    }

    return EXIT_SUCCESS;
}

C++にはqueueがあるので、それを使って簡単に書ける。

PHP

<?php

class Queue {
    private $elemData = array();
    public function isEmpty() {
        return count($this->elemData) === 0;
    }
    public function push($value) {
        array_push($this->elemData, $value);
    }
    public function pop() {
        return array_shift($this->elemData);
    }
}

$lines = file('php://stdin');

$queue = new Queue();

foreach ($lines as $line) {
    $queue->push((int)$line);
}

while (!$queue->isEmpty()) {
    printf("%d\n", $queue->pop());
}

PHPには標準ではQueueクラスが無いので書いてみた。単なる配列のラッパー。

ただ、65536個の数値を食わせてみたら、array_shiftで時間を食っているのか、返ってくるのに3分強かかったので、大量データに対しては実用的ではないかも。array_shiftを使わずに、先頭のインデックスを持っておいてインクリメントしていく方がいいのかも。

Python 2

import sys

class Queue:
    elemData = []
    def push(self, value):
        self.elemData.append(value)
    def pop(self):
        return self.elemData.pop(0)
    def isEmpty(self):
        return len(self.elemData) == 0

queue = Queue()
while True:
    line = sys.stdin.readline()
    if line == '':
        break
    queue.push(int(line))

while queue.isEmpty() != True:
    print queue.pop()

Python 2ではQueueクラスが見当たらなかったので書いてみた。単なる配列のラッパー。

Python 3

import sys

class Queue:
    elemData = []
    def push(self, value):
        self.elemData.append(value)
    def pop(self):
        return self.elemData.pop(0)
    def isEmpty(self):
        return len(self.elemData) == 0

queue = Queue()
while True:
    line = sys.stdin.readline()
    if line == '':
        break
    queue.push(int(line))

while queue.isEmpty() != True:
    print(queue.pop())

Python 3ではQueueクラスが見当たらなかったので書いてみた。単なる配列のラッパー。

Ruby

class Queue
    def initialize
        @elemData = []
    end
    def push(value)
        @elemData.push(value)
    end
    def pop
        @elemData.shift
    end
    def isEmpty
        return @elemData.size == 0
    end
end

queue = Queue.new
while line = STDIN.gets
    num = line.to_i
    queue.push(num)
end

while !queue.isEmpty
    print queue.pop(),"\n"
end

RubyではQueueクラスが見当たらなかったので書いてみた。単なる配列のラッパー。

Perl

Perlにはpush/shift関数があるということだが、なんか微妙なので、2パターン書いてみた。

push/shift関数バージョン

my @queue = ();

my $line;
while ($line = readline(STDIN)) {
    my $num = $line + 0;
    push @queue, $num;
}

while ($#queue + 1 > 0) {
    my $value = @queue[0];
    shift @queue;
    print "$value\n";
}

Queueモジュールバージョン

Queue.pm

package Queue;

sub new {
    my %self;
    my $class = shift;
    $self->{elemData} = ();
    $self->{cur} = 0;
    $self->{last} = 0;
    return bless $self, $class;
}
sub push {
    my $self = shift;
    my $value = shift;
    $self->{elemData}[$self->{last}] = $value;
    ++$self->{last};
}
sub front {
    my $self = shift;
    return $self->{elemData}[$self->{cur}];
}
sub pop {
    my $self = shift;
    delete $self->{elemData}[$self->{cur}];
    ++$self->{cur};
}
sub isEmpty {
    my $self = shift;
    return $self->{cur} >= $self->{last};
}

1;

Main.pl

require "Queue.pm";

my $queue = Queue->new;

my $line;
while ($line = readline(STDIN)) {
    my $num = $line + 0;
    $queue->push($num);
}

while (!$queue->isEmpty()) {
    my $value = $queue->front();
    $queue->pop();
    print "$value\n";
}

Go

listをキュー代わりに直接使うということを考えたが、せっかくなので、Queueパッケージを作ってみた。

src/queue/queue.go

package queue;

import (
    "container/list"
)

type Queue struct {
    elemData *list.List
}

func (s *Queue) Init() *Queue {
    s.elemData = list.New()
    return s
}

func New() *Queue {
    return new(Queue).Init()
}

func (s *Queue) Push(v interface{}) {
    s.elemData.PushBack(v)
}

func (s *Queue) Pop() interface{} {
    e := s.elemData.Front()
    s.elemData.Remove(e)
    return e.Value
}

func (s *Queue) IsEmpty() bool {
    return s.elemData.Len() == 0
}

Main.go

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "queue"
)

func main() {
    aQueue := queue.New()
    stdin := bufio.NewReader(os.Stdin)
    buf := make([]byte, 0, 1024)
    for {
        line, prefix, err := stdin.ReadLine()
        if err == io.EOF {
            break
        }
        buf = append(buf, line...)
        if prefix {
            continue
        }
        s := string(buf)
        num, err2 := strconv.Atoi(s)
        if err2 != nil {
            panic(err2)
        }
        buf = make([]byte, 0, 1024)

        aQueue.Push(num)
    }

    for !aQueue.IsEmpty() {
        fmt.Println(aQueue.Pop())
    }
}

実行するときに、GOPATH=$(pwd) go run Main.goってしてやらないと、カレントディレクトリのソースを参照してくれないのは注意点の一つ。

bash

#! /bin/bash

queue=()

while IFS=$'\n' read line ; do
    num=$(echo ${line} | sed -e 's/^\([+-]*[0-9][0-9]*\).*/\1/')
    num=$((num+0))
    queue=("${queue[@]}" ${num})
done

while [ ${#queue[@]} -gt 0 ]; do
    echo ${queue[0]}
    queue=("${queue[@]:1}")
done

あえて配列を使って書いたが、65536行のデータを食わせたら全然返ってこなかったので、大量のデータを処理する際には素直に他の言語で書いた方が良い。 あと、キューからの取り出しが面倒だったので、他の言語と違って、「末尾に追加」「先頭から削除」という形になっているので注意。

各言語でStack

手元にある各言語で、標準入力からの数値列をStackに放り込んで、入力とは逆順になるように標準出力に吐き出すプログラムを書いてみようと思ったメモ。

標準入力から入力される数値列の要件は以下の通り。

  • 1行に1つの数値が書かれている
    • 不正入力のチェックは不要とする
  • いくつの数値が入力されるかは不明(ただし、メモリがあふれることが無い程度に手加減する)
  • 入力される数値は符号付32ビット整数とする

前回と要件ややることは一緒だが、Stack構造を扱ってみようというのが今回の目的。

環境

手元にあるものということで、環境は以下のものに限定する。

入力ファイルの例

  • 001.txt
0
1
-1
256
-256
32768
-32768
2147483647
-2147483648

期待される出力の例

  • 001.txt
-2147483648
2147483647
-32768
32768
-256
256
-1
1
0

Java

import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in);
            PrintWriter out = new PrintWriter(System.out)
        ) {
            Deque<Integer> stack = new ArrayDeque<>();

            while (in.hasNextInt()) {
                stack.push(in.nextInt());
            }

            while (stack.peek() != null) {
                out.println(stack.pop());
            }
        }
    }
}

Javaには、Stackとして使えるjava.util.Dequeの実装クラスがあるので、それを使って簡単に書ける。

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int capacity;
    int size;
    int* elemData;
} IntStack;

IntStack* IntStack_new(int capacity) {
    IntStack* stack = (IntStack*)calloc(sizeof(IntStack), 1);
    stack->elemData = (int*)calloc(sizeof(int), capacity);
    stack->capacity = capacity;
    stack->size = 0;
    return stack;
}
void IntStack_destroy(IntStack* stack) {
    free(stack->elemData);
    free(stack);
}
int IntStack_isEmpty(IntStack* stack) {
    return stack->size == 0;
}
void IntStack_push(IntStack* stack, int elem) {
    if (stack->size + 1 > stack->capacity) {
        int newCapacity = stack->capacity * 2;
        int* newElemData = (int*)calloc(sizeof(int), newCapacity);
        memcpy(newElemData, stack->elemData, sizeof(int) * stack->size);
        free(stack->elemData);
        stack->elemData = newElemData;
        stack->capacity = newCapacity;
    }

    stack->elemData[(stack->size)++] = elem;
}
int IntStack_pop(IntStack* stack) {
    return stack->elemData[--(stack->size)];
}

int main(int argc, char** argv) {
    IntStack* stack = IntStack_new(256);

    int num;
    while (scanf("%ld", &num) == 1) {
        IntStack_push(stack, num);
    }

    while (!IntStack_isEmpty(stack)) {
        printf("%d\n", IntStack_pop(stack));
    }

    IntStack_destroy(stack);

    return 0;
}

C言語は当然自前実装。

C++

#include <algorithm>
#include <iostream>
#include <stack>

using namespace std;

int main(int argc, char** argv) {
    stack<int> stack;
    int num;

    while (cin >> num) {
        stack.push(num);
    }

    while (!stack.empty()) {
        cout << stack.top() << endl;
        stack.pop();
    }

    return EXIT_SUCCESS;
}

C++にはstackがあるので、それを使って簡単に書ける。

PHP

<?php

class Stack {
    private $elemData = array();
    public function isEmpty() {
        return count($this->elemData) === 0;
    }
    public function push($value) {
        array_push($this->elemData, $value);
    }
    public function pop() {
        $value = array_pop($this->elemData);
        return $value;
    }
}

$lines = file('php://stdin');

$stack = new Stack();

foreach ($lines as $line) {
    $stack->push((int)$line);
}

while (!$stack->isEmpty()) {
    printf("%d\n", $stack->pop());
}

PHPには標準ではStackクラスが無いので書いてみた。単なる配列のラッパー。

Python 2

import sys

class Stack:
    elemData = []
    def push(self, value):
        self.elemData.append(value)
    def pop(self):
        return self.elemData.pop()
    def isEmpty(self):
        return len(self.elemData) == 0

stack = Stack()
while True:
    line = sys.stdin.readline()
    if line == '':
        break
    stack.push(int(line))

while stack.isEmpty() != True:
    print stack.pop()

Python 2ではStackクラスが見当たらなかったので書いてみた。単なる配列のラッパー。

Python 3

import sys

class Stack:
    elemData = []
    def push(self, value):
        self.elemData.append(value)
    def pop(self):
        return self.elemData.pop()
    def isEmpty(self):
        return len(self.elemData) == 0

stack = Stack()
while True:
    line = sys.stdin.readline()
    if line == '':
        break
    stack.push(int(line))

while stack.isEmpty() != True:
    print(stack.pop())

Python 3ではStackクラスが見当たらなかったので書いてみた。単なる配列のラッパー。

Ruby

class Stack
    def initialize
        @elemData = []
    end
    def push(value)
        @elemData.push(value)
    end
    def pop
        @elemData.pop
    end
    def isEmpty
        return @elemData.size == 0
    end
end

stack = Stack.new
while line = STDIN.gets
    num = line.to_i
    stack.push(num)
end

while !stack.isEmpty
    print stack.pop(),"\n"
end

RubyではStackクラスが見当たらなかったので書いてみた。単なる配列のラッパー。

Perl

Perlにはpush/pop関数があるということだが、なんか微妙なので、2パターン書いてみた。

push/pop関数バージョン

my @stack = ();

my $line;
while ($line = readline(STDIN)) {
    my $num = $line + 0;
    push @stack, $num;
}

while ($#stack + 1 > 0) {
    my $value = @stack[$#stack];
    pop @stack;
    print "$value\n";
}

Stackモジュールバージョン

Stack.pm

package Stack;

sub new {
    my %self;
    my $class = shift;
    $self->{elemData} = ();
    $self->{size} = 0;
    return bless $self, $class;
}
sub push {
    my $self = shift;
    my $value = shift;
    $self->{elemData}[$self->{size}] = $value;
    ++$self->{size};
}
sub top {
    my $self = shift;
    return $self->{elemData}[$self->{size} - 1];
}
sub pop {
    my $self = shift;
    --$self->{size};
    delete $self->{elemData}[$self->{size}];
}
sub isEmpty {
    my $self = shift;
    return $self->{size} == 0;
}

1;

Main.pl

require "Stack.pm";

my $stack = Stack->new;

my $line;
while ($line = readline(STDIN)) {
    my $num = $line + 0;
    $stack->push($num);
}

while (!$stack->isEmpty()) {
    my $value = $stack->top();
    $stack->pop();
    print "$value\n";
}

Go

listをスタック代わりに直接使うということを考えたが、せっかくなので、Stackパッケージを作ってみた。

src/stack/stack.go

package stack;

import (
    "container/list"
)

type Stack struct {
    elemData *list.List
}

func (s *Stack) Init() *Stack {
    s.elemData = list.New()
    return s
}

func New() *Stack {
    return new(Stack).Init()
}

func (s *Stack) Push(v interface{}) {
    s.elemData.PushBack(v)
}

func (s *Stack) Pop() interface{} {
    e := s.elemData.Back()
    s.elemData.Remove(e)
    return e.Value
}

func (s *Stack) IsEmpty() bool {
    return s.elemData.Len() == 0
}

Main.go

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "stack"
)

func main() {
    aStack := stack.New()
    stdin := bufio.NewReader(os.Stdin)
    buf := make([]byte, 0, 1024)
    for {
        line, prefix, err := stdin.ReadLine()
        if err == io.EOF {
            break
        }
        buf = append(buf, line...)
        if prefix {
            continue
        }
        s := string(buf)
        num, err2 := strconv.Atoi(s)
        if err2 != nil {
            panic(err2)
        }
        buf = make([]byte, 0, 1024)

        aStack.Push(num)
    }

    for !aStack.IsEmpty() {
        fmt.Println(aStack.Pop())
    }
}

実行するときに、GOPATH=$(pwd) go run Main.goってしてやらないと、カレントディレクトリのソースを参照してくれないのでちょっとハマった。

bash

#! /bin/bash

stack=()

while IFS=$'\n' read line ; do
    num=$(echo ${line} | sed -e 's/^\([+-]*[0-9][0-9]*\).*/\1/')
    num=$((num+0))
    stack=(${num} "${stack[@]}")
done

while [ ${#stack[@]} -gt 0 ]; do
    echo ${stack[0]}
    stack=("${stack[@]:1}")
done

あえて配列を使って書いたが、65536行のデータを食わせたら全然返ってこなかったので、大量のデータを処理する際には素直に他の言語で書いた方が良い。

Go言語のパッケージ名と変数名の罠

Go言語で以下のようなコードを書いて一瞬ハマったのでメモ。

package main

import (
    "fmt"
    "container/list"
)

func main() {
    list := list.New()
    list.PushBack(1)
    list.PushBack(2)
    list.PushBack(3)
    for elem := list.Front(); elem != nil; elem = elem.Next() {
        fmt.Println(elem.Value)
    }

    list2 := list.New()
    list2.PushBackList(list)
    for elem := list2.Front(); elem != nil; elem = elem.Next() {
        fmt.Println(elem.Value)
    }
}
$ go run Main.go
# command-line-arguments
./Main.go:17: list.New undefined (type *list.List has no field or method New)
$ 

‥えっ?

17行目は以下の部分。

    list2 := list.New()

実はこれ、9行目の

    list := list.New()

listという名前の変数を定義することによって、パッケージ名よりも変数名の方が優先されてしまうことが原因(多分)。

なので、以下のようにでも書いてやり、パッケージ名と変数名の衝突を避けてやらないといけない。

package main

import (
    "fmt"
    "container/list"
)

func main() {
    aList := list.New()
    aList.PushBack(1)
    aList.PushBack(2)
    aList.PushBack(3)
    for elem := aList.Front(); elem != nil; elem = elem.Next() {
        fmt.Println(elem.Value)
    }

    aList2 := list.New()
    aList2.PushBackList(aList)
    for elem := aList2.Front(); elem != nil; elem = elem.Next() {
        fmt.Println(elem.Value)
    }
}

Javaだったら、以下のようなコードが許されるんだがな(良い悪いは別として)。

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> List = new ArrayList<>();
        List.add(1);
        List.add(2);
        List.add(3);
        for (Integer elem : List) {
            System.out.println(elem);
        }

        List<Integer> List2 = new ArrayList<>();
        List2.addAll(List);
        for (Integer elem : List2) {
            System.out.println(elem);
        }
    }
}

標準入力から数値列を読み込んで、逆順に標準出力に吐き出す

手元にある各言語で、標準入力から数値列を読み込んで、逆順にしたうえで標準出力に吐き出すプログラムを書いてみようと思ったメモ。

標準入力から入力される数値列の要件は以下の通り。

  • 1行に1つの数値が書かれている
    • 不正入力のチェックは不要とする
  • いくつの数値が入力されるかは不明(ただし、メモリがあふれることが無い程度に手加減する)
  • 入力される数値は符号付32ビット整数とする

入力される数値の上限数設定が無いことで、前々回、前回のように配列を静的に準備しておくということができないので、真面目に動的な配列あるいはリスト構造を考えないといけなくなるところがポイント。

環境

手元にあるものということで、環境は以下のものに限定する。

入力ファイルの例

  • 001.txt
0
1
-1
256
-256
32768
-32768
2147483647
-2147483648

期待される出力の例

  • 001.txt
-2147483648
2147483647
-32768
32768
-256
256
-1
1
0

Java

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in);
            PrintWriter out = new PrintWriter(System.out)
        ) {
            List<Integer> list = new ArrayList<>();
            while (in.hasNextInt()) {
                list.add(in.nextInt());
            }
            Collections.reverse(list);
            for (Integer num : list) {
                out.println(num);
            }
        }
    }
}

Javaの場合、Listの要素を逆順にするメソッドがCollectionsクラスに用意されているので、それを使えば一発。

C

#include <stdio.h>
#include <stdlib.h>

struct _IntNode {
    int value;
    struct _IntNode* prev;
    struct _IntNode* next;
};
typedef struct _IntNode IntNode;
typedef struct {
    int size;
    IntNode* first;
    IntNode* last;
} IntList;

IntList* IntList_new() {
    IntList* list = (IntList*)calloc(sizeof(IntList), 1);
    list->first = NULL;
    list->last = NULL;
    list->size = 0;
    return list;
}
void IntList_destroy(IntList* list) {
    IntNode* node = list->first;
    while (node != NULL) {
        IntNode* next = node->next;
        free(node);
        node = next;
    }
    free(list);
}
void IntList_add(IntList* list, int value) {
    IntNode* node = (IntNode*)calloc(sizeof(IntNode), 1);
    node->next = NULL;
    if (list->last != NULL) {
        list->last->next = node;
        node->prev = list->last;
    } else {
        list->first = node;
        node->prev = NULL;
    }
    list->size++;
    list->last = node;
    node->value = value;
}
void IntList_reverse(IntList* list) {
    int left = 0;
    int right = list->size - 1;
    IntNode* leftNode = list->first;
    IntNode* rightNode = list->last;
    while (left < right) {
        int tmp = leftNode->value;
        leftNode->value = rightNode->value;
        rightNode->value = tmp;

        ++left;
        --right;
        leftNode = leftNode->next;
        rightNode = rightNode->prev;
    }
}

int main(int argc, char** argv) {
    IntList* list = IntList_new();

    int num;
    while (scanf("%ld", &num) == 1) {
        IntList_add(list, num);
    }
    IntList_reverse(list);
    for (IntNode* node = list->first; node != NULL; node = node->next) {
        printf("%d\n", node->value);
    }

    IntList_destroy(list);

    return 0;
}

C言語にはリスト構造がそもそも無いので、そこの実装から。今回はlinked listで実装したが、Javaで言うところのArrayList方式の実装も考えられる。今回は面倒だったので止めたが。

逆順にする処理は、実装したlinked listに対して愚直に各要素の値を入れ替える処理。

C++

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

void reverse_vector(vector<int>& list) {
    for (int left = 0, right = list.size() - 1; left < right; ++left, --right) {
        int tmp = list[left];
        list[left] = list[right];
        list[right] = tmp;
    }
}

int main(int argc, char** argv) {
    vector<int> list;
    int num;

    while (cin >> num) {
        list.push_back(num);
    }

    reverse_vector(list);

    for (int i = 0; i < list.size(); ++i) {
        cout << list[i] << endl;
    }

    return EXIT_SUCCESS;
}

逆順にする処理は、愚直に各要素の値を入れ替える処理。

PHP

<?php

$lines = file('php://stdin');
$ary = array();
foreach ($lines as $line) {
    $ary[] = (int)$line;
}

$left = 0;
$right = count($ary) - 1;
while ($left < $right) {
    $tmp = $ary[$left];
    $ary[$left] = $ary[$right];
    $ary[$right] = $tmp;

    ++$left;
    --$right;
}

foreach ($ary as $num) {
    printf("%d\n", $num);
}

逆順にする処理は、愚直に各要素の値を入れ替える処理。

Python 2

import sys

list = []
while True:
    line = sys.stdin.readline()
    if line == '':
        break
    list.append(int(line))

list.reverse()

for num in list:
    print num

逆順にする処理は、reverseメソッドで一発。

Python 3

import sys

list = []
while True:
    line = sys.stdin.readline()
    if line == '':
        break
    list.append(int(line))

list.reverse()

for num in list:
    print(num)

逆順にする処理は、reverseメソッドで一発。

Ruby

list = []
while line = STDIN.gets
    num = line.to_i
    list.push(num)
end

list = list.reverse()

for num in list
    print num,"\n"
end

逆順にする処理は、reverseメソッドで一発。

Perl

my $line;
my @list = ();
my $count = 0;
while ($line = readline(STDIN)) {
    my $num = $line + 0;
    $list[$count] = $num;
    ++$count;
}

@list = reverse @list;

for (my $i = 0; $i < $count; ++$i) {
    print "$list[$i]\n";
}

逆順にする処理は、reverse関数で一発。

Go

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "container/list"
)

func main() {
    l := list.New()
    stdin := bufio.NewReader(os.Stdin)
    buf := make([]byte, 0, 1024)
    for {
        line, prefix, err := stdin.ReadLine()
        if err == io.EOF {
            break
        }
        buf = append(buf, line...)
        if prefix {
            continue
        }
        s := string(buf)
        num, err2 := strconv.Atoi(s)
        if err2 != nil {
            panic(err2)
        }
        l.PushBack(num)
        buf = make([]byte, 0, 1024)
    }

    l2 := list.New()
    for elem := l.Back(); elem != nil; elem = elem.Prev() {
        l2.PushBack(elem.Value)
    }
    l = l2

    for elem := l.Front(); elem != nil; elem = elem.Next() {
        fmt.Println(elem.Value)
    }
}

初めてlistコンテナを使ってみた。

逆順にする処理は、元のリストを末尾から捜査して別のリストに放り込むことで実現。 そもそも、入力処理の際にlist.PushFront()すればいいという話もあるが、それはそれとして(ぉ。

bash

#! /bin/bash

nl -ba | sort -nr | cut -f 2

nlコマンドで行番号を付けて、行番号で逆順ソートして、行番号をカットする、という単純な処理。

標準入力から数値列を読み込んで、降順にソートして標準出力に吐き出す

手元にある各言語で、標準入力から数値列を読み込んで、降順にソートしたうえで標準出力に吐き出すプログラムを書いてみようと思ったメモ。 プログラム言語にもよるが、昇順は簡単なのに降順となったとたんに苦労するケースがあったりする。

標準入力から入力される数値列の要件は以下の通り。

  • 1行に1つの数値が書かれている
    • 不正入力のチェックは不要とする
  • 最大で256個の数値が入力される
  • 入力される数値は符号付32ビット整数とする

環境

手元にあるものということで、環境は以下のものに限定する。

入力ファイルの例

  • 001.txt
0
1
-1
256
-256
32768
-32768
2147483647
-2147483648

期待される出力の例

  • 001.txt
2147483647
32768
256
1
0
-1
-256
-32768
-2147483648

Java

入力される数値の上限数が分かっているということで、Javaでは2パターン作ってみた。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            PrintWriter out = new PrintWriter(System.out)
        ) {
            String buf;
            int count = 0;
            int[] ary = new int[256];
            while ((buf = in.readLine()) != null) {
                ary[count] = Integer.parseInt(buf);
                ++count;
            }
            Arrays.sort(ary, 0, count);
            // 降順ソートする手段がないので、昇順ソートした後に逆順にする。。
            for (int left = 0, right = count - 1; left < right; ++left, --right) {
                int tmp = ary[left];
                ary[left] = ary[right];
                ary[right] = tmp;
            }
            for (int i = 0; i < count; ++i) {
                out.println(ary[i]);
            }
        } catch (NumberFormatException e) {
            // 今回は不正入力のチェックは不要なので、RuntimeExceptionを投げておく。
            throw new RuntimeException(e);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

昇順との違いは‥コメントにある通り「降順ソートする手段がないので、昇順ソートした後に逆順にする」という手法を取っていること。

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in);
            PrintWriter out = new PrintWriter(System.out)
        ) {
            List<Integer> list = new ArrayList<>();
            while (in.hasNextInt()) {
                list.add(in.nextInt());
            }
            Collections.sort(list, Collections.reverseOrder());
            for (Integer num : list) {
                out.println(num);
            }
        }
    }
}

昇順との違いは、Collections.sortの第2パラメータに逆順を表すComparatorを指定していること。

C

#include <stdio.h>
#include <stdlib.h>

int cmp(const void* pa, const void* pb) {
    int a = *(const int*)pa;
    int b = *(const int*)pb;
    if (a < b) {
        return 1;
    } else if (a > b) {
        return -1;
    } else {
        return 0;
    }
}

int main(int argc, char** argv) {
    int ary[256];
    int count = 0;
    while (scanf("%ld", &ary[count]) == 1) {
        ++count;
    }
    qsort(ary, count, sizeof(int), cmp);
    for (int i = 0; i < count; ++i) {
        printf("%d\n", ary[i]);
    }

    return 0;
}

昇順との違いは、cmp関数の大小による戻り値が逆になっていること。

C++

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

bool cmp(int a, int b) {
    return a > b;
}

int main(int argc, char** argv) {
    vector<int> list;
    int num;
    int count = 0;

    while (cin >> num) {
        list.push_back(num);
        ++count;
    }
    sort(list.begin(), list.end(), cmp);
    for (int i = 0; i < list.size(); ++i) {
        cout << list[i] << endl;
    }

    return EXIT_SUCCESS;
}

昇順との違いは、sort関数の第3パラメータに比較関数を指定して、逆順になるように関数を定義していること。

PHP

<?php

$lines = file('php://stdin');
$ary = array();
foreach ($lines as $line) {
    $ary[] = (int)$line;
}
rsort($ary);
foreach ($ary as $num) {
    printf("%d\n", $num);
}

昇順がsortに対して、降順がrsortという、ただそれだけ。

Python 2

import sys

list = []
while True:
    line = sys.stdin.readline()
    if line == '':
        break
    list.append(int(line))

list.sort(reverse=True)

for num in list:
    print num

昇順との違いは、reverseパラメータにTrueを指定していること。

Python 3

import sys

list = []
while True:
    line = sys.stdin.readline()
    if line == '':
        break
    list.append(int(line))

list.sort(reverse=True)

for num in list:
    print(num)

昇順との違いは、reverseパラメータにTrueを指定していること。

Ruby

list = []
while line = STDIN.gets
    num = line.to_i
    list.push(num)
end
list = list.sort() {|a, b| b <=> a}
for num in list
    print num,"\n"
end

昇順との違いは、逆順になるように何か書いているが、正直よく分かってない(待て)。

Perl

my $line;
my @list = ();
my $count = 0;
while ($line = readline(STDIN)) {
    my $num = $line + 0;
    $list[$count] = $num;
    ++$count;
}
@list = sort {$b <=> $a} @list;
for (my $i = 0; $i < $count; ++$i) {
    print "$list[$i]\n";
}

昇順との違いは、$a$bが逆になっていること。これで逆順(降順)ソートになるのだから、つくづくPerlは不思議な言語‥

Go

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "sort"
)

func main() {
    tmp := make([]int, 256)
    count := 0
    stdin := bufio.NewReader(os.Stdin)
    buf := make([]byte, 0, 1024)
    for {
        line, prefix, err := stdin.ReadLine()
        if err == io.EOF {
            break
        }
        buf = append(buf, line...)
        if prefix {
            continue
        }
        s := string(buf)
        num, err2 := strconv.Atoi(s)
        if err2 != nil {
            panic(err2)
        }
        tmp[count] = num
        count++
        buf = make([]byte, 0, 1024)
    }
    ary := make([]int, count)
    for i := 0; i < count; i++ {
        ary[i] = tmp[i]
    }
    sort.Sort(sort.Reverse(sort.IntSlice(ary)))
    for i := 0; i < count; i++ {
        fmt.Println(ary[i])
    }
}

これが最適なコードなのかどうかよく分からん‥

昇順との違いは、sort.Intsがなにやらややこしいことになっていること。

bash

#! /bin/bash

sort -nr

昇順との違いは、いわずもがな、-r(everse)の指定。