Python 3: Slow and Ugly, But Quick and Easy
Intuition\n\nTime processing questions are irritating.\n\nSometimes you have irregular formats like a seconds field with 6,7,8,9 in it!\n\nAre you tired of wran
# Intuition\n\nTime processing questions are irritating.\n\nSometimes you have irregular formats like a seconds field with 6,7,8,9 in it!\n\nAre you tired of wrangling with off-by-one errors? Base 60 conversions? Minutes and seconds got you down?\n\nThere\'s hope! Introducing **extreme brute force: try every possible digit combination edition!**\n\nIt\'s ugly and it\'s stupid. But it works. And if it works it\'s not stupid, right??\n\n## Brute Force: Try All Buttons\n\nIterate from 1 to [9999](https://youtu.be/SiMHTK15Pik?t=5).\n\nFor each, convert the first two digits to minutes and the second two to seconds. Then compute the duration `t` in seconds.\n\nIf `t == target` then\n* get the digits of `t`\n* each digit must be pressed so add `pushCost * len(digits)`\n* and each time we have to move our finger we add `moveCost`\n\nReturn the minimum cost seen this way.\n\n## Clever: m-1 s+60 Equivalence\n\nI picked this up from looking at other submissions, not sure who came up with it.\n\nThe idea is\n* we can enter the digits normally, the usual 0..59 seconds format\n* OR we can enter something larger than 59 for seconds and use the rollover.\n\n**We can compute the digits after rolling over, i.e. the "normalized time," with the usual `% 60` and `// 60` logic.**\n\nIf we did roll over, then **the equivalent state before rolling over is `m-1` and `s+60` for normalized minutes `m` and seconds `s`.**\n\nSo we can compute the cost of\n* entering the normalized `m` and `s`\n* entering the irregular `m-1` and `s+60` that is equivalent\n  * if `s+60 >= 100` then we can\'t enter this, invalid combination\n  * if `m-1 < 0` then similarly this is invalid\n  * so we just have to check for these before computing the second way\n\n**This is the only rollover possible and thus we only have to compute costs for <= 2 digit strings instead of 9999.**\n\n# Time Problems in General\n\nMost of the time (heh) you can afford to spend `1e4` operations in an OA to get the answer. It\'s not pretty but it works, and often speed is of the essence. OAs are graded on tests passed then time taken then cleverness.\n\nIn-person interviews I think weight the cleverness a bit more, but still better to pass test cases and finish the question than wrangle with a clever idea the whole time.\n\nBut really I\'m just salty because I tried to come up with the clever solution but couldn\'t make it work within about 5 minutes so I gave up and went with brute force.\n\n# Complexity\n- Time complexity: `O(1e4)` try all digits\n\n- Space complexity: `O(1)`\n\n# Code\n```python3 []\nclass Solution:\n    def minCostSetTime(self, startAt: int, moveCost: int, pushCost: int, targetSeconds: int) -> int:\n        # ahhhhhh yeah\n\n        # only worth moving if we\'re going to push another button\n\n        # clever ways: probably\n\n        # OR: super brute force: generate all digit combinations, convert to time, if equal to targetSeconds then compute cost\n\n        # max time is 6039\n        # is that 59:99?\n        #         60:39   yep!\n\n        minCost = math.inf\n        for n in range(1, 9999+1):\n            s = n % 100\n            m = n // 100\n            t = 60*m + s\n            if t == targetSeconds:\n                digits = []\n                while n:\n                    digits.append(n % 10)\n                    n //= 10\n\n                cost = pushCost * len(digits)\n                b = startAt\n                for d in reversed(digits):\n                    if d != b:\n                        # move to d\n                        cost += moveCost\n                        b = d\n                minCost = min(minCost, cost)\n\n        return minCost\n```
['Python3']