あなたの死をかわす!

前書き

“Muhuhuhahahah!”狂った科学者は笑う。 「あなたは私の小さな試合に閉じ込められています!」

あなたの前にはヘビの致命的な穴があり、背後には底なしの穴があります。方法はありません、あなたは立ち往生しています!

「あなたの目の前には、ヘビの窪みが2つありますが、後ろの2歩は峡です。しかし、移動する前に、前後の手順を書き留めて、私に渡す必要があります。今日、
evil というビットを感じているので、すべての n
ステップで、すべてのステップの代わりに、 n あなたのシーケンスの長さ!

今すぐ賢明に選択してください。

差し迫った死の前に取ることができる最大ステップ数はいくらですか?

仕事

上記のイントロは、最近のErdősの不一致の憶測のひねりです実証済みです(詳細については、この動画を参照してください)グライム – 私は彼のひねりの質問を「盗んだ」)。

イントロへの答えは 11 ですが、証拠はあまりにも深くはありません。あなたと2つの「危険」との距離が
3 ステップであった場合の回答は、まだ正しく検証されていませんが、 1160
ステップです。

Your 仕事 is to make a program that generates the longest sequence
of steps you can achieve for a larger x, where
x is the number of steps between you and the two
“dangers”. Your program must take an input for x, and
output a valid sequence for that x.

この挑戦の目的のために、 + は前進を表し、 - は後退を表します。

したがって、入力 2 の出力は次のようになります。

+--+-++--++

これは、狂った科学者が選択する n に関係なく機能します。私たちの挑戦のために、 x =
5

注:この挑戦は、このチャレンジまたはこの課題は、コード自体とは対照的に、私の挑戦がアウトプットに重点を置いているため、言い換えればコードゴルフの挑戦ではありません。同様に、これらの課題は、すでに確立された上限がある
x = 3 に基づいています。

ルール:

  • Your entire program should fit into your answer. However, if it
    doesn’t fit, please provide an additional Github repository, or
    something similar.
  • You may update both your answer and your program, if you can
    get a better score via optimising your code – but by doing so, you
    must update everything in the list below.
  • In your answer, you must have:
    • Your program, in its entirety, or a link to a GH repository
      hosting your code
    • The amount of steps generated – this will be your final
      score
      .

      • You must also provide an online version of the
        sequence
        in a Pastebin, or something similar. This is so
        we can check your answer.
    • The time your final score was last updated, so I don’t have to
      check your history
  • You may NOT hardcode sequences beforehand.
  • Your program must work for all x
    (where x is the number of steps between you and the
    pit & chasm), but you only need to provide the score for x =
    5
    .

最大得点の回答が勝ちます!

ベストアンサー

錆、得点= 4997216、時間= 2017-07-12 00:18 UTC

これは、私が文献で見つけた最高の結果である1148805(Ronan Le Bras、Carla P. Gomes、Bart
Selman、ErdősDiscrepancy Problemについては、2014)、4.3の因子で計算されます。

長さ4997216の出力シーケンス

GitHubのソースコード

ランニング

プログラムは引数として最大の不一致を受け入れます(より一般的な数学的な規則に合わせて、チャレンジの言語で x
– 1)。 x = 3のように少し圧縮した形式で増分出力を生成します。

$ cargo run --release 2
add +--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-+
length 90
delete 12
add --++--+-++-++--+-++--+--+-++--+-
length 110
delete 4
add +-+--+-++-++--+-++--+--+-++-++--+-++-+
length 144
delete 6
add --++-++--+-++--+--++++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-+-
length 214
delete 208
add --+++--+++--+-+--+++--+-+--+++--++---+-+--+-+-++-+--+++--+++--+---++-+--+-++-+++---++--+-++-++--++--+--++--+++--+-+-++-+--+-+--+++---+++-+----+++--+-++--++-+-++--+-+--+-+-++-+--+++--++--+--+--+-++-++---++-++-++-+--+-++
length 224
delete 2
add -+++--+-+--+++---++--+--
length 246
done

add は現在のシーケンスの最後に記号のシーケンスを追加することを意味し、
delete は現在のシーケンスの最後からいくつかの記号を削除し、
は現在のシーケンスの長さをアサートします。このスキームは、長くて長いシーケンスが発見されるにつれ、数ギガバイトの中間結果を生成することを回避する。次のPythonプログラムを使用すると、これまでのところ最良の結果を抽出できます。

import sys
s = ''
for line in sys.stdin:
    cmd = line.split()
    if cmd[0] == 'delete': s = s[:-int(cmd[1])]
    elif cmd[0] == 'add': s += cmd[1]
    elif cmd[0] == 'length': assert len(s) == int(cmd[1])
print(s)

使い方

ここには約1000行のコードがありますので、これは非常に大まかな概観に過ぎません。

検索は、完全乗法のシーケンス( f ( ) a
ab n =
1の部分和を境界付けることだけに気を付ける必要があることを意味し、 n
≧2の部分和は、自動的に同じバウンドになります。

部分的に割り当てられた記号シーケンスの任意の部分文字列 fi + 1)、…、
fj ) (各要素が ‘+’、 ‘ – ‘、または未知)である場合、危険
+ij )を’ ii
の長さを引いたもの)この目的のために + 2と仮定し、 f ( – x + 3)=⋯=
f (0)= ‘+’ )。危険を ij
)同様に定義します。 n = 1の部分和の束縛は、 ij
xjx – 危険と i
j )≤ x – 2。

我々は、対数時間の更新を伴う、最大の危険を伴う部分文字列に対する一定時間問合せをサポートする増分データ構造を構築する。
4つの値を関連付けることで動作します。

  • 危険( ij )、
  • i j> k )、 i k j>
    j )、および ji i > k
    l )、

長さ2のすべての文字列、長さ4の文字列、長さ8の文字列ごとに続きます。長い文字列に関連付けられた値は、その2つの半分に関連付けられた値から一定の時間内に計算できます。

この構造は、いくつかの補助情報を追加することで、部分シーケンスに対する制約伝播と競合検出を非常に迅速に実行することができます。ユニットの伝播、決定レベル、およびその他の情報が含まれた
CDCL の検索には、
(今のところ、句学習はしていませんが)、より長い長さの完全なシーケンスのために、非時間順のバックトラッキングがあります。

各検索ステップで、最も初期の割り当てられていない記号を推測します。この推定を行うために使用されたヒューリスティックは、多くのバックトラッキングを避けるために非常に重要です。
f (3・ k )= – fk )、 (3・
k + 1)= ‘+’、 f (3・ + 2)= ‘ – ‘

結果

不一致0、1、および2の探索は、長さ0,9および246の最適完全乗法系列を直ちに見つける。

不一致3の検索は、Le Bras et
al。、2014によって発見された長さ127645の既知の最適な完全乗法系列(および長さ130000 は、 a href =
“http://cgi.csc.liv.ac.uk/~konev/SAT14/” rel = “nofollow
noreferrer”>長さ17000 を入力してください。

不一致4検索は、4997216で立ち往生するまで、最長シーケンスを約5分間にわたって多かれ少なかれ連続的に改善する。長さ1148805
= 9・127645の最もよく知られたシーケンスは、不一致3シーケンスから、すべての記号 s は+ – + – ++
s
です。私が言うことができる限り、この長いシーケンスは、一般的なSATソルバーが合理的に直接的に改善するのは難しいです(しかし、親愛なる読者は、間違っていると私は証明できます)。

私は、これらの障壁を乗り越えるために私のプログラムに何らかの習慣を追加する必要があると思っています。

2187×2285のビットマップとしてのシーケンス

(クリックしてフル解像度で表示する)

2187×2285のビットマップとしてのシーケンス

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です