Login or Sign Up to become a member!
LessThanDot Site Logo

LessThanDot

A Technical Community for IT Professionals

Less Than Dot is a community of passionate IT professionals and enthusiasts dedicated to sharing technical knowledge, experience, and assistance. Inside you will find reference materials, interesting technical discussions, and expert tips and commentary. Once you register for an account you will have immediate access to the forums and all past articles and commentaries.

LTD Social Sitings

Lessthandot twitter Lessthandot Linkedin Lessthandot facebook Lessthandot rss

Note: Watch for social icons on posts by your favorite authors to follow their postings on these and other social sites.

Highly Rated Users

Forum
No Posts Rated

Top 50
Given
Received

Forum Statistics

Users
Members:
1567
Members Online:
3
Guests Online:
5

Total Post History
Posts:
80461
Topics:
18411

7-Day Post History
New Posts:
20
New Topics:
8
Active Topics:
14

Our newest member
danny500

Other

FAQ
All times are UTC [ DST ]

Google Ads

LTD Puzzle 1: Friday the Thirteenths

Mind Boggling Puzzles, to keep that grey matter in shape...
Forum rules
Always post answers in a "Hidecode" tag, so that others have a chance to answer the question too.
Please wait...

LTD Puzzle 1: Friday the Thirteenths

Postby AlexCuse on Fri Jun 06, 2008 12:16 am

With another friday the thirteenth fast approaching, now seems like a good time for a themed programming puzzle. The goal is to identify all friday the thirteenths for a given timeframe. We'll use a relatively small number of years, like 10. This should make it a little easier in procedural languages.

The rules:
When posting code, please use the [hide]some code here[/hide] tags, so that you don't ruin the fun for others.
Be creative.
Be sure to mention what language it is!
Don't do drugs.

Points will be awarded for "cool code", as identified by whoever chooses to do so via LessThanDot's rating system (http://wiki.lessthandot.com/index.php/F ... ing_system). The winner will be everyone who learns something by either reading or writing the code presented.

Have fun!

Alex
Say what you like about the tenets of National Socialism Dude, at least it's an ethos
User avatar
AlexCuse
LTD Admin
LTD Admin
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021
 
Posts: 5408
Joined: Tue Oct 09, 2007 5:26 pm
Location: Pennsylvania, US
Unrated

Re: Friday the Thirteenths

Postby damber on Fri Jun 06, 2008 12:02 pm

Here is the short version (i.e. doesn't bother with options, summaries, etc and is less efficient (cycles through every date, instead of just the 13th of every month)

Code is hidden, SHOW
a smile is worth a thousand kind words, so smile, it's easy! :-)


CODE: $5
WORKING CODE: $500
PROPERLY DESIGNED & WORKING CODE: Priceless
User avatar
damber
LTD Admin
LTD Admin
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
 
Posts: 3134
Joined: Tue Oct 09, 2007 1:48 pm
Location: North Wales, UK

Re: Friday the Thirteenths

Postby HarleyQuinn on Fri Jun 06, 2008 1:20 pm

Here's a first go in VB6 (it's not particularly optimised at this stage)

Code is hidden, SHOW
Andy
User avatar
HarleyQuinn
LTD Admin
LTD Admin
LTD Bronze - Rating: 46
 
Posts: 308
Joined: Tue Dec 18, 2007 3:14 pm
Location: Sheffield, UK

Re: Friday the Thirteenths

Postby chrissie1 on Fri Jun 06, 2008 2:28 pm

Hers is one that uses VB.Net and linq and the console.

Code is hidden, SHOW


this one takes 708 milliseconds to spit out all the 13ths from 12/02/200 (yes 200) until 12/02/5000 yes 5000.
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium

Re: Friday the Thirteenths

Postby AlexCuse on Fri Jun 06, 2008 2:29 pm

here's a neat solution using C# 3.0

Code is hidden, SHOW
Say what you like about the tenets of National Socialism Dude, at least it's an ethos
User avatar
AlexCuse
LTD Admin
LTD Admin
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021
 
Posts: 5408
Joined: Tue Oct 09, 2007 5:26 pm
Location: Pennsylvania, US

Re: Friday the Thirteenths

Postby SQLDenis on Fri Jun 06, 2008 3:07 pm

SQL server, tested on 2000 and 2005



Code
Code is hidden, SHOW
User avatar
SQLDenis
LTD Admin
LTD Admin
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
 
Posts: 21734
Joined: Wed Oct 10, 2007 6:43 pm
Location: Princeton, New Jersey, USA,World, Solar System, Milky Way, Universe and Beyond

Re: Friday the Thirteenths

Postby sean on Fri Jun 06, 2008 9:45 pm

I think you want to check the and in your where.... try this instead:

Code is hidden, SHOW
sean
 
Unrated

Re: Friday the Thirteenths

Postby SQLDenis on Sat Jun 07, 2008 12:13 pm

Sean I looked at that code for 5 minutes until I found what you were talking about :-)

yes that is a typo I forgot to change it in the WHERE clause (that was from a 1st version I posted, I have changed it now)

The code I ran was actually identical to what you posted
User avatar
SQLDenis
LTD Admin
LTD Admin
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
 
Posts: 21734
Joined: Wed Oct 10, 2007 6:43 pm
Location: Princeton, New Jersey, USA,World, Solar System, Milky Way, Universe and Beyond
Unrated

Re: Friday the Thirteenths

Postby tarwn on Sat Jun 07, 2008 1:22 pm

And of course I have to post an ASP/VBScript solution. I tried to do it differently then everyone else (at most it loops n+2 where n is number of 13's):
Code is hidden, SHOW


Apparently we need to work on the line wrap for the Hide function :P Copy it into a text editor if you want to see the couple lines that are getting cut off.

Um, yeah...I'm going to need you to come in on Saturday -- Bill Lumbergh, Office Space
User avatar
tarwn
LTD Admin
LTD Admin
LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813
LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813
LTD Gold - Rating: 813
 
Posts: 3660
Joined: Fri Oct 12, 2007 11:10 am
Location: Raleigh, NC, USA

Re: Friday the Thirteenths

Postby xtcsonik on Mon Jun 09, 2008 6:42 pm

xtcsonik
Newbie
Newbie
LTD Bronze - Rating: 7
 
Posts: 1
Joined: Mon Jun 09, 2008 6:41 pm

Re: Friday the Thirteenths

Postby cLFlaVA on Tue Jun 10, 2008 2:15 am

JavaScript :)

Code is hidden, SHOW
User avatar
cLFlaVA
LTD Senior Moderator
LTD Senior Moderator
LTD Bronze - Rating: 19
 
Posts: 238
Joined: Fri Oct 12, 2007 3:51 pm

Re: Friday the Thirteenths

Postby eksimba on Tue Jun 10, 2008 4:52 am

C# with a lambda expression:

Code is hidden, SHOW
eksimba
Newbie
Newbie
LTD Bronze - Rating: 11
 
Posts: 1
Joined: Tue Jun 10, 2008 4:47 am

Re: Friday the Thirteenths

Postby spoulson on Tue Jun 10, 2008 2:58 pm

Old school Perl 5

Usage: Perl f13.pl <start year> [end year]
Omit end year and it'll default to 10 years up

Code is hidden, SHOW

Runs in 477ms from year 200 to 5000 with the assumption we only care about the Gregorian calendar. If I take out the printf, it runs in 147ms. My PC is a 1.6GHz dual core Dell Optiplex 745 running XP.

I double commented the time measurement stuff because the module Time::HiRes is not installed by default and will fail to run on plain installs of Perl.

It's funny that in doing this exercise, I found an error in the DOW formula on the WikiPedia page. I commented my code change as "Fix for leap years".
Last edited by spoulson on Tue Jun 10, 2008 9:02 pm, edited 2 times in total.
User avatar
spoulson
Senior Apprentice
Senior Apprentice
LTD Bronze - Rating: 115LTD Bronze - Rating: 115LTD Bronze - Rating: 115
 
Posts: 205
Joined: Mon Jun 02, 2008 2:37 am
Location: Middletown, DE, USA

Re: Friday the Thirteenths

Postby webbes on Tue Jun 10, 2008 3:15 pm

C# 2.0
There's no need to waist memory on a creating a list or to loop through ALL dates in range.. :D

Code is hidden, SHOW
webbes
Newbie
Newbie
LTD Bronze - Rating: 7
 
Posts: 4
Joined: Tue Jun 10, 2008 3:09 pm

Re: Friday the Thirteenths

Postby SQLDenis on Tue Jun 10, 2008 6:32 pm

I would love to see a Python, Ruby, F# or Haskell solution
User avatar
SQLDenis
LTD Admin
LTD Admin
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
 
Posts: 21734
Joined: Wed Oct 10, 2007 6:43 pm
Location: Princeton, New Jersey, USA,World, Solar System, Milky Way, Universe and Beyond
Unrated

Re: Friday the Thirteenths

Postby ilitirit on Tue Jun 10, 2008 6:33 pm

Code is hidden, SHOW
ilitirit
Newbie
Newbie
LTD Bronze - Rating: 4
 
Posts: 2
Joined: Tue Jun 10, 2008 6:29 pm

Re: Friday the Thirteenths

Postby traingamer on Tue Jun 10, 2008 6:48 pm

The first time I wrote a function like this, it was in Pick basic. Haven't used that for a number of years, so here's one in VBA. Rather than cycling through all the months:
Code is hidden, SHOW
Greg

People demand freedom of speech as a compensation for the freedom of thought which they seldom use. Kierkegaard
User avatar
traingamer
Senior Sage
Senior Sage
LTD Bronze - Rating: 233LTD Bronze - Rating: 233LTD Bronze - Rating: 233LTD Bronze - Rating: 233LTD Bronze - Rating: 233
 
Posts: 1485
Joined: Thu Feb 28, 2008 4:13 pm
Location: St. Louis, MO, US

Friday the 13th's in RUBY

Postby coneybeare on Tue Jun 10, 2008 8:18 pm

RUBY
-------

Quick implementation using a for loop over days


Code is hidden, SHOW
coneybeare
Newbie
Newbie
LTD Bronze - Rating: 4
 
Posts: 1
Joined: Tue Jun 10, 2008 8:14 pm

Re: Friday the Thirteenths

Postby mbaird on Tue Jun 10, 2008 9:58 pm

Java -- Just a quick implementation that prints every Friday 13th for the next 10 years (from whenever you run it).

Code is hidden, SHOW
mbaird
Newbie
Newbie
LTD Bronze - Rating: 4
 
Posts: 1
Joined: Tue Jun 10, 2008 9:52 pm

Re: Friday the Thirteenths

Postby fullpunk on Wed Jun 11, 2008 5:44 am

An implementation in python using tables to find friday the 13th according to the first day of the year:

Code is hidden, SHOW
fullpunk
Newbie
Newbie
LTD Bronze - Rating: 9
 
Posts: 1
Joined: Wed Jun 11, 2008 5:35 am

Re: Friday the Thirteenths

Postby Emtucifor on Wed Jun 11, 2008 8:42 pm

VB6. This function is VERY fast.

I wrote a VB6 app using this that calculates the years 1900 through 4899 (including displaying it in a textbox) 100 times. It takes about 0.72 seconds so that is 0.0072 seconds to calculate 5000 years worth of Friday the 13ths.

Code is hidden, SHOW
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA

Re: Friday the Thirteenths

Postby Emtucifor on Wed Jun 11, 2008 8:55 pm

And now that I've looked at all your code, I see that traingamer had the same idea and so did a couple of other people.

In fact, his solution's output is quite a bit more readable than mine! :-)

I also am doing some extra stuff to calculate the correct index offset, but he just reordered the array list. So his way is superior if it's giving the right output.
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA
Unrated

Re: Friday the Thirteenths

Postby spoulson on Thu Jun 12, 2008 12:49 pm

ErikE wrote:And now that I've looked at all your code, I see that traingamer had the same idea and so did a couple of other people.


I wasn't aware of this until after participating in this puzzle, but there's a theorum of Babwani's Congruence that describes formulae for functionally computing a missing datetime field when the others are known. In his paper he also discusses the algorithm that traingamer, fullpunk, and ErikE used in their submissions. It's worth a read if you're ever tasked with coding fast datetime calculations.
User avatar
spoulson
Senior Apprentice
Senior Apprentice
LTD Bronze - Rating: 115LTD Bronze - Rating: 115LTD Bronze - Rating: 115
 
Posts: 205
Joined: Mon Jun 02, 2008 2:37 am
Location: Middletown, DE, USA

Re: Friday the Thirteenths

Postby Emtucifor on Thu Jun 12, 2008 5:56 pm

I used Excel for my analysis in a sort of brute-force graphical way:

1. Generate a list of all the Friday the 13ths for every year from 1900 through 9999.
2. Calculate the first day of the year (represented as 1 - 7 or 0 - 6) for each Fri 13th and whether the year is a leap year.
3. Use a pivot table to move months to their own columns at the top, including year and leap year information on the left.
4. Do an advanced data filter to get only unique variations of leap year + first day of year + Fri 13th pattern.
5. Notice there are only 14 variations, one for each day of the week in a leap and non-leap year.
6. Try as I might, I couldn't render the resulting pattern in a way that compressed easily or decompressed cheaply, so I finally just stuck the entire thing in an array, of sorts.
7. The list can be reduced to only 7 variations with the understanding that in leap years the "first day of the year" calculation will be advanced one for month 3 and up. However in my algorithm the extra logic for "month 3 and up" made the whole thing slower rather than just using the full 14-day map. For small ranges of years, the 7-variation list with the month 3 logic (or think of it as month 1 & 2 logic if you like) is faster.

After seeing traingamer's solution, I realized I could have simulated the output of a brute-force approach with:

Map(0) = "January 13, <year>" & vbcrlf & "October 13, <year>"

And the output would involve Replace(Map(index), "<year>", StartYear)

Now my somewhat cryptic and table-bound result (I used a textbox with JFMAMJJASOND at the top lined up with the x's) can be friendly looking but still just as fast.

Also, reading through the document found at spoulson's link, I wonder if calculating the day of the week for the month rather than the entire year could yield some optimization for my code. Obviously I'm doing more calculation than traingamer.
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA
Unrated

Re: Friday the Thirteenths

Postby spoulson on Tue Jun 17, 2008 12:50 pm

From the looks of it, if you wanted to generalize the day of week calculation, you should be able to generate a lookup table containing 4 calendar years of day/month/dow, because it just repeats. Then lookup by day, month, and year mod 4. No runtime calculation.
User avatar
spoulson
Senior Apprentice
Senior Apprentice
LTD Bronze - Rating: 115LTD Bronze - Rating: 115LTD Bronze - Rating: 115
 
Posts: 205
Joined: Mon Jun 02, 2008 2:37 am
Location: Middletown, DE, USA
Unrated

Next