34
\$\begingroup\$

Last month I borrowed a plenty of books from the library. They all were good books, packed with emotions and plot-twists. Unfortunately, at some points I got very angry/sad/disappointed, so I tore some pages out.

Now the library wants to know how many pages I have torn out for each book.

Your goal is to write a program, which takes a sorted, comma-delimited list of numbers as input and prints the minimum and maximum possible page count I could have torn out. Each line represents a book, each number represents a missing page from the book.

Example input:

7,8,100,101,222,223
2,3,88,89,90,103,177
2,3,6,7,10,11
1
1,2

Example output:

4/5
5/6
3/6
1/1
1/2

4/5 means, that I may have torn out either 4 or 5 pages, depending on which side the book's page numbering starts. One could have torn out page 6/7, page 8/9, page 100/101, and page 222/223 (4 pages). Alternatively, one could have torn out page 7/8, page 99/100, page 101/102, page 221/222, and page 223/224 (5 pages).

Remember that a book page always has a front and a back side. Also the page numbering differs from book to book. Some books have even page numbers on the left page; some on the right page. All books are read from left to right.

Shortest code in bytes win. Strict I/O format is not required. Your programs must be able to take one or more books as input. Have fun.

\$\endgroup\$
  • 3
    \$\begingroup\$ Would it be acceptable if the output values are not guaranteed to be sorted? (such as 4/5 and 5/4) \$\endgroup\$ – Arnauld Feb 5 '18 at 17:58
  • \$\begingroup\$ Don't forget to update to the challenges to specify that output order must be consistent, either all min/max or all max/min. (Although, personally, I'd prefer that not to be part of the spec!) \$\endgroup\$ – Shaggy Feb 6 '18 at 11:58
  • 2
    \$\begingroup\$ What would be the reason to programs must be able to take one or more books as input rule? Most (if not all) will just wrap the code to verify a single book into a loop or something. IMHO it just add an overhead to the answer with little to no gains to the challenge. This questions already got lots of answers, so it's better to keep this as is, but keep this in mind for you future challenges. \$\endgroup\$ – Rod Feb 6 '18 at 13:36
  • \$\begingroup\$ Suggested test case (courtesy of @Arnauld): 1,3,5,7,9,11,13,15,17,18 - for the benefit of languages whose built-in sort method sorts lexicographically by default (assuming the requirement of consistently sorted output is added to the spec). \$\endgroup\$ – Shaggy Feb 6 '18 at 16:07

11 Answers 11

6
\$\begingroup\$

05AB1E, 13 bytes

εD>)ÅÈε€θγg}{

Try it online!

Thanks to Emigna for the heads-up on spec changes.

Explanation

εD>)ÅÈε€θγg}{ – Full program.
ε             – For each book...
 D            – Push two copies of it.
  >           – Increment all the elements of the second copy.
   )          – Wrap the whole stack into a list.
    ÅÈ        – Produces the lists of even natural numbers lower or equal to each element.
      ε       – For each (the modified copies of the book):
       €θ     – Get the last item of each.
         γg   – And split into chunks of equal adjacent elements.
           }  – Close the loop.
            { – Sort the resulting list.
\$\endgroup\$
  • \$\begingroup\$ Nice submission. I updated the challenge with 2 extra input/output lines. Also strict I/O is not required. \$\endgroup\$ – arminb Feb 6 '18 at 9:37
  • \$\begingroup\$ Btw, your program does not take multiple books as input. \$\endgroup\$ – arminb Feb 6 '18 at 10:32
  • \$\begingroup\$ @Emigna Thanks for the heads-up. Edited my answer accordingly. \$\endgroup\$ – Mr. Xcoder Feb 6 '18 at 12:05
  • \$\begingroup\$ @arminb It should be fixed now. \$\endgroup\$ – Mr. Xcoder Feb 6 '18 at 12:06
4
\$\begingroup\$

Python 2, 72 56 68 67 bytes

lambda b:[map(len,map(set,zip(*[[p/2,-p/2]for p in t])))for t in b]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Your program does not accept multiple line inputs (multiple books). I updated the challenge with 2 extra input/output lines. Also strict I/O is not required. \$\endgroup\$ – arminb Feb 6 '18 at 9:37
  • 1
    \$\begingroup\$ Wouldn't multiple inputs per run fall into strict I/O? \$\endgroup\$ – Rod Feb 6 '18 at 12:09
  • 1
    \$\begingroup\$ One could argue. \$\endgroup\$ – arminb Feb 6 '18 at 12:39
  • \$\begingroup\$ How you take the books and their pages as input is covered by the I/O spec. The requirement that you do take multiple books as input is part of the challenge spec. \$\endgroup\$ – Shaggy Feb 6 '18 at 13:21
4
\$\begingroup\$

JavaScript, 104 93 92 85 80 79 74 bytes

Would be 57 bytes if not for the unnecessary (in my opinion) requirement that each pair of numbers in the output be consistently sorted, or 47 bytes if we only needed to take one book as input.

Input and output are both an array of arrays.

a=>a.map(x=>[0,1].map(n=>new Set(x.map(y=>y+n>>1)).size).sort((x,y)=>x-y))
  • Initially inspired by Olivier's Java solution and my own (currently deleted) Japt solution.
  • 2 bytes saved thanks to Arnauld (plus another 3 we both spotted at the same time) and 10 bytes added thanks to him spotting the broken sorting I'd hoped nobody would notice while that requirement was still under discussion!

Test cases

Test cases are split into individual books for better readability with the last case (which includes the [1,2] edge case) serving to illustrate that this solution supports multiple books in the input.

f=
a=>a.map(x=>[0,1].map(n=>new Set(x.map(y=>y+n>>1)).size).sort((x,y)=>x-y))
o.innerText=` Input                         | Output\n${`-`.repeat(31)}|${`-`.repeat(21)}\n`+[[[7,8,100,101,222,223]],[[2,3,88,89,90,103,177]],[[2,3,6,7,10,11]],[[1,3,5,7,9,11,13,15,17,18]],[[1],[1,2],[8,10]]].map(b=>` `+JSON.stringify(b).padEnd(30)+"| "+JSON.stringify(f(b))).join`\n`
<pre id=o></pre>


History

//104
a=>a.map(x=>x.map(y=>b.add(y/2|0)&c.add(++y/2|0),b=new Set,c=new Set)&&[b.size,c.size].sort((x,y)=>x-y)))
// 93
a=>a.map(x=>[new Set(x.map(y=>y/2|0)).size,new Set(x.map(y=>++y/2|0)).size].sort((x,y)=>x-y)))
// 92
a=>a.map(x=>[(g=z=>new Set(z).size)(x.map(y=>y/2|0)),g(x.map(y=>++y/2|0))].sort((x,y)=>x-y))
// 85
a=>a.map(x=>[(g=h=>new Set(x.map(h)).size)(y=>y/2|0),g(y=>++y/2|0)].sort((x,y)=>x-y))
// 80
a=>a.map(x=>[(g=n=>new Set(x.map(y=>(y+n)/2|0)).size)(0),g(1)].sort((x,y)=>x-y))
// 79
a=>a.map(x=>[(g=n=>new Set(x.map(y=>y/2+n|0)).size)(0),g(.5)].sort((x,y)=>x-y))
// 76
a=>a.map(x=>[0,.5].map(n=>new Set(x.map(y=>y/2+n|0)).size).sort((x,y)=>x-y))

\$\endgroup\$
  • \$\begingroup\$ Nowhere is it written that the output has to be sorted from min to max. The question only says that the input will be sorted. \$\endgroup\$ – Olivier Grégoire Feb 6 '18 at 13:33
  • \$\begingroup\$ @OlivierGrégoire; while true that the consistent sorting of the output is not currently included in the spec, arminb has commented on a couple of solutions stating that it is indeed a requirement. I have already commented on the challenge asking for it to be included and stating my preference against it - after all, to me, that would fall under strict I/O. \$\endgroup\$ – Shaggy Feb 6 '18 at 13:36
  • 1
    \$\begingroup\$ I think this should work for 64 bytes. However, your current sort method without any callback is flawed. It would fail on e.g. [1,3,5,7,9,11,13,15,17,18]. \$\endgroup\$ – Arnauld Feb 6 '18 at 15:32
  • \$\begingroup\$ Thanks, @Arnauld. Had just finished writing an update to map over [0,.5] instead of using g when I spotted your comment. Don't know why I have such a mental block with bitwise operators! I was hoping that the output sorting wouldn't become a requirement and that nobody would notice my broken sort() in the meantime ;) Need to get some work done so will be back in a while to update. \$\endgroup\$ – Shaggy Feb 6 '18 at 15:46
  • \$\begingroup\$ @Shaggy What is the original intent of y/2? What is the reasoning of dividing the page number in half for this algorithm? \$\endgroup\$ – MicFin Feb 8 '18 at 6:11
2
\$\begingroup\$

Retina 0.8.2, 60 bytes

\d+
$*
.+
$&,/$&,
,(?=.*/)
1,
((11)+,)1\1|1+,
1
%O`1+
1+
$.&

Try it online! Explanation:

\d+
$*

Convert the page numbers to unary.

.+
$&,/$&,

Duplicate the list, interposing a /.

,(?=.*/)
1,

Increment the page numbers in one copy of the list.

((11)+,)1\1|1+,
1

Count the number of pages, but consecutive even and odd numbers only counts as one page.

%O`1+

Sort the counts into order.

1+
$.&

Convert the counts back to decimal.

\$\endgroup\$
  • \$\begingroup\$ Nice submission! I updated the challenge with 2 extra input/output lines. Also strict I/O is not required. It seems your program is the only one by now which passes all the test cases. \$\endgroup\$ – arminb Feb 6 '18 at 9:56
  • \$\begingroup\$ Can't ,(?=.*/)¶1, be something like ,.*/¶1$& instead? \$\endgroup\$ – Ven Feb 6 '18 at 13:48
  • \$\begingroup\$ @Ven No, that would only increment one number, but I need to increment all of them. \$\endgroup\$ – Neil Feb 6 '18 at 17:35
  • \$\begingroup\$ Ok, and using overlapping takes it back to same byte count, so fair nuff \$\endgroup\$ – Ven Feb 6 '18 at 21:41
2
\$\begingroup\$

Haskell, 62 bytes

import Data.List
p t=sort[length$nub[div(p+o)2|p<-t]|o<-[0,1]]

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think this is technically valid, as the question requires a full program (Your goal is to write a program, which takes a sorted, comma-delimmited list of numbers as input ) \$\endgroup\$ – Οurous Feb 6 '18 at 9:19
  • \$\begingroup\$ @Ourous that' right. Also I updated the challenge with 2 extra input/output lines. Also strict I/O is not required. \$\endgroup\$ – arminb Feb 6 '18 at 9:38
2
\$\begingroup\$

Java (OpenJDK 9), 163 bytes

import java.util.*;
n->{for(int i=n.length;i-->0;){Set s=new HashSet(),t=new HashSet();for(int p:n[i]){s.add(p/2);t.add(++p/2);}n[i]=new int[]{s.size(),t.size()};}}

Try it online!

Explanations

n->{                                   // Input-output of int[][]
 for(int i=n.length;i-->0;){           // Iterate on books
  Set s=new HashSet(),t=new HashSet(); // Create two hashsets
  for (int p:n[i]) {                   // Iterate over each page
   s.add(p/2);                         // Add the sheet-of-page of books [ even | odd ] to one set.
   t.add(++p/2);                       // Add the sheet-of-page of books [ odd | even ] to the other set.
  }
  n[i]=new int[] {                     // change the input to the number of sheets used.
   s.size(),
   t.size()
  };
 }
}

Note: since there is no requirement about it, the min and max numbers of pages aren't ordered.

\$\endgroup\$
  • \$\begingroup\$ Can you chain size with add in Java to maybe save a few bytes? e.g., s.add(p/2).size. \$\endgroup\$ – Shaggy Feb 6 '18 at 12:12
  • 1
    \$\begingroup\$ @Shaggy No. I could chain stuff with streams, but that would add a <s>few</s> lot of bytes, not save ;-) \$\endgroup\$ – Olivier Grégoire Feb 6 '18 at 12:16
2
\$\begingroup\$

APL (Dyalog Unicode), 37 bytes

{(≢⍵)≤2:⌽≢∘∪¨⌊⍵(1+⍵)÷2⋄≢∘∪¨⌊⍵(1+⍵)÷2}

Try it online!

This can be done for less than half the byte count if the output order of pages doesn't matter:

{≢∘∪¨⌊⍵(1+⍵)÷2}

How?

{(≢⍵)≤2:⌽≢∘∪¨⌊⍵(1+⍵)÷2⋄≢∘∪¨⌊⍵(1+⍵)÷2}⍝ Prefix dfn
{(≢⍵)≤2:                               ⍝ If argument length ≤2 
                    ÷2                 ⍝ Divide by 2
              ⍵(1+⍵)                   ⍝ Both the argument and 1+argument
             ⌊                         ⍝ Round down to the nearest integer
           ∪¨                          ⍝ Get the unique values of each
          ∘                            ⍝ And then
         ≢                             ⍝ Get the tally of elements of each
        ⌽                              ⍝ And reverse the result
                      ⋄                ⍝ Else
                       ≢∘∪¨⌊⍵(1+⍵)÷2} ⍝ Same as above, without reverting the result.
\$\endgroup\$
  • \$\begingroup\$ 21 bytes \$\endgroup\$ – dzaima Sep 16 '18 at 13:48
2
\$\begingroup\$

Perl 5, 95 + 1 (-a) = 96 bytes

@0=@1=0;map{$i=-1;$F[$i]+1==$F[$i+1]&&$F[$i]%2==$_&&$i++while++$i<@F&&++@{$_}[0]}0,1;say"@0/@1"

Try it online!

\$\endgroup\$
  • \$\begingroup\$ There are some cases your program does not execute properly. I updated the challenge with 2 extra input/output lines. Also strict I/O is not required. \$\endgroup\$ – arminb Feb 6 '18 at 9:41
  • \$\begingroup\$ I don't see where any of your test cases are failing. The only thing that isn't working is multiple cases, which you added long after I posted my solution. In any case, I have updated the solution to handle multiple tests. \$\endgroup\$ – Xcali Feb 6 '18 at 15:56
2
\$\begingroup\$

Wolfram Language (Mathematica), 37 bytes

Thanks @MartinEnder for 8 bytes!

Sort[Length@*Split/@{#,#+1}~Floor~2]&

Try it online!

Explanation

In: {3, 4, 5}

{#,#+1}

Take (input) and (input + 1). {{3, 4, 5}, {4, 5, 6}}

... ~Floor~2

For each number from above, take the largest even number less it. {{2, 4, 4}, {4, 4, 6}}

Length@*Split/@

For each list from above, split the list by same elements {{{2}, {4, 4}}, {{4, 4}, {6}}}

and take the length of each: {2, 2}

Sort[ ... ]

Sort the output.

\$\endgroup\$
  • 1
    \$\begingroup\$ You don't need SplitBy: Length@Split@⌊#/2⌋&/@{#,#+1}& works. But then it's even shorter to do the flooring before the map: Length@*Split/@⌊{#,#+1}/2⌋&. And if you like, you can get the same byte count without Unicode: Length@*Split/@{#,#+1}~Floor~2& \$\endgroup\$ – Martin Ender Feb 5 '18 at 17:46
  • \$\begingroup\$ Uh, I think the challenge requires a strict I/O format. \$\endgroup\$ – Erik the Outgolfer Feb 5 '18 at 17:54
1
\$\begingroup\$

Clean, 222 210 204 196 bytes

import StdEnv,ArgEnv,Data.Maybe,qualified GenLib as G
Start=tl[let(Just l)='G'.parseString i;?s=sum[1\\n<-[s,s+2..last(sort l)]|isAnyMember[n,n+1]l]in zip2(sort[?0,?1])['/\n']\\i<-:getCommandLine]

Try it online!

Full-program requirements absolutely murder Clean's ability to compete.

For those who have been paying attention to my answers in Clean, you'll notice import qualified, which is an ugly hack to get around using modules that shouldn't be used together, together - which is only needed here because of another ugly hack to do with GenLib depending on Data.Maybe instead of StdMaybe, which is the result of yet another ugly hack in the libraries translated from Haskell's Data to get functionality before Clean's own libraries are equally complete.

Takes input via command-line arguments.

\$\endgroup\$
  • \$\begingroup\$ Nice submission. I updated the challenge with 2 extra input/output lines. Also strict I/O is not required. \$\endgroup\$ – arminb Feb 6 '18 at 9:55
  • \$\begingroup\$ @arminb Thanks! I'll be able to shorten it a lot tomorrow in that case. \$\endgroup\$ – Οurous Feb 6 '18 at 10:01
  • \$\begingroup\$ @arminb I've updated it so it should be valid with the new cases. If the I/O I've used isn't acceptable, I'll revise it again in the morning. \$\endgroup\$ – Οurous Feb 6 '18 at 10:18
0
\$\begingroup\$

Perl, 40 bytes

Inludes +1 for a

perl -aE 'say/$/*grep${$.}{$_*$`|1}^=1,@F for-1,1' <<< "7 8 100 101 222 223"

Output is not ordered.

Assumes positive page numbers (especially no page 0). Assumes missing pages are only mentioned once. Doesn't care if the input is ordered or not.

Processing only one book per run saves 3 bytes for 37:

perl -aE 'say/$/*grep$z{$_*$`|1}^=1,@F for-1,1' <<< "7 8 100 101 222 223"
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.