From octave-sources-request at bevo dot che dot wisc dot edu Fri Jan 11 09:36:42 2002 Subject: Re: simplex optimization From: "G.W.M. Vissers" To: Date: Fri, 11 Jan 2002 09:35:53 -0600 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 at docserver dot cac dot washington dot edu for more info. ---1367106628-348044227-1010763106=:2109 Content-Type: TEXT/PLAIN; charset=ISO-8859-1 Content-Transfer-Encoding: 8BIT Hello everybody, Since I couldn't find a minimization function in Octave, I decided to write it myself. The result is attached, a simple Nelder-Mead simplex minimization routine. This is my first programming experience for Octave, so please let me know if you have any comments. Gé Vissers ---1367106628-348044227-1010763106=:2109 Content-Type: TEXT/PLAIN; charset=US-ASCII; name="fminsearch.cc" Content-Transfer-Encoding: BASE64 Content-ID: Content-Description: Content-Disposition: attachment; filename="fminsearch.cc" I2luY2x1ZGUgPG9jdC5oPg0KI2luY2x1ZGUgPHBhcnNlLmg+DQojaW5jbHVk ZSA8cGFnZXIuaD4NCg0KI2RlZmluZSBERUZBVUxUX01BWElUICA1MDAwDQoj ZGVmaW5lIERFRkFVTFRfRlVOVE9MIDFlLTQNCiNkZWZpbmUgREVGQVVMVF9Y VE9MICAgMWUtNA0KI2RlZmluZSBERUZBVUxUX0xPRyAgICAwDQoNCiNkZWZp bmUgVElOWSAgICAgICAgICAgMWUtMTYNCg0KI2RlZmluZSBHRVRfWFNVTVwN CiAgZm9yICh4c3VtID0gWC5jb2x1bW4oMCksIGl2ZWMgPSAxOyBpdmVjIDw9 IGRpbTsgaXZlYysrKVwNCiAgICB4c3VtICs9IFguY29sdW1uIChpdmVjKTsN CiNkZWZpbmUgUkVGTEVDVChmKVwNCiAgZmFjMSA9ICgxLShmKSkvZGltO1wN CiAgZmFjMiA9IGZhYzEgLSAoZik7XA0KICB4ICAgID0gZmFjMSAqIHhzdW0g LSBmYWMyICogWC5jb2x1bW4gKGl3b3JzdCk7ICANCiNkZWZpbmUgQ0FMQ19G KGYseCxzKVwNCiAgcmVzICA9IGZldmFsIChmbmFtZSwgb2N0YXZlX3ZhbHVl X2xpc3QgKHgpLCAxKTtcDQogIG5pdCsrO1wNCiAgaWYgKCFjaGVja19yZXMg KHJlcykpIHJldHVybiBvY3RhdmVfdmFsdWVfbGlzdCAoKTtcDQogIGYgICAg PSByZXMoMCkuZG91YmxlX3ZhbHVlICgpO1wNCiAgaWYgKGxvZyA+IDApIHtc DQogICAgbWVzc2FnZSAoMCwgIiVkXHQlZlx0JXMiLCBuaXQsIGYsIHMpO1wN CiAgICBpZiAobG9nID4gMSkgb2N0YXZlX3ZhbHVlIChYKS5wcmludCAob2N0 YXZlX3N0ZG91dCk7XA0KICB9DQoNCmJvb2wgY2hlY2tfYXJncyAob2N0YXZl X3ZhbHVlX2xpc3QgY29uc3QgJmFyZ3MsIHN0cmluZyAqZm5hbWUsIA0KICAg ICAgICAgICAgICAgICBDb2x1bW5WZWN0b3IgKngwLCBpbnQgKm1heGl0LCBk b3VibGUgKmZ1bnRvbCwgZG91YmxlICp4dG9sLA0KICAgICAgICAgICAgICAg ICBpbnQqIGxvZykgew0KICBpbnQgbmFyZ2luID0gYXJncy5sZW5ndGggKCk7 DQogIA0KICBpZiAobmFyZ2luIDwgMikgew0KICAgIHVzYWdlICgiZm1pbnNl YXJjaCAoZm5hbWUsIHgwIFssIG9wdHNdKSIpOw0KICAgIHJldHVybiBmYWxz ZTsNCiAgfQ0KICANCiAgaWYgKCFhcmdzKDApLmlzX3N0cmluZyAoKSkgew0K ICAgIGVycm9yICgiZXhwZWN0aW5nIHN0cmluZyBmb3IgZnVuY3Rpb24gbmFt ZSAoYXJnIDEpIik7DQogICAgcmV0dXJuIGZhbHNlOw0KICB9DQogICpmbmFt ZSA9IGFyZ3MoMCkuc3RyaW5nX3ZhbHVlICgpOw0KICANCiAgaWYgKCFhcmdz KDEpLmlzX3JlYWxfdHlwZSAoKSkgew0KICAgIGVycm9yICgiV2hvb3BzISBD dXJyZW50bHkgb25seSBpbXBsZW1lbnRlZCBmb3IgcmVhbCBzZWFyY2hlcyEh Iik7DQogICAgcmV0dXJuIGZhbHNlOw0KICB9DQoNCiAgaWYgKGFyZ3MoMSku aXNfc2NhbGFyX3R5cGUgKCkpIHsNCiAgICAqeDAgPSBDb2x1bW5WZWN0b3Ig KDEsIGFyZ3MoMSkuZG91YmxlX3ZhbHVlICgpKTsNCiAgfSBlbHNlIGlmIChh cmdzKDEpLmlzX21hdHJpeF90eXBlICgpDQogICAgICAgICAgICAmJiBhcmdz KDEpLmNvbHVtbnMgKCkgPT0gMSkgew0KICAgICp4MCA9IGFyZ3MoMSkubWF0 cml4X3ZhbHVlICgpLmNvbHVtbiAoMCk7DQogIH0gZWxzZSB7DQogICAgZXJy b3IgKCJleHBlY3RpbmcgY29sdW1uIHZlY3RvciBmb3IgaW5pdGlhbCBwb2lu dCAoYXJnIDIpIik7DQogICAgcmV0dXJuIGZhbHNlOw0KICB9ICANCiAgDQog ICptYXhpdCAgPSBERUZBVUxUX01BWElUOw0KICAqZnVudG9sID0gREVGQVVM VF9GVU5UT0w7DQogICp4dG9sICAgPSBERUZBVUxUX1hUT0w7DQogICpsb2cg ICAgPSBERUZBVUxUX0xPRzsNCiAgaWYgKG5hcmdpbiA+IDIpIHsNCiAgICBp ZiAoIWFyZ3MoMikuaXNfbWFwICgpKSB7DQogICAgICBlcnJvciAoImV4cGVj dGluZyBzdHJ1Y3R1cmUgZm9yIG9wdGlvbnMgKGFyZyAzKSIpOw0KICAgICAg cmV0dXJuIGZhbHNlOw0KICAgIH0NCiAgICANCiAgICBvY3RhdmVfdmFsdWUg dG1wID0gYXJncygyKS5kb19zdHJ1Y3RfZWx0X2luZGV4X29wICgibWF4aXQi LCB0cnVlKTsNCiAgICBpZiAodG1wLmlzX2RlZmluZWQgKCkpIHsNCiAgICAg IGlmICghdG1wLmlzX3NjYWxhcl90eXBlICgpDQogICAgICAgICB8fCAhdG1w LmlzX3JlYWxfdHlwZSAoKQ0KICAgICAgICAgfHwgZmxvb3IgKHRtcC5kb3Vi bGVfdmFsdWUgKCkpICE9IHRtcC5kb3VibGVfdmFsdWUgKCkNCiAgICAgICAg IHx8IHRtcC5kb3VibGVfdmFsdWUgKCkgPD0gMCkgew0KICAgICAgICBlcnJv ciAoImV4cGVjdGluZyBwb3NpdGl2ZSBpbnRlZ2VyIGZvciBtYXhpbXVtIG5y LiBvZiBpdGVyYXRpb25zIik7DQogICAgICAgIHJldHVybiBmYWxzZTsNCiAg ICAgIH0NCiAgICAgICptYXhpdCA9IGludCAodG1wLmRvdWJsZV92YWx1ZSAo KSk7DQogICAgfQ0KDQogICAgdG1wID0gYXJncygyKS5kb19zdHJ1Y3RfZWx0 X2luZGV4X29wICgiZnVudG9sIiwgdHJ1ZSk7DQogICAgaWYgKHRtcC5pc19k ZWZpbmVkICgpKSB7DQogICAgICBpZiAoIXRtcC5pc19zY2FsYXJfdHlwZSAo KQ0KICAgICAgICAgfHwgIXRtcC5pc19yZWFsX3R5cGUgKCkNCiAgICAgICAg IHx8IHRtcC5kb3VibGVfdmFsdWUgKCkgPD0gMCkgew0KICAgICAgICBlcnJv ciAoImV4cGVjdGluZyBwb3NpdGl2ZSByZWFsIGZvciB0b2xlcmFuY2UgaW4g ZnVuY3Rpb24gdmFsdWUiKTsNCiAgICAgICAgcmV0dXJuIGZhbHNlOw0KICAg ICAgfQ0KICAgICAgKmZ1bnRvbCA9IHRtcC5kb3VibGVfdmFsdWUgKCk7DQog ICAgfQ0KDQogICAgdG1wID0gYXJncygyKS5kb19zdHJ1Y3RfZWx0X2luZGV4 X29wICgieHRvbCIsIHRydWUpOw0KICAgIGlmICh0bXAuaXNfZGVmaW5lZCAo KSkgew0KICAgICAgaWYgKCF0bXAuaXNfc2NhbGFyX3R5cGUgKCkNCiAgICAg ICAgIHx8ICF0bXAuaXNfcmVhbF90eXBlICgpDQogICAgICAgICB8fCB0bXAu ZG91YmxlX3ZhbHVlICgpIDw9IDApIHsNCiAgICAgICAgZXJyb3IgKCJleHBl Y3RpbmcgcG9zaXRpdmUgcmVhbCBmb3IgdG9sZXJhbmNlIGluIHBvc2l0aW9u Iik7DQogICAgICAgIHJldHVybiBmYWxzZTsNCiAgICAgIH0NCiAgICAgICp4 dG9sID0gdG1wLmRvdWJsZV92YWx1ZSAoKTsNCiAgICB9DQoNCiAgICB0bXAg PSBhcmdzKDIpLmRvX3N0cnVjdF9lbHRfaW5kZXhfb3AgKCJsb2ciLCB0cnVl KTsNCiAgICBpZiAodG1wLmlzX2RlZmluZWQgKCkpIHsNCiAgICAgIGlmICh0 bXAuaXNfc3RyaW5nICgpKSB7DQogICAgICAgIHN0cmluZyBzdHJsb2cgPSB0 bXAuc3RyaW5nX3ZhbHVlICgpOw0KICAgICAgICBpZiAoc3RybG9nID09ICJu b25lIiB8fCBzdHJsb2cgPT0gIm9mZiIpIHsNCiAgICAgICAgICAqbG9nID0g MDsNCiAgICAgICAgfSBlbHNlIGlmIChzdHJsb2cgPT0gIml0ZXIiIHx8IHN0 cmxvZyA9PSAib24iKSB7DQogICAgICAgICAgKmxvZyA9IDE7DQogICAgICAg IH0gZWxzZSBpZiAoc3RybG9nID09ICJkZWJ1ZyIpIHsNCiAgICAgICAgICAq bG9nID0gMjsNCiAgICAgICAgfSBlbHNlIHsNCiAgICAgICAgICB3YXJuaW5n ICgiaW52YWxpZCBsb2dnaW5nIG9wdGlvbiwgcmV2ZXJ0aW5nIHRvIGRlZmF1 bHQiKTsNCiAgICAgICAgfQ0KICAgICAgfSBlbHNlIGlmICh0bXAuaXNfc2Nh bGFyX3R5cGUgKCkpIHsNCiAgICAgICAgaWYgKHRtcC5pc19yZWFsX3R5cGUg KCkNCiAgICAgICAgICAgICYmIGZsb29yICh0bXAuZG91YmxlX3ZhbHVlICgp KSA9PSB0bXAuZG91YmxlX3ZhbHVlICgpKSB7DQogICAgICAgICAgKmxvZyA9 IGludCAodG1wLmRvdWJsZV92YWx1ZSAoKSk7DQogICAgICAgICAgaWYgKCps b2cgPCAwIHx8ICpsb2cgPiAyKSB7DQogICAgICAgICAgICB3YXJuaW5nICgi aW52YWxpZCBsb2dnaW5nIG9wdGlvbiwgcmV2ZXJ0aW5nIHRvIGRlZmF1bHQi KTsNCiAgICAgICAgICAgICpsb2cgPSBERUZBVUxUX0xPRzsNCiAgICAgICAg ICB9DQogICAgICAgIH0gZWxzZSBpZiAodG1wLmlzX2Jvb2xfdHlwZSAoKSkg ew0KICAgICAgICAgICpsb2cgPSB0bXAuYm9vbF92YWx1ZSAoKSA/IDEgOiAw Ow0KICAgICAgICB9IGVsc2Ugew0KICAgICAgICAgIHdhcm5pbmcgKCJpbnZh bGlkIGxvZ2dpbmcgb3B0aW9uLCByZXZlcnRpbmcgdG8gZGVmYXVsdCIpOw0K ICAgICAgICB9DQogICAgICB9IGVsc2Ugew0KICAgICAgICB3YXJuaW5nICgi aW52YWxpZCBsb2dnaW5nIG9wdGlvbiwgcmV2ZXJ0aW5nIHRvIGRlZmF1bHQi KTsNCiAgICAgIH0NCiAgICB9DQogIH0gIA0KICAgIA0KICByZXR1cm4gdHJ1 ZTsNCn0NCg0KYm9vbCBjaGVja19yZXMgKG9jdGF2ZV92YWx1ZV9saXN0IHJl cykgew0KICBpZiAocmVzLmxlbmd0aCAoKSA8IDEpIHsNCiAgICBlcnJvciAo InNvbWV0aGluZyB3ZW50IHdyb25nIGluIGZ1bmN0aW9uIGNhbGwiKTsNCiAg ICByZXR1cm4gZmFsc2U7DQogIH0NCg0KICBpZiAoIXJlcygwKS5pc19yZWFs X3R5cGUgKCkNCiAgICAgfHwgIXJlcygwKS5pc19zY2FsYXJfdHlwZSAoKSkg ew0KICAgIGVycm9yICgiZXhwZWN0aW5nIHJlYWwgc2NhbGFyIHJlc3VsdCBm cm9tIGZ1bmN0aW9uIGNhbGwiKTsNCiAgICByZXR1cm4gZmFsc2U7DQogIH0N CiAgDQogIHJldHVybiB0cnVlOw0KfQ0KDQoNCkRFRlVOX0RMRChmbWluc2Vh cmNoLCBhcmdzLCBuYXJnb3V0LCANCiAiLSotIHRleGluZm8gLSotXG5cDQog QGRlZnR5cGVmbiB7TG9hZGFibGUgRnVuY3Rpb259IHtAdmFye3h9ID19IFwN CmZtaW5zZWFyY2ggKEB2YXJ7Zm5hbWV9LCBAdmFye3gwfSlcblwNCkBkZWZ0 eXBlZm54IHtMb2FkYWJsZSBGdW5jdGlvbn0ge1tAdmFye3h9LCBAdmFye2Z4 fV0gPX0gXA0KZm1pbnNlYXJjaCAoQHZhcntmbmFtZX0sIEB2YXJ7eDB9KVxu XA0KQGRlZnR5cGVmbngge0xvYWRhYmxlIEZ1bmN0aW9ufSB7W0B2YXJ7eH0s IEB2YXJ7ZngsIEB2YXJ7bml0fX1dID19IFwNCmZtaW5zZWFyY2ggKEB2YXJ7 Zm5hbWV9LCBAdmFye3gwfSlcblwNCmZpbmRzIGEgbG9jYWwgbWluaW11bSBv ZiBmdW5jdGlvbiBAdmFye2ZuYW1lfSBieSBtZWFucyBvZiBOZWxkZXItTWVh ZCBzaW1wbGV4IFwNCm1pbmltaXphdGlvbiwgc3RhcnRpbmcgZnJvbSBpbml0 aWFsIHBvaW50IEB2YXJ7eDB9LiBAdmFye2Z1bn0gc2hvdWxkIGJlIGEgXA0K ZnVuY3Rpb24gdGhhdCBnaXZlbiBhIGNvbHVtbiB2ZWN0b3IgcmV0dXJucyBh IHJlYWwgdmFsdWUuIFRoZSBvdXRwdXQgY29uc2lzdHMgXA0Kb2YgdGhlIG1p bmltdW0gQHZhcnt4fSwgYW5kIG9wdGlvbmFsbHkgdGhlIGZ1bmN0aW9uIHZh bHVlIGluIHRoZSBtaW5pbXVtLCBcDQpAdmFye2Z4fSwgYW5kIHRoZSBudW1i ZXIgb2YgZnVuY3Rpb24gZXZhbHVhdGlvbnMgcGVyZm9ybWVkLCBAdmFye25p dH0uXG5cDQpAZGVmdHlwZWZueCB7TG9hZGFibGUgRnVuY3Rpb259IHtAdmFy e3h9ID19IFwNCmZtaW5zZWFyY2ggKEB2YXJ7Zm5hbWV9LCBAdmFye3gwfSwg QHZhcntvcHRzfSlcblwNCkBkZWZ0eXBlZm54IHtMb2FkYWJsZSBGdW5jdGlv bn0ge1tAdmFye3h9LCBAdmFye2Z4fV0gPX0gXA0KZm1pbnNlYXJjaCAoQHZh cntmbmFtZX0sIEB2YXJ7eDB9LCBAdmFye29wdHN9KVxuXA0KQGRlZnR5cGVm bngge0xvYWRhYmxlIEZ1bmN0aW9ufSB7W0B2YXJ7eH0sIEB2YXJ7Znh9LCBA dmFye25pdH1dID19IFwNCmZtaW5zZWFyY2ggKEB2YXJ7Zm5hbWV9LCBAdmFy e3gwfSwgQHZhcntvcHRzfSlcblwNCmRvZXMgdGhlIHNhbWUsIGJ1dCByZXBs YWNlcyB0aGUgZGVmYXVsdCBwYXJhbWV0ZXJzIHdpdGggdGhlIG9uZXMgZm91 bmQgaW4gdGhlIFwNCnN0cnVjdHVyZSBAdmFye29wdHN9LiBWYWxpZCBwYXJh bWV0ZXJzIGFyZTpcblwNCkBpdGVtaXplXG5cDQpAaXRlbSBtYXhpdDogYSBw b3NpdGl2ZSBpbnRlZ2VyIGluZGljYXRpbmcgdGhlIG1heGltdW0gbnVtYmVy IG9mIGZ1bmN0aW9uIFwNCmV2YWx1YXRpb25zIHRvIGJlIG1hZGUuIEJ5IGRl ZmF1bHQsIG1heGl0ID0gNTAwMC5cDQpAaXRlbSB0b2xmdW46IGEgcG9zaXRp dmUgcmVhbCBudW1iZXIuIFRoZSBmdW5jdGlvbiB2YWx1ZSBpbiB0aGUgbWlu aW11bSBsaWVzIFwNCndpdGhpbiB0b2xmdW4gZnJvbSB0aGUgcmVhbCBtaW5p bWFsIHZhbHVlLiBCeSBkZWZhdWx0LCB0b2xmdW4gPSAxZS00LlwNCkBpdGVt IHRvbHg6IGEgcG9zaXRpdmUgcmVhbCBudW1iZXIuIFRoZSBtaW5pbXVtIGZv dW5kIGxpZXMgd2l0aGluIGEgZGlzdGFuY2UgXA0KdG9seCBmcm9tIHRoZSBy ZWFsIG1pbmltdW0uIEJ5IGRlZmF1bHQsIHRvbHggPSAxZS00LlwNCkBpdGVt IGxvZzogYSBwYXJhbWV0ZXIgdGhhdCBkZXNjcmliZXMgdGhlIGxvZ2dpbmcg dG8gYmUgZG9uZS4gV2hlbiBsb2cgaXMgXA0KMCwgXCJub25lXCIsIFwib2Zm XCIsIG9yIGZhbHNlLCBubyBtZXNzYWdlcyBhcmUgZ2l2ZW4gZHVyaW5nIGV4 ZWN1dGlvbiBvZiBcDQpmbWluc2VhcmNoLiBXaGVuIGxvZyBpcyAxLCBcIml0 ZXJcIiwgXCJvblwiLCBvciB0cnVlLCBhIGxpbmUgaXMgcHJpbnRlZCBmb3Ig XA0KZWFjaCBmdW5jdGlvbiBldmFsdWF0aW9uLCB3aXRoIHRoZSByZXN1bHQg b2YgdGhlIGZ1bmN0aW9uIGNhbGwgYW5kIHRoZSB0eXBlIG9mIFwNCmFjdGlv biBwZXJmb3JtZWQuIFdoZW4gbG9nIGlzIDIgb3IgXCJkZWJ1Z1wiLCBhbHNv IHRoZSBjdXJyZW50IHNpbXBsZXggaXMgXA0KcHJpbnRlZCBhZnRlciBlYWNo IGZ1bmN0aW9uIGV2YWx1YXRpb24uIEJ5IGRlZmF1bHQsIG5vIGxvZ2dpbmcg aXMgZG9uZS5cDQpAZW5kIGl0ZW1pemVcblwNCkBlbmQgZGVmdHlwZWZuIikg ew0KDQogIGludCBtYXhpdCwgbG9nOw0KICBzdHJpbmcgZm5hbWU7DQogIENv bHVtblZlY3RvciB4MDsNCiAgZG91YmxlIGZ1bnRvbCwgeHRvbDsNCg0KICBp ZiAoIWNoZWNrX2FyZ3MgKGFyZ3MsICZmbmFtZSwgJngwLCAmbWF4aXQsICZm dW50b2wsICZ4dG9sLCAmbG9nKSkgDQogICAgcmV0dXJuIG9jdGF2ZV92YWx1 ZV9saXN0ICgpOw0KICANCiAgaW50IGRpbSA9IHgwLmxlbmd0aCAoKSwgaXZl Yywgbml0ID0gMDsNCiAgTWF0cml4IFggKGRpbSwgZGltKzEpOw0KICBDb2x1 bW5WZWN0b3IgeCwgZlggKGRpbSsxKTsNCiAgb2N0YXZlX3ZhbHVlX2xpc3Qg cmVzOw0KICANCiAgLy8gaWYgbG9nZ2luZyBpcyBvbiwgcHJpbnQgYSBoZWFk ZXINCiAgaWYgKGxvZyA+IDApIHsNCiAgICBtZXNzYWdlICgwLCAiY291bnRc dGZ1bmN0aW9uIHZhbHVlXHRzdGVwIik7DQogICAgbWVzc2FnZSAoMCwgIi0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSIpOw0KICB9DQogIA0K ICAvLyBzZXQgdXAgYSBzaW1wbGV4DQogIFguaW5zZXJ0ICh4MCwgMCwgMCk7 DQogIENBTENfRihmWCgwKSx4MCwiaW5pdGlhbCIpOw0KICBmb3IgKGl2ZWMg PSAwOyBpdmVjIDwgZGltOyBpdmVjKyspIHsNCiAgICB4ID0geDA7DQogICAg aWYgKHggKGl2ZWMpID09IDAuMCkgew0KICAgICAgeChpdmVjKSA9IDAuMDAw MjU7DQogICAgfSBlbHNlIHsNCiAgICAgIHgoaXZlYykgKj0gMS4wNTsNCiAg ICB9DQogICAgWC5pbnNlcnQgKHgsIDAsIGl2ZWMrMSk7DQogICAgQ0FMQ19G KGZYKGl2ZWMrMSkseCwiaW5pdGlhbCIpOw0KICB9DQogIA0KICBpbnQgaXdv cnN0ID0gZlgoMSk+ZlgoMCkgPyAxIDogMCwgaW53b3JzdCA9IDEgLSBpd29y c3QsIGliZXN0ID0gaW53b3JzdDsNCiAgZG91YmxlIGZhYzEsIGZhYzIsIGZ4 Ow0KICBDb2x1bW5WZWN0b3IgeHN1bTsNCiAgDQogIEdFVF9YU1VNDQogIHdo aWxlICh0cnVlKSB7DQogICAgLy8gZmluZCBiZXN0LCB3b3JzdCBhbmQgbmV4 dC13b3JzdCBwb2ludHMNCiAgICBmb3IgKGl2ZWMgPSAwOyBpdmVjIDw9IGRp bTsgaXZlYysrKSB7DQogICAgICBpZiAoZlgoaXZlYykgPCBmWChpYmVzdCkp IHsNCiAgICAgICAgaWJlc3QgPSBpdmVjOw0KICAgICAgfSBlbHNlIGlmIChm WChpdmVjKSA+PSBmWChpd29yc3QpKSB7DQogICAgICAgIGlud29yc3QgPSBp d29yc3Q7DQogICAgICAgIGl3b3JzdCA9IGl2ZWM7DQogICAgICB9IGVsc2Ug aWYgKGZYKGl2ZWMpID49IGZYKGlud29yc3QpKSB7DQogICAgICAgIGlud29y c3QgPSBpdmVjOw0KICAgICAgfQ0KICAgIH0NCiAgICANCiAgICAvLyBjaGVj ayB3aGV0aGVyIGZ1bmN0aW9uIHZhbHVlIGlzIGNvbnZlcmdlZA0KICAgIGlm IChmYWJzIChmWChpd29yc3QpIC0gZlgoaWJlc3QpKSA8IGZ1bnRvbCkgew0K ICAgICAgLy8gY2hlY2sgd2hldGhlciBzaW1wbGV4IGRpYW1ldGVyIGlzIGNv bnZlcmdlZA0KICAgICAgaWYgKChYLmNvbHVtbiAoaXdvcnN0KSAtIFguY29s dW1uIChpYmVzdCkpLm1heCAoKSA8IHh0b2wNCiAgICAgICAgICYmIChYLmNv bHVtbiAoaXdvcnN0KSAtIFguY29sdW1uIChpYmVzdCkpLm1pbiAoKSA+IC14 dG9sKSBicmVhazsNCiAgICB9DQogICAgDQogICAgLy8gY2hlY2sgbnIgb2Yg aXRlcmF0aW9ucw0KICAgIGlmIChuaXQgPiBtYXhpdCkgew0KICAgICAgZXJy b3IgKCJtYXhpbXVtIG51bWJlciBvZiBpdGVyYXRpb25zIGV4Y2VlZGVkIik7 DQogICAgICBicmVhazsNCiAgICB9DQogDQogICAgUkVGTEVDVCgtMS4wKQ0K ICAgIENBTENfRihmeCx4LCJyZWZsZWN0IikNCiAgICBpZiAoZnggPCBmWChp d29yc3QpKSB7DQogICAgICBmWChpd29yc3QpID0gZng7DQogICAgICB4c3Vt ICs9IHggLSBYLmNvbHVtbiAoaXdvcnN0KTsNCiAgICAgIFguaW5zZXJ0ICh4 LCAwLCBpd29yc3QpOw0KICAgIH0NCiAgICBpZiAoZnggPCBmWCAoaWJlc3Qp KSB7DQogICAgICAvLyByZWZsZWN0ZWQgcmVzdWx0IGlzIGJldHRlciB0aGVu IGN1cnJlbnQgYmVzdCwgc28gdHJ5IHRvIGV4cGFuZCBpbiANCiAgICAgIC8v IHRoYXQgZGlyZWN0aW9uDQogICAgICBSRUZMRUNUKDIuMCkNCiAgICAgIENB TENfRihmeCx4LCJleHBhbmQiKQ0KICAgICAgaWYgKGZ4IDwgZlgoaXdvcnN0 KSkgew0KICAgICAgICBmWChpd29yc3QpID0gZng7DQogICAgICAgIHhzdW0g Kz0geCAtIFguY29sdW1uIChpd29yc3QpOw0KICAgICAgICBYLmluc2VydCAo eCwgMCwgaXdvcnN0KTsNCiAgICAgIH0NCiAgICB9IGVsc2UgaWYgKGZ4ID49 IGZYIChpbndvcnN0KSkgew0KICAgICAgLy8gcmVmbGVjdGVkIHBvaW50IGlz IHdvcnNlIHRoYW4gY3VycmVudCBuZXh0LXdvcnN0LCBzbyB0cnkgdG8gY29u dHJhY3QNCiAgICAgIC8vIGluIHRoYXQgZGlyZWN0aW9uDQogICAgICBSRUZM RUNUKDAuNSkNCiAgICAgIENBTENfRihmeCx4LCJjb250cmFjdCIpOw0KICAg ICAgaWYgKGZ4IDwgZlggKGl3b3JzdCkpIHsNCiAgICAgICAgZlgoaXdvcnN0 KSA9IGZ4Ow0KICAgICAgICB4c3VtICs9IHggLSBYLmNvbHVtbiAoaXdvcnN0 KTsNCiAgICAgICAgWC5pbnNlcnQgKHgsIDAsIGl3b3JzdCk7DQogICAgICB9 IGVsc2Ugew0KICAgICAgICAvLyBTdGlsbCB0b28gaGlnaCwgc28gdGhhdCBp cyBub3QgYSB2ZXJ5IGdvb2Qgc2VhcmNoIGRpcmVjdGlvbi4gDQogICAgICAg IC8vIENvbnRyYWN0IGFyb3VuZCBiZXN0IHBvaW50IHNvIGZhci4NCiAgICAg ICAgZm9yIChpdmVjID0gMDsgaXZlYyA8PSBkaW07IGl2ZWMrKykgew0KICAg ICAgICAgIGlmIChpdmVjICE9IGliZXN0KSB7DQogICAgICAgICAgICB4ID0g MC41ICogKFguY29sdW1uIChpdmVjKSArIFguY29sdW1uIChpYmVzdCkpOw0K ICAgICAgICAgICAgWC5pbnNlcnQgKHgsIGl2ZWMsIDApOw0KICAgICAgICAg ICAgQ0FMQ19GKGZYKGl2ZWMpLHgsImNvbnRyYWN0IHJvdW5kIGJlc3QiKTsN CiAgICAgICAgICB9DQogICAgICAgIH0NCiAgICAgIH0NCiAgICB9IGVsc2Ug ew0KICAgICAgLy8gQ3VycmVudCByZWZsZWN0aW9uIGlzIGJldHdlZW4gd29y c3QgYW5kIG5leHQgd29yc3QsIHNvIG5vdGhpbmcgbGVmdA0KICAgICAgLy8g dG8gZG8uDQogICAgICBHRVRfWFNVTQ0KICAgIH0NCiAgfQ0KIA0KICByZXMg PSBvY3RhdmVfdmFsdWVfbGlzdCAoWC5jb2x1bW4gKGliZXN0KSk7DQogIGlm IChuYXJnb3V0ID4gMSkgew0KICAgIHJlcy5hcHBlbmQgKG9jdGF2ZV92YWx1 ZSAoZlggKGliZXN0KSkpOw0KICAgIGlmIChuYXJnb3V0ID4gMikgew0KICAg ICAgcmVzLmFwcGVuZCAob2N0YXZlX3ZhbHVlIChkb3VibGUgKG5pdCkpKTsN CiAgICB9DQogIH0NCiAgDQogIHJldHVybiByZXM7DQp9DQo= ---1367106628-348044227-1010763106=:2109--