Weekend Programming Challenge – Week #67 Missing pages in book 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.

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 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

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 = 
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 = 
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)))

• OLIMEX Ltd
Oct 05, 2014 @ 10:00:55

nice, but why don’t follow the rules? 🙂

• bngtlrs
Oct 05, 2014 @ 20:08:17

I had these and thought I’d just share them here. Sorry if this does not fit your workflow; I will send them in via email, too.

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 …

• 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

• 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.

• 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);

• 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?

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.

• guest
Oct 06, 2014 @ 02:39:34

You have to wrap the code with an html pre tag (<pre>…</pre>)

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.

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

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

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.