JamCoders

💾 Download

# 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==", "ZGVmIG1ha2VfcHJldHR5X2Fzc2VydCgpOgogICAgaW1wb3J0IHN5cwogICAgaW1wb3J0IElQeXRob24KICAgIGltcG9ydCBhc3QKICAgIGltcG9ydCBpbnNwZWN0CiAgICBpbXBvcnQgaW8KICAgIGltcG9ydCBpdGVydG9vbHMKICAgIAogICAgZ2xvYmFsIG1ha2VfcHJldHR5X2Fzc2VydAogICAgZGVsIG1ha2VfcHJldHR5X2Fzc2VydAoKICAgIGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjUuNS4wIjoKICAgICAgICAjIGNvbGFiIFRPRE8KICAgICAgICBkZWYgZ2V0X2Fzc2VydF9saW5lKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGUiXQogICAgICAgIGRlZiBhdF90b3BfbGV2ZWwoZnJhbWUpOgogICAgICAgICAgICBjb2RlID0gZnJhbWUuZl9iYWNrLmZfYmFjay5mX2NvZGUKICAgICAgICAgICAgcmV0dXJuIGNvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKICAgICAgICBkZWYgY2FuX2Fubm90YXRlKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIEZhbHNlCgogICAgZWxpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI4LjQuMCI6CiAgICAgICAgIyBsYWIgY29tcHV0ZXJzCiAgICAgICAgZGVmIGdldF9hc3NlcnRfbGluZShmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9iYWNrLmZfbG9jYWxzWyJub2RlIl0KICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgY29kZSA9IGZyYW1lLmZfYmFjay5mX2JhY2suZl9jb2RlCiAgICAgICAgICAgIHJldHVybiBjb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpIGFuZCBjb2RlLmNvX25hbWUgPT0gInJ1bl9hc3Rfbm9kZXMiCiAgICAgICAgZGVmIGNhbl9hbm5vdGF0ZShmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhdF90b3BfbGV2ZWwoZnJhbWUpIGFuZCBGYWxzZQoKICAgIGRlZiBpc19saXRlcmFsKGEpOgogICAgICAgIHRyeToKICAgICAgICAgICAgYXN0LmxpdGVyYWxfZXZhbChhKQogICAgICAgICAgICByZXR1cm4gVHJ1ZQogICAgICAgIGV4Y2VwdCBWYWx1ZUVycm9yOgogICAgICAgICAgICByZXR1cm4gRmFsc2UKICAgICAgICByZXR1cm4gRmFsc2UKCgogICAgZGVmIGFubm90YXRlX2NhbGwoZnJhbWUpOgogICAgICAgIGlmIG5vdCBjYW5fYW5ub3RhdGUoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4KICAgICAgICAKICAgICAgICBleHByOiBhc3QuRXhwciA9IGdldF9hc3NlcnRfbGluZShmcmFtZSkKICAgICAgICBmb3Iga3dhcmcgaW4gZXhwci52YWx1ZS5rZXl3b3JkczoKICAgICAgICAgICAgaWYga3dhcmcuYXJnID09ICJnb3QiOgogICAgICAgICAgICAgICAgZ290ID0ga3dhcmcudmFsdWUKCiAgICAgICAgaWYgaXNpbnN0YW5jZShnb3QsIGFzdC5DYWxsKToKICAgICAgICAgICAgaWYgbm90IGlzaW5zdGFuY2UoZ290LmZ1bmMsIGFzdC5OYW1lKToKICAgICAgICAgICAgICAgIHJldHVybgogICAgICAgICAgICBuYW1lID0gZ290LmZ1bmMuaWQKICAgICAgICAgICAgZnVuYyA9IGZyYW1lLmZfbG9jYWxzW25hbWVdCiAgICAgICAgICAgIGlmIG5vdCBoYXNhdHRyKGZ1bmMsIERFQlVHR0FCTEVfQVJHUyk6CiAgICAgICAgICAgICAgICByZXR1cm4KICAgICAgICAgICAgYXJncyA9IGdldGF0dHIoZnVuYywgREVCVUdHQUJMRV9BUkdTKQogICAgICAgICAgICBrd2FyZ3MgPSBnZXRhdHRyKGZ1bmMsIERFQlVHR0FCTEVfS1dBUkdTKQogICAgICAgICAgICBib3VuZGFyZ3MgPSBpbnNwZWN0LnNpZ25hdHVyZShmdW5jKS5iaW5kKCphcmdzLCAqKmt3YXJncykKCiAgICAgICAgICAgIHJlc3VsdCA9IGlvLlN0cmluZ0lPKCkKICAgICAgICAgICAgcG9zID0gcmVzdWx0LndyaXRlKG5hbWUpCiAgICAgICAgICAgIHBvcyArPSByZXN1bHQud3JpdGUoIigiKQoKICAgICAgICAgICAgc2VwID0gJywgJwogICAgICAgICAgICBhcmdfdHVwbGVzID0gW10gICMgKGFzdF9hcmdfc3RyLCBldmFsdWF0ZWRfYXJnLCBzdGFydCwgbGltaXQpCgogICAgICAgICAgICAjIFVzZSBhbiBpdGVyYXRvciBoZXJlLiBJZiBhIGJvdW5kYXJnIGlzIG5vdCBjb25zdW1lZCBoZXJlLAogICAgICAgICAgICAjIGl0IG1heSBiZSBjb25zdW1lZCBsYXRlciBieSBhIHBvcytrdyBhcmcuCiAgICAgICAgICAgIGJvdW5kYXJnc19pdGVyID0gaXRlcihib3VuZGFyZ3MuYXJncykKICAgICAgICAgICAgZm9yIGFzdF9hcmcsIGFyZyBpbiB6aXAoZ290LmFyZ3MsIGJvdW5kYXJnc19pdGVyKToKICAgICAgICAgICAgICAgIGFzdF9hcmdfc3RyID0gYXN0LnVucGFyc2UoYXN0X2FyZykKICAgICAgICAgICAgICAgIGFyZ190dXBsZXMuYXBwZW5kKChhc3RfYXJnX3N0ciwgYXJnLCBwb3MsIHBvcyArIGxlbihhc3RfYXJnX3N0cikpKQogICAgICAgICAgICAgICAgcG9zICs9IGxlbihhc3RfYXJnX3N0cikgKyBsZW4oc2VwKQoKICAgICAgICAgICAgZm9yIGFzdF9rd2FyZywga3dhcmcgaW4gaXRlcnRvb2xzLnppcF9sb25nZXN0KGdvdC5rZXl3b3JkcywgYm91bmRhcmdzX2l0ZXIpOgogICAgICAgICAgICAgICAgYXN0X2FyZ19zdHIgPSBhc3QudW5wYXJzZShhc3Rfa3dhcmcpCiAgICAgICAgICAgICAgICBhcmdfdHVwbGVzLmFwcGVuZCgoYXN0X2FyZ19zdHIsIGt3YXJnLCBwb3MgKyBsZW4oYXN0X2t3YXJnLmFyZykgKyBsZW4oJz0nKSwgcG9zICsgbGVuKGFzdF9hcmdfc3RyKSkpCiAgICAgICAgICAgICAgICBwb3MgKz0gbGVuKGFzdF9hcmdfc3RyKSArIGxlbihzZXApCgogICAgICAgICAgICBwb3MgLT0gbGVuKHNlcCkKICAgICAgICAgICAgcmVzdWx0LndyaXRlKHNlcC5qb2luKHRbMF0gZm9yIHQgaW4gYXJnX3R1cGxlcykpCiAgICAgICAgICAgIHJlc3VsdC53cml0ZSgnKScpCiAgICAgICAgICAgIHJlc3VsdF9zdHIgPSByZXN1bHQuZ2V0dmFsdWUoKQoKICAgICAgICAgICAgeWllbGQgcmVzdWx0X3N0cgoKICAgICAgICAgICAgbm9ubGl0ZXJhbHMgPSBbXSAgIyAoZXZhbHVhdGVkX2FyZywgcmVzdWx0X3N0ciwgc3RhcnQsIGxpbWl0KQogICAgICAgICAgICBmb3IgXywgZXZhbHVhdGVkX2FyZywgc3RhcnQsIGxpbWl0IGluIGFyZ190dXBsZXM6CiAgICAgICAgICAgICAgICBpZiBub3QgaXNfbGl0ZXJhbChyZXN1bHRfc3RyW3N0YXJ0OmxpbWl0XSk6CiAgICAgICAgICAgICAgICAgICAgbm9ubGl0ZXJhbHMuYXBwZW5kKChldmFsdWF0ZWRfYXJnLCByZXN1bHRfc3RyW3N0YXJ0OmxpbWl0XSwgc3RhcnQsIGxpbWl0KSkKCiAgICAgICAgICAgIHVuZGVybGluZXMgPSBpby5TdHJpbmdJTygpCiAgICAgICAgICAgIHBvcyA9IDAKICAgICAgICAgICAgZm9yIF8sIF8sIHN0YXJ0LCBsaW1pdCBpbiBub25saXRlcmFsczoKICAgICAgICAgICAgICAgIGlmIChsaW1pdCAtIHN0YXJ0KSA8IDM6CiAgICAgICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJyAnICogKHN0YXJ0IC0gcG9zKSkKICAgICAgICAgICAgICAgICAgICBwb3MgKz0gdW5kZXJsaW5lcy53cml0ZSgn4oaRJykKICAgICAgICAgICAgICAgICAgICBwb3MgKz0gdW5kZXJsaW5lcy53cml0ZSgn4oaRJyAqIChsaW1pdCAtIHBvcykpCiAgICAgICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgICAgIGlkeCA9IHN0YXJ0ICsgKGxpbWl0IC0gc3RhcnQpIC8vIDIKICAgICAgICAgICAgICAgIHBvcyArPSB1bmRlcmxpbmVzLndyaXRlKCcgJyAqIChzdGFydCAtIHBvcykpCiAgICAgICAgICAgICAgICAjcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KVmScpCiAgICAgICAgICAgICAgICBwb3MgKz0gdW5kZXJsaW5lcy53cml0ZSgn4oaRJyAqIChpZHggLSBwb3MpKQogICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScpCiAgICAgICAgICAgICAgICBwb3MgKz0gdW5kZXJsaW5lcy53cml0ZSgn4oaRJyAqIChsaW1pdCAtIHBvcykpCiAgICAgICAgICAgICAgICAjcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KVnCcpCiAgICAgICAgICAgIHlpZWxkIHVuZGVybGluZXMuZ2V0dmFsdWUoKQoKICAgICAgICAgICAgZGVmIG1ha2VfYmFyc19idWYobm9ubGl0ZXJhbHMsIGVuZCwgZXZhbGVkKToKICAgICAgICAgICAgICAgIGJ1ZiA9IGlvLlN0cmluZ0lPKCkKICAgICAgICAgICAgICAgIHBvcyA9IDAKICAgICAgICAgICAgICAgIGZvciBpIGluIHJhbmdlKGxlbihub25saXRlcmFscykgLSAxKToKICAgICAgICAgICAgICAgICAgICBfLCBfLCBzdGFydCwgbGltaXQgPSBub25saXRlcmFsc1tpXQogICAgICAgICAgICAgICAgICAgIGlmIChsaW1pdCAtIHN0YXJ0KSA8IDM6CiAgICAgICAgICAgICAgICAgICAgICAgIGlkeCA9IHN0YXJ0CiAgICAgICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICAgICAgaWR4ID0gc3RhcnQgKyAobGltaXQgLSBzdGFydCkgLy8gMgogICAgICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJyAnICogKGlkeCAtIHBvcykpCiAgICAgICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgn4pSCJykKICAgICAgICAgICAgICAgICAgICBwb3MgKz0gYnVmLndyaXRlKCcgJyAqIChsaW1pdCAtIHBvcykpCgogICAgICAgICAgICAgICAgXywgcmVzdWx0X3N0ciwgc3RhcnQsIGxpbWl0ID0gbm9ubGl0ZXJhbHNbLTFdCiAgICAgICAgICAgICAgICBpZiAobGltaXQgLSBzdGFydCkgPCAzOgogICAgICAgICAgICAgICAgICAgIGlkeCA9IHN0YXJ0CiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIGlkeCA9IHN0YXJ0ICsgKGxpbWl0IC0gc3RhcnQpIC8vIDIgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICBwb3MgKz0gYnVmLndyaXRlKCcgJyAqIChpZHggLSBwb3MpKQogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgn4pSUJykKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJ+KUgCcgKiAoZW5kIC0gMSAtIHBvcykpCiAgICAgICAgICAgICAgICBwb3MgKz0gYnVmLndyaXRlKCfilbQnKQogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZShyZXN1bHRfc3RyKQogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgnIOKJlCAnKQogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZShzdHIoZXZhbGVkKSkKCiAgICAgICAgICAgICAgICByZXR1cm4gYnVmLCBwb3MKCiAgICAgICAgICAgIHdoaWxlIG5vbmxpdGVyYWxzOgogICAgICAgICAgICAgICAgYnVmLCBwb3MgPSBtYWtlX2JhcnNfYnVmKG5vbmxpdGVyYWxzLCBsZW4ocmVzdWx0X3N0cikgKyA0LCBub25saXRlcmFsc1stMV1bMF0pCiAgICAgICAgICAgICAgICB5aWVsZCBidWYuZ2V0dmFsdWUoKQogICAgICAgICAgICAgICAgbGFzdCA9IG5vbmxpdGVyYWxzLnBvcCgpCgogICAgZGVmIGFzc2VydF9lcXVhbCgqLCB3YW50LCBnb3QsIG91dD1zeXMuc3Rkb3V0KToKICAgICAgICBpZiB3YW50ID09IGdvdDoKICAgICAgICAgICAgcHJpbnQoIlRlc3QgY2FzZSBwYXNzZWQuIikKICAgICAgICAgICAgcmV0dXJuCgogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKCiAgICAgICAgYm94X3BhZGRpbmcgPSAyCiAgICAgICAgaGVhZGVyID0gIiBUZXN0IGNhc2UgZmFpbGVkLiAiCiAgICAgICAgd2FudF9saW5lID0gZiJ7Ym94X3BhZGRpbmcgKiAnICd9V2FudDoge3JlcHIod2FudCl9ICh0eXBlOiB7dHlwZSh3YW50KS5fX25hbWVfX30pIgogICAgICAgIGdvdF9saW5lID0gZiJ7Ym94X3BhZGRpbmcgKiAnICd9R290OiAge3JlcHIoZ290KX0gKHR5cGU6IHt0eXBlKGdvdCkuX19uYW1lX199KSIKICAgICAgICAKICAgICAgICBpZiBjYW5fYW5ub3RhdGUoZnJhbWUpOgogICAgICAgICAgICBhc3NlcnRfbGluZSA9IGYie2JveF9wYWRkaW5nICogJyAnfT4+PiB7YXN0LnVucGFyc2UoZ2V0X2Fzc2VydF9saW5lKGZyYW1lKSl9IgogICAgICAgIGVsc2U6CiAgICAgICAgICAgIGFzc2VydF9saW5lID0gIiIKICAgICAgICAgICAgCiAgICAgICAgZGVidWdfbGluZXMgPSBsaXN0KGFubm90YXRlX2NhbGwoZnJhbWUpKQogICAgICAgIGlmIGRlYnVnX2xpbmVzOgogICAgICAgICAgICBnb3RfbGluZSArPSAiIOKGkCAiCiAgICAgICAgICAgIHBhZGRpbmcgPSBsZW4oZ290X2xpbmUpCiAgICAgICAgICAgIGdvdF9saW5lICs9IGRlYnVnX2xpbmVzWzBdCgogICAgICAgIHBhZGRlZF9kZWJ1Z19saW5lcyA9IFtdCiAgICAgICAgZm9yIGksIGxpbmUgaW4gZW51bWVyYXRlKGRlYnVnX2xpbmVzKToKICAgICAgICAgICAgICAgIGlmIGkgPT0gMDoKICAgICAgICAgICAgICAgICAgICBjb250aW51ZQogICAgICAgICAgICAgICAgcGFkZGVkX2RlYnVnX2xpbmVzLmFwcGVuZCgnICcgKiBwYWRkaW5nICsgbGluZSkKICAgICAgICAgICAgICAgIAogICAgICAgIGxpbmVfbWF4X2xlbiA9IG1heChsZW4obCkgKyBib3hfcGFkZGluZyBmb3IgbCBpbiAoYXNzZXJ0X2xpbmUsIHdhbnRfbGluZSwgZ290X2xpbmUsICpwYWRkZWRfZGVidWdfbGluZXMpKQogICAgICAgIGxpbmVfbWF4X2xlbiA9IG1heCgzMiwgbGluZV9tYXhfbGVuKQogICAgICAgIGhlYWRlcl9kYXNoZXMgPSBsaW5lX21heF9sZW4gLSBsZW4oaGVhZGVyKQoKCiAgICAgICAgcHJpbnQoZmlsZT1vdXQpCiAgICAgICAgcHJpbnQoJy0nICogKGhlYWRlcl9kYXNoZXMgLy8gMiksIGVuZD0iIiwgZmlsZT1vdXQpCiAgICAgICAgcHJpbnQoaGVhZGVyLCBlbmQ9IiIsIGZpbGU9b3V0KQogICAgICAgIHByaW50KCctJyAqICgoaGVhZGVyX2Rhc2hlcyArIDEpIC8vIDIpLCBlbmQ9IiIsIGZpbGU9b3V0KQogICAgICAgIHByaW50KGZpbGU9b3V0KQogICAgICAgIHByaW50KGZpbGU9b3V0KQoKICAgICAgICAKICAgICAgICBpZiBhc3NlcnRfbGluZToKICAgICAgICAgICAgcHJpbnQoYXNzZXJ0X2xpbmUsIGZpbGU9b3V0KQogICAgICAgICAgICBwcmludChmaWxlPW91dCkKCiAgICAgICAgcHJpbnQod2FudF9saW5lLCBmaWxlPW91dCkKICAgICAgICBwcmludChnb3RfbGluZSwgZmlsZT1vdXQpCiAgICAgICAgZm9yIGxpbmUgaW4gcGFkZGVkX2RlYnVnX2xpbmVzOgogICAgICAgICAgICBwcmludChsaW5lLCBmaWxlPW91dCkKICAgICAgICAKICAgICAgICBwcmludChmaWxlPW91dCkKICAgICAgICBwcmludCgnLScgKiBsaW5lX21heF9sZW4sIGZpbGU9b3V0KQogICAgICAgIHByaW50KGZpbGU9b3V0KQogICAgICAgIAogICAgREVCVUdHQUJMRV9BUkdTID0gIl9kZWJ1Z2dhYmxlX2FyZ3MiCiAgICBERUJVR0dBQkxFX0tXQVJHUyA9ICJfZGVidWdnYWJsZV9rd2FyZ3MiCgogICAgZGVmIGRlYnVnZ2FibGUoZik6CiAgICAgICAgaW1wb3J0IGZ1bmN0b29scwogICAgICAgIEBmdW5jdG9vbHMud3JhcHMoZikKICAgICAgICBkZWYgZygqYXJncywgKiprd2FyZ3MpOgogICAgICAgICAgICByZXN1bHQgPSBmKCphcmdzLCAqKmt3YXJncykKICAgICAgICAgICAgc2V0YXR0cihnLCBERUJVR0dBQkxFX0FSR1MsIGFyZ3MpCiAgICAgICAgICAgIHNldGF0dHIoZywgREVCVUdHQUJMRV9LV0FSR1MsIGt3YXJncykKICAgICAgICAgICAgcmV0dXJuIHJlc3VsdAogICAgICAgIHJldHVybiBnCiAgICAKICAgIHJldHVybiBhc3NlcnRfZXF1YWwsIGRlYnVnZ2FibGUKCmFzc2VydF9lcXVhbCwgZGVidWdnYWJsZSA9IG1ha2VfcHJldHR5X2Fzc2VydCgpCg==")
    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 16, Lab B: Classes

Question 0: What's in a class?

Classes provide a means of bundling data and functionality together. Creating a new class creates a new type of object, allowing new instances of that type to be made. Each class instance can have attributes attached to it for maintaining its state. Class instances can also have methods (defined by its class) for modifying its state. [The Python Tutorial, Chapter 9]

In this lab, we'll think about three important components of a class:

• Attributes: data that an instance of a class "remembers" about its state.
• Methods: functions associated with a class that may change its attributes.
• Initializer: a special method that creates a new instance of a class.

Let's take a look at a simple class that represents a student.

class Student:
    """Represents a high school student (name, age and school).
    """
    def __init__(self, name, school, form):
        """Creates a representation of a student.
        
        Arguments: name (str), form (int, between 1 and 6), school (str).
        Effects: Initializes the Student instance.
        """
        self.name = name
        self.school = school
        self.form = form
        self.graduated = False
    
    def next_year(self):
        """Advances the student to the next school year.
        
        Effects: Updates the student's form or graduated attribute.
        """
        if self.form == 6:
            self.graduated = True
        else:
            self.form += 1
    
    def can_attend_jamcoders(self):
        """Checks whether the student can attend JamCoders.
        
        Returns: (bool).
        Effects: No effects.
        """
        return self.form <= 5 and self.form >= 3

Let's look at the components of the above code piece by piece (we'll skip docstrings).

class Student:

The class keyword tells Python we are declaring a class, and Student is the name of the class. The three functions defined in this scope are methods of Student.

def __init__(self, name, school, form):
            self.name = name
            self.school = school
            self.form = form
            self.graduated = False

The initalizer method of the Student class. In Python, the initializer is named __init__ (we'll see how to call it in a bit). The initializer takes in values of three of the attributes: name, school and form. The attribute graduated is always initialized to be False.

def next_year(self):
        if self.form == 6:
            self.graduated = True
        else:
            self.form += 1

    def can_attend_jamcoders(self):
        return self.form <= 5 and self.form >= 3

Two more methods of the Student class. The nice thing about classes is that they bundle together data and how to interact with it. In this case, the next_year method handles the logic behind checking whether a student has graduated. Similarly, can_attend_jamcoders keeps the logic of the JamCoders student requirements (between third and fifth form) neatly with the relevant data (form).

0.1 Using classes

Here's how we use classes in Python:

alani = Student("Alani", "Immaculate", 5) # Calls the __init__ function
print(alani.name)                         # Access attributes using a dot .
print(alani.school)
print(alani.form)
print(alani.can_attend_jamcoders())       # Similarly, call methods using a dot .

Soon the summer will be over, and Alani will be in sixth form. Could Alani attend JamCoders next year as well?

alani.next_year()
print(alani.can_attend_jamcoders())

0.2 Mystery student

Next, we'll load a mystery student. Can you find out their identity using attributes and methods?

mystery_student = uh(b'U3R1ZGVudCgiQ2xheXRvbiIsICJHbGVubXVpciIsIDUp') # Weird code that loads the mystery student

# Your code here

Question 1: Stacks, revisited

Last week (probs13a) we introduced the Stack data structure. We then implemented the following interface:

• 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.

It's natural to think of a Stack as a Class; then, the above interface will instead be implemented as methods of this class---rather than a collection of functions that happen to end with _s.

1.1 Implementing the Stack class

Next, we'll implement a stack (again), this time as a class called Stack. Feel free to adapt your solution to question 2.2 in probs13a.

class Stack:
    """An implementation of the stack data structure.
    """
    @debuggable
    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[:]

    @debuggable
    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.
        """
        # YOUR CODE HERE


    @debuggable
    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()


    @debuggable
    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.
        """
        return self.data[-1]


    @debuggable
    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 == []

# Test stacks with integers.
stack = Stack()

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

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

assert_equal(want=3, got=stack.top())

assert_equal(want=False, got=stack.is_empty())


# Test stack with other types.
stack = Stack()
stack.push("Hello")
stack.push("Goodbye")
stack.push([])

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


# Test empty stacks.
stack = Stack()
assert_equal(want=True, got=stack.is_empty())

1.2 Mind the (syntax) gap

Let's take a moment to look the differences between the old implementation and the new one. The following table compares code for initializing and manipulating a stack stck in both implementations.

Operation	Stack class	probs13b implementation
Initialize stck	stck = Stack()	stck = init_s()
Push elem	stck.push(elem)	push_s(stck, elem)
Pop	stck.pop()	pop_s(stck)
Peek	stck.peek()	peek_s(stck)
Check if empty	stck.is_empty()	is_empty_s(stck)

Which syntax do you like better? Why?

# Your thoughts here

1.3 Hiding details, catching bugs

Alright, so we dropped the _s's and use .'s instead. But is there any other difference other than the way we write our programs?

Yes! If we use classes, Python can protect us from sneaky bugs. Look back at the interface of Stack. Notice that it does not support arbitrary access to elements: unlike Lists, you should not be able to use stack[i] to access the i-th element of a stack---the whole point of using a Stack is that you can only access the topmost element!

Recall our old implementation of Stack, from probs13b

def init_s(lst=[]):
    """Old code for implementing a stack, from probs13b.
    """
    if lst is None:
        return []
    return lst[:]

def push_s(stack, elem):
    stack.append(elem)

def top_s(stack):
    return stack[-1]

We now have a stack of three dirty plates. Without popping the top plate (Bereket's), we should not be able to access any of the other plate. Imagine grabbing a plate from the middle of a stack of dirty dishes---the whole thing would come tumbling down!

print(f"Plate on top is: {top_s(dishes)}") # Prints Top; ok.
print(f"Grabbing {dishes[1]}")      # Oops! We aren't supposed to do this!
print("Boom, crash, clang!")

Uh oh! The problem was that we accessed dishes[1]; dishes is a Stack, but Python allowed us to access the underlying list and grab Tyler's Bowl from the middle... If we use the Stack class, this issue cannot happen. Take a look:

dishes = Stack()
dishes.push("Orr's Cup")
dishes.push("Tyler's Bowl")
dishes.push("Berket's Bowl")
print(f"Plate on top is: {dishes.top()}") # Prints Top; ok.
print(f"Grabbing plate {dishes[1]}")      # Oops! We aren't supposed to do this!
print("Boom, crash, clang!")

Take a look at the last line above. See that TypeError? 'Stack' is not subscriptable is Python's way of telling us that you cannot access any element you want from a Stack. Thanks, Python!

More generally, this concept is called encapsulation. From Wikipedia:

Encapsulation is used to hide the values or state of a structured data object inside a class, preventing direct access to them by clients in a way that could expose hidden implementation details or violate state invariance maintained by the methods.

By hiding our implementation details (the fact that our Stack is based on an underlying List), we prevented users from violating an important invariance of the Stack (that only the top object may be accessed).

Question 2: Graphs

Remember last week's Graphs lab (jamcoders_14a)? Ever wondered how graphs were really stored on the computer? In this question we'll offer one possible answer by implementing our very own Graph class!

🔔 Reminder 🔔

An undirected graph is a mathematical object that consists of nodes and edges. Each edge represents a connection between two nodes.

• This is a graph with three vertices and three edges:

• And this is a graph with 102 vertices and 153 edges:

2.1 The plan

There are many ways to implement graphs in a computer, each with its own advantages and disadvantages. We'll base our implementation on a dict because it's simple (and relatively fast).

This is the plan:

• The Graph class is initialized with an empty dict attribute called self.data.
• The keys of self.data are strings that represent nodes in the graph. The value of each key is the adjacency list of the node.
  • For example, having self.data == {'a': ['b', 'c'], 'b': ['a', 'c'], 'c': ['a', 'b']} means that our graph has three nodes, where each node is connected to all other nodes -- a triangle (like in the reminder).
• Nodes are added by calling graph.add_node(node_label) method. Each node has a string label. When a node is just added, its adjacency list is empty.
• Edges are added with the graph.add_edge(node1, node2) method.
  • You may assume that the nodes are different (no loops).
  • Since we are implementing undirected graphs, you will need to update the adjacency list of node1 and node2.
• The graph.get_nodes() method returns a list of all nodes in the graph. We've implemented this method for you.
• The graph.get_neighbors(node) method returns a list of nodes neighboring node (i.e., that share an edge with node).
• A draw method. We've implemented this method for you.

2.2 Implementing undirected graphs

Alright, let's do this. Replace the # YOUR CODE HERE's in the next cell with, umm, your code.

`class Graph:
    """Represents a mathematical graph consisting of nodes and edges.
    """
    
    def __init__(self):
        """Initializes an empty graph.
        """
        # Initialize self.data with an empty dict
        # Eventually, this dict will map {node: [list of neighbors]}.
        self.data = # YOUR CODE HERE
    
    def add_node(self, node_label):
        """Adds a node to the graph.
        
        The node is associated with a string node_label which is used to add edges to it later.
        If a node associated with node_label already exists, does nothing.
        Arguments: node_label (string).
        Returns: (None).
        Effects: Modifies the graph. If the node already exists, does nothing.
        """
        # First, check if a node associated with node_label already exists
        # Hint: The expression "k in dict" is True if dict has a key called 'k' (else False).
        # If the node doesn't already exist, add it by initializing an empty adjacency list []
        self.data[node_label] = # YOUR CODE HERE
    
    def add_edge(self, node1, node2):
        """Connects node1 and node2 with an edge.
        Arguments: node1 (string), node2 (string).
        Returns: (None).
        Effects: Modifies the graph. If an edge already exists, does nothing.
        """
        # First, check if the nodes are already connected
        # Hint: The expression "x in list" is True if list contains the element 'x' (else False).
        # If they aren't already connected, connect them by adding each to the other's adjacency list.
        self.data[node1] += # YOUR CODE HERE
        self.data[node2] += # YOUR CODE HERE
        
    def get_nodes(self):
        """Returns a list of all nodes in the graph. (Already implemented by TAs)
        Returns: (list of strings).
        Effects: None.
        """
        return list(self.data.keys()) # Need to cast to list because .keys() returns a dict_keys object...
    
    def get_neighbors(self, node):
        """Returns list of neighbors of node.
        Arguments: node (string).
        Returns: (list of string).
        Effects: None.
        """
        # YOUR CODE HERE
    
    def draw(self):
        """Draws graph. (Already implemented by TAs)
        Effects: Prints drawing of graph.
        """
        # Create set of edges
        edges = set(tuple(sorted([u, v])) for u, neighbs in self.data.items() for v in neighbs)
        # Create nx graph
        nx_graph = nx.Graph()
        nx_graph.add_edges_from(edges)
        # Draw
        nx.draw(nx_graph, with_labels=True)

Now let's test your code.

# Test your code by running this cell.

# Test graph init, adding two nodes and connecting them.
graph = Graph()
assert_equal(want=None, got=graph.add_node("a"))
assert_equal(want=[], got=graph.get_neighbors("a"))
assert_equal(want=["a"], got=graph.get_nodes())
assert_equal(want=None, got=graph.add_node("b"))
sae(want=["a", "b"], got=graph.get_nodes()) # Sort because order doesn't matter.
assert_equal(want=[], got=graph.get_neighbors("a"))
assert_equal(want=[], got=graph.get_neighbors("b"))
assert_equal(want=None, got=graph.add_edge("a", "b"))
assert_equal(want=["b"], got=graph.get_neighbors("a"))
assert_equal(want=["a"], got=graph.get_neighbors("b"))

# Test adding an existing node
assert_equal(want=None, got=graph.add_node("a"))
sae(want=["a", "b"], got=graph.get_nodes())
# Test adding an existing edge
assert_equal(want=None, got=graph.add_edge("a", "b"))
assert_equal(want=None, got=graph.add_edge("b", "a")) # Reverse order, shouldn't matter.
assert_equal(want=["b"], got=graph.get_neighbors("a"))
assert_equal(want=["a"], got=graph.get_neighbors("b"))

# Test adding a new node "c" and connect it to "b"
assert_equal(want=None, got=graph.add_node("c"))
sae(want=["a", "b", "c"], got=graph.get_nodes())
assert_equal(want=None, got=graph.add_edge("c", "b"))
sae(want=["a", "c"], got=graph.get_neighbors("b"))
sae(want=["b"], got=graph.get_neighbors("c"))
# Now connect "c" to "a" to form a triangle
assert_equal(want=None, got=graph.add_edge("c", "a"))
sae(want=["b", "c"], got=graph.get_neighbors("a"))
sae(want=["a", "b"], got=graph.get_neighbors("c"))

graph.draw() # Should look like a triangle

2.3 Challenge: Removing edges and nodes

Sometimes we want to remove edges from a graph. In this challenge you will enrich your Graph class with this functioanlity.

class Graph2(Graph):
    def remove_edge(self, node1, node2):
        """Removes an edge between node1 and node2 if it exists. If it doesn't, does nothing.
        Arguments: node1 (string), node2 (string).
        Effects: Modifies the graph. If no edge was present, does nothing.
        """
        # Hint: list.remove(elem) removes elem from list -- if it exists.
        #       list.remove(elem) will error if elem is not in list. So check that first.
        # YOUR CODE HERE

    def remove_node(self, node):
        """Removes node and all edges touching it. If node is not in graph, does nothing.
        Arguments: node (string).
        Effects: Modifies the graph. If node was not in the graph, does nothing.
        """
        # Hint #1: See previous hint...
        if node not in self.get_nodes():
            return
        
        neighbors_copy = self.get_neighbors(node)[:]
        # Ponder: why must we make a copy of the neighbors list above?
        for neighbor in neghighbors_copy:
            # YOUR CODE HERE
        
        # Finally, delete the node entry from self.data
        # Hint #2: 'del dict[k]' deletes key 'k' from dict.
        # YOUR CODE HERE

Next you can test your code. You may uncomment the graph.draw() statements one-at-a-time to see the graph change (be sure to uncomment them only one at a time, else all the drawings will render on top of each other...)

# Now test your code
from itertools import permutations

# Create a 4-clique (square with both diagonals).
graph = Graph2()
# We'll access data manually to avoid writing 4 + (4 choose 2) = 10 lines of code
graph.data = {x: [y, z, w] for x, y, z, w in permutations(['a', 'b', 'c', 'd'])}
# graph.draw()

# Then remove the edge between 'a' and 'b'
assert_equal(want=None, got=graph.remove_edge('a', 'b'))
sae(want=['c', 'd'], got=graph.get_neighbors('a'))
sae(want=['c', 'd'], got=graph.get_neighbors('b'))
sae(want=['a', 'b', 'd'], got=graph.get_neighbors('c'))
sae(want=['a', 'b', 'c'], got=graph.get_neighbors('d'))
# graph.draw()

# Then remove the node 'c'
assert_equal(want=None, got=graph.remove_node('c'))
sae(want=['d'], got=graph.get_neighbors('a'))
sae(want=['d'], got=graph.get_neighbors('b'))
sae(want=['a', 'b'], got=graph.get_neighbors('d'))
# graph.draw()

Challenge Question 3: Queues, revisited (on your own)

Design and implement the Queue class, which supports the following operations:

• Initialize: Constructs a new empty queue.
• Enqueue: Adds an element to the back of the queue.
• Peek: Returns the value of the frontmost element in the queue, without removing it.
• Deqeueue: Removes the frontmost element in the queue and returns its value.
• Is empty?: Returns whether or not queue is empty.

You may want to refer to your solution of Question 1 in this notebook, and Question 1 in probs13a. The challenging aspect of this question is in writing a bunch of code on your own, without guidance and ready-made tests.

class Queue:
    """An implementation of the queue data structure
    """
    # YOUR CODE HERE