19
\$\begingroup\$

A stem and leaf plot displays a bunch of numerical values in groups, which are determined by all but the last digit. For example, suppose we have this set of data:

0, 2, 12, 13, 13, 15, 16, 20, 29, 43, 49, 101

We could produce this stem and leaf plot:

0|02
1|23356
2|09
3|
4|39
5|
6|
7|
8|
9|
10|1

The first row's stem is 0, so its "leaves" - the digits after the | - represent the values between 0 inclusive and 10 exclusive. The leaves on each stem are sorted. Stems with no leaves (like 3) still appear in the plot. The value of 101 is between 100 inclusive and 110 exclusive, so its stem is 10 (100 divided by 10).

Your challenge is to check whether a piece of text is a valid stem and leaf plot. A valid plot satisfies these rules:

  • Has exactly one row for every stem (i.e. 10-wide group) in the range of the data (including stems in the middle of the range with no leaves)
  • Has no stems outside the range
  • All leaves are sorted ascending to the right
  • All stems are sorted ascending down
  • Has only numeric characters (besides the separator |)

You do not have to deal with numbers that have fractional parts. You may approve or reject extra leading zeros in the stems, but a blank stem is not allowed. There will be at least one value. You may only assume extra spaces after the leaves on each row. You may assume a leading and/or trailing newline. All characters will be printable ASCII.

Your function or program should return or output (to screen or the standard output) a truthy value for a valid plot, or a falsy value for an invalid plot. You may take input from the standard input, from a file, as one big string, as an array of strings - whatever is most convenient.

Here are some test cases that are valid plots (separated by blank lines):

2|00003457
3|35
4|799
5|3

99|3
100|0556
101|
102|
103|8

0|0

Here are some test cases that are invalid plots, with commentary to the right:

|0               Blank stem

5|347            Missing a stem (6) in the range
7|9

4|               Has a stem (4) outside the range
5|26
6|7

11|432           Leaves aren't sorted correctly
12|9989

5|357            Stems aren't sorted correctly
4|002
6|1

4|5              Duplicate stem
4|6
4|6
5|1

51114            No stem and leaf separator
609

1|2|03           Multiple separators
2|779|

4|8abcdefg9      Invalid characters
5|1,2,3

75 | 4 6         Invalid characters (spaces)
76 | 2 8 8 9

This is code golf, so the shortest code wins! Standard loopholes are disallowed.

\$\endgroup\$
  • 3
    \$\begingroup\$ This is a very nice first challenge, awesome job! :) I’d add an invalid test case that has a line like 1|2|3 in it. \$\endgroup\$ – Lynn Sep 13 '16 at 22:20
  • 1
    \$\begingroup\$ Excellent first challenge! \$\endgroup\$ – AdmBorkBork Sep 14 '16 at 1:42
  • \$\begingroup\$ Nice first challenge. One test case you maybe could add is similar to the 4|;5|26;6|7 which has the first stem outside the range, but instead at the end, i.e. 12|3;13|4559;14|. \$\endgroup\$ – Kevin Cruijssen Sep 14 '16 at 7:07
4
\$\begingroup\$

Perl, 47 bytes

Includes +2 for -0p

Give input on STDIN

stem.pl:

#!/usr/bin/perl -0p
$"="*";$_=/^((??{$_+$n++})\|@{[0..9,"
"]})+$/
\$\endgroup\$
  • \$\begingroup\$ This is awsome... That trick with $" is very nice! \$\endgroup\$ – Dada Sep 14 '16 at 11:38
2
\$\begingroup\$

Pip, 60 58 + 1 = 59 bytes

First stab at the problem, probably could use more golfing. Uses the -r flag to read lines of input from stdin. Truthy output is 1, falsy output is 0 or empty string.

g=a+,#g&a@vNE'|NEg@v@v&$&{Y(a^'|1)a@`^\d+\|\d*$`&SNy=^y}Mg

Explanation and test suite pending, but in the meantime: Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript, 189 bytes

(x,y=x.split`
`.map(a=>a.split`|`),z=y.map(a=>a[0]))=>!(/[^0-9|\n]|^\|/m.exec(x)||/^\d+\|\n|\|$/.exec(x)||y.some((c,i,a)=>c.length!=2||c[1]!=[...c[1]].sort().join``)||z!=z.sort((a,b)=>a-b))

Same length alternate solution:

(x,y=x.split`
`.map(a=>a.split`|`),z=y.map(a=>a[0]))=>!(/[^0-9|\n]|^\||^.*\|.*\|.*$/m.exec(x)||/^\d+\|\n|\|$/.exec(x)||y.some((c,i,a)=>c[1]!=[...c[1]].sort().join``)||z!=z.sort((a,b)=>a-b))

Defines an anonymous function that takes input as a multiline string.

I'm sure there's more to golf, so let me know if you see any possible improvements.

Explanation:

The function checks for a number of bad things, and if any of those are true, it returns false (using logical ORs and a NOT)

(x,y=x.split("\n").map(a=>a.split`|`),          //y is input in pairs of stem and leaves
z=y.map(a=>a[0]))                               //z is stems
=>                                              //defines function
!(                                              //logical not
/[^0-9|\n]|^\|/m.exec(x)                        //checks for invalid chars and blank stems
||/^\d+\|\n|\|$/.exec(x)                        //checks for stems out of range
||y.some((c,i,a)=>c.length!=2                   //checks for multiple |s in a line
||c[1]!=[...c[1]].sort().join``))               //checks if leaves are in wrong order
||z!=z.sort((a,b)=>a-b))                        //checks for stems in wrong order

In the alternate solution, checking for multiple |s in a line is done as part of the first regex instead.

\$\endgroup\$
  • \$\begingroup\$ If you use test instead of exec (you nearly always want to use test if you only need a boolean result`) then you can probably use bitwise or instead of logical or. \$\endgroup\$ – Neil Sep 14 '16 at 8:34
  • \$\begingroup\$ Does this actually check for duplicate or missing stems? \$\endgroup\$ – Neil Sep 14 '16 at 8:57
  • \$\begingroup\$ You could save some bytes replacing y.some((c,i,a)=>... by y.some(c=>... since i and a are not used. And seems like z!=z.sort((a,b)=>a-b) does not work it could be replaced by ''+z!=z.sort() \$\endgroup\$ – Hedi Sep 17 '16 at 13:53
1
\$\begingroup\$

Batch, 409 bytes

echo off
set/pp=||exit/b1
set t=
set i=%p:|=&set t=%
if "%t%"=="" exit/b1
for /f "delims=0123456789" %%s in ("%i%")do exit/b1
:l
set t=-
set s=%p:|=&set t=%
if "%s%"=="" exit/b1
if not "%s%"=="%i%" exit/b1
set/ai+=1
for /f "delims=0123456789" %%s in ("%t%")do exit/b1
:m
if "%t:~1,1%"=="" goto n
if %t:~0,1% gtr %t:~1,1% exit/b1
set t=%t:~1%
goto m
:n
set/pp=&&goto l
if "%t%"=="" exit/b1

Takes input on STDIN, but exits as soon as it sees an error.

\$\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.