Skip to content

Instantly share code, notes, and snippets.

takuma-saito

View GitHub Profile
View suffix-automan.rb
class Node
attr_accessor :edges, :terminal, :suffix_link, :id
def initialize
@edges = {}
@done = false
@suffix_link = nil
@id = nil
end
def [](char)
View level5-death.rb
INF = 2 ** 20
def turn(k, counter = 0)
@dp ||= {}
return nil if k < 1 || k > 255 || counter > 100
return @dp[k] if @dp[k]
return @dp[k] = {count: 1, prev: k, action: :D, current: k} if (k % 5) === 0
t1 = nil
t2 = turn(k/2, counter + 1)
t3 = turn(k + 10, counter + 1)
t4 = turn(k + 20, counter + 1)
@takuma-saito
takuma-saito / naive-suffix-tree.rb
Last active Mar 23, 2019
naive-suffix-tree.rb
View naive-suffix-tree.rb
class Node
attr_accessor :edges, :link
def initialize(link = nil, edges = {})
@link = nil
@edges = edges
end
end
class Edge
attr_reader :l, :r, :node, :text
def initialize(l, r, node, text)
View stack-calculator.rb
ORDER = {
'$' => 1,
'-' => 2,
'+' => 3,
'*' => 4,
'/' => 5,
}
OPERATOR = {
'-' => -> (a, b) {a - b},
View algo-1.rb
# a_1, a_2, ..., a_n に対して, それぞれ 0 <= a_i <= c_i という成約を満たしつつ
# \sum_{i = 1}^n a_i = N を満たす組み合わせをすべてリストアップする
def solve(n, sum, d, cap)
c = cap.pop
if cap.empty?
yield [sum]
cap.push c
return
end
@takuma-saito
takuma-saito / hitorini-sitekure-problem-7-1.rb
Last active Mar 3, 2019
hitorini-sitekure-problem-7-1.rb
View hitorini-sitekure-problem-7-1.rb
# coding: utf-8
def dfs(board, i, j)
return if (i <= 0 || i > LEN) ||
(j <= 0 || j > LEN) ||
board[i][j] <= 0 || board[i][j] > M
board[i][j] += M
[[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]].each do |pos|
l, m = pos
v = board[l][m]
View apuzzle-83.rb
def out(from, to, k)
$state[to - 1] += 1
$state[from - 1] -= 1
puts "[#{k}]: #{from} -> #{to}, #{$state}"
end
def move_2_to_3(k)
return if k == 0
move_2_to_1(k - 1)
out(2, 3, k)
View q-puzzle.rb
# 9 パズルビームサーチの擬似コード
queue.push({s: {7, 8, 0, 1, 2, 3, 4, 5, 6}, r: 2})
while (not queue.empty())
pqueue = PriorityQueue.new
while (q = queue.pop())
[[-1, 0], [0, 1], [1, 0], [0, -1]].each do |d|
newState = state(q, d)
pqueue.push(newState)
pqueue.pop() if pqueue.size > K
View apuzzle-49.rb
# coding: utf-8
require 'set'
def solve
nodes = []
nodes.push({s: {m: 3, c: 3, d: -1}, prev: nil})
set = Set.new
set << nodes[0][:s]
while node = nodes.shift
v = node[:s]
You can’t perform that action at this time.