任意の不等式の処理と成り立つ場合のチェック

Question

非負整数nとユーザ定義の任意の不等式（例えば、外部テキストファイル）が与えられた場合、nが満たすかどうかを判定したい任意の不等式、もしあれば、どのような不等式であるかを示す。

---

ここにポイントリストがあります。

n = 0: 1 
n < 5: 5 
n = 5: 10 

5に等しい数nを描画すると、10点が得られます。
nが5未満の場合、5ポイントを獲得します。
nが0の場合、1ポイントが得られます。

---

コロンの左のものは「条件」、右側のものは「値」です。
すべてのエントリの形式は次のようになります。

このシステムでは

n1 op n2: val 

、平等は不平等よりも優先されますので、彼らが表示される順序は、最終的には問題はありません。入力は非負の整数であるが、中間と結果は非負ではないかもしれない。結果は数字でなくてもよい（例：文字列でもよい）。それが唯一のパーサを書くためにそれを容易にするために（そして、このアイデアは実現可能であるかどうかを確認するために）、最も基本的な不平等を受け入れるので、私はそれを設計している

私のプログラムは、2つのコンポーネントがあります。

1. を構造化された入力を読み込み、条件と関連する結果を格納するデータ構造を構築します。

2. （、例のように、Iは、受信点の数又は）引数（非負整数）を取り、結果を返す関数

リストがハードコードされた場合これは簡単な作業です：case-whenブロックまたはif-elseブロックを使用するだけで済みます。しかし問題はそれほど簡単ではありません。

上部のリストを思い出してください。任意の数の（等号）等価を含むことができます。おそらく、上記のような3つしかないでしょう。多分、存在しないかもしれないし、多分10,20,50、またはさらには1000000あるかもしれない。本質的に、m> = 0のためにm不等式を持つことができる。

任意の数の条件を含む数nとデータ構造私はそれが条件のいずれかを満たしているかどうかを判断し、関連する値を返すことができるようにしたいと考えています。上記の例のように、5を渡すと、関数は10を返します。

これらの条件と値のペアは、生の形式で一意ではありません。同じ（等）の複数のインスタンスが異なる値を持つことがあります。例：

n = 0: 10 
n = 0: 1000 
n > 0: n 

最後のエントリに注意してください.nが0より大きい場合は、取得したものだけです。

複数の不等式が満たされている場合（n> 5、n> 6、n> 7など）、すべてが返されます。それが効率的に行うことができない場合、私はそれを満足し、残りを無視する最初のものだけを返すことができます。しかし、私はリスト全体を取得することができるようにしたいと思います。

---

私はしばらくの間、これについて考えてきたと私は、私は2つのハッシュテーブルを使用する必要があります考えています：最初のものは等式を格納する、第二の不平等を保存する一方。

扱うのは簡単です：条件をキーとして取得し、値のリストを取得するだけです。次に、nがハッシュに入っているかどうかを素早く確認し、適切な値を取得できます。

しかし、不等式のために、私はそれがどのように動作するかはわかりません。誰も私ができるだけ少ない計算ステップでこの問題を解決できる方法を知っていますか？私はO（n）時間で簡単にこれを達成できることは明らかです。それぞれを（1つずつ）均等に実行するだけです。しかし、このチェックがリアルタイムで行われるとどうなりますか？

たとえば、100の不等式があり、99の値が100より大きい値をチェックし、もう1つの値が< = 100であるかどうかをチェックすると、気にする必要はありませんこれらの99の不等式を47を渡すとチェックします。

データを格納するために任意のデータ構造を使用できます。パーサ自体は事前処理され、一度だけ実行する必要がありますが、データの解析に時間がかかりすぎると問題が発生する可能性があるため、計算には含まれません。

私はRubyを使用しているので、データを使いこなす方法や解釈方法について、より柔軟な選択肢があると思います。

Answer 1

class RuleSet 
    Rule = Struct.new(:op1,:op,:op2,:result) do 
    def <=>(r2) 
     # Op of "=" sorts before others 
     [op=="=" ? 0 : 1, op2.to_i] <=> [r2.op=="=" ? 0 : 1, r2.op2.to_i] 
    end 
    def matches(n) 
     @op2i ||= op2.to_i 
     case op 
     when "=" then n == @op2i 
     when "<" then n < @op2i 
     when ">" then n > @op2i 
     end 
    end 
    end 

    def initialize(text) 
    @rules = text.each_line.map do |line| 
     Rule.new *line.split(/[\s:]+/) 
    end.sort 
    end 

    def value_for(n) 
    if rule = @rules.find{ |r| r.matches(n) } 
     rule.result=="n" ? n : rule.result.to_i 
    end 
    end 
end 

set = RuleSet.new(DATA.read) 
-1.upto(8) do |n| 
    puts "%2i => %s" % [ n, set.value_for(n).inspect ] 
end 

#=> -1 => 5 
#=> 0 => 1 
#=> 1 => 5 
#=> 2 => 5 
#=> 3 => 5 
#=> 4 => 5 
#=> 5 => 10 
#=> 6 => nil 
#=> 7 => 7 
#=> 8 => nil 

__END__ 
n = 0: 1 
n < 5: 5 
n = 5: 10 
n = 7: n 

Answer 2

私はあなたの問題に多くの時間を費やしていないんだけど、ここで私の迅速な考えがあります：

points listは形式n1 op n2: valに常にあるので、私はハッシュの配列としてポイントをモデル化すると思います。

最初のステップは、入力ポイントリストをデータ構造、つまりハッシュの配列に解析することです。 各ハッシュの値はn1、op、n2、値は

です。次に、すべてのハッシュ（すべての点）を実行し、それぞれを処理します（入力データと一致するかどうかを判断します）。 ）。貿易の

いくつかのトリックは

は、不正な入力を扱うあなたのパーサでの時間をお過ごしください。例えば

n < = 1000 # no colon 
n < : 1000 # missing n2 
x < 2 : 10 # n1, n2 and val are either number or "n" 
n   # too short, missing :, n2, val 
n < 1 : 10x # val is not a number and is not "n" 

など

も丁寧に非数値の入力データ

追加を扱う

日時：n1は重要ではありません。注意してください、これはトリックかもしれません。なぜならない

5 < n : 30 

有効なポイントリストの項目ですか？

Re：複数のハッシュ配列、演算子ごとに1つの配列、1ポイントあたり1つのハッシュリスト項目 - これは問題ありません。各演算子は特定の方法で処理されるため、演算子を1つずつ処理することは問題ありません。しかし....その後、注文することは問題になる：

あなたが複数の結果が複数のマッチング点のリスト項目から返さたいので、あなたがそれらの全体的な秩序を維持する必要があります。したがって、私はすべてのポイントリストの1つの配列がこれを行う最も簡単な方法だろうと思う。

Answer 3

私は入力行を解析し、それらを述語/結果の組に分け、呼び出し可能な手続きのハッシュを構築します（eval - oh noes！）。 「チェック」機能は、各述語を反復処理し、いずれかに該当する場合に関連した結果を返すことができます。ここでは

class PointChecker 
    def initialize(input) 
    @predicates = Hash[input.split(/\r?\n/).map do |line| 
     parts = line.split(/\s*:\s*/) 
     [Proc.new {|n| eval(parts[0].sub(/=/,'=='))}, parts[1].to_i] 
    end] 
    end 
    def check(n) 
    @predicates.map { |p,r| [p.call(n) ? r : nil] }.compact 
    end 
end 

は、サンプルの使用である：もちろん

p = PointChecker.new <<__HERE__ 
    n = 0: 1 
    n = 1: 2 
    n < 5: 5 
    n = 5: 10 
__HERE__ 
p.check(0) # => [1, 5] 
p.check(1) # => [2, 5] 
p.check(2) # => [5] 
p.check(5) # => [10] 
p.check(6) # => [] 

、この実装で多くの問題があります。私はちょうど概念実証を提供しています。アプリケーションの範囲に応じて、適切なパーサとランタイム（evalを使用する代わりに）を作成し、より一般的に/優雅に入力を処理することができます。