Weekend Programming Challenge – Week #67 Missing pages in book


book-pages

Problem:

There is a book and a number of consecutive pages are missing from this book. All we know is that the sum of the page numbers of these pages is 9808.
Make code which calculates which are the missing pages and displays the result.

The rules:

You can code the solution in any programming language during the weekend and have to submit it to info@olimex.com latest on Sunday October 5th.

On Monday we will upload the solutions on GitHub https://github.com/OLIMEX/WPC

You can play with your real name or with nick if you want to be anonymous, we will not disclosure your personal info if you do not want to.

19 Comments (+add yours?)

  1. guest
    Oct 04, 2014 @ 08:38:19

    Short enough to be posted here:

    #!/usr/bin/env luajit
    -- WPC#67 - brute force (runs in under 1 sec so good enough)
    local sum = tonumber(arg[1] or 9808)
    
    local function printf(...)  print(string.format(...))  end
    
    local n = 0
    local sum2 = sum*2
    for p = math.floor(math.sqrt(sum2)), sum do
        for e = p-1, 1, -1 do -- assume last page is present
            local se = p*(p+1) - e*(e+1)
            if se <= sum2 then
                for s = e, 1, -1 do
                    if se + s*(s-1) == sum2 then
                        printf("%4d pages, %4d-%-4d missing", p, s, e)
                        n = n+1
                    end
                end
            end
        end
    end
    
    printf("%d solutions", n) -- 9808: 636 solutions
    

    Reply

  2. bngtlrs
    Oct 05, 2014 @ 05:38:59

    Here are three variants in Python, that are all arguably OK. Basic idea: Collect pages beginning at page 1 until the sum exceeds the desired number and throw the lowest away until the sum is smaller than desired, again. Stop when the sum is the desired number.

    #!/usr/bin/env python
    # Iterative generation of an object oriented list using functions on iterables.
    pages = [0]
    while sum(pages) != 9808:
    while sum(pages) 9808:
    pages.remove(min(pages))
    print(“%i = sum(%s)” % (sum(pages), pages))

    #!/usr/bin/env python
    # Iterative generation of a list using conditional expressions.
    pages = [0]
    while sum(pages) != 9808:
    pages = pages + [max(pages) + 1] if sum(pages) 9808 else pages
    print(“%i = sum(%s)” % (sum(pages), pages))

    #!/usr/bin/env python
    # Iterative search for valid integer arguments of the range built-in.
    start, stop = 0, 1
    while sum(range(start, stop)) != 9808:
    while sum(range(start, stop)) 9808:
    start += 1
    print(“%i = sum(%s)” % (sum(range(start, stop)), range(start, stop)))

    Reply

  3. guest
    Oct 05, 2014 @ 19:24:07

    Hmm… the two posts above look for different questions. The first (lua) where the sum of the remaining pages is 9808 and the second (python) where the sum of the missing pages is 9808. What’s the intended question?

    Anyway, I think the python solutions (sum of missing pages) only give one answer – there are usually more (unless the sum is a power of 2, no idea why). I.e. for sum==15 there’s 1-5, 4-6, 7-8 and 15-15.

    Re “why don’t follow the rules?”: Because they are pointless? Posting them by mail they just get buried in some git repo, without any review, no discussion taking place, no summary, nada. Not sending them at all would give the same result. And, there’s nothing to lose, so …

    Reply

    • OLIMEX Ltd
      Oct 05, 2014 @ 19:35:26

      ok, the choice is yours
      the repo is archive of all solutions received by e-mail, when you just post here your solution will not be put in the archive and no one will notice it after few more posts on the blog

      Reply

    • bngtlrs
      Oct 05, 2014 @ 20:44:24

      Interesting point that there might be multiple solutions; I read into the question, that there is only one. I adapted my solution to find all valid ranges, but as it turns out there aren’t any.

      Reply

      • guest
        Oct 06, 2014 @ 02:37:44

        The second solution is 9808-9808😉

      • bngtlrs
        Oct 06, 2014 @ 15:38:54

        The question asks about *consecutive* pages and to me it makes no sense to talk about one page being consecutive to itself.

      • Jerry Ross
        Oct 07, 2014 @ 00:28:25

        There is only one solution: consecutive pages requires multiple pages in the solution. There is only one multiple page solution.

  4. testman
    Oct 05, 2014 @ 23:59:46

    unsigned int16 i,n,sum,first=0,last=0;

    for (i=1;i<10000;i++){
    for (n=i;n9808) break;
    }
    if (sum == 9808) {first = i; last = n; break;}
    }

    printf(“first missing page = %Lu/n/r”,first);
    printf(“last missing page = %Lu/n/r”,last);

    Reply

    • AlsoAGuest
      Oct 06, 2014 @ 14:47:15

      Okay, I know. This ist the page in the middle of the epochal book “C – easy for extra-extrem dummies”. Right?

      Reply

  5. testman
    Oct 06, 2014 @ 00:05:53

    I don’t know why my posting is not showed correct. I sent it on email. If admin liked it please post it on forum.

    Reply

  6. testman
    Oct 06, 2014 @ 00:29:50

    I think the equation is :

    Sum = ((Pfisrt + Plast ) * (Plast – Pfirst + 1)) / 2

    Pfirst = i -> number of the first misiing page
    Plast = n -> number of the last missing page

    Every one can write simple code ( C, Pascal Python or… )
    Full version of the code I sent to admin.

    Reply

  7. ultimateohm
    Oct 07, 2014 @ 06:27:46

    Hint for breaking O(n**2):
    (1+m)+(2+m) = (1+2) + m*2
    (1+m)+(2+m)+(3+m) = (1 + 2 + 3) + m*3
    (1+m)+(2+m)+(3+m)+..+(n+m) = (1 + 2 + 3 +..+ n) + m*n

    Reply

  8. Navin
    Oct 07, 2014 @ 07:43:39

    Reply

  9. Jerry Ross
    Oct 07, 2014 @ 21:28:14

    I am curious. How does WPC / ISSUE-67 / SOLUTION-5 / wp031014.php
    qualify as a solution? The rules clearly state “Make code which calculates which are the missing pages and displays the result.” SOLUTION-5 prints the correct solution but there is no evidence of it being computed.

    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: