JamCoders

💾 Download
In [ ]:
%config InteractiveShell.ast_node_interactivity="none"
%pip install networkx
%pip install matplotlib
%pip install pygraphviz
import networkx as nx
import warnings
import base64
warnings.simplefilter(action='ignore', category=FutureWarning)

def f(globals, locals):
    import base64
    CODE = (
        "ZGVmIG1ha2VfcHJpbnRfbG9jYWxzKCk6IAogICAgIyBJbiBhIGZ1bmN0aW9uIHRvIHByZXZlbnQgbG9jYWxzIGFuZCBpbXBvcnRzIGZyb20gbGVha2luZy4KICAgIGdsb2JhbCBtYWtlX3ByaW50X2xvY2FscwogICAgZGVsIG1ha2VfcHJpbnRfbG9jYWxzICAjIE9ubHkgcnVuIHRoaXMgZnVuY3Rpb24gb25jZS4KCiAgICBpbXBvcnQgSVB5dGhvbgogICAgaW1wb3J0IGFzdAogICAgaW1wb3J0IGluc3BlY3QKCiAgICBjbGFzcyBWaXNpdG9yKGFzdC5Ob2RlVmlzaXRvcik6CiAgICAgICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICAgICBzZWxmLnZhcmlhYmxlcyA9IHNldCgpCiAgICAgICAgZGVmIHZpc2l0X05hbWUoc2VsZiwgbmFtZSk6CiAgICAgICAgICAgIHNlbGYudmFyaWFibGVzLmFkZChuYW1lLmlkKQogICAgICAgICMgVE9ETzogUG9zc2libHkgZGV0ZWN0IHdoZXRoZXIgdmFyaWFibGVzIGFyZSBhc3NpZ25lZCB0by4KCiAgICBBTExPV19UWVBFUyA9IFtpbnQsIGZsb2F0LCBzdHIsIGJvb2wsIGxpc3QsIGRpY3QsIHR1cGxlLCByYW5nZV0KICAgIGRlZiBmaWx0ZXJfdmFyaWFibGVzKHZhcmlhYmxlcywgbG9jYWxzKToKICAgICAgICBmb3IgdiBpbiB2YXJpYWJsZXM6CiAgICAgICAgICAgIGlmIHYgaW4gbG9jYWxzIGFuZCB0eXBlKGxvY2Fsc1t2XSkgaW4gQUxMT1dfVFlQRVM6CiAgICAgICAgICAgICAgICB5aWVsZCB2CiAgCiAgICAjIFVuZm9ydHVuYXRlbHksIHRoZXJlIGRvZXNuJ3Qgc2VlbSB0byBiZSBhIHN1cHBvcnRlZCB3YXkgb2YgZ2V0dGluZwogICAgIyB0aGUgY3VycmVudCBjZWxsJ3MgY29kZSB2aWEgdGhlIHB1YmxpYyBJUHl0aG9uIEFQSXMuIEhvd2V2ZXIsIGJlY2F1c2UKICAgICMgd2UgYXJlIGdldHRpbmcgY2FsbGVkIGZyb20gSVB5dGhvbiBpdHNlbGYgYW5kIHdlIGFyZSBhbHJlYWR5IGluc3BlY3RpbmcKICAgICMgdGhlIHN0YWNrdHJhY2UsIHdlIG1pZ2h0IGFzIHdlbGwganVzdCBwZWVrIGludG8gaXRzIGZyYW1lLi4uCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYgogICAgICAgIGRlZiBnZXRfYXN0KGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGFzdC5Nb2R1bGUoZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZWxpc3QiXSkKICAgICAgICBkZWYgZmluZF9sb2NhbHMoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9sb2NhbHMKICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2NvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKCiAgICBlbGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjguNC4wIjoKICAgICAgICAjIGxhYiBjb21wdXRlcnMKICAgICAgICBkZWYgZ2V0X2FzdChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhc3QuTW9kdWxlKGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGVsaXN0Il0pCiAgICAgICAgZGVmIGZpbmRfbG9jYWxzKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfbG9jYWxzCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9jb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICBlbHNlOgogICAgICAgIHByaW50KGYicHJpbnRfbG9jYWxzKCkgbm90IHN1cHBvcnRlZCBvbiBJUHl0aG9uIHZlcnNpb24ge0lQeXRob24uX192ZXJzaW9uX199IikKCiAgICBkZWYgZ2V0X2NlbGxfbmFtZXMoZnJhbWUpOgogICAgICAgIHRyZWUgPSBnZXRfYXN0KGZyYW1lKQogICAgICAgIHZpc2l0b3IgPSBWaXNpdG9yKCkKICAgICAgICB2aXNpdG9yLnZpc2l0KHRyZWUpCiAgICAgICAgcmV0dXJuIGZpbHRlcl92YXJpYWJsZXModmlzaXRvci52YXJpYWJsZXMsIGZyYW1lLmZfbG9jYWxzKQoKICAgIGRlZiBmaW5kX3doaWNoKGZyYW1lKToKICAgICAgICAjIEZyYW1lIGlzIHRoZSBmcmFtZSB3aG9zZSBsb2NhbHMgd2UgYXJlIGludGVyZXN0ZWQgaW4gcHJpbnRpbmcuCiAgICAgICAgaWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgIyBUaGUgcGFyZW50IGZyYW1lIG9mIHRoZSBpbnRlcmVzdGVkIGZyYW1lIGlzIGEgbW9kdWxlLCBtb3N0IGxpa2VseQogICAgICAgICAgICAjICJpbnRlcmFjdGl2ZXNoZWxsIi4gVGhpcyBtZWFucyB3ZSBhcmUgaW4gdGhlIGdsb2JhbCBzY29wZSwgc2luY2UKICAgICAgICAgICAgIyBvbmx5IHRoZSBnbG9iYWwgc2NvcGUgc2hvdWxkIGJlIGRpcmVjdGx5IHJ1biBieSB0aGUgaW50ZXJhY3RpdmUgc2hlbGwuCiAgICAgICAgICAgIHJldHVybiBzZXQoZ2V0X2NlbGxfbmFtZXMoZnJhbWUpKQogICAgICAgICMgVGhlIHBhcmVudCBmcmFtZSBpcyBub3QgYSBtb2R1bGUsIHNvIHdlIGFyZSBpbiBhIGxvY2FsIHNjb3BlLgogICAgICAgIHJldHVybiBzZXQoZnJhbWUuZl9sb2NhbHMpCgogICAgZGVmIHByaW50X2xvY2Fscygqd2hpY2gsIHR5cGVzPUZhbHNlKToKICAgICAgICAiIiJQcmludCB0aGUgbG9jYWwgdmFyaWFibGVzIGluIHRoZSBjYWxsZXIncyBmcmFtZS4iIiIKICAgICAgICBpbXBvcnQgaW5zcGVjdAogICAgICAgICMgY3VycmVudGZyYW1lKCkgZnJhbWUgaXMgcHJpbnRfbG9jYWxzLiBXZSB3YW50IHRoZSBjYWxsZXIncyBmcmFtZQogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKICAgICAgICBsb2NhbHMgPSBmaW5kX2xvY2FscyhmcmFtZSkKICAgICAgICB3aGljaCA9IHNldCh3aGljaCkgaWYgd2hpY2ggZWxzZSBmaW5kX3doaWNoKGZyYW1lKQogICAgICAgIGxsID0ge2s6IHYgZm9yIGssIHYgaW4gbG9jYWxzLml0ZW1zKCkgaWYgayBpbiB3aGljaH0KICAgICAgICBpZiBub3QgbGw6CiAgICAgICAgICAgIHByaW50KCJwcmludF9sb2NhbHM6IG5vIGxvY2FscyIpCiAgICAgICAgICAgIHJldHVybgogICAgICAgIGlmIHR5cGVzOgogICAgICAgICAgICBwcmludCgiXG4iLmpvaW4oZiJ7a306IHt0eXBlKHYpLl9fbmFtZV9ffSDihpAge3Z9IiBmb3IgaywgdiBpbiBsbC5pdGVtcygpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBwcmludCgiOyAiLmpvaW4oZiJ7a30g4oaQIHtyZXByKHYpfSIgZm9yIGssIHYgaW4gbGwuaXRlbXMoKSkpCgogICAgcmV0dXJuIHByaW50X2xvY2FscwoKcHJpbnRfbG9jYWxzID0gbWFrZV9wcmludF9sb2NhbHMoKQ==",
        "ZGVmIG1ha2VfcHJldHR5X2Fzc2VydCgpOgogICAgaW1wb3J0IHN5cwogICAgaW1wb3J0IElQeXRob24KICAgIGltcG9ydCBhc3QKICAgIGltcG9ydCBpbnNwZWN0CiAgICBpbXBvcnQgaW8KICAgIGltcG9ydCBpdGVydG9vbHMKICAgIGltcG9ydCBmdW5jdG9vbHMKICAgIGltcG9ydCBjb3B5CiAgICAKICAgIGdsb2JhbCBtYWtlX3ByZXR0eV9hc3NlcnQKICAgIGRlbCBtYWtlX3ByZXR0eV9hc3NlcnQKCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYiBUT0RPCiAgICAgICAgZGVmIGdldF9hc3NlcnRfbGluZShmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9iYWNrLmZfbG9jYWxzWyJub2RlIl0KICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgY29kZSA9IGZyYW1lLmZfYmFjay5mX2JhY2suZl9jb2RlCiAgICAgICAgICAgIHJldHVybiBjb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICAgICAgZGVmIGNhbl9hbm5vdGF0ZShmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBGYWxzZQoKICAgIGVsaWYgSVB5dGhvbi5fX3ZlcnNpb25fXyA9PSAiOC40LjAiOgogICAgICAgICMgbGFiIGNvbXB1dGVycwogICAgICAgIGRlZiBnZXRfYXNzZXJ0X2xpbmUoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZSJdCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIGNvZGUgPSBmcmFtZS5mX2JhY2suZl9iYWNrLmZfY29kZQogICAgICAgICAgICByZXR1cm4gY29kZS5jb19maWxlbmFtZS5lbmRzd2l0aCgiSVB5dGhvbi9jb3JlL2ludGVyYWN0aXZlc2hlbGwucHkiKSBhbmQgY29kZS5jb19uYW1lID09ICJydW5fYXN0X25vZGVzIgogICAgICAgIGRlZiBjYW5fYW5ub3RhdGUoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gYXRfdG9wX2xldmVsKGZyYW1lKQoKICAgIGRlZiBpc19saXRlcmFsKGEpOgogICAgICAgIHRyeToKICAgICAgICAgICAgYXN0LmxpdGVyYWxfZXZhbChhKQogICAgICAgICAgICByZXR1cm4gVHJ1ZQogICAgICAgIGV4Y2VwdCBWYWx1ZUVycm9yOgogICAgICAgICAgICByZXR1cm4gRmFsc2UKICAgICAgICByZXR1cm4gRmFsc2UKCgogICAgZGVmIGFubm90YXRlX2NhbGwoZnJhbWUpOgogICAgICAgIGlmIG5vdCBjYW5fYW5ub3RhdGUoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4KICAgICAgICAKICAgICAgICBleHByOiBhc3QuRXhwciA9IGdldF9hc3NlcnRfbGluZShmcmFtZSkKICAgICAgICBmb3Iga3dhcmcgaW4gZXhwci52YWx1ZS5rZXl3b3JkczoKICAgICAgICAgICAgaWYga3dhcmcuYXJnID09ICJnb3QiOgogICAgICAgICAgICAgICAgZ290ID0ga3dhcmcudmFsdWUKCiAgICAgICAgaWYgaXNpbnN0YW5jZShnb3QsIGFzdC5DYWxsKToKICAgICAgICAgICAgaWYgbm90IGlzaW5zdGFuY2UoZ290LmZ1bmMsIGFzdC5OYW1lKToKICAgICAgICAgICAgICAgIHJldHVybgogICAgICAgICAgICBuYW1lID0gZ290LmZ1bmMuaWQKICAgICAgICAgICAgZnVuYyA9IGZyYW1lLmZfbG9jYWxzW25hbWVdCiAgICAgICAgICAgIGlmIG5vdCBoYXNhdHRyKGZ1bmMsIERFQlVHR0FCTEVfQVJHUyk6CiAgICAgICAgICAgICAgICByZXR1cm4KICAgICAgICAgICAgYXJncyA9IGdldGF0dHIoZnVuYywgREVCVUdHQUJMRV9BUkdTKQogICAgICAgICAgICBrd2FyZ3MgPSBnZXRhdHRyKGZ1bmMsIERFQlVHR0FCTEVfS1dBUkdTKQogICAgICAgICAgICBpZiBhcmdzIGlzIE5vbmUgb3Iga3dhcmdzIGlzIE5vbmU6CiAgICAgICAgICAgICAgICByZXR1cm4KICAgICAgICAgICAgYm91bmRhcmdzID0gaW5zcGVjdC5zaWduYXR1cmUoZnVuYykuYmluZCgqYXJncywgKiprd2FyZ3MpCgogICAgICAgICAgICByZXN1bHQgPSBpby5TdHJpbmdJTygpCiAgICAgICAgICAgIHBvcyA9IHJlc3VsdC53cml0ZShuYW1lKQogICAgICAgICAgICBwb3MgKz0gcmVzdWx0LndyaXRlKCIoIikKCiAgICAgICAgICAgIHNlcCA9ICcsICcKICAgICAgICAgICAgYXJnX3R1cGxlcyA9IFtdICAjIChhc3RfYXJnX3N0ciwgZXZhbHVhdGVkX2FyZywgc3RhcnQsIGxpbWl0KQoKICAgICAgICAgICAgIyBVc2UgYW4gaXRlcmF0b3IgaGVyZS4gSWYgYSBib3VuZGFyZyBpcyBub3QgY29uc3VtZWQgaGVyZSwKICAgICAgICAgICAgIyBpdCBtYXkgYmUgY29uc3VtZWQgbGF0ZXIgYnkgYSBwb3Mra3cgYXJnLgogICAgICAgICAgICBib3VuZGFyZ3NfaXRlciA9IGl0ZXIoYm91bmRhcmdzLmFyZ3MpCiAgICAgICAgICAgIGZvciBhc3RfYXJnLCBhcmcgaW4gemlwKGdvdC5hcmdzLCBib3VuZGFyZ3NfaXRlcik6CiAgICAgICAgICAgICAgICBhc3RfYXJnX3N0ciA9IGFzdC51bnBhcnNlKGFzdF9hcmcpCiAgICAgICAgICAgICAgICBhcmdfdHVwbGVzLmFwcGVuZCgoYXN0X2FyZ19zdHIsIGFyZywgcG9zLCBwb3MgKyBsZW4oYXN0X2FyZ19zdHIpKSkKICAgICAgICAgICAgICAgIHBvcyArPSBsZW4oYXN0X2FyZ19zdHIpICsgbGVuKHNlcCkKCiAgICAgICAgICAgIGZvciBhc3Rfa3dhcmcsIGt3YXJnIGluIGl0ZXJ0b29scy56aXBfbG9uZ2VzdChnb3Qua2V5d29yZHMsIGJvdW5kYXJnc19pdGVyKToKICAgICAgICAgICAgICAgIGFzdF9hcmdfc3RyID0gYXN0LnVucGFyc2UoYXN0X2t3YXJnKQogICAgICAgICAgICAgICAgYXJnX3R1cGxlcy5hcHBlbmQoKGFzdF9hcmdfc3RyLCBrd2FyZywgcG9zICsgbGVuKGFzdF9rd2FyZy5hcmcpICsgbGVuKCc9JyksIHBvcyArIGxlbihhc3RfYXJnX3N0cikpKQogICAgICAgICAgICAgICAgcG9zICs9IGxlbihhc3RfYXJnX3N0cikgKyBsZW4oc2VwKQoKICAgICAgICAgICAgcG9zIC09IGxlbihzZXApCiAgICAgICAgICAgIHJlc3VsdC53cml0ZShzZXAuam9pbih0WzBdIGZvciB0IGluIGFyZ190dXBsZXMpKQogICAgICAgICAgICByZXN1bHQud3JpdGUoJyknKQogICAgICAgICAgICByZXN1bHRfc3RyID0gcmVzdWx0LmdldHZhbHVlKCkKCiAgICAgICAgICAgIHlpZWxkIHJlc3VsdF9zdHIKCiAgICAgICAgICAgIG5vbmxpdGVyYWxzID0gW10gICMgKGV2YWx1YXRlZF9hcmcsIHJlc3VsdF9zdHIsIHN0YXJ0LCBsaW1pdCkKICAgICAgICAgICAgZm9yIF8sIGV2YWx1YXRlZF9hcmcsIHN0YXJ0LCBsaW1pdCBpbiBhcmdfdHVwbGVzOgogICAgICAgICAgICAgICAgaWYgbm90IGlzX2xpdGVyYWwocmVzdWx0X3N0cltzdGFydDpsaW1pdF0pOgogICAgICAgICAgICAgICAgICAgIG5vbmxpdGVyYWxzLmFwcGVuZCgoZXZhbHVhdGVkX2FyZywgcmVzdWx0X3N0cltzdGFydDpsaW1pdF0sIHN0YXJ0LCBsaW1pdCkpCgogICAgICAgICAgICB1bmRlcmxpbmVzID0gaW8uU3RyaW5nSU8oKQogICAgICAgICAgICBwb3MgPSAwCiAgICAgICAgICAgIGZvciBfLCBfLCBzdGFydCwgbGltaXQgaW4gbm9ubGl0ZXJhbHM6CiAgICAgICAgICAgICAgICBpZiAobGltaXQgLSBzdGFydCkgPCAzOgogICAgICAgICAgICAgICAgICAgIHBvcyArPSB1bmRlcmxpbmVzLndyaXRlKCcgJyAqIChzdGFydCAtIHBvcykpCiAgICAgICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScpCiAgICAgICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScgKiAobGltaXQgLSBwb3MpKQogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgICAgICBpZHggPSBzdGFydCArIChsaW1pdCAtIHN0YXJ0KSAvLyAyCiAgICAgICAgICAgICAgICBwb3MgKz0gdW5kZXJsaW5lcy53cml0ZSgnICcgKiAoc3RhcnQgLSBwb3MpKQogICAgICAgICAgICAgICAgI3BvcyArPSB1bmRlcmxpbmVzLndyaXRlKCfilZknKQogICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScgKiAoaWR4IC0gcG9zKSkKICAgICAgICAgICAgICAgIHBvcyArPSB1bmRlcmxpbmVzLndyaXRlKCfihpEnKQogICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScgKiAobGltaXQgLSBwb3MpKQogICAgICAgICAgICAgICAgI3BvcyArPSB1bmRlcmxpbmVzLndyaXRlKCfilZwnKQogICAgICAgICAgICB5aWVsZCB1bmRlcmxpbmVzLmdldHZhbHVlKCkKCiAgICAgICAgICAgIGRlZiBtYWtlX2JhcnNfYnVmKG5vbmxpdGVyYWxzLCBlbmQsIGV2YWxlZCk6CiAgICAgICAgICAgICAgICBidWYgPSBpby5TdHJpbmdJTygpCiAgICAgICAgICAgICAgICBwb3MgPSAwCiAgICAgICAgICAgICAgICBmb3IgaSBpbiByYW5nZShsZW4obm9ubGl0ZXJhbHMpIC0gMSk6CiAgICAgICAgICAgICAgICAgICAgXywgXywgc3RhcnQsIGxpbWl0ID0gbm9ubGl0ZXJhbHNbaV0KICAgICAgICAgICAgICAgICAgICBpZiAobGltaXQgLSBzdGFydCkgPCAzOgogICAgICAgICAgICAgICAgICAgICAgICBpZHggPSBzdGFydAogICAgICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgICAgIGlkeCA9IHN0YXJ0ICsgKGxpbWl0IC0gc3RhcnQpIC8vIDIKICAgICAgICAgICAgICAgICAgICBwb3MgKz0gYnVmLndyaXRlKCcgJyAqIChpZHggLSBwb3MpKQogICAgICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJ+KUgicpCiAgICAgICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgnICcgKiAobGltaXQgLSBwb3MpKQoKICAgICAgICAgICAgICAgIF8sIHJlc3VsdF9zdHIsIHN0YXJ0LCBsaW1pdCA9IG5vbmxpdGVyYWxzWy0xXQogICAgICAgICAgICAgICAgaWYgKGxpbWl0IC0gc3RhcnQpIDwgMzoKICAgICAgICAgICAgICAgICAgICBpZHggPSBzdGFydAogICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICBpZHggPSBzdGFydCArIChsaW1pdCAtIHN0YXJ0KSAvLyAyICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgnICcgKiAoaWR4IC0gcG9zKSkKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJ+KUlCcpCiAgICAgICAgICAgICAgICBwb3MgKz0gYnVmLndyaXRlKCfilIAnICogKGVuZCAtIDEgLSBwb3MpKQogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgn4pW0JykKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUocmVzdWx0X3N0cikKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJyDiiZQgJykKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoc3RyKGV2YWxlZCkpCgogICAgICAgICAgICAgICAgcmV0dXJuIGJ1ZiwgcG9zCgogICAgICAgICAgICB3aGlsZSBub25saXRlcmFsczoKICAgICAgICAgICAgICAgIGJ1ZiwgcG9zID0gbWFrZV9iYXJzX2J1Zihub25saXRlcmFscywgbGVuKHJlc3VsdF9zdHIpICsgNCwgbm9ubGl0ZXJhbHNbLTFdWzBdKQogICAgICAgICAgICAgICAgeWllbGQgYnVmLmdldHZhbHVlKCkKICAgICAgICAgICAgICAgIGxhc3QgPSBub25saXRlcmFscy5wb3AoKQoKICAgIGRlZiBhc3NlcnRfZXF1YWwoKiwgd2FudCwgZ290LCBvdXQ9c3lzLnN0ZG91dCk6CiAgICAgICAgaWYgd2FudCA9PSBnb3Q6CiAgICAgICAgICAgIHByaW50KCJUZXN0IGNhc2UgcGFzc2VkLiIpCiAgICAgICAgICAgIHJldHVybgoKICAgICAgICBmcmFtZSA9IGluc3BlY3QuY3VycmVudGZyYW1lKCkuZl9iYWNrCgogICAgICAgIGJveF9wYWRkaW5nID0gMgogICAgICAgIGhlYWRlciA9ICIgVGVzdCBjYXNlIGZhaWxlZC4gIgogICAgICAgIHdhbnRfbGluZSA9IGYie2JveF9wYWRkaW5nICogJyAnfVdhbnQ6IHtyZXByKHdhbnQpfSAodHlwZToge3R5cGUod2FudCkuX19uYW1lX199KSIKICAgICAgICBnb3RfbGluZSA9IGYie2JveF9wYWRkaW5nICogJyAnfUdvdDogIHtyZXByKGdvdCl9ICh0eXBlOiB7dHlwZShnb3QpLl9fbmFtZV9ffSkiCiAgICAgICAgCiAgICAgICAgaWYgY2FuX2Fubm90YXRlKGZyYW1lKToKICAgICAgICAgICAgYXNzZXJ0X2xpbmUgPSBmIntib3hfcGFkZGluZyAqICcgJ30+Pj4ge2FzdC51bnBhcnNlKGdldF9hc3NlcnRfbGluZShmcmFtZSkpfSIKICAgICAgICBlbHNlOgogICAgICAgICAgICBhc3NlcnRfbGluZSA9ICIiCiAgICAgICAgICAgIAogICAgICAgIGRlYnVnX2xpbmVzID0gbGlzdChhbm5vdGF0ZV9jYWxsKGZyYW1lKSkKICAgICAgICBpZiBkZWJ1Z19saW5lczoKICAgICAgICAgICAgZ290X2xpbmUgKz0gIiDihpAgIgogICAgICAgICAgICBwYWRkaW5nID0gbGVuKGdvdF9saW5lKQogICAgICAgICAgICBnb3RfbGluZSArPSBkZWJ1Z19saW5lc1swXQoKICAgICAgICBwYWRkZWRfZGVidWdfbGluZXMgPSBbXQogICAgICAgIGZvciBpLCBsaW5lIGluIGVudW1lcmF0ZShkZWJ1Z19saW5lcyk6CiAgICAgICAgICAgICAgICBpZiBpID09IDA6CiAgICAgICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgICAgIHBhZGRlZF9kZWJ1Z19saW5lcy5hcHBlbmQoJyAnICogcGFkZGluZyArIGxpbmUpCiAgICAgICAgICAgICAgICAKICAgICAgICBsaW5lX21heF9sZW4gPSBtYXgobGVuKGwpICsgYm94X3BhZGRpbmcgZm9yIGwgaW4gKGFzc2VydF9saW5lLCB3YW50X2xpbmUsIGdvdF9saW5lLCAqcGFkZGVkX2RlYnVnX2xpbmVzKSkKICAgICAgICBsaW5lX21heF9sZW4gPSBtYXgoMzIsIGxpbmVfbWF4X2xlbikKICAgICAgICBoZWFkZXJfZGFzaGVzID0gbGluZV9tYXhfbGVuIC0gbGVuKGhlYWRlcikKCgogICAgICAgIHByaW50KGZpbGU9b3V0KQogICAgICAgIHByaW50KCctJyAqIChoZWFkZXJfZGFzaGVzIC8vIDIpLCBlbmQ9IiIsIGZpbGU9b3V0KQogICAgICAgIHByaW50KGhlYWRlciwgZW5kPSIiLCBmaWxlPW91dCkKICAgICAgICBwcmludCgnLScgKiAoKGhlYWRlcl9kYXNoZXMgKyAxKSAvLyAyKSwgZW5kPSIiLCBmaWxlPW91dCkKICAgICAgICBwcmludChmaWxlPW91dCkKICAgICAgICBwcmludChmaWxlPW91dCkKCiAgICAgICAgCiAgICAgICAgaWYgYXNzZXJ0X2xpbmU6CiAgICAgICAgICAgIHByaW50KGFzc2VydF9saW5lLCBmaWxlPW91dCkKICAgICAgICAgICAgcHJpbnQoZmlsZT1vdXQpCgogICAgICAgIHByaW50KHdhbnRfbGluZSwgZmlsZT1vdXQpCiAgICAgICAgcHJpbnQoZ290X2xpbmUsIGZpbGU9b3V0KQogICAgICAgIGZvciBsaW5lIGluIHBhZGRlZF9kZWJ1Z19saW5lczoKICAgICAgICAgICAgcHJpbnQobGluZSwgZmlsZT1vdXQpCiAgICAgICAgCiAgICAgICAgcHJpbnQoZmlsZT1vdXQpCiAgICAgICAgcHJpbnQoJy0nICogbGluZV9tYXhfbGVuLCBmaWxlPW91dCkKICAgICAgICBwcmludChmaWxlPW91dCkKICAgICAgICAKICAgIERFQlVHR0FCTEVfQVJHUyA9ICJfZGVidWdnYWJsZV9hcmdzIgogICAgREVCVUdHQUJMRV9LV0FSR1MgPSAiX2RlYnVnZ2FibGVfa3dhcmdzIgoKICAgIGRlZiBkZWJ1Z2dhYmxlKGYpOgogICAgICAgIEBmdW5jdG9vbHMud3JhcHMoZikKICAgICAgICBkZWYgZygqYXJncywgKiprd2FyZ3MpOgogICAgICAgICAgICB0cnk6CiAgICAgICAgICAgICAgICBhcmdzX2NvcHkgPSBjb3B5LmRlZXBjb3B5KGFyZ3MpCiAgICAgICAgICAgICAgICBrd2FyZ3NfY29weSA9IGNvcHkuZGVlcGNvcHkoa3dhcmdzKQogICAgICAgICAgICBleGNlcHQgRXhjZXB0aW9uOgogICAgICAgICAgICAgICAgYXJnc19jb3B5ID0gTm9uZQogICAgICAgICAgICAgICAga3dhcmdzX2NvcHkgPSBOb25lCiAgICAgICAgICAgIHJlc3VsdCA9IGYoKmFyZ3MsICoqa3dhcmdzKQogICAgICAgICAgICBzZXRhdHRyKGcsIERFQlVHR0FCTEVfQVJHUywgYXJnc19jb3B5KQogICAgICAgICAgICBzZXRhdHRyKGcsIERFQlVHR0FCTEVfS1dBUkdTLCBrd2FyZ3NfY29weSkKICAgICAgICAgICAgcmV0dXJuIHJlc3VsdAogICAgICAgIHJldHVybiBnCiAgICAKICAgIHJldHVybiBhc3NlcnRfZXF1YWwsIGRlYnVnZ2FibGUKCmFzc2VydF9lcXVhbCwgZGVidWdnYWJsZSA9IG1ha2VfcHJldHR5X2Fzc2VydCgpCg==",
    )
    for code in CODE:
        exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f

def uh(b64):
    return eval(base64.b64decode(b64))

def h(code):
    return base64.b64encode(code)

def sae(*, want, got):
    assert_equal(want=sorted(want), got=sorted(got))

Day 17, Lab B: Dijkstra's Algorithm

1 Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path between a given source node and all the other nodes in a graph. Thus, it allows us to find the shortest path between any two nodes.

Edges connecting the nodes in a graph are weighted with a number. The weights can represent the "cost" to travel between the two nodes via that edge.

For example, to get from UWI Mona to Downtown Kingston, there are many paths. UWI Mona and Downtown Kingston are nodes in a graph. The different streets are edges. Each street might take a different amount of time, so the weight of the edges in the graph represent time in this example. Shortest path algorithms like Dijkstra's Algorithm helps us to find the fastest path to get from UWI Mona to Downtown Kingston.

1.1 Algorithm Overview

Dijkstra's works by visiting nodes in increasing order of their distance from the source node. Dijkstra's repeatedly visits the unvisited node with the smallest distance from the shortest node. When Dijkstra's visits a node $u$, it inspects all its neighbors $v$ to see if a new shortest path to $v$ can be discovered using the edge from $u \to v$.

After visiting all nodes, Dijkstra's returns the dist dictionary, which contains the distance (length of the shortest path) from the source node to all other nodes.

1.2 An Example

For example, in the following weighted undirected graph, we have five nodes: $A$, $B$, $C$, $D$, and $E$. Let's see how we can use Dijkstra's algorithm to find the distances and shortest paths from node $A$ to all other nodes.

First, we initialize the distance from $A$ to all other nodes to $\infty$, and the distance from $A$ to itself to $0$. As Dijkstra's traverses the graph, these distances will converge to their true values. We also set all nodes to unvisited.

Node Distance Visited
$A$ $0$ False
$B$ $\infty$ False
$C$ $\infty$ False
$D$ $\infty$ False
$E$ $\infty$ False

d1.png

Now, we start traversing the graph by visiting the closest (by distance) unvisited node. Looking at the table of distances, that node is node $A$:

Node Distance Visited
$A$ $0$ False
$B$ $\infty$ False
$C$ $\infty$ False
$D$ $\infty$ False
$E$ $\infty$ False

First, we set $A$ to visited:

Node Distance Visited
$A$ $0$ True
$B$ $\infty$ False
$C$ $\infty$ False
$D$ $\infty$ False
$E$ $\infty$ False

Next, we look at all of $A$'s neighbors and see whether we have discovered a new shortest path to that neighbor. $A$ has two neighbors, $B$, and $D$.

  1. Edge $A \to B$: We know the shortest path to $A$ has $0$ distance (by looking up that distance in the distance dictionary). The edge $A \to B$ has length $6$, so there exists a path from the source node $A$ to $B$ with length $6 = 0 \text{ (distance from $A$)} + 6 \text{ (length of edge $A \to B$)}$. This is shorter than the current known distance from $A$ to $B$, $\infty$ (again looking up in the distance table). So we can set the distance to $B$ to $6$.
  2. Edge $A \to D$. By the same logic as above, there must exist a path from $A$ to $D$ with length $1$. Since $1 < \infty$ (the current distance for $D$), so we can update the distance to $D$ to $1$ as well.

After the above distance updates, the new distance and visited table looks like:

Node Distance Visited
$A$ $0$ True
$B$ $6$ False
$C$ $\infty$ False
$D$ $1$ False
$E$ $\infty$ False

d2.png

Here's our distance and visited table on the second iteration of Dijkstra's:

Node Distance Visited
$A$ $0$ True
$B$ $6$ False
$C$ $\infty$ False
$D$ $1$ False
$E$ $\infty$ False

Next, the unvisited node with the shortest distance from the source node is $D$ with distance $1$. Thus, we visit $D$:

Node Distance Visited
$A$ $0$ True
$B$ $6$ False
$C$ $\infty$ False
$D$ $1$ True
$E$ $\infty$ False

Next, we consider $D$'s neighbors. $D$ has three neighbors: $A$, $B$, and $E$.

  1. Edge $D \to A$: This edge has weight $1$. We know that there is a path from $A$ to $D$ with length $1$ (because that is $D$'s distance in the distance table). Then there must be a path from $A$ to $A$ with length $2 = 1 + 1$. But $2$ is larger than the distance already stored in the table (which again is the length of the shortest path), so we don't update $A$'s distance in the table.
  2. Edge $D \to B$: This edge has weight $2$. That means that there must be a path from $A$ to $B$ through $D$ with length $3 = 1 + 2$. This is better than the distance to $B$ stored in the above table ($3 < 6$), so we update $B$'s distance in the table again.
  3. Edge $D \to E$. This edge has weight $1$. That means that there must be a path from $A$ to $E$ through $D$ with length $2 = 1 + 1$. This is better than the length of the current best path to $E$, $\infty$, so we also update $E$'s distance in the table.

Our new table looks like

Node Distance Visited
$A$ $0$ True
$B$ $3$ False
$C$ $\infty$ False
$D$ $1$ True
$E$ $2$ False