Spotify Best-Before challenge

Posted on August 25, 2011

Last updated on February 10, 2013

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:

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

Markdown SHA1: c7a96869440193e83438bbb7a6787df252b12067