[Reality] Markov/Probability tables added

Glyph Lefkowitz glyph@twistedmatrix.com
Fri, 24 Dec 1999 09:41:57 -0500 (EST)


  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.
  Send mail to mime@docserver.cac.washington.edu for more info.

---791590007-1638864361-946046517=:24039
Content-Type: TEXT/PLAIN; charset=US-ASCII


On Fri, 24 Dec 1999 sneftel@popmail.com wrote:

> My thoughts on this: Intelligent randomness. Being able to transition
> between states like this is great for a more dynamic world. For
> instance, in my first playings-around with bots, I made one that goes
> a random direction each tick. That was cool, but anyone following him
> would have noticed that he moves randomly. A Markov table would make
> him move in a rather intelligent manner, if given as input his
> previous move. I could program actual routes into bots, but that would
> be timeconsuming and hard to maintain, for only slightly more realism.
> Other situations are similar, in that there are other ways to do them.

Cool.  Do you think you want to do weather too? =) ::subtly attempts to
avoid responsability...::

> So, when will this be released? I can't wait to reprogram my bot.
> 
> Ben Sunshine-Hill

This might take another week or so to get out the door, given that Dave's
on vacation, I'm leaving tomorrow, James hasn't committed the JList-ed
faucet.  So in the interest of letting you get to bot-reprogramming
faster, here's Mike's MarkovTable, as it should be in the 1.2.2 release.

Enjoy =)

If this is buggy in some way (I can't tell, I don't even know what it is,
really! ^_^) feel free to send any patches or whatever.

----
The Tao is like a glob pattern:             It is masked but always present.
used but never used up.                     I don't know who built to it.
It is like the extern void:                 It came before the first kernel.
filled with infinite possibilities.         [glyph@twistedmatrix.com]


---791590007-1638864361-946046517=:24039
Content-Type: TEXT/PLAIN; charset=US-ASCII; name="MarkovTable.java"
Content-Transfer-Encoding: BASE64
Content-ID: <Pine.LNX.4.10.9912240941570.24039@helix.twistedmatrix.com>
Content-Description: MarkovTable.java
Content-Disposition: attachment; filename="MarkovTable.java"

LyoqDQogKiBBIE1hcmtvdiB0YWJsZSBpcyBhIHN0cnVjdHVyZSB1c2VkIGZv
ciBzdG9yaW5nIHRoZSBwcm9iYWJpbGl0aWVzDQogKiBvZiB0cmFuc2l0aW9u
aW5nIGZyb20gYW4gaW5pdGlhbCBzdGF0ZSB0byBvbmUgb2Ygc2V2ZXJhbCBw
b3NzaWJsZQ0KICogbmV3IHN0YXRlcy4gIEZvciBleGFtcGxlLCBpZiB5b3Un
cmUgZGVhbGluZyB3aXRoIHdlYXRoZXIsIHlvdXINCiAqIHN0YXRlcyBtaWdo
dCBiZSA8aT5zdW4sIHJhaW4sPC9pPiBhbmQgPGk+c25vdzwvaT4sIHdpdGgg
eW91ciB0YWJsZQ0KICogbG9va2luZyBsaWtlIHRoaXM6DQogKg0KICo8dGFi
bGUgY2VsbHBhZGRpbmc9IjUiPg0KICogIDx0cj48dGg+SW5pdGlhbCBTdGF0
ZXM8L3RoPjwvdHI+DQogKiAgPHRyPg0KICogICAgPHRkPnN1bjwvdGQ+PHRk
PnJhaW48L3RkPjx0ZD5zbm93PC90ZD48dGQ+Jm5ic3A7PC90ZD48dGQ+Jm5i
c3A7PC90ZD4NCiAqICA8L3RyPg0KICogIDx0cj4NCiAqICAgIDx0ZD4zPC90
ZD48dGQ+MjwvdGQ+PHRkPjE8L3RkPjx0ZD5zdW48L3RkPjx0ZCByb3dzcGFu
PSIzIiB2YWxpZ249ImNlbnRlciI+PGI+UG9zc2libGUgU3RhdGVzPC9iPjwv
dGQ+DQogKiAgPC90cj4NCiAqICA8dHI+DQogKiAgICA8dGQ+MjwvdGQ+PHRk
PjQ8L3RkPjx0ZD4wPC90ZD48dGQ+cmFpbjwvdGQ+DQogKiAgPC90cj4NCiAq
ICA8dHI+DQogKiAgICA8dGQ+MjwvdGQ+PHRkPjA8L3RkPjx0ZD40PC90ZD48
dGQ+c25vdzwvdGQ+DQogKiAgPC90cj48L3RhYmxlPg0KICoNCiAqIChJZiB5
b3UndmUgc3R1ZGllZCBtYXRoLCB5b3UgbWlnaHQgYmUgd29uZGVyaW5nIHdo
YXQncyB1cCB3aXRoIHRoZQ0KICogdGFibGUgdmFsdWVzLiBOb3JtYWxseSwg
dGhlIHZhbHVlcyBpbiBhIGNvbHVtbiBhcmUgZmxvYXRzIHdob3NlIHN1bSBp
cyAxLg0KICogVGhpcyBjbGFzcyB1c2VzIGludHMgYmVjYXVzZSBpdCdzIG11
Y2ggZWFzaWVyIHRvIGltcGxlbWVudCBmb3IgdGhlIHB1cnBvc2VzDQogKiBp
dCdzIGxpa2VseSB0byBiZSB1c2VkIGZvci4gIEJlYXIgd2l0aCB1cy4gIDot
KQ0KICoNCiAqIEJ5IHRoaXMgdGFibGUsIGlmIGl0J3MgY3VycmVudGx5IHN1
bm55LCB0aGUgY2hhbmNlIG9mIGl0IHN0YXJ0aW5nIHRvIHJhaW4NCiAqIGlz
IDIgaW4gNiwgb3IgYWJvdXQgMzMlLg0KICoNCiAqIFRoaXMgY2xhc3MgYWxz
byBhbGxvd3MgeW91IHRvIGFkZCBhbiBpbnN0YW5jZSBvZiBhIHN0YXRlLCBz
byB5b3UgY2FuIGJhc2ljYWxseQ0KICogbG9nIHRyZW5kcy4gIEEgZGlmZmVy
ZW50IGV4YW1wbGUgaWxsdXN0cmF0ZXMgdGhpczogc2F5IHlvdSBzY2FuIGEg
ZGljdGlvbmFyeSwNCiAqIHNlbmRpbmcgZm9yIGVhY2ggd29yZCB0aGUgc2Vx
dWVuY2Ugb2YgbGV0dGVycyB0byB0aGUgTWFya292IHRhYmxlLiAgWW91IGNv
dWxkDQogKiB0aGVuIHVzZSB0aGUgdGFibGUgdG8gZ2VuZXJhdGUgd29yZHMg
dGhhdCwgd2hpbGUgbm90IGxpa2VseSB0byBiZSBhY3R1YWwNCiAqIGRpY3Rp
b25hcnkgd29yZHMsIHdvdWxkIGF0IGxlYXN0IGJlIHByb25vdW5jZWFibGUu
ICBUaGlzIHNvcnQgb2YgdGVjaG5pcXVlIA0KICogY291bGQgYmUgdXNlZCBm
b3IgZ2VuZXJhdGluZyBuYW1lcyBvZiBwbGFjZXMsIHdvcmRzIGluIGZvcmVp
Z24gdG9uZ3VlcywNCiAqIGFuZCBnb29kIGRlYWwgbWFueSBvdGhlciB0aGlu
Z3MuDQogKg0KICogPGI+UGxlYXNlIG5vdGUgdGhhdCBzdGF0ZSBuYW1lcyBh
cmUgPGk+Y2FzZS1zZW5zaXRpdmU8L2k+PC9iPg0KICoNCiAqIEBhdXRob3Ig
TWljaGFlbCBEYXJ0dCwgamVkaW5AdHdpc3RlZG1hdHJpeC5jb20NCiAqDQog
Ki8NCg0KDQpwYWNrYWdlIHR3aXN0ZWQudXRpbDsNCg0KLyogUG9zc2libGUg
SW1wcm92ZW1lbnRzDQogKiAtLS0tLS0tLS0tLS0tLS0tLS0tLS0NCiAqIG4t
ZGltZW5zaW9uYWwgbWF0cml4IC0tIFRISVMgV09VTEQgQkUgUkVBTExZIENP
T0whISENCiAqIFJlc2l6YWJsZS9leHBhbmRhYmxlIHRhYmxlcyAoY2FuIGFk
ZCBzdGF0ZXMgYmV5b25kIGluaXRpYWxpemF0aW9uKS0tQUxTTyBDT09MDQog
KiBBZGQgY29tcGFyaXNvbnMgdGhhdCBpZ25vcmUgY2FzZQ0KICogQWxsb3cg
Zm9yY2libHkgaW5zZXJ0aW5nIHNlcXVlbmNlcywgaWdub3Jpbmcgbm9uZXhz
aXN0ZW50IHN0YXRlcw0KICogVGFrZSBzZXF1ZW5jZSBsZW5ndGggaW50byBh
Y2NvdW50DQogKiBTYXZlIGxvY2F0aW9ucyB3aGVuIHZhbGlkYXRpbmcgc28g
dGhleSBkb24ndCBoYXZlIHRvIGJlIHJlY2FsY3VsYXRlZA0KICogRnVuY3Rp
b25zOiBkZWxldGVTdGF0ZSwgc3dhcFN0YXRlcywgcmVwbGFjZVN0YXRlLCBz
ZXRWYWx1ZXNGcm9tLCBzZXRWYWx1ZXNUbw0KICoNCiAqLw0KDQpwdWJsaWMg
Y2xhc3MgTWFya292VGFibGUNCnsNCiAgICBwcml2YXRlIFN0cmluZ1tdIHN0
YXRlczsNCiAgICAvL3ByaXZhdGUgaW50IG1heF9udW1fc3RhdGVzOw0KICAg
IHByaXZhdGUgaW50IG51bV9zdGF0ZXM7DQogICAgLy9zdGF0ZXNbXSBpcyB1
c2VkIGZvciBpbmRleGluZyB0aGUgcHJvYmFiaWxpdGllcywgc2luY2UgYSBN
YXJrb3YgdGFibGUNCiAgICAvL2lzIHNxdWFyZQ0KICAgIHByaXZhdGUgaW50
W11bXSBwcm9iX3RhYmxlOw0KDQogICAgLy9UaGUgcHJldmlvdXMgc3RhdGUg
aW5mbyBoYXMgdGhlc2Ugc2V0dGluZ3Mgd2hlbiB0aGVyZSdzIG5vdCBhIHNl
cXVlbmNlIGFjdGl2ZQ0KICAgIHByaXZhdGUgU3RyaW5nIHByZXZfc3RhdGUg
PSBudWxsOw0KICAgIHByaXZhdGUgaW50IHByZXZfc3RhdGVfbG9jID0gLTE7
DQoNCiAgICAvKioNCiAgICAgKiBAcGFyYW0gc3RhdGVzIC0gdGhlIHRhYmxl
IG11c3QgYmUgY3JlYXRlZCB3aXRoIGFsbCBvZiB0aGUgcG9zc2libGUgc3Rh
dGVzLCBlYWNoIGEgc2VwYXJhdGUgc3RyaW5nLg0KICAgICAqDQogICAgICov
DQogIC8vU3RyaW5ncyBhcmUgdXNlZCB0byBtYWtlIGNvbXBhcmlzb25zIGVh
c2llci4NCiAgICBNYXJrb3ZUYWJsZShTdHJpbmdbXSBzdGF0ZXMpDQogICAg
ew0KCXRoaXMuc3RhdGVzID0gc3RhdGVzOw0KCW51bV9zdGF0ZXMgPSBzdGF0
ZXMubGVuZ3RoOyAvL1RvIHNhdmUgY2FsbHMgbGF0ZXINCg0KCXByb2JfdGFi
bGUgPSBuZXcgaW50W251bV9zdGF0ZXNdW251bV9zdGF0ZXNdOw0KICAgIH0N
CiAgICANCiAgICANCiAgICAvKioNCiAgICAgKiBDaGVja3MgdG8gc2VlIHdo
ZXRoZXIgdGhlIHN1Ym1pdHRlZCBzdGF0ZSBleGlzdHMgb3Igbm90IGJ5IGRv
aW5nIGEgU3RyaW5nDQogICAgICogY29tcGFyaXNvbiB0aGF0IGlzIDxpPmNh
c2Utc2Vuc2l0aXZlPC9pPi4NCiAgICAgKiBAcmV0dXJuIFRoZSBwb3NpdGlv
biBpbiB0aGUgYXJyYXkgb2Ygc3RhdGVzIGlmIHRoZSBzdGF0ZSBleGlzdHMs
IC0xIG90aGVyd2lzZQ0KICAgICAqDQogICAgICovDQogICAgcHVibGljIGlu
dCB2ZXJpZnlTdGF0ZShTdHJpbmcgc3RhdGUpDQogICAgew0KCWludCBzdGF0
ZV9sb2MgPSAwOyAvL1N0YXRlJ3MgbG9jYXRpb24gaW4gdGhlIGFycmF5DQoN
Cgl3aGlsZSgNCgkgICAgICAoc3RhdGVfbG9jIDwgbnVtX3N0YXRlcykgJiYN
CgkgICAgICAhKHN0YXRlc1tzdGF0ZV9sb2NdLmVxdWFscyhzdGF0ZSkpDQoJ
ICAgICAgKSANCgl7DQoJICAgIHN0YXRlX2xvYysrOw0KCX0NCg0KCWlmKHN0
YXRlX2xvYyA9PSBudW1fc3RhdGVzKSByZXR1cm4gLTE7IC8vTm90IGluIHRo
ZSBzdGF0ZSBhcnJheQ0KCWVsc2UgcmV0dXJuIHN0YXRlX2xvYzsNCiAgICB9
DQogIA0KICANCiAgLyoqDQogICAqIFN0YXJ0cyBhIHNlcXVlbmNlIGdvaW5n
IGFmdGVyIHZlcmlmeWluZyB0aGUgZ2l2ZW4gc3RhdGUtLWdvb2QgZm9yIA0K
ICAgKiBwcm9ncmVzc2l2ZWx5IGFkZGluZyBvY2N1cnJlbmNlcyBvZiBzdGF0
ZXMuDQogICAqIFVzZSB0aGlzIHRvIHN0YXJ0IGEgbmV3IHNlcXVlbmNlLS1u
byBuZWVkIGZvciBhbiBlbmRTZXF1ZW5jZSgpIGZ1bmN0aW9uLiANCiAgICov
DQogICAgLy9TZXRzIHRoZSBwcmV2X3N0YXRlIHZhcmlhYmxlcyB0byB0aGUg
Z2l2ZW4gc3RhdGUsIGlmIGl0J3MgbGVnaXQNCiAgICBwdWJsaWMgYm9vbGVh
biBzdGFydFNlcXVlbmNlKFN0cmluZyBzdGF0ZSkNCiAgICB7DQoJaW50IHN0
YXRlX2xvYyA9IHZlcmlmeVN0YXRlKHN0YXRlKTsNCgkNCglpZiAoc3RhdGVf
bG9jIDwgMCkgcmV0dXJuIGZhbHNlOyAgLy9Ob3QgaW4gdGhlIGFycmF5DQoJ
ZWxzZSAvL0ZvdW5kIGl0DQoJew0KICAgICAgIAkgICAgcHJldl9zdGF0ZSA9
IHN0YXRlOw0KCSAgICBwcmV2X3N0YXRlX2xvYyA9IHN0YXRlX2xvYzsNCgkg
DQoJICAgIHJldHVybiB0cnVlOw0KCX0NCiAgICB9DQoNCg0KICAvKg0KICAg
IC8vQ2xlYW5zIHRoaW5ncyB1cA0KICAgIC8vWW91IHJlYWxseSBkb24ndCBu
ZWVkIHRoaXMtLXlvdSBjYW4ganVzdCB1c2Ugc3RhcnRTZXF1ZW5jZSBhZ2Fp
biBpbg0KICAgIC8vbW9zdCBjYXNlcw0KICAgIHB1YmxpYyB2b2lkIGVuZFNl
cXVlbmNlKCkNCiAgICB7DQogICAgcHJldl9zdGF0ZSA9IG51bGw7DQogICAg
cHJldl9zdGF0ZV9sb2MgPSAtMTsNCiAgICB9Ki8NCg0KDQogIC8qKg0KICAg
KiBWZXJpZmllcyBhIHNlcXVlbmNlIG9mIHN0YXRlcyBhbmQgdGhlbiBhZGRz
IHRoZSBlbnRpcmUgc2V0IG9mIA0KICAgKiBvY2N1cnJlbmNlcyB0byB0aGUg
dGFibGUuDQogICAqLw0KICAgIC8vQWRkcyBhIHNlcXVlbmNlLCBmaXJzdCBt
YWtpbmcgc3VyZSB0aGF0IGFsbCBvZiB0aGUgc3RhdGVzIGFyZSBsZWdpdA0K
ICAgIC8qIE9wdGltaXphdGlvbjogc2F2ZSBsb2NhdGlvbnMgZnJvbSBmaXJz
dCBsb29wIHNvIHlvdSBkb24ndCBoYXZlIHRvIHJlY2FsYyAqLw0KICAgIHB1
YmxpYyBib29sZWFuIGFkZFNlcXVlbmNlKFN0cmluZ1tdIG5ld19zdGF0ZXMp
DQogICAgew0KCWludCBuZXdfc3RhdGVzX2xlbiA9IG5ld19zdGF0ZXMubGVu
Z3RoOw0KCQ0KCS8vVXNlZCBmb3Iga2VlcGluZyB0cmFjayBvZiB3aGVyZSB0
aGUgc3RhdGVzIGFyZSBpbiBzdGF0ZXNbXQ0KCWludFtdIG5ld19zdGF0ZXNf
bG9jID0gbmV3IGludFtuZXdfc3RhdGVzX2xlbl07DQoJDQoJaW50IGk7IC8v
Q291bnRpbmcgdmFyaWFibGUhDQoNCgkvL0NoZWNrIGFsbCB0aGUgc3RhdGVz
LiAgRXhpdCBpZiBhbnkgb25lIGlzIG5vdCBsZWdpdA0KCWZvciAoaSA9IDA7
IGkgPCBuZXdfc3RhdGVzX2xlbjsgaSsrKQ0KCXsNCgkgICAgLy9Bc3NpZ24g
cmV0dXJuZWQgcG9zaXRpb25zIHRvIHRoZSBsb2NhdGlvbiBhcnJheQ0KCSAg
ICBpZiAoKG5ld19zdGF0ZXNfbG9jW2ldID0gdmVyaWZ5U3RhdGUobmV3X3N0
YXRlc1tpXSkpIDwgMCkgcmV0dXJuIGZhbHNlOw0KCX0NCg0KCS8vSWYgeW91
J3JlIGhlcmUsIGV2ZXJ5dGhpbmcgY2hlY2tlZCBvdXQtLWdvIGFoZWFkDQoJ
c3RhcnRTZXF1ZW5jZShuZXdfc3RhdGVzWzBdKTsNCg0KCS8vQWRkIGVhY2gg
c3RhdGUNCglmb3IgKGkgPSAxOyBpIDwgbmV3X3N0YXRlc19sZW47IGkrKykN
Cgl7DQoJICAgIGFkZE9jY3VycmVuY2UobmV3X3N0YXRlc19sb2NbaV0pOw0K
CX0NCgkNCglyZXR1cm4gdHJ1ZTsNCiAgICB9DQoNCiAgICANCiAgLyoqDQog
ICAqIEFkZHMgdGhlIHN0YXRlJ3Mgb2NjdXJyZW5jZSB0byB0aGUgY3VycmVu
dCBzZXF1ZW5jZSwNCiAgICogd2hpY2ggbXVzdCBiZSBhbHJlYWR5IHN0YXJ0
ZWQuDQogICAqIEBwYXJhbSBuZXh0X3N0YXRlX2xvYyAtIHRoZSBsb2NhdGlv
biBvZiB0aGUgc3RhdGUgaW4gYXJyYXkgb2Ygc3RhdGVzIChjYW4gYmUgZ290
dGVuIGZyb20gdmVyaWZ5U3RhdGUpDQogICAqIEByZXR1cm4gdHJ1ZSBpZiB0
aGUgc3RhdGUgZXhpdHMgKGFuZCBwZXJmb3JtcyB0aGUgYWRkKSwgZmFsc2Ug
b3RoZXJ3aXNlIChleGl0cyBhZnRlciBjaGVja2luZykNCiAgICogQHNlZSB2
ZXJpZnlTdGF0ZSgpDQogICAqIEBzZWUgc3RhcnRTZXF1ZW5jZSgpDQogICAq
Lw0KICAgIC8vQWRkcyBhbiBpbnN0YW5jZSBvZiBhIHN0YXRlDQogICAgcHVi
bGljIGJvb2xlYW4gYWRkT2NjdXJyZW5jZShpbnQgbmV4dF9zdGF0ZV9sb2Mp
DQogICAgew0KDQoJLy9JbmNyZW1lbnQgdGhlIHRyYW5zaXRpb24gY2VsbCBm
b3IgcHJldmlvdXMgc3RhdGUgLT4gbmV4dCBzdGF0ZQ0KCXRyeSB7IHByb2Jf
dGFibGVbbmV4dF9zdGF0ZV9sb2NdW3ByZXZfc3RhdGVfbG9jXSArPSAxOyB9
DQoJDQoJLy9JZiwgZm9yIHdoYXRldmVyIHJlYXNvbiwgdGhlcmUgaXNuJ3Qg
YSBzdGF0ZSB0aGVyZSwgcmV0dXJuIGZhbHNlLg0KCS8vTGlrZWx5IGNhdXNl
cyBhcmUgdGhlIGxvY2F0aW9uIGJlaW5nIGludmFsaWQgb3IgdGhlIHByZXZp
b3VzIHN0YXRlDQoJLy9ub3QgYmVpbmcgc2V0Lg0KCWNhdGNoIChJbmRleE91
dE9mQm91bmRzRXhjZXB0aW9uIGUpIHsgcmV0dXJuIGZhbHNlOyB9DQoNCgkv
L0lmIHlvdSdyZSBoZXJlLCBpdCB3b3JrZWQuICBUaGUgcHJldmlvdXMgc3Rh
dGUgYmVjb21lcyB0aGUgbmV4dCBzdGF0ZS4NCglwcmV2X3N0YXRlID0gc3Rh
dGVzW25leHRfc3RhdGVfbG9jXTsNCglwcmV2X3N0YXRlX2xvYyA9IG5leHRf
c3RhdGVfbG9jOw0KDQoJcmV0dXJuIHRydWU7DQogICAgfQ0KDQoNCiAgLyoq
DQogICAqIFZlcmlmaWVzIHRoZSBzdGF0ZSBhbmQgYWRkcyBpdHMgb2NjdXJy
ZW5jZSB0byB0aGUgY3VycmVudCBzZXF1ZW5jZSwgd2hpY2ggDQogICAqIG11
c3QgYWxyZWFkeSBiZSBzdGFydGVkLg0KICAgKiBAc2VlIHN0YXJ0U2VxdWVu
Y2UoKQ0KICAgKi8NCiAgICAvL0Fub3RoZXIgd2F5IG9mIGFkZGluZyBhIHN0
YXRlIHRoYXQncyBwcm9iYWJseSBtb3JlIGludHVpdGl2ZSBmb3IgdGhlDQog
ICAgLy91c2VyLiAgVXNlZnVsIGZvciBwcm9ncmVzc2l2ZSBhZGRpbmcuDQog
ICAgcHVibGljIGJvb2xlYW4gYWRkT2NjdXJyZW5jZShTdHJpbmcgbmV4dF9z
dGF0ZSkNCiAgICB7DQoJaW50IG5ld19zdGF0ZV9sb2MgPSB2ZXJpZnlTdGF0
ZShuZXh0X3N0YXRlKTsNCgkNCglpZiAobmV3X3N0YXRlX2xvYyA8IDApIHJl
dHVybiBmYWxzZTsNCg0KCWFkZE9jY3VycmVuY2UobmV3X3N0YXRlX2xvYyk7
DQoJDQoJcmV0dXJuIHRydWU7DQogICAgfQ0KICAgIA0KDQogIC8qKg0KICAg
KiBAcmV0dXJuIFRoZSBuZXh0IHN0YXRlIGZyb20gdGhlIGdpdmVuIG9uZSwg
ZGV0ZXJtaW5lZCBwcm9iYWJhbGlzdGljYWxseTsgbnVsbCBpZiB0aGUgZ2l2
ZW4gc3RhdGUgaXNuJ3QgdmFsaWQsIGkuZS4gaXQgZG9lc24ndCBleGlzdCwg
b3Igbm8gc3RhdGVzIGNhbiBmb2xsb3cgaXQuICAoQWxsIHByb2JhYmlsaXRp
ZXMgYXJlIDAuKQ0KICAgKi8NCiAgICBwdWJsaWMgU3RyaW5nIGdldE5leHRT
dGF0ZShTdHJpbmcgc3RhdGUpDQogICAgew0KCWludCBwcm9iX3RvdGFsID0g
MDsgLy9TdW0gb2YgYWxsIHByb2JhYmlsaXRpZXMgb2YgcG90ZW50aWFsIHN0
YXRlcw0KCWludCBzdGF0ZV9sb2MgPSAwOw0KCWludCBkaWVfcm9sbDsgLy9S
YW5kb20gIyBmcm9tIDEtPnByb2JfdG90YWwsIHVzZWQgZm9yIGZpbmRpbmcg
bmV4dCBzdGF0ZQ0KCWludCBpOyAvL1llIG9sZGUgbG9vcCB2YXJpYWJsZQ0K
DQoJLy9GaW5kIG91dCB0aGUgc3RhdGUncyBwb3NpdGlvbiBpbiB0aGUgYXJy
YXkNCgkvL0lmIGl0IHdhc24ndCBpbiB0aGUgYXJyYXksIGV4aXQNCglpZiAo
KHN0YXRlX2xvYyA9IHZlcmlmeVN0YXRlKHN0YXRlKSkgPCAwKSByZXR1cm4g
bnVsbDsNCg0KCS8vVG90YWwgdXAgdGhlIHByb2JhYmlsaXRpZXMNCglmb3Ig
KGkgPSAwOyBpIDwgbnVtX3N0YXRlczsgaSsrKQ0KCXsNCgkgICAgcHJvYl90
b3RhbCArPSBwcm9iX3RhYmxlW2ldW3N0YXRlX2xvY107DQoJfQ0KDQoJaWYg
KHByb2JfdG90YWwgPT0gMCkgcmV0dXJuIG51bGw7IC8vbm90aGluZyBjYW4g
Y29tZSBhZnRlciB0aGlzIHN0YXRlDQoJDQoJLy9HZXQgYSByYW5kb20gbnVt
YmVyIHRvIHVzZSBmb3IgZmluZGluZyB0aGUgbmV4dCBzdGF0ZQ0KCS8vIjEi
LCBub3QgIjAiIGlzIG1pbmltdW0sIHNpbmNlIHN0YXRlcyB3aXRoIGEgMCBz
aG91bGRuJ3QgYmUgY2hvc2VuDQoJZGllX3JvbGwgPSAoaW50KShNYXRoLnJh
bmRvbSgpICogKHByb2JfdG90YWwgLSAxKSkgKyAxOw0KICAgDQoJLy9TdGVw
IHRocm91Z2ggdGhlIG1hdHJpeC4gIEtlZXAgYSBydW5uaW5nIHRvdGFsIGFn
YWluLg0KCS8vVGhlIG5leHQgc3RhdGUgaXMgdGhlIGZpcnN0IG9uZSB3aGVy
ZQ0KCS8vZGllX3JvbGwgPD0gc3VtKGN1cnJlbnRfc3RhdGUgKyBhbGxfcHJl
dmlvdXNfc3RhdGVzKQ0KCWZvciAoaSA9IDAsIHByb2JfdG90YWwgPSAwOyBp
IDwgbnVtX3N0YXRlczsgaSsrKQ0KCXsNCgkgICAgcHJvYl90b3RhbCArPSBw
cm9iX3RhYmxlW2ldW3N0YXRlX2xvY107DQoJICAgIGlmIChkaWVfcm9sbCA8
PSBwcm9iX3RvdGFsKSBicmVhazsNCgl9DQoNCglyZXR1cm4gc3RhdGVzW2ld
Ow0KICAgIH0NCg0KICAgIA0KICAvKioNCiAgICogQHJldHVybiBBbiBhcnJh
eSBvZiBzdGF0ZXMsIGdlbmVyYXRlZCBwcm9iYWJhbGlzdGljYWxseSBmcm9t
IGEgcmFuZG9tbHktc2VsZWN0ZWQgc3RhcnQgc3RhdGUNCiAgICogSWYgYSBz
dGF0ZSBpcyBjaG9zZW4gZnJvbSB3aGljaCBubyBvdGhlciBzdGF0ZXMgY2Fu
IGZvbGxvdyAocHJvYmFiaWxpdGllcyBhcmUgYWxsIDApLCB0aGUgc2VxdWVu
Y2UgZW5kcyB0aGVyZSBhbmQgaXMgcmV0dXJuZWQuDQogICAqIEBwYXJhbSBs
ZW5ndGggLSB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZSB0byBiZSBnZW5l
cmF0ZWQNCiAgICogQHBhcmFtIGFzX3N0cmluZyAtIGlmIHRydWUsIHJldHVy
bnMgb25seSBvbmUgU3RyaW5nLCB3aGljaCBpcyB0aGUgY29uY2F0ZW5hdGlv
biBvZiB0aGUgcmV0dXJuZWQgc3RhdGVzLCBzZXBhcmF0ZWQgYnkgdGhlIGdp
dmVuIHNlcGFyYXRvciBzdHJpbmcsIG9yIG5vdGhpbmcgaWYgbnVsbCBpcyBw
YXNzZWQgYXMgdGhlIHNlcGFyYXRvciANCiAgICogQHBhcmFtIHNlcGFyYXRv
ciAtIHRoZSBTdHJpbmcgd2l0aCB3aGljaCB0byBzZXBhcmF0ZSBlYWNoIHJl
dHVybmVkIHN0YXRlIGlmIGFzX3N0cmluZyBpcyBzZXQNCiAgICovDQogICAg
Ly9SZXR1cm5zIGEgYnVuY2ggb2Ygc3RhdGVzLCBpbiB0aGVpciAicHJvcGVy
IG9yZGVyIiwgc3RhcnRpbmcgZnJvbSANCiAgICAvL2EgcmFuZG9tbHktY2hv
c2VuIG9uZS4gIA0KICAgIHB1YmxpYyBTdHJpbmdbXSBnZXRTZXF1ZW5jZShp
bnQgbGVuZ3RoLCBib29sZWFuIGFzX3N0cmluZywgU3RyaW5nIHNlcGFyYXRv
cikNCiAgICB7DQoJU3RyaW5nW10gc2VxID0gbmV3IFN0cmluZ1tsZW5ndGhd
OyAvL1RoZSBzZXF1ZW5jZSB0byByZXR1cm4NCg0KCS8vR2V0IHRoZSBzdGFy
dCBzdGF0ZQ0KCS8vSSBtdWx0LiBzdGF0ZXMubGVuZ3RoIGJ5IDIsIHJhdGhl
ciB0aGFuIHVzZSBhIG1hZ2ljIG51bWJlcg0KCS8vc28gdGhhdCB5b3UncmUg
Z3VhcmFudGVlZCB0aGUgcG9zc2liaWxpdHkgb2YgYSAjIGF0IGxlYXN0IA0K
CS8vYXMgYmlnIGFzIHRoZSBsZW5ndGguDQoJc2VxWzBdID0gc3RhdGVzWyhp
bnQpKE1hdGgucmFuZG9tKCkgKiAoMiAqIHN0YXRlcy5sZW5ndGgpKSAlIHN0
YXRlcy5sZW5ndGhdOw0KDQoJLy9JZiBjYWxsZXIgd2FudHMgaXQgYXMgYSBz
dHJpbmcsIGp1c3QgYXBwZW5kIHRvIHRoZSBmaXJzdCBzdGF0ZSBjaG9zZW4N
CglpZiAoYXNfc3RyaW5nID09IHRydWUpDQoJew0KCSAgICBTdHJpbmcgc3Ry
ID0gc2VxWzBdOw0KCSAgICBmb3IgKGludCBpID0gMTsgaSA8IHNlcS5sZW5n
dGg7IGkrKykNCgkgICAgew0KCQkvL1JlbWVtYmVyIHRoYXQgc3RyIHN0YXJ0
cyB3aXRoIHRoZSB2YWx1ZSBvZiB0aGUgcHJldmlvdXMgc3RhdGUNCgkJc3Ry
ID0gZ2V0TmV4dFN0YXRlKHN0cik7IA0KCQkvL0lmIG51bGwgaGFzIGJlZW4g
cmV0dXJuZWQsIG5vIHN0YXRlcyBjYW4gZm9sbG93LCBzbyBzdG9wDQoJCWlm
IChzdHIgPT0gbnVsbCkgYnJlYWs7DQoJCWVsc2Ugc2VxWzBdICs9IChzZXBh
cmF0b3IgPT0gbnVsbCA/ICIiIDogc2VwYXJhdG9yKSArIHN0cjsNCgkgICAg
fQ0KCX0NCgkNCgllbHNlIC8vRW50ZXIgc3RhdGVzIHNlcGFyYXRlbHkNCgl7
DQoJICAgIGZvciAoaW50IGkgPSAxOyBpIDwgc2VxLmxlbmd0aDsgaSsrKQ0K
CSAgICB7DQoJCXNlcVtpXSA9IGdldE5leHRTdGF0ZShzZXFbaS0xXSk7DQoJ
CS8vSWYgbnVsbCBoYXMgYmVlbiByZXR1cm5lZCwgbm8gc3RhdGVzIGNhbiBm
b2xsb3csIHNvIHN0b3ANCgkJaWYgKHNlcVtpXSA9PSBudWxsKSBicmVhazsN
CgkgICAgfQ0KCX0NCglyZXR1cm4gc2VxOw0KICAgIH0NCg0KDQogIC8qKg0K
ICAgKiBTYW1lIGFzIHByZXZpb3VzIGdldFNlcXVlbmNlLCBidXQgdGFrZXMg
YSBzdGFydCBzdGF0ZQ0KICAgKiBAc2VlIGdldFNlcXVlbmNlKGludCBsZW5n
dGgsIGJvb2xlYW4gYXNfc3RyaW5nLCBTdHJpbmcgc2VwYXJhdG9yKQ0KICAg
Ki8NCiAgICBwdWJsaWMgU3RyaW5nW10gZ2V0U2VxdWVuY2UoU3RyaW5nIHN0
YXJ0LCBpbnQgbGVuZ3RoLCBib29sZWFuIGFzX3N0cmluZywgU3RyaW5nIHNl
cGFyYXRvcikNCiAgICB7DQoJU3RyaW5nW10gc2VxID0gbmV3IFN0cmluZ1ts
ZW5ndGhdOyAvL1RoZSBzZXF1ZW5jZSB0byByZXR1cm4NCg0KCXNlcVswXSA9
IHN0YXJ0Ow0KDQoJLy9JZiBjYWxsZXIgd2FudHMgaXQgYXMgYSBzdHJpbmcs
IGp1c3QgYXBwZW5kIHRvIHRoZSBmaXJzdCBzdGF0ZSBjaG9zZW4NCglpZiAo
YXNfc3RyaW5nID09IHRydWUpDQoJew0KCSAgICBTdHJpbmcgc3RyID0gc2Vx
WzBdOw0KDQoJICAgIGZvciAoaW50IGkgPSAxOyBpIDwgc2VxLmxlbmd0aDsg
aSsrKQ0KCSAgICB7DQoJCS8vUmVtZW1iZXIgdGhhdCBzdHIgc3RhcnRzIHdp
dGggdGhlIHZhbHVlIG9mIHRoZSBwcmV2aW91cyBzdGF0ZQ0KCQlzdHIgPSBn
ZXROZXh0U3RhdGUoc3RyKTsgDQoJCS8vSWYgbnVsbCBoYXMgYmVlbiByZXR1
cm5lZCwgbm8gc3RhdGVzIGNhbiBmb2xsb3csIHNvIHN0b3ANCgkJaWYgKHN0
ciA9PSBudWxsKSBicmVhazsNCgkJZWxzZSBzZXFbMF0gKz0gKHNlcGFyYXRv
ciA9PSBudWxsID8gIiIgOiBzZXBhcmF0b3IpICsgc3RyOw0KCSAgICB9DQoJ
fQ0KCQ0KCWVsc2UgLy9FbnRlciBzdGF0ZXMgc2VwYXJhdGVseQ0KCXsNCgkg
ICAgZm9yIChpbnQgaSA9IDE7IGkgPCBzZXEubGVuZ3RoOyBpKyspDQoJICAg
IHsNCgkJc2VxW2ldID0gZ2V0TmV4dFN0YXRlKHNlcVtpLTFdKTsNCgkJLy9J
ZiBudWxsIGhhcyBiZWVuIHJldHVybmVkLCBubyBzdGF0ZXMgY2FuIGZvbGxv
dywgc28gc3RvcA0KCQlpZiAoc2VxW2ldID09IG51bGwpIGJyZWFrOw0KCSAg
ICB9DQoJfQ0KCXJldHVybiBzZXE7DQogICAgfQ0KCQ0KDQogIC8qKg0KICAg
KiBQcmludHMgdGhlIHRhYmxlIHRvIHN0ZG91dCwgd2l0aCBzb21lIG5pY2Ug
KG5haXZlKSBmb3JtYXR0aW5nIHRvIGdldA0KICAgKiByZWFkYWJsZSByb3dz
IGFuZCBjb2x1bW5zIChsaWtlIHRoZSBvcGVuaW5nIGV4YW1wbGUgaW4gQVND
SUkpDQogICAqLw0KICAgIHB1YmxpYyB2b2lkIHByaW50VGFibGUoKQ0KICAg
IHsNCglpbnQgaTsNCglTdHJpbmcgdGFibGVfcm93ID0gIiI7DQoNCgkvL1By
aW50IHRoZSBzdGF0ZXMgYXMgY29sdW1uIGhlYWRlcnMNCglmb3IgKGkgPSAw
OyBpIDwgbnVtX3N0YXRlczsgaSsrKQ0KCSAgICB0YWJsZV9yb3cgKz0gc3Rh
dGVzW2ldICsgIlx0IjsNCglTeXN0ZW0ub3V0LnByaW50bG4odGFibGVfcm93
KTsNCg0KCS8vUHJpbnQgdGhlIHJvd3Mgb2YgdmFsdWVzLCB3aXRoIGNvcnJl
c3BvbmRpbmcgc3RhdGVzIGZvbGxvd2luZw0KCWZvciAoaSA9IDA7IGkgPCBu
dW1fc3RhdGVzOyBpKyspDQoJew0KCSAgICAvL1JlaW5pdGlhbGl6ZSB0YWJs
ZV9yb3cNCgkgICAgdGFibGVfcm93ID0gIiI7DQoJICAgIA0KCSAgICAvL0dl
dCBhIHN0cmluZyBvZiB0aGUgdmFsdWVzDQoJICAgIGZvciAoaW50IGogPSAw
OyBqIDwgbnVtX3N0YXRlczsgaisrKQ0KCSAgICB7DQoJCXRhYmxlX3JvdyAr
PSBwcm9iX3RhYmxlW2ldW2pdICsgIlx0IjsgDQoJICAgIH0NCgkgICAgDQoJ
ICAgIC8vUHJpbnQgdGhlIHJvdyB3aXRoIHRoZSBzdGF0ZSBsYWJlbCBhbmQg
YSBuZXdsaW5lDQoJICAgIFN5c3RlbS5vdXQucHJpbnRsbih0YWJsZV9yb3cg
KyBzdGF0ZXNbaV0pOw0KCX0NCiAgICB9DQp9DQoJICAgIA0K
---791590007-1638864361-946046517=:24039--