# Run this cell
%config InteractiveShell.ast_node_interactivity="none"
%pip install networkx
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))

Week 4, Morning Lab¶

Towers of Hanoi Game¶

$image.png$

Practice playing the Towers of Hanoi game here: make sure you understand how it works before beginning to implement the class.

https://www.transum.org/Maths/Investigation/Tower_Of_Hanoi/

Our Stack class from yesterday - Do Not Edit¶

We will be using this to implement Towers of Hanoi¶

Yesterday we introduced and implemented the Stack data class. It has the following interface:

stack = Stack(): Constructs a new empty Stack object called stack.
stack.push(elem): Adds an element, elem, to the top of the Stack stack.
stack.pop(): Removes the frontmost/popmost element in the Stack stack and returns its value.
stack.top(): Returns the value of the frontmost/ element in the Stack stack without removing it.
stack.is_empty(): Tests whether or not Stack stack is empty, returns a boolean.

class Stack:
    """An implementation of the stack data structure.
    """
    def __init__(self, lst=[]):
        """Constructs a new Stack, optionally initialized with the elements of lst.
        Arguments: lst (Optional[list])
        Effects: Initializes the Stack.
        """
        if lst is None:
            self.data = []
        else:
            self.data = lst[:]

    def push(self, elem):
        """Adds an element to the top of the stack
        Arguments:
            elem (any): The element to be pushed onto the stack.
        Effects: Adds the element on top of the stack.
        """
        self.data.append(elem)

    def pop(self):
        """Remove the element on top of the stack.
        Returns (any): The element on the top of the stack
        Effects: Removes the top element from the stack.
        """
        return self.data.pop()

    def top(self):
        """Returns the value of the topmost element on the stack without removing it.
        Returns (any): The element on the top of stack, if it has any elements
        """
        if not self.is_empty():
            return self.data[-1]

    def is_empty(self):
        """Checks if the stack is empty.
        Returns (bool): True if the stack is empty or False if it is not
        """
        return self.data == []

Implementing Towers of Hanoi¶

We are going to make a class called HanoiGame, with the interface:

game = HanoiGame(num_disks): Constructs a new HanoiGame object called game.
game.move(from_tower, to_tower): Will move one disk from the top of from_tower to the top of to_tower, if the move is valid, otherwise, it will have no effect on the game.
game.is_solved(): Returns True if the game is solved and returns False otherwise.
game.pretty_print: This will print the game. It is already implemented for you.

We will use the Stack class to represent the towers of disks, so you will need to make use the Stack class and its functions.

How will we use our `HanoiGame` class?¶

Make a new game, with 3 disks:

game = HanoiGame(3)
game.pretty_print()

Output:

After 0 moves:
  x|x      |       |   
 xx|xx     |       |   
xxx|xxx    |       |   
-----------------------

Move one disk from left tower to right tower:

game.move(LEFT_TOWER, RIGHT_TOWER)
game.pretty_print()

Output:

After 1 moves:
   |       |       |   
 xx|xx     |       |   
xxx|xxx    |      x|x  
-----------------------

LEFT_TOWER = 0
MIDDLE_TOWER = 1
RIGHT_TOWER = 2

class HanoiGame:
    """Implements the Towers of Hanoi game.
    """

    # Function to make a new game
    def __init__(self, num_disks):
        """Makes a new HanoiGame instance.

        Arguments: num_disks (int) representing the number of disks to play with
        """

        self.num_moves = # YOUR CODE HERE: What should num_moves be at the start of the game? 
        self.num_disks = # YOUR CODE HERE

        self.right_tower = # YOUR CODE HERE: Initialize an empty stack 
        self.middle_tower = # YOUR CODE HERE: Initialize an empty stack 

        # Make a list of disk numbers
        disks = list(range(num_disks))
        disks.reverse()
        
        # Initialize a Stack with disks, with the biggest 
        # disk at bottom and smallest disk (1) at the top
        self.left_tower = Stack(lst=disks) 
        self.towers = [self.left_tower, self.middle_tower, self.right_tower]


    def move(self, from_tower, to_tower):
        """Moves the top disk from `from_tower` to `to_tower` if possible.
          Doesn't return anything. If the move requested is invalid, nothing should happen!

          Arguments: from_tower and to_tower (int, either START_TOWER, MIDDLE_TOWER, or FINAL_TOWER)
          Effects: Executes the move - changes the stacks for the from_tower and to_tower, if it is a valid move.

        """

        from_stack = self.towers[from_tower] # from_tower's stack
        to_stack = self.towers[to_tower] # to_tower's stack

        # Check if from_tower is empty, if it is empty, our function shouldn't do anything, and halt
        if self.towers[from_tower].is_empty():
            # YOUR CODE HERE

        # Check if the move is valid
        # If it is valid, we should make the move
        # Hint: use your stack functions on t_stack and f_stack
        if self.towers[to_tower].is_empty() or __________ < __________:  # YOUR CODE HERE
            
            # YOUR CODE HERE
      
            # Update number of moves, but only if it was a valid move
            # YOUR CODE HERE


    def is_solved(self):
        """Returns True if the game has been solved. False otherwise.

        Arguments: No arguments
        Effects: No side effects (does not change the game)
        Returns: True or False
        """

        # Hint: Check to see if the self.start_tower and self.middle_tower are empty Stacks

        # YOUR CODE HERE


    # We can call .pretty_print() to show the current state of the tower game
    def pretty_print(self):  
        n = self.num_disks
        print("After", self.num_moves, "moves:")
        padded_widths = [([0] * n + [i +1 for i in tower.data[::-1]])[-n:] for tower in self.towers]
        for i in range(n):
            print(' '.join(('x'* w[i] + '|' + 'x' * w[i]).center(2 * n + 1) for w in padded_widths))
        print("-" * (6 * n + 5))
        print()
        if self.is_solved():
            print("!!! YAY !!!\n")

Test your code here:¶

game = HanoiGame(3)
assert_equal(want=0, got=game.num_moves)
assert_equal(want=3, got=game.num_disks)
assert_equal(want=True, got=game.middle_tower.is_empty())
assert_equal(want=True, got=game.right_tower.is_empty())
assert_equal(want=False, got=game.is_solved())
game.move(LEFT_TOWER, MIDDLE_TOWER) # move 0 to middle
assert_equal(want=1, got=game.left_tower.top())
assert_equal(want=0, got=game.middle_tower.top())
game.move(LEFT_TOWER, MIDDLE_TOWER) # try to move 1 on top of 0 in middle
assert_equal(want=1, got=game.left_tower.top())
game.move(MIDDLE_TOWER, RIGHT_TOWER)
assert_equal(want=1, got=game.left_tower.top())
assert_equal(want=0, got=game.right_tower.top())
assert_equal(want=True, got=game.middle_tower.is_empty())
game.move(LEFT_TOWER, MIDDLE_TOWER) # move 1 to middle
game.move(RIGHT_TOWER, MIDDLE_TOWER) # move 0 to middle
game.move(LEFT_TOWER, RIGHT_TOWER) # move 2 to right
game.move(MIDDLE_TOWER, LEFT_TOWER) # move 0 to left
game.move(MIDDLE_TOWER, RIGHT_TOWER) # move 1 to right
game.move(LEFT_TOWER, RIGHT_TOWER) # move 0 to right, should solve game
assert_equal(want=True, got=game.is_solved())
assert_equal(want=8, got=game.num_moves)

Play/test your game here:¶

from IPython.display import clear_output

LEFT_TOWER = 0
MIDDLE_TOWER = 1
RIGHT_TOWER = 2

def get_input():
    """Gets input (a move) from the current player.
    """
    # Do not modify this function.
    #
    # You are not expected to understand how this function works,
    # so don't worry if you don't.
    to = None
    fr = None
    while fr is None:
        s = input(f"Choose the tower to move a disk from: ")
        if not (s == "left" or s == "right" or s == "middle"):
            print(f"That was not \"left\", \"middle\", or \"right\", please try again")
        else:
            fr = s
    while to is None:
        s = input(f"Choose the tower to move the disk to: ")
        if not (s == "left" or s == "right" or s == "middle"):
            print(f"That was not \"left\", \"middle\", or \"right\", please try again")
        elif s == fr:
            print(f"Pick a different tower to move the disk to, you are moving from tower {fr}, please try again")
        else:
            to = s
    
    def convert(s):
        if s == "left": return LEFT_TOWER
        elif s == "middle": return MIDDLE_TOWER
        else: return RIGHT_TOWER

    print(f"You chose to move from the {fr} tower to the {to} tower")
    return convert(fr), convert(to)

def run_game(num_disks):
    game = HanoiGame(num_disks)
    while not game.is_solved():
        # get the next input from the next player
        game.pretty_print()
        fr, to = get_input()
        game.move(fr, to)
        clear_output(wait=True)
    print(f"Nice job, you solved it in {game.num_moves} moves")


# CHOOSE HOW MANY DISKS TO PLAY WITH:
run_game(5)

Solving Towers of Hanoi¶

We are going to design a strategy to recursively solve the Towers of Hanoi game like Adam showed us in lecture.

First, we make a variable called extra_tower, whichever of the 3 towers is not a or b, this line is given for you:

extra_tower = 3 - a - b
For example, if a = LEFT_TOWER and b = MIDDLE_TOWER, then extra_tower = RIGHT_TOWER.

Next, you will have to recursively move the i disks, by calling your function move_i_disks in its own definition.
You will have to make multiple recursive calls, in order to move all i disks.

Can you figure out how to do this recursively?

LEFT_TOWER = 0
MIDDLE_TOWER = 1
RIGHT_TOWER = 2

def move_i_disks(game, i, a, b): 
        '''Move the smallest i disks from tower a to tower b'''

        # BASE CASE
        if _____________:  # YOUR CODE HERE
            # YOUR CODE HERE

        # RECURSIVE CASE
        else:

            # YOUR CODE HERE
            extra_tower = 3 - a - b

            # RECURSIVE FUNCTION CALLS

            # YOUR CODE HERE

Test your code here:¶

def solve(hanoi):
    n = hanoi.num_disks
    move_i_disks(hanoi, n, LEFT_TOWER, RIGHT_TOWER)


# TEST YOUR CODE HERE
hanoi = HanoiGame(8)
hanoi.pretty_print()
solve(hanoi)
hanoi.pretty_print()
assert_equal(want=True, got=hanoi.is_solved())

Random Hanoi Strategy:¶

What if instead of recursively solving the game, we just made random moves instead? How long would it take to accidentally solve the game?

from random import randint
import matplotlib.pyplot as plt


def random_solve(num_disks):
    game = HanoiGame(num_disks)
    while not game.is_solved():
        a = randint(0, 2) # get random tower a
        b = randint(0, 2) # get random tower b
        game.move(a, b)   # move disk from tower a to tower b
    return game.num_moves


num_disks = 6 # choose the number of disks to play with (too many disks will take a LONG time to test!)
data = [random_solve(num_disks) for i in range(50)]
print(f"How many random moves does it take to accidentally solve Towers of Hanoi with {num_disks} disks?")
plt.hist(data, bins=30)

JamCoders

Week 4, Morning Lab¶

Towers of Hanoi Game¶

Our Stack class from yesterday - Do Not Edit¶

We will be using this to implement Towers of Hanoi¶

Implementing Towers of Hanoi¶

How will we use our `HanoiGame` class?¶

Test your code here:¶

Play/test your game here:¶

Solving Towers of Hanoi¶

Test your code here:¶

Random Hanoi Strategy:¶

If you finish the lab for today, please use this time to review previous labs.¶

JamCoders

Week 4, Morning Lab¶

Towers of Hanoi Game¶

Our Stack class from yesterday - Do Not Edit¶

We will be using this to implement Towers of Hanoi¶

Implementing Towers of Hanoi¶

How will we use our HanoiGame class?¶

Test your code here:¶

Play/test your game here:¶

Solving Towers of Hanoi¶

Test your code here:¶

Random Hanoi Strategy:¶

If you finish the lab for today, please use this time to review previous labs.¶

How will we use our `HanoiGame` class?¶