6
\$\begingroup\$

Came over a similar problem in a project I'm working on and found it quite hard to solve it without excesive use of if. I'm eager to see if anyone can come up with more elegant solutions to this, with the aribitary numbers I have given to the line segments.

The problem

You are given two integers that act like the end points of a line segment. Determine what existing line segments this line will overlap with.

Intervals / line segments

The other lines, named Q, W, E, R and T, are as following:

Q:   0 -   7
W:   8 -  18
E:  19 -  32
R:  33 - 135
T: 136 - 

The last one, T, starts at 136 and has no end point.

Example

Given the numbers 5 and 27, the line will overlapp with Q, W and E. This can be roughly illustrated like this:

    Q  W   E       R           T 
---+--+---+-------+-----------+-----
   0  7   18      32         135

     +---------+
     5         27

  (somewhat arbitrary scale)

Input

Two integers from stdin.

Output

A String containing the names of the lines that our new line overlap with, for instance in the example above QWE.

Rules

Shortest code.

\$\endgroup\$
  • \$\begingroup\$ The numbers 18 and 32 should give WE right? \$\endgroup\$ – grc Jun 11 '12 at 11:51
  • \$\begingroup\$ Do we hard-code the line segments, then? \$\endgroup\$ – Peter Taylor Jun 11 '12 at 12:02
  • \$\begingroup\$ @grc: yes. Peter: yes. \$\endgroup\$ – daniero Jun 11 '12 at 12:27

12 Answers 12

6
\$\begingroup\$

GolfScript (43 32 30 chars)

Contains escape characters. As a hex dump:

00000000  7e 29 27 51 08 57 0b 45  0e 52 67 27 32 2f 7b 29  |~)'Q.W.E.Rg'2/{)|
00000010  2a 7d 25 27 54 27 32 24  2a 2b 3c 3e 2e 26        |*}%'T'2$*+<>.&|

Base-64 encoded:

fiknUQhXC0UOUmcnMi97KSp9JSdUJzIkKis8Pi4m

Using bold to indicate escape characters:

~)'Q^HW^KE^NRg'2/{)*}%'T'2$*+<>.&

Thanks to Howard for the suggestion to use escape characters.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I was just trying this out in the online golfscript tester to see how it worked and kept getting a 'negative argument' error at the {~*}% bit. I preceded the code with 5 27. What am I doing wrong? \$\endgroup\$ – Gareth Jun 11 '12 at 15:07
  • \$\begingroup\$ @Gareth, the tester starts with the empty string on the stack from stdin; you need to pop that with ; and then add the string which you're simulating as coming from stdin. So you need to precede with ;'5 27' rather than just 5 27. \$\endgroup\$ – Peter Taylor Jun 11 '12 at 15:38
  • 2
    \$\begingroup\$ Maybe you can use 'Q\x8W\x0bE\xeRgT\x1c'2/{)*}% to generate your string? It is -5 chars if you use escapes and even less if you directly encode the values. \$\endgroup\$ – Howard Jun 11 '12 at 18:50
  • \$\begingroup\$ @Howard correct, but the string should be enclosed in double quotes \$\endgroup\$ – Cristian Lupascu Jun 11 '12 at 19:44
  • \$\begingroup\$ @Howard, not quite: the 9$ after 'T' was to ensure that the string is long enough not to be truncated to the empty string by <, so that still needs some special treatment. But otherwise, yes, that works and is useful. \$\endgroup\$ – Peter Taylor Jun 11 '12 at 21:55
9
\$\begingroup\$

APL (39)

'QWERT'/⍨1↓⊃≠/1 0⌽¨0,¨0 7 18 32 135∘<¨⎕

Takes input as two whitespace-separated numbers.

Explanation:

  • 0 7 18 32 135∘<¨⎕: For each number in the input, see if 0, 7, 18, 32, and/or 135 is smaller than the number. If the input was 5 27 we now have (1 0 0 0 0) (1 1 1 0 0). (The first one is taken to be the start of the line and the second one the end).
  • 1 0⌽¨0,¨: Prefix a zero to each of those lists and rotate the first one left by 1. (We now have (1 0 0 0 0 0) (0 1 1 1 0 0)).
  • ≠/: Gives a list where the individual items of the two input lists were not equal. (We now have 1 1 1 1 0 0).
  • 1↓⊃: Remove the first item from this list. The other five stand for whether or not to display a Q, W, E, R or T.
  • 'QWERT'/⍨: For each letter, output N of those letters, where N is the corresponding value in the list on the right. Since the list was 1 1 1 0 0 the answer is QWE.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice soution and very nice explanation! \$\endgroup\$ – daniero Jun 12 '12 at 8:15
6
\$\begingroup\$

Python 82 84

There you are. Edit: Fixed for inputs like -1 10 and -10 -1 for 2 chars

z=lambda a:(a>7)+(a>18)+(a>32)+(a>135)+1
a,b=input()
print"QWERT"[z(a)-1:z(b)*(b>0)]
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

J, 58 54 characters

'QWERT '#~0 8 19 33 136 _(([<1{])*(1|.[>:0{]))".1!:1[1

Reads one line of input from the keyboard.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Aargh! Hacky ugly code! ;) \$\endgroup\$ – Peter Taylor Jun 11 '12 at 22:04
3
\$\begingroup\$

Python, 79

x,y=input()
print"".join(set(("Q"*8+"W"*11+"E"*14+"R"*103)[x:y+1]))+"T"*(y>135)

It could be a lot shorter if it's allowed to leave duplicates in the output, but I figured that would be bending the rules a bit.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ How does that handle test case 500 510? \$\endgroup\$ – Peter Taylor Jun 11 '12 at 13:58
  • \$\begingroup\$ Not very well. I've fixed it now. \$\endgroup\$ – grc Jun 11 '12 at 20:57
  • \$\begingroup\$ Try -10 1. It's a pretty box clever answer though. \$\endgroup\$ – walpen Jun 11 '12 at 21:49
2
\$\begingroup\$

Scala 113

val i=Seq(0,8,19,33,136,(1<<31)-1)
i.zip(i.tail)zip("qwert")filter(x=>x._1._2>readInt&&x._1._1<=readInt)map(_._2)

Handles test cases 5-27(QWE), 400-500(T), 40-40(R), 33-33(R).

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 400-500 should be T. 40-40 and 33-33 should be R. \$\endgroup\$ – marinus Jun 11 '12 at 16:56
  • \$\begingroup\$ @marinus: You're right. For the R-cases, it was a sloppy testing, but I have to rework the solution to get the case of (400-500) right. \$\endgroup\$ – user unknown Jun 11 '12 at 18:02
2
\$\begingroup\$

K, 68 58

{$[y>135;`T,;]`Q`W`E`R@&max'(x+!1+y-x)in/:(!8;8+!11;19+!15;33+!104)}

{$[y>135;"T",;]"QWER"@&(=).'(y>'0,-1_a),'x<'a:8 19 33 136}

.

k){$[y>135;"T",;]"QWER"@&(=).'(y>'0,-1_a),'x<'a:8 19 33 136}[5;27]
"QWE"
k){$[y>135;"T",;]"QWER"@&(=).'(y>'0,-1_a),'x<'a:8 19 33 136}[0;139]
"TQWER"
k){$[y>135;"T",;]"QWER"@&(=).'(y>'0,-1_a),'x<'a:8 19 33 136}[20;135]
"ER"
k){$[y>135;"T",;]"QWER"@&(=).'(y>'0,-1_a),'x<'a:8 19 33 136}[32;135]
"ER"
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

PHP, 159 characters

<?$b=array(0=>"Q",8=>"W",19=>"E",33=>"R",136=>"T",1e9=>"");$a=split(" ",fgets(STDIN));foreach($b as $k=>$v){if($a[0]<$k&&$a[1]>=$j)$o.=$p;$p=$v;$j=$k;}echo $o;

With line breaks:

<?
$b=array(0=>"Q",8=>"W",19=>"E",33=>"R",136=>"T",1e9=>"");
$a=split(" ",fgets(STDIN));
foreach($b as $k=>$v)
{
    if($a[0]<$k&&$a[1]>=$j)
        $o.=$p;
    $p=$v;
    $j=$k;
}
echo $o;

Assumes that the line segments are contiguous and non-overlapping as in the given example.

Working version at ideone.com.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ ideone.com/DANYq should output T, outputs nothing. \$\endgroup\$ – Peter Taylor Jun 11 '12 at 14:00
  • \$\begingroup\$ @PeterTaylor Bugger. I'll have a look. \$\endgroup\$ – Gareth Jun 11 '12 at 14:09
  • 2
    \$\begingroup\$ @PeterTaylor Added an ugly hacky fix for an extra 8 characters. Maybe I'll stick to J - at least then not many people can understand how hacky and ugly my code is. :-) \$\endgroup\$ – Gareth Jun 11 '12 at 14:19
  • \$\begingroup\$ I think $a[1]>$j should be $a[1]>=$j (i.e. greater OR EQUAL) to correctly hit the edges of each range. e.g. 135 136 should output RT but just outputs R. \$\endgroup\$ – Johno Jun 12 '12 at 14:15
1
\$\begingroup\$

M (Micronetics System MUMPS 4.4) - 82 Chars

f i=1:1:2 r a s x=(a>0)+(a>7)+(a>18)+(a>32)+(a>135) w:$d(y) $e("QWERT",y,x) s y=x

5-27(QWE), 400-500(T), 40-40(R), 33-33(R).

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

PHP 119

<?fscanf(STDIN,'%d%d',$a,$b);foreach(array('Q'=>7,'W'=>18,'E'=>32,'R'=>135,'T'=>136)as$x=>$y)echo$y>=$a&&$y<=$b?$x:'';

Getting Input from command-line reduces the size, but, I don't think it is applicable here, but still:

PHP 111

<?list(,$a,$b)=$argv;foreach(array('Q'=>7,'W'=>18,'E'=>32,'R'=>135,'T'=>136)as$x=>$y)echo$y>=$a&&$y<=$b?$x:'';
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Mathematica

Cases[{{q, 0, 7}, {w, 8, 18}, {e, 19, 32}, {r, 33, 135}, {t, 136, \[Infinity]}}, 
  {a_, b_, c_} /; Length@IntervalIntersection[Interval[{b, c}], Interval[{5, 27}]] !=0 
   :> a]
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Jelly, 27 bytes (improvements wanted!)

®Ṁṭ“®¿Çg‘
ØQFḣ5ż¢Œṙ
Ɠ©r/ị¢Q

Try it online!

®Ṁṭ“®¿Çg‘    actual runlengths here
®Ṁ           recall the input numbers, and get the maximum of them
  ṭ          append that max (to be used as runlength for 'T') to...
   “®¿Çg‘    [ 8, 11, 14, 103 ] (listed as base-250 numbers on jelly's codepage)

ØQFḣ5ż¢Œṙ    run-length encoding function:
ØQF          get "QWERTYUIOPASDF..."
   ḣ5        get the first 5 characters of that to yield "QWERT"
     ż¢      zip it with the above link (RLE values)...
       Œṙ    and then apply RLE decode to produce the uncompressed string

Ɠ©r/ị¢Q      main function:
Ɠ©           take two integers from stdin, evaluate them and save them to a register
  r/         take the range between them (technically a fold)
    ị¢       for each element in the range, get the value at its index in the link above...
      Q      and return all the unique values (remove duplicates).

I think that I'm doing something wrong / non-optimally with the register save / recall to get the max value. If I just make that value 250, the program goes down to just 22 bytes:

ØQFḣ5ż“®¿Çgż‘Œṙ
Ɠr/ị¢Q

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Maybe you can do something like >“©×þ⁶‘S‘, i.e. 1+sum(x>i for i in [7,18,32,135]), and then ndex into ØQF¤. That's 21 bytes. But then inlining the whole thing gets you 20 bytes: Ɠr/>€“©×þ⁶‘ḅ1‘ịØQF¤Q using the ḅ1 trick \$\endgroup\$ – Lynn May 9 '18 at 10:17
  • \$\begingroup\$ Err, I guess that trick isn't strictly necessary here because it's just as long as S€ :) but it's good to know about! \$\endgroup\$ – Lynn May 9 '18 at 10:18

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.