Weekend Programming Challenge – Week #67 Solutions


book-pages

We got 25 solutions!

  • Python x10
  • C x4
  • C++ x4
  • Java x2
  • Ruby x1
  • JavaScript x1
  • Nimrod x1
  • Php x1
  • Perl x1

The solutions are on Github as usual.

4 Comments (+add yours?)

  1. Dylan
    Oct 08, 2014 @ 14:38:20

    I’m saddened by the number of brute force entries even more than by the over-engineered code. To clarify my entry:

    A number of sheets is missing. Each sheet consists of recto (odd-numbered) and verso (even) sides. That’s the way books work. Sometimes blank pages say “this page intentionally left blank” but even then they will have a page number.

    Since odd+even=odd, a single sheet cannot be missing. Since odd+odd=even, a pair of sheets could be missing. Since even+even=even, any number of pairs of sheets could be missing. Since sum(range(141)) – Python for 0 to 140 – is 9870, no more than 70 sheets can be missing (a small bug in my program!)

    Since the pages are consecutive, they have a “middle”, in this case “306.5”, with 8 sheets either side, pages 291-306 and 307-322 respectively.

    My own code could be better – http://goo.gl/yZVCb6 prints the solution in 32 steps (of 86 total) – and as it happens there is only one solution. Exploring the solution space with nested loops of the first page number and the number of pages doesn’t just sadden me, it scares me.

    Reply

  2. ultimateohm
    Oct 08, 2014 @ 14:40:47

    Solutions 10, 14 and 20 could be O(sqrt(n)).
    I like solution 14. Simple, no floating-point, mul, div, mod operations.
    Another solution I miss?

    Reply

    • Dylan
      Oct 08, 2014 @ 23:08:46

      My solution (10) is sqrt – no coincidence in 70*140 being 10K. Thanks for pointing out solution 14 which with integer arithmetic is certainly going to find the first (and only) solution using the sliding window method. I’ll look at runsums from #20 again tomorrow, or rather the link in it.

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: