JamCoders

 💾 Download
In [1]:
%config InteractiveShell.ast_node_interactivity="none"
import base64

def f(globals, locals):
    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))

Day 16, Lab A: Memoization

1 Coin Change

We saw, in lecture, the coin change problem: given a set of coin denominations and a target coin value, find the smallest number of coins that add up to that value. For example, what is the smallest set of coins you need to get J\$75, using the Jamacian coins J\$1, J\$5, J\$10, J\$20? (5 coins: J\$20 + J\$20 + J\$20 + J\$10 + J\$5).

We want to create an algorithm that, given any set of coin denominations and a target value, finds the smallest set of coins for us.

1.1 Pot of Greed

The first idea that might come to mind is to be greedy. That is, keep choosing the largest coin that doesn't make your total larger than the target value. This works for some sets of coin denominations. For example, a greedy algorithm always will find the smallest combination of coins when you use the Jamacian coins (J\$1, J\$5, J\$10, J\$20).

Using the greedy algorithm, what Jamaican coins would you choose that add up to J\$34?

In [ ]:
# What Jamaican coins would the greedy algorithm use to add up to J$34?
# Write your answer in the array below as integers.
# For example, [20, 20, 20, 10, 5] would represent J$20 + J$20 + J$20 + J$10 + J$5.

coins =    # YOUR ANSWER HERE

assert_equal(want=uh("WzIwLCAxMCwgMSwgMSwgMSwgMV0="), got=sorted(coins, reverse=True))

Using the greedy algorithm, what US coins would you choose that add up to 30¢? Recall that the US coin denominations are 1¢, 5¢, 10¢, and 25¢.

In [ ]:
# What US coins would would the greedy algorithm use to add up to 30¢?
# The US coins are 1¢, 5¢, 10¢, and 25¢.
# Write your answer in the array below as integers.
# For example, [25, 25, 25] would represent 25¢ + 25¢ + 25¢.

coins =    # YOUR ANSWER HERE

assert_equal(want=uh("WzI1LCA1XSA="), got=sorted(coins, reverse=True))

What if we weren't allowed to use the 5¢ coin? What coins would the greedy algorithm choose?

In [ ]:
# What US coins would the greedy algorithm use to add up to 30¢, without the 5¢ coin?
# Use the coins 1¢, 10¢, and 25¢. 

coins =    # YOUR ANSWER HERE

assert_equal(want=uh("WzI1LCAxLCAxLCAxLCAxLCAxXQ=="), got=sorted(coins, reverse=True))

Is this the least number of coins? Can you do better?

In [ ]:
# What US coins would *you* use to make 30¢?
# Use the coins 1¢, 10¢, and 25¢. 

coins =    # YOUR ANSWER HERE

assert_equal(want=uh("WzEwLCAxMCwgMTBd"), got=sorted(coins, reverse=True))

Why doesn't greedy work? Think, then run the code below for our answer.

In [ ]:
exec(base64.b64decode("aW1wb3J0IHRleHR3cmFwCgp0ZXh0ID0gJ0dyZWVkeSBhbGdvcml0aG1zIGFsd2F5cyB0YWtlIHRoZSAiYmVzdCIgY3VycmVudCBvcHRpb24uIEJ1dCBzb21ldGltZXMgaXRcJ3MgZ29vZCB0byBsb29rIGFoZWFkOiB0aGUgc2hvcnQgdGVybSBiZXN0IG9wdGlvbiBpcyBub3QgYWx3YXlzIHRoZSBsb25nIHRlcm0gYmVzdCBvcHRpb24uIEEgc21hbGwgc2FjcmlmaWNlIG5vdyAodGFraW5nIHRoZSAxMMKiIGluc3RlYWQgb2YgdGhlIDI1wqIpIGNhbiB0cmFuc2xhdGUgaW50byBhIGJpZyB3aW4gaW4gdGhlIGZ1dHVyZS4nCnByaW50KCdcbicuam9pbih0ZXh0d3JhcC53cmFwKHRleHQsIDgwKSkp"))

1.2 Greed isn't good

If greedy doesn't work, how can we proceed? We can always use brute force.

For the first coin, we know we must choose one of the coins in our set. Why not try all of them?

Let's try the above problem again: we want to make 30¢ out of 1¢, 10¢, and 25¢ coins. We can try each one:

$$ \texttt{coin_change(30)} \\ \begin{align*} 30¢& - 1¢ &=\;&29¢ \\ 30¢& - 10¢ &=\;&20¢ \\ 30¢& - 25¢ &=\;&5¢ \\ \end{align*} $$

Notice that after choosing one coin, we now have a coin change problem for a smaller value. How do we find coins that add up to that value? We can recursively call ourselves, of course, and take the minimum. For example, here are the recursive calls for coin_change(30):

$$ \texttt{coin_change(30)} \\ \begin{align*} 30¢& - 1¢ &=\;&29¢ &\rightarrow \texttt{coin_change(29)} \\ 30¢& - 10¢ &=\;&20¢ &\rightarrow \texttt{coin_change(20)} \\ 30¢& - 25¢ &=\;&5¢ &\rightarrow \texttt{coin_change(5)} \\ \end{align*} $$

Fill in the skeleton for coin_change below.

In [ ]:
@debuggable
def coin_change(target, coins):
    """Finds a list of coins with smallest size that adds up to target.
    
    Arguments:
        target: The value to reach.
        coins: The allowed (positive) denominations of coins.
        
    Returns (list or None):
        The smallest list of coins that add up to `target`.
        If there is no possible way to add to `target`, returns None.
    """
    # Base cases.
    if ________________:                  # YOUR CODE HERE
        return ________________           # YOUR CODE HERE
    
    if ________________:                  # YOUR CODE HERE
        return ________________
    
    # Recursive case.
    best = None
    for coin in coins:
        result = ______________________   # YOUR CODE HERE
        if result is None:
            continue
        
        if best is None or ___________ < ___________:   # YOUR CODE HERE
            best = [coin] + result
        
    return best


assert_equal(want=[10, 10, 10], got=coin_change(30, [1, 10, 25]))
assert_equal(want=[5, 1, 1, 1], got=coin_change(8, [1, 5, 10, 20]))
assert_equal(want=[10, 5, 1, 1], got=coin_change(17, [20, 10, 5, 1]))
assert_equal(want=[4, 4], got=coin_change(8, [20, 10, 5, 4, 1]))
assert_equal(want=[5, 4], got=coin_change(9, [1, 4, 5, 10, 20]))
assert_equal(want=[], got=coin_change(0, [20, 10, 5, 1]))

1.3 coin_change allows me to create FOUR MORE CALLS

Try running your coin_change operation on larger values of target. How long does it take?

If your code runs for too long because target was too big, you can press the stop button in Jupyter (⏹).

In [ ]:
# Try running coin_change below.

for i in (10, 20, 30, 40, 50, 60, 70, 80, 90, 100):
    print(i, end="\t")
    repeats = 7 if i < 50 else 1
    get_ipython().run_line_magic('timeit', f'-r {repeats} coin_change(i, [1, 5, 10, 20])')

Why is coin_change taking so long? The call to coin_change(50) creates four new recursive calls to coin_change(49), coin_change(45), coin_change(40), and coin_change(30). Each one of those creates four new recursive calls as well, and so on. The total amount of work done is exponential; $\mathcal{O}(b^n)$ (where $b$ is some base that depends on the coins that are passed in).

Exponential growth is extremely fast. Here are the running times for coin_change from my laptop:

target time multiplier from previous
10 0.0000171s
20 0.000379s x22.1
30 0.00816s x21.6
40 0.176s x21.5
50 3.78s x21.5
60 81.6s x21.6
70 29m 50s x21.9
80 10h 53m (estimate) x21.9
90 9d 22h (estimate) x21.9
100 217d 12h (estimate) x21.9

But clearly we can do better. It doesn't take a cashier 9 days to give you J\$90 in coins!

How can we make coin_change run faster? Below is coin_change_count, which counts how many times coin_change calls itself on a particular target value:

In [ ]:
# Don't worry about understanding this code.
@debuggable
def coin_change_count(target, coins, count_target):
    # Replace the global coin_change with our own function...
    global coin_change
    # Save the real coin change function so we can restore it later.
    real_coin_change = coin_change
    counter = 0
    def counting_coin_change(t, c):
        # Need nonlocal to write to the counter in the parent scope.
        nonlocal counter
        if t == count_target:
            counter += 1
        return real_coin_change(t, c)
    coin_change = counting_coin_change

    # Call our counting_coin_change function.
    coin_change(target, coins)
    
    # Restore the real coin change function.
    coin_change = real_coin_change
    
    return counter


# How many times do we recursively call coin_change(10) in for each of
# coin_change(10), coin_change(20), ..., coin_change(60)?
assert_equal(want=1, got=coin_change_count(10, [1, 5, 10, 20], count_target=10))
assert_equal(want=9, got=coin_change_count(20, [1, 5, 10, 20], count_target=10))
assert_equal(want=198, got=coin_change_count(30, [1, 5, 10, 20], count_target=10))
assert_equal(want=4287, got=coin_change_count(40, [1, 5, 10, 20], count_target=10))
assert_equal(want=92249, got=coin_change_count(50, [1, 5, 10, 20], count_target=10))
assert_equal(want=1984369, got=coin_change_count(60, [1, 5, 10, 20], count_target=10))

We're repeating the call to coin_change(10) many thousands of times. Why? coin_change(10) is called by coin_change(11), coin_change(15), coin_change(20), and coin_change(30), which are themselves called many times. But we know that each time they are called, they return the same thing. What if we remembered the result for each call, and returned it instead of recomputing the result?

2 Memoization

2.1 Fibonacci

Let's take a detour and return to the Fibonacci numbers. Recall that the Fibonacci sequence is defined recursively, with $f_0 = 0$, $f_1 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for all $n \geq 2$. Below is an implementation:

In [ ]:
@debuggable
def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    return fib(n - 1) + fib(n - 2)

%timeit fib(30)

What is the running time of fib(n)? Let's observe two things.

  1. First, whenever we call fib, we are either returning the result of two subcalls, or returning a base case. The only "numbers" that appear in fib's definition are 0 and 1 in the base cases. We can imagine that the only time we "add one" to the result of fib(n) is thus whenever we arrive at some call to fib(1) in some chain of recursive subcalls. So the running time of fib(n) is at least the number of subcalls to fib(1), which is equal to the number returned by fib(n) ($f_n$).
  2. $f_n$ grows exponentially large. We can observe this by comparing the ratios between successive Fibonacci numbers:
In [3]:
print(fib(11) / fib(10))
print(fib(21) / fib(20))
print(fib(31) / fib(30))

1.6181818181818182
1.6180339985218033
1.6180339887505408

We see that $f_{n+1} \approx f_{n} \times 1.618$. Combined with observation 1, this implies that fib(n) itself takes exponential running time. And, as we saw emperically above, even fib(30) is already fairly slow (~1 second!). How can we speed this up?

Again, fib(1) is being called many many times. Why? Because fib(2) and fib(3) are themselves being called many many times. And those are being called by fib(3), fib(4), and fib(5) many many times. And so on.

What if we "remembered" the result of calls to all fib(i) so they are only computed once? We'd be a lot faster! This technique is known as memoization.

In [ ]:
def fib_memo(n, mem):
    if mem[n] is not None:
        return mem[n]
    
    mem[n] = fib_memo(n - 1, mem) + fib_memo(n - 2, mem)
    return mem[n]
    
    
def fib_fast(n):
    mem = [None] * (n + 1)
    # Instead of defining base cases in fib_memo,
    # we can instead populate the cache for 0 and 1.
    mem[0] = 0
    mem[1] = 1
    return fib_memo(n, mem)

How fast is fib(30) on the memoized version? Instant! (A µs, pronounced "microsecond", is 1/1,000,000'th of a second).

In [ ]:
print(fib_fast(30))

%timeit fib_fast(30)

We can also compute $f_{500}$ nearly instantly. This would have taken $1 \text{ second} \times (1.618)^{(500 - 30)} = 5.258 \times 10^{90} \text{ years}$ with fib. That's ($3.8 \times 10^{80}$ times longer than the universe has been alive!

In [ ]:
print(fib_fast(500))

%timeit fib_fast(500)

What is the running time of fib_fast? Because we only call fib_memo(i) on every $0 \leq i \leq n$ once, we make linearly many calls to fib_memo (instead of exponentially many calls to fib). Assuming constant-time addition, fib_fast thus takes $\mathcal{O}(n)$ time.

2.2 Coin Change, Fast

Write coin_change_fast and coin_change_memo. For the body of coin_change_memo, copy the body of coin_change above, except surround the body with logic that checks the mem cache for whether we have seen that recursive call before. Also, add results to the cache after it is computed for the first time.

coin_change_fast should create a mem array and pass that to coin_change_memo.

In [ ]:
def coin_change_memo(n, coins, memo):
    # Check memo for cached value.
    if _________________:                    # YOUR CODE HERE
        return _________________             # YOUR CODE HERE
    
    # REPLACE WITH coin_change BODY
    
    # Add the result to the memo cache
    _____________________                    # YOUR CODE HERE
    
def coin_change_fast(n, coins):
    # How large does the cache need to be?
    memo = _________________                 # YOUR CODE HERE
    
    return  ____________________             # YOUR CODE HERE



assert_equal(want=[10, 10, 10], got=coin_change_fast(30, [1, 10, 25]))
assert_equal(want=[5, 1, 1, 1], got=coin_change_fast(8, [1, 5, 10, 20]))
assert_equal(want=[10, 5, 1, 1], got=coin_change_fast(17, [20, 10, 5, 1]))
assert_equal(want=[4, 4], got=coin_change_fast(8, [20, 10, 5, 4, 1]))
assert_equal(want=[5, 4], got=coin_change_fast(9, [1, 4, 5, 10, 20]))
assert_equal(want=[], got=coin_change_fast(0, [20, 10, 5, 1]))
assert_equal(want=[20, 20, 20, 20, 10, 5, 1, 1, 1, 1], got=coin_change_fast(99, [20, 10, 5, 1]))
assert_equal(want=[25, 25, 25, 10, 10, 1, 1, 1, 1], got=coin_change_fast(99, [25, 10, 5, 1]))

3 Challenge

3.1 fib_fast(n) runtime

We said that computing fib_fast(n) requires at most linearly many in $n$ calls to fib_fast(n). But what is its runtime?

Hint: Adding two numbers $A + B$ takes $\mathcal{O}(\log{A} + \log{B})$ runtime. Also, $f_n \approx 1.618^{n}$.

In [ ]:
# YOUR CODE/ANSWER HERE

3.2 fib_fast(n) space

fib_fast(n) currently stores every Fibonacci number $f_i : 0 \leq i \leq n$ in memory. How might you rewrite fib_fast(n) to use even less space?

Hint: Think of each invocation of fib_fast(i) as a separate node in a graph, and draw an edge from fib_fast(i) to fib_fast(j) if fib_fast(i) recursively calls fib_fast(j). In what order does fib_fast above "call" each node? When does the result of a call become unneeded? Can you call them in a different order to save space?

In [ ]:
# YOUR CODE/ANSWER HERE

3.3 Canonical Coin Making

A coin making system (i.e. the denominations of coins that are given) is called canonical if the greedy algorithm is also an optimal algorithm. (Our coin_change and coin_change_fast algorithms are optimal because they exhaustively search through all possibilities.)

Are the Jamaican and US coin systems canonical? Why or why not?

In [ ]:
# YOUR CODE/ANSWER HERE