code challenges - language of your choice

[PaulStat]

Hi Folks,

Here's an idea for a thread. Someone posts a challenge (that they've already completed) with the expected results and a deadline to solve the problem.

If it's solved before the deadline feel free to post screenshots of the result. but not the code itself. You may use any language you like, I used python for this

I'm happy for the idea to evolve with further rules etc. But let's keep it simple for the moment

The challenge that follows the last can be something completely new or one that builds on the challenge that was just solved

I'll go first

Assume you have an object that has a from date and to date.

Now create a number of these objects

A-> fromDate 27/9/13, toDate 1/10/13
B-> fromDate 5/10/13, toDate 10/10/13
C-> fromDate 2/10/13, toDate 4/10/13
D-> fromDate 13/10/13, toDate 15/10/13

The idea is to find any missing date coverages, take the lists below for example

list1 = [A, B, C, D]
list2 = [A,B,D]
list3 = [A,B,C]
list4= [A,B]

Feeding the above lists into a method will give the results below

list1: "missing coverage for 11/10/13->12/10/13"
list2: "missing coverage for 2/10/13->4/10/13 + 11/10/13->12/10/13"
list3: "no missing coverage"
list4: "missing coverage for 2/10/13->4/10/13

So deadline 29/9/13 @ 8pm? And just to prove it's not my homework

DEADLINE finished

Here's mine, could've made it shorter by creating the MyDate objects/lists all in one line but decided to keep it clearer

Spoiler

from datetime import date, timedelta

class MyDate:
   def __init__(self, _fromDate, _toDate):
      self.fromDate = _fromDate
      self.toDate = _toDate
   
   def __eq__(self, other):
      return (self.fromDate == other.fromDate and self.toDate == other.toDate)
   
   def getFromDate(self):
      return self.fromDate
   
   def getToDate(self):
      return self.toDate

def check_coverage_list(datelist):
  print ("\r\nNew test")
  print ("Input dates")
  print ("######################")
  for mydate in datelist:
     print ("From date: " + str(mydate.getFromDate()))
     print ("To date: " + str(mydate.getToDate())) 
  coverageList = []
  toDatePlusOne = datelist[0].getToDate() + timedelta(days=1)
  for date in datelist[1:]:
    if( date.getFromDate() > toDatePlusOne):
      missingFrom = toDatePlusOne
      missingTo = date.getFromDate() - timedelta(days=1)
      missingDate = MyDate(missingFrom, missingTo)
      if missingDate not in datelist:
        coverageList.append(missingDate)
      toDatePlusOne = date.getToDate() + timedelta(days=1)
  
  print ("\r\nResult")
  print ("######################")
  if len(coverageList) == 0:
     print( "woohoo" )	
  else:
    print( "warning missing coverage for:")
    for date in coverageList:      
      print( "From " + str(date.getFromDate()))
      print( "To " + str(date.getToDate()))    

fromX = date(2013, 9, 27)
toX = date(2013, 10, 1)
fromY = date(2013, 10, 5)
toY = date(2013, 10, 10)
fromZ = date(2013, 10, 2)
toZ = date(2013, 10, 4)
fromA = date(2013, 10 , 13)
toA = date(2013, 10 , 17)

dateA = MyDate(fromA, toA)
dateX = MyDate(fromX, toX)
dateY = MyDate(fromY, toY)
dateZ = MyDate(fromZ, toZ)

#Missing 11/10/13->12/10/13 - working
check_coverage_list([dateX, dateY, dateZ, dateA])

#Missing  2/10/13->4/10/13 + 11/10/13->12/10/13 - working
check_coverage_list([dateX, dateY, dateA])

#Complete date range - working
check_coverage_list([dateX, dateY, dateZ])

#Missing 2/10/13->4/10/13 - working
check_coverage_list([dateX, dateY])

 

[kkelly]

Good idea , will have a go tonight hopefully.

 

[JHeaton]

Sounds like fun. How do you want the solutions to be submitted?

 

[PaulStat]

As I said if you finish before the deadline post a screenshot but not the code itself, then when the deadline is past edit your post to include the code, there are no winners but it's always interesting to see how others have tackled a problem

 

[JHeaton]

I have no idea how I missed that.

 

[Fallen god]

Seems like a lot of fun, will give it a go after I wrap up some work.

 

[Phantom Shadow]

Working through this now.

Good excuse to give python some practice as it is what I've been using on the raspberry pi.

Put in A, B, C and D and it will check for missing ranges based on ABCD and ABD - not really sure what you were after with XYZ

 

[PaulStat]

^Sorry only just noticed that, should have been [A,B,C] + [A,B]

 

[Phantom Shadow]

Ah cool, very easy to add those in as well with the way I've done the code

 

[kkelly]

Will do my version tomorrow (I know late )

 

[Haircut]

Decided to have a crack at this in F#.
I'm a C# programmer by day and have been meaning to learn more F# for ages, but never seem to actually get around to it.

It ended up being pretty messy and I'm sure it could be cleaned up a lot.
There's a lot of stuff messing about with tuples that I'm sure could be done better and the type inference could be improved as well.
It's the first thing I've done in F# that's more than a couple of functions though so I won't beat myself up too much!

Seeing as the deadline has passed I'll post the code for anyone who's interested.

Spoiler

open System

let rec getDaysBetween (startDate:DateTime) (endDate:DateTime) =
        if (startDate > endDate) then []
        else startDate::getDaysBetween (startDate.AddDays(1.0)) endDate

let getAllDaysFromList (list:seq<DateTime * DateTime>) =
    list
    |> Seq.map (fun l -> getDaysBetween (fst l) (snd l))
    |> Seq.concat
    |> Seq.distinct
    |> Seq.sortBy (fun x -> x)

let getGroup (prev:DateTime) (groupNumber:int) (curr:DateTime) =
    if (curr > prev.AddDays(1.0)) then groupNumber + 1 else groupNumber

let getDateGroup (prev:DateTime option) (groupNumber:int) (curr:DateTime option) =
    match prev with
    | Some(prev) -> (curr, (getGroup prev groupNumber curr.Value))
    | None -> (curr, 0)
    
let groupResults (dates:seq<DateTime>) =
    dates
    |> Seq.scan (fun acc seed -> getDateGroup (fst acc) (snd acc) (Some seed)) (None, 0)
    |> Seq.filter (fun x -> match (fst x) with | Some(x) -> true | None -> false)
    |> Seq.groupBy (fun x -> (snd x))
    |> Seq.map (fun x -> snd x)
    |> Seq.map (fun x -> ((fst (Seq.nth 0 x)).Value, (fst (Seq.last x)).Value))

let getTotalRange (range:seq<DateTime>) =
    (Seq.min range, Seq.max range)
    
let except seq1 seq2 = (Set.ofSeq seq1) - (Set.ofSeq seq2)

let formatDates (dates:DateTime * DateTime) =
    let startString = (fst dates).ToShortDateString()
    let endString = (snd dates).ToShortDateString()
    String.Format ("{0}->{1}", startString, endString)

let outputResults (dates:seq<DateTime * DateTime>) =
    let formattedDates = Seq.map formatDates dates
    printfn "Missing coverage for %O" (String.Join (" + ", formattedDates))

let process (list:seq<DateTime * DateTime>) =
    let allDays = getAllDaysFromList list
    let totalRange = getDaysBetween (fst (getTotalRange allDays)) (snd (getTotalRange allDays))
    let uncoveredDays = except totalRange allDays
    let groupedResults = groupResults uncoveredDays
    if (Seq.isEmpty groupedResults) then
        printfn "No missing coverage"
    else
        outputResults groupedResults

let a = (new DateTime(2013, 9, 27), new DateTime(2013, 10, 1))
let b = (new DateTime(2013, 10, 5), new DateTime(2013, 10, 10))
let c = (new DateTime(2013, 10, 2), new DateTime(2013, 10, 4))
let d = (new DateTime(2013, 10, 13), new DateTime(2013, 10, 15))

let list1 = a::b::c::d::[]
let list2 = a::b::d::[]
let list3 = a::b::c::[]
let list4 = a::b::[]

printfn "Processing list1"
process list1
printfn "\nProcessing list2"
process list2
printfn "\nProcessing list3"
process list3
printfn "\nProcessing list4"
process list4

[<EntryPoint>]
let main argv = 
    Console.ReadKey()
    0

 

[heavy-rotation]

A bit late to this party, but I've been away from the forums for some time, so only just seen it.

Here's a quick Haskell version:

import Data.Time.Calendar
import Data.List

data Range = Range Day Day deriving (Eq, Ord, Show)
 
expandRange :: Range -> Range -> Range
expandRange (Range from1 to1) (Range from2 to2) = 
  Range (min from1 from2) (max to1 to2)
  
joinRange :: Range -> Range -> Either Range Range
joinRange (Range from1 to1) (Range from2 to2) 
  | diffDays to1 from2 < -1 = Left (Range (addDays 1 to1) (addDays (-1) from2))
  | otherwise               = Right (Range from1 to2)
  
findGaps :: [Range] -> [Range]
findGaps ranges =
  snd $ foldl find (r, []) rs
  where
    (r:rs) = sort ranges
    find (x, rs) y = case (joinRange x y) of
      Left r -> (expandRange x y, r:rs)
      Right r -> (r, rs)

showGaps :: [Range] -> String
showGaps ranges = 
  "In range:\n" ++ unlines (map show ranges) ++ 
    case (findGaps ranges) of
        [] -> "There is no missing coverage.\n\n"
        rs -> "There is missing coverage:\n" ++ (unlines (map show (reverse rs))) ++ "\n"

main :: IO ()
main = do
  putStr $ showGaps [rngA, rngB, rngC, rngD]
  putStr $ showGaps [rngA, rngB, rngD]
  putStr $ showGaps [rngA, rngB, rngC]
  putStr $ showGaps [rngA, rngB]
  return ()
    where
      rngA = Range (fromGregorian 2013 9 27) (fromGregorian 2013 10 1)
      rngB = Range (fromGregorian 2013 10 5) (fromGregorian 2013 10 10)
      rngC = Range (fromGregorian 2013 10 2) (fromGregorian 2013 10 4)
      rngD = Range (fromGregorian 2013 10 13) (fromGregorian 2013 10 15)

 

[Haircut]

A bit late to this party, but I've been away from the forums for some time, so only just seen it.

Here's a quick Haskell version:
...

Nice, I did consider Haskell in terms of learning a functional language, but went for F# because of my familiarity with C#.
I'm still training myself to think in a functional way, I still always think imperative first at the moment - I'm sure some of the code I posted above could be written in a better way than I have done it there.

 

[heavy-rotation]

I'm pretty sure my version could be improved too. I'm in a slightly strange position with Haskell in that I know a lot about how it works (I'm working on my own programming language that has practically turned into a subset of Haskell at this point, but implemented in Scala) but have hardly written any actual Haskell code from scratch.

The core langauge of F# and Haskell aren't too dissimilar really given they're both descendants of ML, probably the library differences would be the biggest hurdle in switching between the two... and Haskell's usage of monads perhaps... and F# has a lot of stuff it's inherited so it can interact with the other CLR languages... and they use different evaluation strategies... ok yeah they're pretty different I guess.