2015年1月18日日曜日

150118

Ruby


「アルゴリズムとデータ構造」のRuby版。

2分木を使ったマップ

# -*- coding: cp932 -*-

# Node Class
class Node
  attr_accessor :key, :value, :left, :right
  def initialize(num, val)
    @key = num      # ノードのキー
    @value = val    # ノードが保持する値
    @left = nil     # 左側のノード
    @right = nil    # 右側のノード
  end
end

# ノードを生成する
def create_new_node(num, val)
  newNode = Node.new(num, val)
  return newNode
end

# ノードの追加
def insert_tree(num, val, node)
  # 1つも挿入されていない場合
  if node == nil
    @tree_root = create_new_node(num, val)
    return
  end

  if node.key > num
    if node.left != nil
      insert_tree(num, val, node.left)
    else
      node.left = create_new_node(num, val)
    end
  else
    if node.right != nil
      insert_tree(num, val, node.right)
    else
      node.right = create_new_node(num, val)
    end
  end
end

# ノードの検索
def find_value(node, num)
  if node.key > num
    if node.left == nil
      return nil
    end
    return find_value(node.left, num)
  end
  if node.key < num
    if node.right == nil
      return nil
    end
    return find_value(node.right, num)
  end
  return node
end

# ノードの削除
def delete_tree(num)
  node = @tree_root
  parent_node = nil
  direction = 0
  # while文で削除すべき対象を見つける
  while (node != nil && node.key != num)
    if node.key > num
      parent_node = node
      node = node.left
      direction = -1
    else
      parent_node = node
      node = node.right
      direction = 1
    end
  end
  if node == nil
    return false
  end
  if node.left == nil || node.right == nil
    if node.left == nil
      if direction == -1
        parent_node.left = node.right
      elsif direction == 1
        parent_node.right = node.right
      elsif direction == 0
        @tree_root = node.right
      end
   else
      if direction == -1
        parent_node.left = node.left
      elsif direction == 1
        parent_node.right = node.left
      elsif direction == 0
        @tree_root = node.left
      end
    end
  else
    left_biggest = node.left
    parent_node = node
    direction = -1
    while left_biggest.right != nil
      parent_node = left_biggest
      left_biggest = left_biggest.right
      direction = 1
    end
    node.key = left_biggest.key
    node.value = left_biggest.value
    if direction == -1
      parent_node.left = left_biggest.left
    else
      parent_node.right = left_biggest.left
    end
  end
  return true
end

def print_tree(depth, node = nil)
  if node == nil
    return
  end
  print_tree(depth + 1, node.left)
  i = 0
  while i < depth
    printf ""
    i += 1
  end
  printf("%s :%s \n", node.key, node.value)
  print_tree(depth + 1, node.right)
end

def main
  action = nil
  while action != 0
    print_tree(0, @tree_root)
    printf("0:終了1:挿入2:探索3:削除>")
    action = gets.chomp.to_i
    case action
      when 1
        printf("挿入する文字列(キー):>")
        key = gets.chomp.to_i
        printf("キーに対応させる値:>")
        value = gets.chomp
        insert_tree(key, value, @tree_root)
      when 2
        printf("探索する文字列:>")
        i = gets.chomp.to_i
        node_found = find_value(@tree_root, i)
        if node_found != nil
          printf("対応する値は%sです\n", node_found.value)
        else
          printf("見つかりませんでした\n")
        end
      when 3
        printf("削除する文字列:>")
        i = gets.chomp.to_i
        if delete_tree(i)
          printf("削除しました\n")
        else
          printf("見つかりませんでした\n")
        end
    end
  end
end

main

2015年1月17日土曜日

150117

Ruby


「アルゴリズムとデータ構造」のRuby版。

2分木のデータ追加、サーチ、削除
(ただし、書籍のように最初にtreeを作成しません。)

# -*- coding: cp932 -*-

# Node Class
class Node
  attr_accessor :value, :left, :right
  def initialize(val)
    @value = val   # ノードが保持する値
    @left = nil    # 左側のノード
    @right = nil   # 右側のノード
  end 
end

# ノードを生成する
def create_new_node(val)
  newNode = Node.new(val)
  return newNode
end

# ノードの追加
def insert_tree(num, node)
  # 1つも挿入されていない場合
  if node == nil
    @tree_root = create_new_node(num)
    return
  end 
  # num が現在の node の値よりも小さい場合
  if node.value > num
    if node.left != nil
      insert_tree(num, node.left)
    else
      node.left = create_new_node(num)
    end
  # num が現在の node の値以上の場合
  else
    if node.right != nil
      insert_tree(num, node.right)
    else
      node.right = create_new_node(num)
    end
  end
end

# ノードの検索
def find_value(node, val)
  # 自分より小さい値ならば、左側
  if node.value > val
    if node.left == nil
      return nil
    end
    return find_value(node.left, val)
  end
  # 自分より大きい値ならば、右側
  if node.value < val
    if node.right == nil
      return nil
    end
    return find_value(node.right, val)
  end
  return node 
end

# ノードの削除
def delete_tree(val)
  node = @tree_root
  parent_node = nil
  direction = 0
  # while文で削除すべき対象を見つける
  while (node != nil && node.value != val)
    if node.value > val
      parent_node = node
      node = node.left
      direction = -1
    else
      parent_node = node
      node = node.right
      direction = 1
    end
  end
  if node == nil
    return false
 end
  if node.left == nil || node.right == nil
    if node.left == nil
      if direction == -1
        parent_node.left = node.right
      elsif direction == 1
        parent_node.right = node.right
      elsif direction == 0
        @tree_root = node.right
      end
    else
      if direction == -1
        parent_node.left = node.left
      elsif direction == 1
        parent_node.right = node.left
      elsif direction == 0
        @tree_root = node.left
      end
    end
  else
    left_biggest = node.left
    parent_node = node
    direction = -1
    while left_biggest.right != nil
      parent_node = left_biggest
      left_biggest = left_biggest.right
      direction = 1
    end
    node.value = left_biggest.value
    if direction == -1
      parent_node.left = left_biggest.left
    else
      parent_node.right = left_biggest.left
    end
  end
  return true
end

def print_tree(depth, node = nil)
  if node == nil
    return
  end
  print_tree(depth + 1, node.left)
  i = 0
  while i < depth
    printf "   "
    i += 1
  end
  printf("%d\n", node.value)
  print_tree(depth + 1, node.right)
end

def main
  action = nil
  while action != 0
    print_tree(0, @tree_root)
    printf("実行する操作のタイプを入力してください。\n 1 :追加\t2 :検索\t3 :削除\t それ以外:終了>")
    action = gets.chomp.to_i
    case action
      when 1
        printf("1 ~100の範囲で,追加する数字を入力してください:")
        i = gets.chomp.to_i
        if i < 1 || i > 100
          continue
        end
        insert_tree(i, @tree_root)
      when 2
        printf("検索する数字を入力してください:")
        i = gets.chomp.to_i
        if find_value(@tree_root, i) != nil
          printf("%dを発見しました\n", i)
        else
          printf("%dは見つかりませんでした\n", i)
        end
      when 3
        printf("削除する数字を入力してください:")
        i = gets.chomp.to_i
        if delete_tree(i)
          printf("%dを削除しました\n", i)
        else
          printf("%dは見つかりませんでした\n", i)
        end
      else
        break
    end
  end
end

main

2015年1月12日月曜日

150112

Ruby


「アルゴリズムとデータ構造」のRuby版。

リストのなかのデータのサーチと削除。

# -*- coding: cp932 -*-

class TagListNode
  attr_reader :data
  attr_accessor :prev, :next
  def initialize(data)
    @data = data
    @prev = nil
    @next = nil
  end
end

buf = nil
firstnode = nil
lastnode = nil
while buf != 0
  printf("整数を入力してください(0を入力すると終了):")
  buf = gets().to_i
  if buf != 0
  # 新しいノードを作成
  newnode = TagListNode.new(buf)
  newnode.next = nil
    if lastnode != nil
      # すでにあるリストの末尾に新しいノードをつなげる
      lastnode.next = newnode
      newnode.prev = lastnode
      lastnode = newnode
    else # これが最初の要素だった場合
      firstnode = lastnode = newnode
      newnode.prev = nil
    end
  end
end

buf = nil
while buf != 0
  printf("検索する値を入力してください:")
  buf = gets().to_i
  thisnode = firstnode
  # 最初に入力した値のなかから検索し,見つかったら削除
  while thisnode != nil
    if thisnode.data == buf
      printf("入力された値のなかに%dが見つかりました。ノードを削除します。\n", buf)
      if thisnode.prev != nil
        thisnode.prev.next = thisnode.next
      else
        firstnode = thisnode.next
      end
      if thisnode.next != nil
        thisnode.next.prev = thisnode.prev
      else
        lastnode = thisnode.prev
      end
      break
    end
    thisnode = thisnode.next
  end
  if thisnode == nil
    printf("%dは入力されていないか,あるいはすでに削除されています。\n", buf)
  end
end

2015年1月11日日曜日

150111(3)

Ruby


「アルゴリズムとデータ構造」のRuby版。

リストを使って入力したいくつかの数値とその合計を出力する。

# -*- coding: cp932 -*-

class TagListNode
  attr_reader :data
  attr_accessor :prev, :next
  def initialize(data)
    @data = data
    @prev = nil
    @next = nil
  end
end

buf = nil
firstnode = nil
lastnode = nil
while buf != 0
  printf("整数を入力してください(0を入力すると終了):")
  buf = gets().to_i
  if buf != 0
  # 新しいノードを作成
  newnode = TagListNode.new(buf)
  newnode.next = nil
    if lastnode != nil
      # すでにあるリストの末尾に新しいノードをつなげる
      lastnode.next = newnode
      newnode.prev = lastnode
      lastnode = newnode
    else # これが最初の要素だった場合
      firstnode = lastnode = newnode
      newnode.prev = nil
    end
  end
end

# 合計値を算出
printf("--入力されたのは以下の数です--\n");
sum = 0
thisnode = firstnode
while thisnode != nil
  printf("%d\t",thisnode.data)
  sum += thisnode.data
  thisnode = thisnode.next
end
printf("\n----\n以上の数の合計値は%dです。\n", sum)

150111(2)

C


簡単な線形リスト

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

typedef int data_t;

typedef struct nodetag {
    data_t data;
    struct nodetag *next;
} node_t;

main()
{
int i;

node_t nd1, nd2, nd3;
node_t *p;

nd1.data = 1;
nd1.next = &nd2;
nd2.data = 2;
nd2.next = &nd3;
nd3.data = 3;
nd3.next = NULL;

p = &nd1;

for (i = 1; i <= 3; i++){
printf("%d\n", p->data);
p = p->next;
    }
}

150111

Ruby


「アルゴリズムとデータ構造」のRuby版。

バイナリサーチ

# -*- coding: cp932 -*-

NOT_FOUND = -1
N = 10

def binary_search(x, a, left, right)
  while left <= right
    mid = (left + right) / 2
    return mid if a[mid] == x
    if a[mid] < x 
      left = mid + 1
    else
      right = mid - 1
    end
  end
  return NOT_FOUND
end

# 適当な配列を作る
array = []
printf("array ")
printf("[0]:%d ", array[0] = rand(3))
for i in (1..N - 1)
  printf("[%d]:%d ", i, array[i] = array[i - 1] + rand(3))
end
printf("\n何を探しますか:")
i = gets().to_i
r = binary_search(i, array, 0, N - 1)
if r == NOT_FOUND
  printf("%dは見つかりません\n", i)
else
  printf("%dは%d番目です\n", i, r)
end

バイナリサーチ(lower_bound)

# -*- coding: cp932 -*-

NOT_FOUND = -1
N = 10

def binary_search(x, a, left, right)
  while left < right
    mid = (left + right) / 2
    if a[mid] < x
      left = mid + 1
    else
      right = mid
    end
  end
  return left if a[left] == x
  return NOT_FOUND
end

# 適当な配列を作る
array = []
printf("array ")
printf("[0]:%d ", array[0] = rand(3))
for i in (1..N - 1)
  printf("[%d]:%d ", i, array[i] = array[i - 1] + rand(3))
end
printf("\n何を探しますか:")
i = gets().to_i
r = binary_search(i, array, 0, N - 1)
if r == NOT_FOUND
  printf("%dは見つかりません\n", i)
else
  printf("%dは%d番目です\n", i, r)
end

2015年1月10日土曜日

150110(4)

Ruby


「アルゴリズムとデータ構造」のRuby版。

リニアサーチ

# -*- coding: cp932 -*-

NOT_FOUND = -1
N = 10

def linear_search(x, a, num)
  # 配列の範囲内で目的の値を探す
  n = 0
  while n < num && a[n] != x
    n += 1
  end
  return n if n < num
  return NOT_FOUND
end

# 適当な配列を作る
array = []
printf("array ")
for i in (0..N - 1)
  printf("[%d]:%d ", i, array[i] = rand(20))
end
printf("\n何を探しますか:")
i = gets().to_i
r = linear_search(i, array, N)
if r == NOT_FOUND
  printf("%dは見つかりません\n", i)
else
  printf("%dは%d番目です\n", i, r)
end

リニアサーチ(番兵つき)

# -*- coding: cp932 -*-

NOT_FOUND = -1
N = 10

def linear_search(x, a, num)
  n = 0
  # 最後の値をxに入れ替える(番兵)
  t = a[num - 1]
  a[num - 1] = x
  while a[n] != x
    n += 1
  end
  # 配列の最後の値を元に戻す
  a[num - 1] = t
  return n if n < num - 1
  return n if x == t
  return NOT_FOUND
end

# 適当な配列を作る
array = []
printf("array ")
for i in (0..N - 1)
  printf("[%d]:%d ", i, array[i] = rand(20))
end
printf("\n何を探しますか:")
i = gets().to_i
r = linear_search(i, array, N)
if r == NOT_FOUND
  printf("%dは見つかりません\n", i)
else
  printf("%dは%d番目です\n", i, r)
end

150110(3)

Ruby


「アルゴリズムとデータ構造」のRuby版。

マージソート

# -*- coding: cp932 -*-

# データの件数
N = 10

def mergeSort(n, x, offset)
  return if n <= 1
  m = n / 2
  # ブロックを2分割する
  mergeSort(m, x, offset)
  mergeSort(n - m, x, offset + m)
  # 併合操作
  buffer = Array.new(m)
  for i in (0..m - 1)
    buffer[i] = x[offset + i]
  end
  j = m
  i = 0
  k = 0
  while i < m && j < n
    if buffer[i] <= x[offset + j]
      x[offset + k] = buffer[i]
      i += 1
    else
      x[offset + k] = x[offset + j]
      j += 1
    end
      k += 1
  end
  while i < m
    x[offset + k] = buffer[i]
    k += 1
    i += 1
  end
end

@sort = []
printf("ソート準備:\n")
for i in (0..N - 1)
  # 配列にランダムな値を格納
  @sort[i] = rand(1000)
  printf("%d ", @sort[i])
end
printf("\nソート開始:\n")
mergeSort(N, @sort, 0)
printf("\nソート終了:\n")
for i in (0..N - 1)
  printf("%d ", @sort[i])
end

150110(2)

Ruby


「アルゴリズムとデータ構造」のRuby版。

クイックソート

# -*- coding: cp932 -*-

# データの件数
N = 10

def quickSort(bottom, top, data)
  return if bottom >= top
  # 先頭の値を「適当な値」とする
  div = data[bottom]
  lower = bottom
  upper = top
  while lower < upper
    while lower <= upper && data[lower] <= div
      lower += 1
    end
    while lower <= upper && data[upper] > div
      upper -= 1
    end
    if lower < upper
      temp = data[lower]
      data[lower] = data[upper]
      data[upper] = temp
    end
  end
  # 最初に選択した値を中央に移動する
  temp = data[bottom]
  data[bottom] = data[upper]
  data[upper] = temp
  quickSort(bottom, upper - 1, data)
  quickSort(upper + 1, top, data)
end

@sort = []
printf("ソート準備:\n")
for i in (0..N - 1)
  # 配列にランダムな値を格納
  @sort[i] = rand(1000)
  printf("%d ", @sort[i])
end
printf("\nソート開始:\n")
quickSort(0, N - 1, @sort)
printf("\nソート終了:\n")
for i in (0..N - 1)
  printf("%d ", @sort[i])
end

150110

Ruby


「アルゴリズムとデータ構造」のRuby版。

バブルソート

# -*- coding: cp932 -*-

# データの件数
N = 10

def bubbleSort()
  flag = true
  # 1度も並べ替えをせずに見終わったら終了
  while flag
    flag = false
    for i in (0..N - 2)
      # 左右の並びがおかしければ
      if @sort[i] > @sort[i + 1]
        flag = true
        j = @sort[i]
        @sort[i] = @sort[i + 1]
        @sort[i + 1] = j
      end
    end
  end
end

@sort = []
printf("ソート準備:\n")
for i in (0..N - 1)
  # 配列にランダムな値を格納
  @sort[i] = rand(1000)
  printf("%d ", @sort[i])
end
printf("\nソート開始:\n")
bubbleSort()
printf("\nソート終了:\n")
for i in (0..N - 1)
  printf("%d ", @sort[i])
end

2015年1月4日日曜日

150104(2)

Ruby


「n-クイーン」パズル

バリエーション解を全て出力するコードを、
「アルゴリズムとデータ構造」第10章と、
スタック・オーバーフローにおける回答を
もとに作成。
http://ja.stackoverflow.com/questions/3021/%E3%82%A8%E3%82%A4%E3%83%88%E3%82%AF%E3%82%A4%E3%83%BC%E3%83%B3%E3%83%91%E3%82%BA%E3%83%AB%E3%81%AE%E8%A7%A3%E6%B3%95%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6

N = 5
@count = 0
@board = Array.new(N){Array.new(N, false)}

# (x,y)にクィーンがあるかどうかチェック
def check(x, y)
  # 左方向をチェック
  p = x
  while p > 0
    return false if @board[p -= 1][y]
  end
  # 左上方向をチェック
  p, q = x, y
  while p > 0 && q > 0
    return false if @board[p -= 1][q -= 1]
  end
  # 左下方向をチェック
  p, q = x, y
  while p > 0 && q < N - 1
    return false if @board[p -= 1][q += 1]
  end
  return true
end

def showBoard
  for y in (0..N - 1)
    for x in (0..N - 1)
      printf @board[x][y]? 'Q ' : '. '
    end
    printf "\n"
  end
end

def solve(x)
  if x == N
    # すべての列にクィーンを置けたので、解を表示する。
    @count += 1
    showBoard
    puts "--" * N
  else
    # (x, 0) ... (x, N-1) にクィーンを置くことを試していく。
    for i in (0..N - 1)
      if check(x, i)
        # (x, i) にクィーンが置けるので、実際に置く。
        @board[x][i] = true
        # 次の列に進む
        solve(x + 1)
        # (x, i) に置いたクィーンを取り除く。
        @board[x][i] = false
      end
    end
  end
end

solve(0)
puts @count

150104

Ruby


ナップザック問題

アルゴリズムとデータ構造という本にC言語, Java版が載っているので、
そのRuby版。

# -*- coding: cp932 -*-

# 商品の数と,それぞれの大きさ,価値
N = 5
size = [2,3,5,6,9]
value = [2,4,7,10,14]

# ナップザックの大きさ
NAP_SIZE = 16

# ナップザックの現時点での価値
nap_value= Array.new(NAP_SIZE + 1, 0)

printf("ナップザックの大きさ:")
for i in (1..NAP_SIZE)
  printf("%2d ",i)
end
printf("\n\n")

# 扱う品物を,1つずつ増やしていく
for i in (0..N - 1)
  # ナップザックの大きさがjのものに対して,品物i番を入れてみる
  for j in (size[i]..NAP_SIZE)
    # 品物iを入れてみた場合,新しい価値はどう変わるか
    new_value = nap_value[j - size[i]] + value[i]
    if new_value > nap_value[j]
      nap_value[j] = new_value
    end
  end
  printf("     品物 %dまで使う:",i+1)
  for j in (1..NAP_SIZE)
    printf("%2d ",nap_value[j])
  end
  printf("\n")
end

2015年1月2日金曜日

150102(6)

Haskell


すごいH本

第14章14.1

import Control.Monad.Writer

gcd' :: Int -> Int -> Writer [String] Int
gcd' a b
    | b == 0 = do
      tell ["Finished with " ++ show a]
      return a
    | otherwise = do
      tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod`b)]
      gcd' b (a `mod` b)

Prelude> :l 14.1
[1 of 1] Compiling Main             ( 14.1.hs, interpreted )
Ok, modules loaded: Main.
*Main> fst $ runWriter (gcd' 8 3)
Loading package transformers-0.3.0.0 ... linking ... done.
Loading package mtl-2.1.2 ... linking ... done.
1
*Main> mapM_ putStrLn $ snd $ runWriter (gcd' 8 3)
8 mod 3 = 2
3 mod 2 = 1
2 mod 1 = 0
Finished with 1

第14章14.5

import Control.Monad

powerset :: [a]->[[a]]
powerset xs = filterM (\x->[True,False]) xs

Prelude> :l 14.5
[1 of 1] Compiling Main             ( 14.5.hs, interpreted )
Ok, modules loaded: Main.
*Main> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

150102(5)

Haskell


すごいH本

第13章13.6

type KnightPos = (Int, Int)

moveKnight :: KnightPos -> [KnightPos]
moveKnight (x, y) = filter onBoard
    [(x + 1, y + 2),(x + 1, y - 2),(x + 2, y + 1),(x + 2, y - 1),(x - 1, y + 2),(x - 1, y - 2),(x - 2, y + 1),(x - 2, y - 1)]
    where onBoard (x', y') = x' `elem` [1..8] && y' `elem` [1..8]

in3 :: KnightPos -> [KnightPos]
in3 start = do
    first <- moveKnight start
    second <- moveKnight first
    moveKnight second
 
canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start

Prelude> :l 13.6
[1 of 1] Compiling Main             ( 13.6.hs, interpreted )
Ok, modules loaded: Main.
*Main> canReachIn3 (6, 2) (6, 1)
True
*Main> canReachIn3 (6, 2) (7, 3)
False

150102(4)

Haskell


Tree

-- Tree.hs : 二分探索木
module Tree (
  Tree,
  emptyTree, singleton,
  treeInsert, treeElem
) where

-- データ型の定義
data Tree a = Nil | Node a (Tree a) (Tree a) deriving Show

-- 空の木
emptyTree :: Tree a
emptyTree = Nil

-- 要素が一つの木
singleton :: a -> Tree a
singleton x = Node x Nil Nil

-- データの挿入
treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x Nil = singleton x
treeInsert x (Node y l r)
  | x == y    = Node x l r
  | x < y     = Node y (treeInsert x l) r
  | otherwise = Node y l (treeInsert x r)

-- データの探索
treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem _ Nil = False
treeElem x (Node y l r)
  | x == y    = True
  | x < y     = treeElem x l
  | otherwise = treeElem x r

Prelude> :l Tree
[1 of 1] Compiling Tree             ( Tree.hs, interpreted )
Ok, modules loaded: Tree.
*Tree> emptyTree
Nil
*Tree> singleton 1
Node 1 Nil Nil
*Tree> let nums = [8, 6, 4, 1, 7, 3, 5]
*Tree> let numsTree = foldr treeInsert emptyTree nums
*Tree> numsTree
Node 5 (Node 3 (Node 1 Nil Nil) (Node 4 Nil Nil)) (Node 7 (Node 6 Nil Nil) (Node
 8 Nil Nil))
*Tree> treeElem 3 numsTree
True
*Tree> treeElem 2 numsTree
False
*Tree> treeInsert 2 numsTree
Node 5 (Node 3 (Node 1 Nil (Node 2 Nil Nil)) (Node 4 Nil Nil)) (Node 7 (Node 6 N
il Nil) (Node 8 Nil Nil))

150102(3)

Haskell


アプリカティブ・スタイル

リスト

ついでに141224分もやり直してみました。

Prelude> import Control.Applicative
Prelude Control.Applicative> [(*0),(+100),(^2)] <*> [1,2,3]
[0,0,0,101,102,103,1,4,9]
Prelude Control.Applicative> [(+),(*)] <*> [1,2] <*> [3,4]
[4,5,5,6,3,4,6,8]
Prelude Control.Applicative> import Data.List
Prelude Control.Applicative Data.List> sort [x + y | x <- [2,5,10], y <- [8,10,1
1]]
[10,12,13,13,15,16,18,20,21]
Prelude Control.Applicative Data.List> sort ((+) <$> [2,5,10] <*> [8,10,11])
[10,12,13,13,15,16,18,20,21]
Prelude Control.Applicative Data.List> [x | x <- [220,230..320]] \\ ((+) <$> [0,
50..300] <*> [0,80..320])
[220,270]

Zip リスト

Prelude> import Control.Applicative
Prelude Control.Applicative> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [1
00,100..]
[101,102,103]
Prelude Control.Applicative> getZipList $ max <$> ZipList [1,2,3,4,5,3] <*> ZipL
ist [5,3,1,2]
[5,3,3,4]
Prelude Control.Applicative> getZipList $ (,,) <$> ZipList "dog" <*> ZipList "ca
t" <*> ZipList "rat"
[('d','c','r'),('o','a','a'),('g','t','t')]

150102(2)

Haskell


すごいH本

第10章10.2

--道路網のデータ構造
data Section = Section { getA :: Int, getB :: Int, getC :: Int}
    deriving (Show)
type RoadSystem = [Section]

--道路網を引数として取って,経路を返す関数
data Label = A | B | C deriving (Show)
type Path = [(Label, Int)]

roadStep :: (Path, Path) -> Section -> (Path, Path)
roadStep (pathA, pathB) (Section a b c) =
    let timeA = sum (map snd pathA) -- Aまでの所要時間
        timeB = sum (map snd pathB)

        forwardTimeToA = timeA + a     --次のAまでの時間 直進
        crossTimeToA   = timeB + b + c --次のAまでの時間 道路を曲がる
        forwardTimeToB = timeB + b
        crossTimeToB   = timeA + a + c

        --AとBへの新しい経路を生成する
        newPathToA = if forwardTimeToA <= crossTimeToA
                        then (A, a) : pathA         --前から追加
                        else (C, c) : (B, b) :pathB

        newPathToB = if forwardTimeToB <= crossTimeToB
                        then (B, b) : pathB
                        else (C, c) : (A, a) :pathA

    in (newPathToA, newPathToB)
   
--最短経路を求める.
optimalPath :: RoadSystem -> Path
optimalPath roadSystem =
    let (bestApath, bestBpath) = foldl roadStep ([], []) roadSystem
    in if sum (map snd bestApath) <= sum (map snd bestBpath)
            then reverse bestApath
            else reverse bestBpath

--ヒースロー空港からロンドンまでの道路網
heathrowToLondon :: RoadSystem
heathrowToLondon = [
                    Section 50 10 30,
                    Section  5 90 20,
                    Section 40  2 25,
                    Section 10  8  0]

Prelude> :l 10.2
[1 of 1] Compiling Main             ( 10.2.hs, interpreted )
Ok, modules loaded: Main.
*Main> optimalPath heathrowToLondon
[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8),(C,0)]

150102

Ruby


RPN

def calc(num1, num2, operator)
  a, b = num1.to_f, num2.to_f
  return a + b if operator == "+"
  return a - b if operator == "-"
  return a * b if operator == "*"
  return a / b if operator == "/"
end

def solveRPN(str)
  stack = []
  datas = str.split(" ")
  datas.each{|data|
    # dataが数字のとき
    if data =~ /\d/
      stack << data
    # dataが記号のとき
    else
      p2 = stack.pop
      p1 = stack.pop
      stack << calc(p1, p2, data)
    end
  }
  stack
end

puts solveRPN("10 4 3 + 2 * -")
puts solveRPN("12 2 / 3 /")