0

非負の整数 n とユーザー定義の不等式の任意のセット (外部テキスト ファイルなど) が与えられた場合、n が不等式を満たすかどうか、満たす場合はどの不等式かを判断したいと考えています。

ポイント一覧はこちら。

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

n が 5 に等しい数字を引くと、10 ポイントを獲得できます。
n が 5 未満の場合、5 点を獲得します。
n が 0 の場合、1 ポイントを獲得します。

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

n1 op n2: val

このシステムでは、平等が不平等よりも優先されるため、それらが現れる順序は最終的には問題になりません。入力は非負の整数ですが、中間および結果は非負ではない場合があります。結果は数値でさえないかもしれません (例: 文字列かもしれません)。私は、最も基本的な不等式のみを受け入れるように設計しました。これは、パーサーを簡単に作成できるようにするためです (そして、このアイデアが実現可能かどうかを確認するため)。

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

  1. 構造化された入力を読み取り、データ構造を構築して条件とそれに関連する結果を格納するパーサー。

  2. 引数 (負でない整数) を取り、結果 (または、例のように、私が受け取るポイント数) を返す関数

リストがハードコーディングされている場合、それは簡単な作業です。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 をチェックしている場合、47 を渡すときにそれらの 99 個の不等式をわざわざチェックする必要がないことは明らかです。

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

私は Ruby を使用しているので、データの「いじり」やデータの解釈方法に関しては、より柔軟なオプションがあると思います。

4

3 に答える 3

2 
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
于 2012-05-04T20:33:51.360 に答える
1

入力行を解析し、それらを述語/結果のペアに分割し、呼び出し可能なプロシージャのハッシュを作成します ( eval- oh noes! を使用)。「チェック」関数は、各述語を繰り返し処理し、1 つが真の場合に関連する結果を返すことができます。

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アプリケーションの範囲に応じて、(を使用する代わりに) 適切なパーサーとランタイムを構築したり、入力をより一般的/適切に処理したりしたい場合があります。

于 2012-05-04T20:25:55.407 に答える
1

私はあなたの問題に多くの時間を費やしていませんが、ここに私の簡単な考えがあります：

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

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

次に、データ入力ごとに、すべてのハッシュ (すべてのポイント) を実行し、それぞれを処理します (入力データと一致するかどうかを判断します)。

取引のいくつかのトリック

間違った入力を処理するパーサーに時間を費やしてください。例えば

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"

等

数値以外の入力データも丁寧に扱う

追加した

Re: n1 doesn't matter. Be careful, this could be a trick. Why wouldn't 

5 < n : 30

be a valid points list item?

Re: multiple arrays of hashes, one array per operator, one hash per point list item -- sure that's fine. Since each op is handled in a specific way, handling the operators one by one is fine. But....ordering then becomes an issue:

Since you want multiple results returned from multiple matching point list items, you need to maintain the overall order of them. Thus I think one array of all the point lists would be the easiest way to do this.

于 2012-05-04T19:58:40.230 に答える