Recently while browsing through stackoverflow I found a question regarding the Spotify programming puzzle bestbefore. You can find the problem description here.
Normally I like doing puzzles in Haskell just to train my functional programming brain muscles, but Haskell wasn’t allowed, so I had to do some python.
The gist of the puzzle is, given a date in a format like ‘ab/cd/ef’, find the earliest possible valid date.
I like functional approaches, so my code in python has a functional rather than an imperative feel for it.
I now outline to you my approach to the problem, followed by the code.
The date comes in a format ‘ab/cd/ef’, or possibly some of the fields are prepended by zeros, or the year is actually a full year, like 2012 for example. My process is as follows:
- Generate all the possible permutations of the given input ( there are only 3*2 = 6…). The result is list of tuples in the format (yy,mm,dd).
- Filter the result to only those that pass the validation ( valid year, month, day, check leap year, etc)
- Sort the list
- Take the first element!
And we are done. Very simple, and much cleaner, more functional, than the Java code I saw on stackoveflow. When I have some time, I will redo the problem in Haskell and it will be much cleaner :P
After sending my code to the puzzle robot, was accepted on the first try! :P
Here is the first version of the code, in which I implemented my own permuation method for practice, instead of using the itertools library.
import sys
import functools
months = [31,28,31,30,31,30,31,31,30,31,30,31]
# leap :: Int -> Bool
# Says whether a year is leap
def leap(x):
return (x % 4 == 0) and not (x % 100 == 0 and not (x % 400 == 0))
# valid :: [Int] -> Bool
# Given a list in format [y,m,d], says whether it's a valid date
def valid( x ):
y = x[0]
m = x[1]
d = x[2]
return ((y >= 2000 and y <= 2999) and
(m >= 1 and m <= 12) and
(d >= 1 and (d <= months[m-1] or ( leap(y) and d <= 29))))
# date_compare :: [Int] -> [Int] -> Int
# Note, this is ugly, there are better ways
def date_compare(a,b):
if(not (a[0] == b[0])): return a[0] - b[0]
if(not (a[1] == b[1])): return a[1] - b[1]
if(not (a[2] == b[2])): return a[2] - b[2]
return 0
# permutations :: [a] -> [[a]]
def permutations(x):
if len(x) == 1:
return [x]
else:
return [i for s in map( functools.partial(insert, x[-1]) , permutations(x[0:len(x)-1]) ) for i in s ]
# insert :: a -> [a] -> [[a]]
# Intersperses the element `elem` into list `l`
def insert(elem,l):
ret = []
for i in range(len(l)+1):
l_temp = list(l)
l_temp.insert(i,elem)
ret.append( l_temp )
return ret
# toStr :: Int -> String
def toStr(x):
if(x <= 9): return "0" + str(x)
else: return str(x)
# fromList :: [Int] -> String
def fromList(x):
return reduce( lambda a,b : toStr(a) + "-" + toStr(b), x)
original_input = sys.stdin.readline()
arr = map((int),original_input.split("/"))
res = permutations(arr)
for r in res:
if r[0] < 2000: r[0] += 2000
possible = sorted(filter(valid, res), cmp=date_compare)
if(len(possible) == 0):
print "{0} is illegal".format(original_input)
else:
print fromList(possible[0])This works perfectly fine, but to make it look prettier, I’ll use the itertools library for permutations and compress the code!
import sys,functools,itertools
months = [31,28,31,30,31,30,31,31,30,31,30,31]
# leap :: Int -> Bool
# Says whether a year is leap
def leap(x): return (x % 4 == 0) and not (x % 100 == 0 and not (x % 400 == 0))
# valid :: (Int,Int,Int) -> Bool
# Given a tuple in format (y,m,d), says whether it's a valid date
def valid( (y,m,d) ):
return ((y >= 2000 and y <= 2999) and
(m >= 1 and m <= 12) and
(d >= 1 and (d <= months[m-1] or ( leap(y) and d <= 29))))
# date_compare :: (Int,Int,Int,) -> (Int,Int,Int) -> Int
def date_compare(d1,d2): return ([ a-b for (a,b) in zip(d1,d2) if not (a-b) == 0 ] + [0] )[0]
# toStr :: Int -> String
def toStr(x):
if(x <= 9): return "0" + str(x)
else: return str(x)
original_input = sys.stdin.readline()
res = map(lambda (y,m,d) : (y+2000,m,d) if y < 2000 else (y,m,d), list(itertools.permutations(map((int),original_input.split("/")))))
possible = sorted(filter(valid, res), cmp=date_compare)
if(len(possible) == 0): print "{0} is illegal".format(original_input)
else: print reduce(lambda a,b : toStr(a) + "-" + toStr(b), possible[0])Thanks for reading, post a comment if you have any questions. I’ll now go the next programming challenge from spotify! :P