JamCoders

 💾 Download

Run this cell first!

In [ ]:
%config InteractiveShell.ast_node_interactivity="none"
def f(globals, locals):
    import base64
    CODE = ("ZGVmIG1ha2VfcHJpbnRfbG9jYWxzKCk6IAogICAgIyBJbiBhIGZ1bmN0aW9uIHRvIHByZXZlbnQgbG9jYWxzIGFuZCBpbXBvcnRzIGZyb20gbGVha2luZy4KICAgIGdsb2JhbCBtYWtlX3ByaW50X2xvY2FscwogICAgZGVsIG1ha2VfcHJpbnRfbG9jYWxzICAjIE9ubHkgcnVuIHRoaXMgZnVuY3Rpb24gb25jZS4KCiAgICBpbXBvcnQgSVB5dGhvbgogICAgaW1wb3J0IGFzdAogICAgaW1wb3J0IGluc3BlY3QKCiAgICBjbGFzcyBWaXNpdG9yKGFzdC5Ob2RlVmlzaXRvcik6CiAgICAgICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICAgICBzZWxmLnZhcmlhYmxlcyA9IHNldCgpCiAgICAgICAgZGVmIHZpc2l0X05hbWUoc2VsZiwgbmFtZSk6CiAgICAgICAgICAgIHNlbGYudmFyaWFibGVzLmFkZChuYW1lLmlkKQogICAgICAgICMgVE9ETzogUG9zc2libHkgZGV0ZWN0IHdoZXRoZXIgdmFyaWFibGVzIGFyZSBhc3NpZ25lZCB0by4KCiAgICBBTExPV19UWVBFUyA9IFtpbnQsIGZsb2F0LCBzdHIsIGJvb2wsIGxpc3QsIGRpY3QsIHR1cGxlLCByYW5nZV0KICAgIGRlZiBmaWx0ZXJfdmFyaWFibGVzKHZhcmlhYmxlcywgbG9jYWxzKToKICAgICAgICBmb3IgdiBpbiB2YXJpYWJsZXM6CiAgICAgICAgICAgIGlmIHYgaW4gbG9jYWxzIGFuZCB0eXBlKGxvY2Fsc1t2XSkgaW4gQUxMT1dfVFlQRVM6CiAgICAgICAgICAgICAgICB5aWVsZCB2CiAgCiAgICAjIFVuZm9ydHVuYXRlbHksIHRoZXJlIGRvZXNuJ3Qgc2VlbSB0byBiZSBhIHN1cHBvcnRlZCB3YXkgb2YgZ2V0dGluZwogICAgIyB0aGUgY3VycmVudCBjZWxsJ3MgY29kZSB2aWEgdGhlIHB1YmxpYyBJUHl0aG9uIEFQSXMuIEhvd2V2ZXIsIGJlY2F1c2UKICAgICMgd2UgYXJlIGdldHRpbmcgY2FsbGVkIGZyb20gSVB5dGhvbiBpdHNlbGYgYW5kIHdlIGFyZSBhbHJlYWR5IGluc3BlY3RpbmcKICAgICMgdGhlIHN0YWNrdHJhY2UsIHdlIG1pZ2h0IGFzIHdlbGwganVzdCBwZWVrIGludG8gaXRzIGZyYW1lLi4uCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYgogICAgICAgIGRlZiBnZXRfYXN0KGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGFzdC5Nb2R1bGUoZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZWxpc3QiXSkKICAgICAgICBkZWYgZmluZF9sb2NhbHMoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9sb2NhbHMKICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2NvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKCiAgICBlbGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjguNC4wIjoKICAgICAgICAjIGxhYiBjb21wdXRlcnMKICAgICAgICBkZWYgZ2V0X2FzdChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhc3QuTW9kdWxlKGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGVsaXN0Il0pCiAgICAgICAgZGVmIGZpbmRfbG9jYWxzKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfbG9jYWxzCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9jb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICBlbHNlOgogICAgICAgIHByaW50KGYicHJpbnRfbG9jYWxzKCkgbm90IHN1cHBvcnRlZCBvbiBJUHl0aG9uIHZlcnNpb24ge0lQeXRob24uX192ZXJzaW9uX199IikKCiAgICBkZWYgZ2V0X2NlbGxfbmFtZXMoZnJhbWUpOgogICAgICAgIHRyZWUgPSBnZXRfYXN0KGZyYW1lKQogICAgICAgIHZpc2l0b3IgPSBWaXNpdG9yKCkKICAgICAgICB2aXNpdG9yLnZpc2l0KHRyZWUpCiAgICAgICAgcmV0dXJuIGZpbHRlcl92YXJpYWJsZXModmlzaXRvci52YXJpYWJsZXMsIGZyYW1lLmZfbG9jYWxzKQoKICAgIGRlZiBmaW5kX3doaWNoKGZyYW1lKToKICAgICAgICAjIEZyYW1lIGlzIHRoZSBmcmFtZSB3aG9zZSBsb2NhbHMgd2UgYXJlIGludGVyZXN0ZWQgaW4gcHJpbnRpbmcuCiAgICAgICAgaWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgIyBUaGUgcGFyZW50IGZyYW1lIG9mIHRoZSBpbnRlcmVzdGVkIGZyYW1lIGlzIGEgbW9kdWxlLCBtb3N0IGxpa2VseQogICAgICAgICAgICAjICJpbnRlcmFjdGl2ZXNoZWxsIi4gVGhpcyBtZWFucyB3ZSBhcmUgaW4gdGhlIGdsb2JhbCBzY29wZSwgc2luY2UKICAgICAgICAgICAgIyBvbmx5IHRoZSBnbG9iYWwgc2NvcGUgc2hvdWxkIGJlIGRpcmVjdGx5IHJ1biBieSB0aGUgaW50ZXJhY3RpdmUgc2hlbGwuCiAgICAgICAgICAgIHJldHVybiBzZXQoZ2V0X2NlbGxfbmFtZXMoZnJhbWUpKQogICAgICAgICMgVGhlIHBhcmVudCBmcmFtZSBpcyBub3QgYSBtb2R1bGUsIHNvIHdlIGFyZSBpbiBhIGxvY2FsIHNjb3BlLgogICAgICAgIHJldHVybiBzZXQoZnJhbWUuZl9sb2NhbHMpCgogICAgZGVmIHByaW50X2xvY2Fscygqd2hpY2gsIHR5cGVzPUZhbHNlKToKICAgICAgICAiIiJQcmludCB0aGUgbG9jYWwgdmFyaWFibGVzIGluIHRoZSBjYWxsZXIncyBmcmFtZS4iIiIKICAgICAgICBpbXBvcnQgaW5zcGVjdAogICAgICAgICMgY3VycmVudGZyYW1lKCkgZnJhbWUgaXMgcHJpbnRfbG9jYWxzLiBXZSB3YW50IHRoZSBjYWxsZXIncyBmcmFtZQogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKICAgICAgICBsb2NhbHMgPSBmaW5kX2xvY2FscyhmcmFtZSkKICAgICAgICB3aGljaCA9IHNldCh3aGljaCkgaWYgd2hpY2ggZWxzZSBmaW5kX3doaWNoKGZyYW1lKQogICAgICAgIGxsID0ge2s6IHYgZm9yIGssIHYgaW4gbG9jYWxzLml0ZW1zKCkgaWYgayBpbiB3aGljaH0KICAgICAgICBpZiBub3QgbGw6CiAgICAgICAgICAgIHByaW50KCJwcmludF9sb2NhbHM6IG5vIGxvY2FscyIpCiAgICAgICAgICAgIHJldHVybgogICAgICAgIGlmIHR5cGVzOgogICAgICAgICAgICBwcmludCgiXG4iLmpvaW4oZiJ7a306IHt0eXBlKHYpLl9fbmFtZV9ffSDihpAge3Z9IiBmb3IgaywgdiBpbiBsbC5pdGVtcygpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBwcmludCgiOyAiLmpvaW4oZiJ7a30g4oaQIHtyZXByKHYpfSIgZm9yIGssIHYgaW4gbGwuaXRlbXMoKSkpCgogICAgcmV0dXJuIHByaW50X2xvY2FscwoKcHJpbnRfbG9jYWxzID0gbWFrZV9wcmludF9sb2NhbHMoKQ==", "ZGVmIG1ha2VfcHJldHR5X2Fzc2VydCgpOgogICAgaW1wb3J0IHN5cwogICAgaW1wb3J0IElQeXRob24KICAgIGltcG9ydCBhc3QKICAgIGltcG9ydCBpbnNwZWN0CiAgICBpbXBvcnQgaW8KICAgIGltcG9ydCBpdGVydG9vbHMKICAgIGltcG9ydCBmdW5jdG9vbHMKICAgIGltcG9ydCBjb3B5CiAgICAKICAgIGdsb2JhbCBtYWtlX3ByZXR0eV9hc3NlcnQKICAgIGRlbCBtYWtlX3ByZXR0eV9hc3NlcnQKCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYiBUT0RPCiAgICAgICAgZGVmIGdldF9hc3NlcnRfbGluZShmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9iYWNrLmZfbG9jYWxzWyJub2RlIl0KICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgY29kZSA9IGZyYW1lLmZfYmFjay5mX2JhY2suZl9jb2RlCiAgICAgICAgICAgIHJldHVybiBjb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICAgICAgZGVmIGNhbl9hbm5vdGF0ZShmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBGYWxzZQoKICAgIGVsaWYgSVB5dGhvbi5fX3ZlcnNpb25fXyA9PSAiOC40LjAiOgogICAgICAgICMgbGFiIGNvbXB1dGVycwogICAgICAgIGRlZiBnZXRfYXNzZXJ0X2xpbmUoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZSJdCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIGNvZGUgPSBmcmFtZS5mX2JhY2suZl9iYWNrLmZfY29kZQogICAgICAgICAgICByZXR1cm4gY29kZS5jb19maWxlbmFtZS5lbmRzd2l0aCgiSVB5dGhvbi9jb3JlL2ludGVyYWN0aXZlc2hlbGwucHkiKSBhbmQgY29kZS5jb19uYW1lID09ICJydW5fYXN0X25vZGVzIgogICAgICAgIGRlZiBjYW5fYW5ub3RhdGUoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gYXRfdG9wX2xldmVsKGZyYW1lKQoKICAgIGRlZiBpc19saXRlcmFsKGEpOgogICAgICAgIHRyeToKICAgICAgICAgICAgYXN0LmxpdGVyYWxfZXZhbChhKQogICAgICAgICAgICByZXR1cm4gVHJ1ZQogICAgICAgIGV4Y2VwdCBWYWx1ZUVycm9yOgogICAgICAgICAgICByZXR1cm4gRmFsc2UKICAgICAgICByZXR1cm4gRmFsc2UKCgogICAgZGVmIGFubm90YXRlX2NhbGwoZnJhbWUpOgogICAgICAgIGlmIG5vdCBjYW5fYW5ub3RhdGUoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4KICAgICAgICAKICAgICAgICBleHByOiBhc3QuRXhwciA9IGdldF9hc3NlcnRfbGluZShmcmFtZSkKICAgICAgICBmb3Iga3dhcmcgaW4gZXhwci52YWx1ZS5rZXl3b3JkczoKICAgICAgICAgICAgaWYga3dhcmcuYXJnID09ICJnb3QiOgogICAgICAgICAgICAgICAgZ290ID0ga3dhcmcudmFsdWUKCiAgICAgICAgaWYgaXNpbnN0YW5jZShnb3QsIGFzdC5DYWxsKToKICAgICAgICAgICAgaWYgbm90IGlzaW5zdGFuY2UoZ290LmZ1bmMsIGFzdC5OYW1lKToKICAgICAgICAgICAgICAgIHJldHVybgogICAgICAgICAgICBuYW1lID0gZ290LmZ1bmMuaWQKICAgICAgICAgICAgZnVuYyA9IGZyYW1lLmZfbG9jYWxzW25hbWVdCiAgICAgICAgICAgIGlmIG5vdCBoYXNhdHRyKGZ1bmMsIERFQlVHR0FCTEVfQVJHUyk6CiAgICAgICAgICAgICAgICByZXR1cm4KICAgICAgICAgICAgYXJncyA9IGdldGF0dHIoZnVuYywgREVCVUdHQUJMRV9BUkdTKQogICAgICAgICAgICBrd2FyZ3MgPSBnZXRhdHRyKGZ1bmMsIERFQlVHR0FCTEVfS1dBUkdTKQogICAgICAgICAgICBpZiBhcmdzIGlzIE5vbmUgb3Iga3dhcmdzIGlzIE5vbmU6CiAgICAgICAgICAgICAgICByZXR1cm4KICAgICAgICAgICAgYm91bmRhcmdzID0gaW5zcGVjdC5zaWduYXR1cmUoZnVuYykuYmluZCgqYXJncywgKiprd2FyZ3MpCgogICAgICAgICAgICByZXN1bHQgPSBpby5TdHJpbmdJTygpCiAgICAgICAgICAgIHBvcyA9IHJlc3VsdC53cml0ZShuYW1lKQogICAgICAgICAgICBwb3MgKz0gcmVzdWx0LndyaXRlKCIoIikKCiAgICAgICAgICAgIHNlcCA9ICcsICcKICAgICAgICAgICAgYXJnX3R1cGxlcyA9IFtdICAjIChhc3RfYXJnX3N0ciwgZXZhbHVhdGVkX2FyZywgc3RhcnQsIGxpbWl0KQoKICAgICAgICAgICAgIyBVc2UgYW4gaXRlcmF0b3IgaGVyZS4gSWYgYSBib3VuZGFyZyBpcyBub3QgY29uc3VtZWQgaGVyZSwKICAgICAgICAgICAgIyBpdCBtYXkgYmUgY29uc3VtZWQgbGF0ZXIgYnkgYSBwb3Mra3cgYXJnLgogICAgICAgICAgICBib3VuZGFyZ3NfaXRlciA9IGl0ZXIoYm91bmRhcmdzLmFyZ3MpCiAgICAgICAgICAgIGZvciBhc3RfYXJnLCBhcmcgaW4gemlwKGdvdC5hcmdzLCBib3VuZGFyZ3NfaXRlcik6CiAgICAgICAgICAgICAgICBhc3RfYXJnX3N0ciA9IGFzdC51bnBhcnNlKGFzdF9hcmcpCiAgICAgICAgICAgICAgICBhcmdfdHVwbGVzLmFwcGVuZCgoYXN0X2FyZ19zdHIsIGFyZywgcG9zLCBwb3MgKyBsZW4oYXN0X2FyZ19zdHIpKSkKICAgICAgICAgICAgICAgIHBvcyArPSBsZW4oYXN0X2FyZ19zdHIpICsgbGVuKHNlcCkKCiAgICAgICAgICAgIGZvciBhc3Rfa3dhcmcsIGt3YXJnIGluIGl0ZXJ0b29scy56aXBfbG9uZ2VzdChnb3Qua2V5d29yZHMsIGJvdW5kYXJnc19pdGVyKToKICAgICAgICAgICAgICAgIGFzdF9hcmdfc3RyID0gYXN0LnVucGFyc2UoYXN0X2t3YXJnKQogICAgICAgICAgICAgICAgYXJnX3R1cGxlcy5hcHBlbmQoKGFzdF9hcmdfc3RyLCBrd2FyZywgcG9zICsgbGVuKGFzdF9rd2FyZy5hcmcpICsgbGVuKCc9JyksIHBvcyArIGxlbihhc3RfYXJnX3N0cikpKQogICAgICAgICAgICAgICAgcG9zICs9IGxlbihhc3RfYXJnX3N0cikgKyBsZW4oc2VwKQoKICAgICAgICAgICAgcG9zIC09IGxlbihzZXApCiAgICAgICAgICAgIHJlc3VsdC53cml0ZShzZXAuam9pbih0WzBdIGZvciB0IGluIGFyZ190dXBsZXMpKQogICAgICAgICAgICByZXN1bHQud3JpdGUoJyknKQogICAgICAgICAgICByZXN1bHRfc3RyID0gcmVzdWx0LmdldHZhbHVlKCkKCiAgICAgICAgICAgIHlpZWxkIHJlc3VsdF9zdHIKCiAgICAgICAgICAgIG5vbmxpdGVyYWxzID0gW10gICMgKGV2YWx1YXRlZF9hcmcsIHJlc3VsdF9zdHIsIHN0YXJ0LCBsaW1pdCkKICAgICAgICAgICAgZm9yIF8sIGV2YWx1YXRlZF9hcmcsIHN0YXJ0LCBsaW1pdCBpbiBhcmdfdHVwbGVzOgogICAgICAgICAgICAgICAgaWYgbm90IGlzX2xpdGVyYWwocmVzdWx0X3N0cltzdGFydDpsaW1pdF0pOgogICAgICAgICAgICAgICAgICAgIG5vbmxpdGVyYWxzLmFwcGVuZCgoZXZhbHVhdGVkX2FyZywgcmVzdWx0X3N0cltzdGFydDpsaW1pdF0sIHN0YXJ0LCBsaW1pdCkpCgogICAgICAgICAgICB1bmRlcmxpbmVzID0gaW8uU3RyaW5nSU8oKQogICAgICAgICAgICBwb3MgPSAwCiAgICAgICAgICAgIGZvciBfLCBfLCBzdGFydCwgbGltaXQgaW4gbm9ubGl0ZXJhbHM6CiAgICAgICAgICAgICAgICBpZiAobGltaXQgLSBzdGFydCkgPCAzOgogICAgICAgICAgICAgICAgICAgIHBvcyArPSB1bmRlcmxpbmVzLndyaXRlKCcgJyAqIChzdGFydCAtIHBvcykpCiAgICAgICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScpCiAgICAgICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScgKiAobGltaXQgLSBwb3MpKQogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgICAgICBpZHggPSBzdGFydCArIChsaW1pdCAtIHN0YXJ0KSAvLyAyCiAgICAgICAgICAgICAgICBwb3MgKz0gdW5kZXJsaW5lcy53cml0ZSgnICcgKiAoc3RhcnQgLSBwb3MpKQogICAgICAgICAgICAgICAgI3BvcyArPSB1bmRlcmxpbmVzLndyaXRlKCfilZknKQogICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScgKiAoaWR4IC0gcG9zKSkKICAgICAgICAgICAgICAgIHBvcyArPSB1bmRlcmxpbmVzLndyaXRlKCfihpEnKQogICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScgKiAobGltaXQgLSBwb3MpKQogICAgICAgICAgICAgICAgI3BvcyArPSB1bmRlcmxpbmVzLndyaXRlKCfilZwnKQogICAgICAgICAgICB5aWVsZCB1bmRlcmxpbmVzLmdldHZhbHVlKCkKCiAgICAgICAgICAgIGRlZiBtYWtlX2JhcnNfYnVmKG5vbmxpdGVyYWxzLCBlbmQsIGV2YWxlZCk6CiAgICAgICAgICAgICAgICBidWYgPSBpby5TdHJpbmdJTygpCiAgICAgICAgICAgICAgICBwb3MgPSAwCiAgICAgICAgICAgICAgICBmb3IgaSBpbiByYW5nZShsZW4obm9ubGl0ZXJhbHMpIC0gMSk6CiAgICAgICAgICAgICAgICAgICAgXywgXywgc3RhcnQsIGxpbWl0ID0gbm9ubGl0ZXJhbHNbaV0KICAgICAgICAgICAgICAgICAgICBpZiAobGltaXQgLSBzdGFydCkgPCAzOgogICAgICAgICAgICAgICAgICAgICAgICBpZHggPSBzdGFydAogICAgICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgICAgIGlkeCA9IHN0YXJ0ICsgKGxpbWl0IC0gc3RhcnQpIC8vIDIKICAgICAgICAgICAgICAgICAgICBwb3MgKz0gYnVmLndyaXRlKCcgJyAqIChpZHggLSBwb3MpKQogICAgICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJ+KUgicpCiAgICAgICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgnICcgKiAobGltaXQgLSBwb3MpKQoKICAgICAgICAgICAgICAgIF8sIHJlc3VsdF9zdHIsIHN0YXJ0LCBsaW1pdCA9IG5vbmxpdGVyYWxzWy0xXQogICAgICAgICAgICAgICAgaWYgKGxpbWl0IC0gc3RhcnQpIDwgMzoKICAgICAgICAgICAgICAgICAgICBpZHggPSBzdGFydAogICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICBpZHggPSBzdGFydCArIChsaW1pdCAtIHN0YXJ0KSAvLyAyICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgnICcgKiAoaWR4IC0gcG9zKSkKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJ+KUlCcpCiAgICAgICAgICAgICAgICBwb3MgKz0gYnVmLndyaXRlKCfilIAnICogKGVuZCAtIDEgLSBwb3MpKQogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgn4pW0JykKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUocmVzdWx0X3N0cikKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJyDiiZQgJykKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoc3RyKGV2YWxlZCkpCgogICAgICAgICAgICAgICAgcmV0dXJuIGJ1ZiwgcG9zCgogICAgICAgICAgICB3aGlsZSBub25saXRlcmFsczoKICAgICAgICAgICAgICAgIGJ1ZiwgcG9zID0gbWFrZV9iYXJzX2J1Zihub25saXRlcmFscywgbGVuKHJlc3VsdF9zdHIpICsgNCwgbm9ubGl0ZXJhbHNbLTFdWzBdKQogICAgICAgICAgICAgICAgeWllbGQgYnVmLmdldHZhbHVlKCkKICAgICAgICAgICAgICAgIGxhc3QgPSBub25saXRlcmFscy5wb3AoKQoKICAgIGRlZiBhc3NlcnRfZXF1YWwoKiwgd2FudCwgZ290LCBvdXQ9c3lzLnN0ZG91dCk6CiAgICAgICAgaWYgd2FudCA9PSBnb3Q6CiAgICAgICAgICAgIHByaW50KCJUZXN0IGNhc2UgcGFzc2VkLiIpCiAgICAgICAgICAgIHJldHVybgoKICAgICAgICBmcmFtZSA9IGluc3BlY3QuY3VycmVudGZyYW1lKCkuZl9iYWNrCgogICAgICAgIGJveF9wYWRkaW5nID0gMgogICAgICAgIGhlYWRlciA9ICIgVGVzdCBjYXNlIGZhaWxlZC4gIgogICAgICAgIHdhbnRfbGluZSA9IGYie2JveF9wYWRkaW5nICogJyAnfVdhbnQ6IHtyZXByKHdhbnQpfSAodHlwZToge3R5cGUod2FudCkuX19uYW1lX199KSIKICAgICAgICBnb3RfbGluZSA9IGYie2JveF9wYWRkaW5nICogJyAnfUdvdDogIHtyZXByKGdvdCl9ICh0eXBlOiB7dHlwZShnb3QpLl9fbmFtZV9ffSkiCiAgICAgICAgCiAgICAgICAgaWYgY2FuX2Fubm90YXRlKGZyYW1lKToKICAgICAgICAgICAgYXNzZXJ0X2xpbmUgPSBmIntib3hfcGFkZGluZyAqICcgJ30+Pj4ge2FzdC51bnBhcnNlKGdldF9hc3NlcnRfbGluZShmcmFtZSkpfSIKICAgICAgICBlbHNlOgogICAgICAgICAgICBhc3NlcnRfbGluZSA9ICIiCiAgICAgICAgICAgIAogICAgICAgIGRlYnVnX2xpbmVzID0gbGlzdChhbm5vdGF0ZV9jYWxsKGZyYW1lKSkKICAgICAgICBpZiBkZWJ1Z19saW5lczoKICAgICAgICAgICAgZ290X2xpbmUgKz0gIiDihpAgIgogICAgICAgICAgICBwYWRkaW5nID0gbGVuKGdvdF9saW5lKQogICAgICAgICAgICBnb3RfbGluZSArPSBkZWJ1Z19saW5lc1swXQoKICAgICAgICBwYWRkZWRfZGVidWdfbGluZXMgPSBbXQogICAgICAgIGZvciBpLCBsaW5lIGluIGVudW1lcmF0ZShkZWJ1Z19saW5lcyk6CiAgICAgICAgICAgICAgICBpZiBpID09IDA6CiAgICAgICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgICAgIHBhZGRlZF9kZWJ1Z19saW5lcy5hcHBlbmQoJyAnICogcGFkZGluZyArIGxpbmUpCiAgICAgICAgICAgICAgICAKICAgICAgICBsaW5lX21heF9sZW4gPSBtYXgobGVuKGwpICsgYm94X3BhZGRpbmcgZm9yIGwgaW4gKGFzc2VydF9saW5lLCB3YW50X2xpbmUsIGdvdF9saW5lLCAqcGFkZGVkX2RlYnVnX2xpbmVzKSkKICAgICAgICBsaW5lX21heF9sZW4gPSBtYXgoMzIsIGxpbmVfbWF4X2xlbikKICAgICAgICBoZWFkZXJfZGFzaGVzID0gbGluZV9tYXhfbGVuIC0gbGVuKGhlYWRlcikKCgogICAgICAgIHByaW50KGZpbGU9b3V0KQogICAgICAgIHByaW50KCctJyAqIChoZWFkZXJfZGFzaGVzIC8vIDIpLCBlbmQ9IiIsIGZpbGU9b3V0KQogICAgICAgIHByaW50KGhlYWRlciwgZW5kPSIiLCBmaWxlPW91dCkKICAgICAgICBwcmludCgnLScgKiAoKGhlYWRlcl9kYXNoZXMgKyAxKSAvLyAyKSwgZW5kPSIiLCBmaWxlPW91dCkKICAgICAgICBwcmludChmaWxlPW91dCkKICAgICAgICBwcmludChmaWxlPW91dCkKCiAgICAgICAgCiAgICAgICAgaWYgYXNzZXJ0X2xpbmU6CiAgICAgICAgICAgIHByaW50KGFzc2VydF9saW5lLCBmaWxlPW91dCkKICAgICAgICAgICAgcHJpbnQoZmlsZT1vdXQpCgogICAgICAgIHByaW50KHdhbnRfbGluZSwgZmlsZT1vdXQpCiAgICAgICAgcHJpbnQoZ290X2xpbmUsIGZpbGU9b3V0KQogICAgICAgIGZvciBsaW5lIGluIHBhZGRlZF9kZWJ1Z19saW5lczoKICAgICAgICAgICAgcHJpbnQobGluZSwgZmlsZT1vdXQpCiAgICAgICAgCiAgICAgICAgcHJpbnQoZmlsZT1vdXQpCiAgICAgICAgcHJpbnQoJy0nICogbGluZV9tYXhfbGVuLCBmaWxlPW91dCkKICAgICAgICBwcmludChmaWxlPW91dCkKICAgICAgICAKICAgIERFQlVHR0FCTEVfQVJHUyA9ICJfZGVidWdnYWJsZV9hcmdzIgogICAgREVCVUdHQUJMRV9LV0FSR1MgPSAiX2RlYnVnZ2FibGVfa3dhcmdzIgoKICAgIGRlZiBkZWJ1Z2dhYmxlKGYpOgogICAgICAgIEBmdW5jdG9vbHMud3JhcHMoZikKICAgICAgICBkZWYgZygqYXJncywgKiprd2FyZ3MpOgogICAgICAgICAgICB0cnk6CiAgICAgICAgICAgICAgICBhcmdzX2NvcHkgPSBjb3B5LmRlZXBjb3B5KGFyZ3MpCiAgICAgICAgICAgICAgICBrd2FyZ3NfY29weSA9IGNvcHkuZGVlcGNvcHkoa3dhcmdzKQogICAgICAgICAgICBleGNlcHQgRXhjZXB0aW9uOgogICAgICAgICAgICAgICAgYXJnc19jb3B5ID0gTm9uZQogICAgICAgICAgICAgICAga3dhcmdzX2NvcHkgPSBOb25lCiAgICAgICAgICAgIHJlc3VsdCA9IGYoKmFyZ3MsICoqa3dhcmdzKQogICAgICAgICAgICBzZXRhdHRyKGcsIERFQlVHR0FCTEVfQVJHUywgYXJnc19jb3B5KQogICAgICAgICAgICBzZXRhdHRyKGcsIERFQlVHR0FCTEVfS1dBUkdTLCBrd2FyZ3NfY29weSkKICAgICAgICAgICAgcmV0dXJuIHJlc3VsdAogICAgICAgIHJldHVybiBnCiAgICAKICAgIHJldHVybiBhc3NlcnRfZXF1YWwsIGRlYnVnZ2FibGUKCmFzc2VydF9lcXVhbCwgZGVidWdnYWJsZSA9IG1ha2VfcHJldHR5X2Fzc2VydCgp")
    for code in CODE:
        exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f

Week 3, Day 3

Ordered Data Structures

1. The Queue Data Structure

A queue is a data structure into which elements can be added (enqueued). When elements are removed from the queue (dequeued), they are removed in first-in-first-out order.

A queue is an abstract data structure. That is, any data structure which supports the queue operations (see below) can be used as a queue. There are many ways to implement the queue operations. Each implementation has its advantages and disadvantages.

a) Expand this for more about First-In-First-Out! ✨

The First-In-First-Out principle is similar to the concept of joining a line to buy food.

  1. Let's say Michael joins the line, then Tyler joins the line, then Bereket joins the line.

  2. Michael is at the the front of the line so he buys his food and gets served first. Then he leaves the line.

  3. Now Tyler is at the start of the line so he buys his food and gets served next. Then he leaves the line.

  4. Bereket is now at the start of the line so he buys his food, is served and then leaves the line.

  5. Now the line is empty.

The Queue Operations

All queues support the following basic operations.

  • init_q(): Constructs a new empty Queue.
  • enqueue_q(queue, elem): Adds an element, elem, to the back of the Queue queue.
  • peek_q(queue): Returns the value of the frontmost element in the Queue queue without removing it.
  • dequeue_q(queue): Removes the frontmost element in the Queue queue and returns its value.
  • is_empty_q(queue): Tests whether or not Queue queue is empty.
b) Expand to see how the example from a) relates to the queue operations 🙂

Using the same example above of the line and a queue, food_line:

'Michael joins the line' - enqueue_q(food_line, 'Michael')

'Tyler joins the line' - enqueue_q(food_line, 'Tyler')

'Bereket joins the line' - enqueue_q(food_line, 'Bereket')

'Michael is at the front of the line' - peek_q(food_line) # 'Michael'

'...gets served. Then he leaves the line' - dequeue_q(food_line)

'Now the line is empty' - is_empty_q(food_line) # True

Implementing a Queue

So far we've just described the "abstract" interface for interacting with a Queue. But to actually use a Queue, we need a concrete implementation.

For this program, we will have you implement a queue using a Python list.

(Ponder: What might be the advantages of such an implementation? What are the disadvantages?)

Please make use of the following functions in your implementations:

  • lst.append(x) will add x to the right end of lst
  • lst.pop(i) will remove the element in lst at position i

1.1 The Queue Operations

In [ ]:
@debuggable
def init_q(lst=None):
    """Constructs a new empty queue.

    Arguments: Optional list of initial elements in the queue (Optional[list]).
    Returns (Queue): The new empty queue.
    Effects: None.
    """
    if lst is None:
        return []
    return lst[:]


@debuggable
def enqueue_q(queue, elem):
    """Adds an element to the rear of the queue.

    Arguments:
        queue (Queue): The queue to which the element should be added.
        elem (Any): The element to be added to the queue.
    Returns: None.
    Effects: Modifies `queue` by adding the new element.
    """
    queue.append(elem)


@debuggable
def dequeue_q(queue):
    """Removes the element from the front of the queue and returns it.
    
    queue must not be empty.

    Arguments:
        queue (Queue): The queue from which the front element should be removed.
    Returns (any): The front element in the queue.
    Effects: The front element is removed from the queue.
    """
    return queue.pop(0)


@debuggable
def peek_q(queue):
    """Returns the element at the front of the queue, without removing it.
    
    queue must not be empty.

    Arguments:
        queue (Queue): The queue from which the front element should be returned.
    Returns (any): The front element in the queue.
    Effects: None
    """
    return queue[0]


@debuggable
def is_empty_q(queue):
    """Determines whether or not the queue is empty.

    Arguments:
        queue (Queue):  The queue to be checked if it is empty or not
    Returns (bool): True if the queue is empty or False if it is not empty
    Effects: None
    """
    return len(queue) == 0
In [ ]:
# Test queues with integers.
queue = init_q()

assert_equal(want=None, got=enqueue_q(queue, 1))  # Queue contains [1]
assert_equal(want=None, got=enqueue_q(queue, 3))  # Queue contains [1, 3]
assert_equal(want=None, got=enqueue_q(queue, 2))  # Queue contains [1, 3, 2]
assert_equal(want=None, got=enqueue_q(queue, 5))  # Queue contains [1, 3, 2, 5]

assert_equal(want=1, got=peek_q(queue))
assert_equal(want=1, got=dequeue_q(queue))  # Queue contains [3, 2, 5]

assert_equal(want=3, got=peek_q(queue))

assert_equal(want=False, got=is_empty_q(queue))


# Test queues with other types.
queue = init_q()
enqueue_q(queue, "Hello")
enqueue_q(queue, "Goodbye")
enqueue_q(queue, [])

assert_equal(want="Hello", got=dequeue_q(queue))
assert_equal(want="Goodbye", got=dequeue_q(queue))
assert_equal(want=[], got=dequeue_q(queue))


# Test empty queues.
queue = init_q()
assert_equal(want=True, got=is_empty_q(queue))

1.2. I'm hungry; where's lunch?

Our queue implementation should work with string's (or really any type), not just int's.

Suppose TAs are waiting in two different lines for lunch. Write code that acts out the following scenario. There are two lines for lunch: one for chicken and one for pork.

  1. First, "Annamira" joins the line for chicken.
  2. Next, "Jabari" joins the line for pork.
  3. "Tyler" joins the line for chicken.
  4. "Natnael" joins the line for chicken.
  5. Since "Annamira" is at the front of the line, she gets her chicken and then leaves the line.
  6. However, "Annamira" is still hungry, so she decides to join the line for pork as well to get a second lunch 😋.
  7. "Jabari" is served his pork and leaves the line.

After the above shenanigans, "Tyler" and "Natnael" are still in line for chicken. "Annamira" is in line for pork.

Enqueue the TAs into and dequeue the TAs from chickenLine and porkLine in the correct order to mimic the above scenario.

Note that some of the steps have already been executed. At the end, "Tyler" and "Natnael" should be in line for chicken, and "Annamira" should be in line for pork.

Only use the queue operations!

In [ ]:
# We have started the code for you:

chicken_line = init_q()
pork_line = init_q()

# Step 1: Annamira joins the queue for chicken.
enqueue_q(chicken_line, "Annamira")

# Step 2: Jabari joins the line for pork.
enqueue_q(pork_line, "Jabari")      

# Step 3: Tyler joins the line for chicken.
# YOUR CODE HERE

# Step 4: Natnael joins the line for chicken.
# YOUR CODE HERE

# Step 5: The first person in the chicken line, Annamira, gets her chicken and
# leaves the line.
# YOUR CODE HERE

# Step 6: Annamira decies she is still hungry, so joins the pork line to get a
# second lunch.
# YOUR CODE HERE

# Step 7: The first person in the pork line, Jabari, gets his chicken and leaves
# the line.
# YOUR CODE HERE
In [ ]:
# Tests. (Your strings should match the strings in the problem description.)

assert_equal(want="Tyler", got=dequeue_q(chicken_line))
assert_equal(want="Natnael", got=dequeue_q(chicken_line))
assert_equal(want=True, got=is_empty_q(chicken_line))
assert_equal(want="Annamira", got=dequeue_q(pork_line))
assert_equal(want=True, got=is_empty_q(pork_line))

2. Stacks

Stacks are similar to queues in that items can be inserted and removed. However, unlike queues, the order of removal is reversed: the last item to be inserted is the first to be removed. Hence, the stack removes items in Last-In-First-Out (LIFO) order.

2.1. The Stack Data Structure

A stack is a data structure into which elements can be added (pushed). When elements are removed from the stack (popped), they are removed in last-in-first-out order.

A stack is also an abstract data structure. That is, any data structure which supports the stack operations (see below) can be used as a stack. There are many ways to implement the stack operations. Each implementation has its advantages and disadvantages.

The Stack Operations

All stacks support the following basic operations.

  • init_s(): Constructs a new empty Stack.
  • push_s(stack, elem): Adds an element, elem, to the top of the Stack stack.
  • pop_s(stack): Removes the frontmost/popmost element in the Stack stack and returns its value.
  • top_s(stack): Returns the value of the frontmost/ element in the Stack stack without removing it.
  • is_empty_s(stack): Tests whether or not Stack stack is empty.

2.2 Implementing the Stack Operations

So far we've just described the "abstract" interface for interacting with a Stack. But to actually use a Stack, we need a concrete implementation.

For this program, we will have you implement a stack using a Python list.

Please make use of the following functions in your implementations:

  • lst.append(x) will add x to the right end of lst.
  • lst.pop() will remove and return the last (rightmost) element in lst.
In [ ]:
@debuggable
def init_s(lst=None):
    """Constructs a new empty stack.

    Arguments: Optional list of initial elements in the stack (Optional[list]).
    Returns (Stack): A new empty stack
    Effects: None
    """
    if lst is None:
        return []
    return lst[:]


@debuggable
def push_s(stack, elem):
    """Adds an element to the top of the stack
    
    Arguments:
        stack (Stack): The stack to push the element onto
        elem (any): The element to be pushed onto the stack
    Returns: None
    Effects: Mutates the stack to add the element to the top of the stack.
        Note that a new stack is not created.
    """
    # YOUR CODE HERE


@debuggable
def pop_s(stack):
    """Remove the element on top of the stack.
    
    Arguments:
        stack (Stack): The stack to pop the element from 
        Returns (any): The element on the top of the stack
    Effects: Modifies `stack` to remove the top element.
        Note that a new stack is  not created.
    """
    # YOUR CODE HERE


@debuggable
def top_s(stack):
    """Returns the value of the topmost element on the stack without removing it
    
    Arguments:
        stack (Stack): The stack to find the top element of.
    Returns (any): The element on the top of stack.
    Effects: None
    """
    # YOUR CODE HERE


@debuggable
def is_empty_s(stack):
    """Checks if the stack is empty.
    
    Arguments: 
        stack (Stack): The stack to be checked if it is empty
    Returns (bool): True if the stack is empty or False if it is not
    Effects: None
    """
    # YOUR CODE HERE
In [ ]:
# Test stacks with integers.
stack = init_s()

assert_equal(want=None, got=push_s(stack, 1))  # Stack contains [1]
assert_equal(want=None, got=push_s(stack, 3))  # Stack contains [1, 3]
assert_equal(want=None, got=push_s(stack, 2))  # Stack contains [1, 3, 2]
assert_equal(want=None, got=push_s(stack, 5))  # Stack contains [1, 3, 2, 5]

assert_equal(want=5, got=pop_s(stack))
assert_equal(want=2, got=pop_s(stack))  # Stack contains [1, 3, 2, 5]

assert_equal(want=3, got=top_s(stack))

assert_equal(want=False, got=is_empty_s(stack))


# Test questacksues with other types.
stack = init_s()
push_s(stack, "Hello")
push_s(stack, "Goodbye")
push_s(stack, [])

# Stacks pop in last-in-first-out.
assert_equal(want=[], got=pop_s(stack))
assert_equal(want="Goodbye", got=pop_s(stack))
assert_equal(want="Hello", got=pop_s(stack))


# Test empty stacks.
stack = init_s()
assert_equal(want=True, got=is_empty_s(stack))

Impressive✨! We are finally done implementing our Queue and Stack classes. Let's move now to some problems!

2.3. Stack reverse a list

Write a function that reverses a list using a stack. Do not use list slicing or the reverse or reversed functions. Don't forget to return a list (and not a stack).

In [ ]:
@debuggable
def rev(lst):
    """Reverses the given list `lst` using a stack.

    Arguments: lst (list) The list to be reversed.
    Returns (list): The reversed list.
    Effects: None.
    """
In [ ]:
# Test your function
assert_equal(want=[4, 3, 2, 1], got=rev([1, 2, 3, 4]))
assert_equal(want=[1, 2, 3, 4], got=rev([4, 3, 2, 1]))
assert_equal(want=[12, 10, 8, 6 ,4, 2], got=rev([2, 4, 6, 8, 10, 12]))

3. More Practice

3.1. Merge two sorted... queues?

Crossover episode! In this question we will merge two sorted queues into a new sorted queue.

You may want to refer back to our code that merges two sorted lists. If you do so, think what needs to be changed for queues. (Hint: you no longer need to keep the two pointers/fingers for each list!)

Remember to access queues only using the five queue operations above.

In [ ]:
@debuggable
def merge(queue1, queue2):
    """Merges two sorted queues into a new sorted queue.
    Arguments: q1 (Queue of ints), q2 (Queue of ints)
    Returns: (Queue of ints)
    Side effects: Empties q1 and q2.
    """
    # YOUR CODE HERE
In [ ]:
# Test your function

queue1, queue2 = init_q([1, 4, 5, 6]), init_q([2, 3, 5, 5, 10])
assert_equal(want=init_q([1, 2, 3, 4, 5, 5, 5, 6, 10]), got=merge(queue1, queue2))

queue1, queue2 = init_q([]), init_q([])
assert_equal(want=init_q([]), got=merge(queue1, queue2))

queue1, queue2 = init_q([1, 1, 1, 1]), init_q([2, 2, 2, 2])
assert_equal(want=init_q([1, 1, 1, 1, 2, 2, 2, 2]), got=merge(queue1, queue2))

3.2. Backspaces

You are given a string that records a sequence of keystroke. There are two possibilities for each keystroke (character is the string):

  1. A letter in the alphabet a-z or A-Z.
  2. A special character '*' which indicates that backspace was pressed.

You will implement a function apply_backspace that applies backspaces to a string. Some examples:

  • "Orrrr**" --> "Orr"
  • "Bri*yan" --> "Bryan"
  • "I'm tired*****having fun! --> I'm having fun!"
  • "Bye***" --> ""
  • "**" --> "" because pressing backspaces on an empty string deletes nothing...
  • "Hi****" -> "" for the same reason

Hint: To turn a list of characters back into a string, use the string.join function. For example, suppose chars = ['a', 'b', 'c']. Then ''.join(chars) would return the string "abc".

Hint: You might want to use the rev reverse function you defined above.

In [ ]:
@debuggable
def apply_backspace(s):
    """Applies backspaces to string s.
    
    For every occurrence of *, deletes the most recent letter.

    Arguments:
        s (str): A string with letters and backspaces.
    Returns (str): A string with all backspaces applied.
    Effects: None.
    """
    # YOUR CODE HERE
In [ ]:
# Test your function

assert_equal(want="Orr", got=apply_backspace("Orrrr**"))
assert_equal(want="Bryan", got=apply_backspace("Bri*yan"))
assert_equal(want="I'm having fun!", got=apply_backspace("I'm tired*****having fun!"))
assert_equal(want="", got=apply_backspace("Bye***"))
assert_equal(want="", got=apply_backspace("**"))
assert_equal(want="", got=apply_backspace("Hi****"))

4. Challenge Problems

4.1 Teeter-totter

You are given a string that contains only the characters '(' or ')'. You will write a function is_valid that checks whether the string is valid if all parentheses are balanced---correctly matched. More formally, a string s is valid if:

  • Each ( is matched with a subsequent ).
  • When reading the string left-to-right, at no point are there more )'s than ('.

Here are some examples:

  • "()" is valid.
  • "(()) is valid.
  • "()()" is valid.
  • "" is valid (because there are no parentheses at all...)
  • "(" is invalid.
  • ")" is invalid.
  • "())" is invalid.
  • "(()" is invalid.
In [ ]:
@debuggable
def is_valid(s):
    """Checks whether a string of parentheses is balanced.

    Arguments: s, a string consisting of parens; '(' or ')'
    Returns (bool): Whether `s` is correctly balanced.
    Effects: None
    """
    # YOUR CODE HERE
In [ ]:
assert_equal(want=False, got=is_valid("())"))  # Too many closing parens.
assert_equal(want=False, got=is_valid("("))  # No matching closing parens.
assert_equal(want=False, got=is_valid("(("))  # No matching closing parens.
assert_equal(want=False, got=is_valid("()("))  # No matching closing parens.
assert_equal(want=False, got=is_valid("(((()))"))  # No matching closing parens.
assert_equal(want=True, got=is_valid("(())"))  # Correctly balanced.
assert_equal(want=False, got=is_valid(")"))  # Too many closing parens.
assert_equal(want=True, got=is_valid(""))  # Empty string is balanced.
assert_equal(want=True, got=is_valid("()()"))
assert_equal(want=True, got=is_valid("()()"))
assert_equal(want=False, got=is_valid("()))"))  # Too many closing parens.
assert_equal(want=False, got=is_valid("((()())))"))  # Too many closing parens.

4.2. See-saw

Modify your code from 1.1 to handle different kinds of square brackets [] and curly brackets {}.

You are given a string consisting of any of the characters ()[]{}. A string is valid if:

  • Each open bracket is matched by the correct closing bracket.
  • Open brackets are matched in the correct order.

Examples:

  • "{[]{()}}" is valid.
  • "[{}{}(]" is invalid.
In [ ]:
@debuggable
def is_valid(s):
    """Checks whether a string of parentheses, brackets, and square brackets is valid.

    Arguments: 
        s (str): String to be checked, consisting of the characters
          '(', ')', '[', ']', '{', or '}').

    Returns (bool): Whether the string has balanced
      parenstheses/brackets/square brackets.

    Effects: None.
    """
    # YOUR CODE HERE
In [ ]:
## Test your solution
assert_equal(want=True, got=is_valid("{[]{()}}"))
assert_equal(want=True, got=is_valid(""))
assert_equal(want=False, got=is_valid("[{}{}(]"))  # Opening parens, but closing square bracket
assert_equal(want=False, got=is_valid("]{}([{])}"))  # No matching opening square bracket for first character
assert_equal(want=False, got=is_valid("[()(){}}"))  # Last character should be a closing square bracket instead of closing bracket
assert_equal(want=False, got=is_valid("[{[[{"))  # Unmatched opening brackets.
assert_equal(want=False, got=is_valid("]})]}"))  # Unmatched closing brackets.
assert_equal(want=True, got=is_valid("()"))
assert_equal(want=True, got=is_valid("()[]{}"))
In [ ]: