Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The unnecessary and convoluted story

I am walking around manhattan, block by block and my feet have gotten tired and want to go back home.

The traffic is pretty bad, but fortunately I'm very rich and I have a helicopter on standby at the hotel. But I need them to know how much fuel to pack for the flight and for that they need to know my direct distance from the hotel. I did remember which blocks I walked and can tell them what route I took. This distance needs to be precise though, if they are too short we won't make it back, too long and I've bought fuel I can't use.

Can you write me a program to convert that into the distance they will have to travel on their flight to fetch me?

Specification:

Write me a function that:

  1. Accepts a list or string of blocks walked relative to an arbitrary grid:
    • U p, D own, L eft and R ight.
    • Can be either upper or lower case - eg. if its shorter to use u instead of U go ahead.
    • An invalid direction has undefined behaviour - eg. a direction of X can cause a failure.
  2. Returns a float/decimal/double that is twice the straight line distance from the point of origin.

For illustration and clarification:

My trip

My trip could have just as easily been recorded as "luluu..." or ['l','u','l'...] but it must be recorded as Up, Down, Left, Right.

share|improve this question
11  
You are enough rich to have an helicopter but you care if some extra fuel is bought? :O –  Fez Vrasta Feb 6 at 7:28
6  
@fezvrasta because I'm stingy. –  Lego Stormtroopr Feb 6 at 7:33
6  
Way to mess with my head by not making this about Manhattan distance. –  Kendall Frey Feb 6 at 13:33
22  
The correct answer is "It doesn't matter. You're a rich guy, so you reach into your pocket, pull out a wad of $20's, and wave it in the air to attract the attention of a cabby; you are then set upon by a group of kindergarten thugs who rob you and beat you to a bloody pulp. You are then arrested for littering and public vagrancy, charged with terrorism for attempting to cause mass panic and a pandemic by spreading your bodily ooze across a public sidewalk, convicted, sent to prison, and locked up with a cellmate nicknamed Brutus who takes a real strong liking to you. Welcome to New York!" –  Bob Jarvis Feb 6 at 13:35
2  
@McKay I interpret it as directions on a map, anyway (otherwise it'd probably be "forward" and "back"), and the distance measure is rather unambiguous "twice the straight line distance from the point of origin", so no manhattan distance). –  FireFly Feb 6 at 16:44
show 13 more comments

24 Answers 24

up vote 28 down vote accepted

J, 17 characters

2*|+/0j1^'urdl'i.

Uses the fact, that the powers of j represent the proper directions.

  • 'urdl'i. take string and calculate indices (0 for 'u', 1 for 'r', ...)
  • 0j1^ transforms into the direction in the complex plane using the corresponding power of j.
  • +/ sums up the single steps
  • 2*| two times the modulus

Example:

> 2*|+/0j1^'urdl'i.'uuuudrrrl'
7.2111
share|improve this answer
5  
Nice job. Maths knowledge for the win. :-) –  Gareth Feb 6 at 10:35
    
Make this "non-extended" ASCII and then it's just 15 bytes (because you don't use the eighth bit). –  Timtech Feb 8 at 0:40
add comment

Python 2.7 56 58 56 51 48

With the stolen Number One Dime from Scrooge McDuck, I made my fortune and now have more wealth than Scrooge.

y=lambda s:2*abs(sum(1j**(ord(i)%15)for i in s))

Python 2.7 - 61 53 50 (case insensitive)

y=lambda s:2*abs(sum(1j**(ord(i)%16%9)for i in s))

Implementation

>>> from random import sample
>>> y=lambda s:2*abs(sum((-1j)**(ord(i)%15)for i in s))
>>> path=sample('RLUD'*1000, 100)
>>> y(path)
20.0
>>> path=sample('RLUD'*1000, 100)
>>> y(path)
34.058772731852805
share|improve this answer
    
I am getting IndexError: list index out of range. What form should the input have? –  plannapus Feb 6 at 9:01
    
@plannapus: I have added an implementation section –  Abhijit Feb 6 at 9:02
    
Ah and it was %5 not %8. Ok it makes more sense now :) –  plannapus Feb 6 at 9:04
add comment

APL (29)

{|+/2 0j2×-⌿2 2⍴+/'URDL'∘.=⍵}

e.g.

     {|+/2 0j2×-⌿2 2⍴+/'URDL'∘.=⍵} 'UUUUDRRRL'
7.211102551

Explanation:

  • +/'URDL'∘.=⍵: see how often the characters URDL occur in the argument
  • -⌿2 2⍴: subtract the U value from the D value, and the R value from the L value
  • 2 0j2×: multiply the vertical value by 2 and the horizontal value by 2i
  • +/: sum
  • |: magnitude
share|improve this answer
add comment

Ruby 1.9+ (67)

f=->s{2*(((g=s.method :count)[?U]-g[?D])**2+(g[?R]-g[?L])**2)**0.5}

Example

f["DRUULULLULL"] => 10.0
f["UUUUDRRRL"] => 7.211102550927978
share|improve this answer
add comment

Python 2.7 - 65

Nice and short one, this uses complex numbers to step through the plane:

x=lambda s:2*abs(sum([[1,-1,1j,-1j]['RLUD'.index(i)]for i in s]))

Props to DSM and Abhijit in other questions that showed me the use of 1j to calculate this.

share|improve this answer
    
Can 1j be written as j, -1j as -j? Also, does this handle upper and lower input, or only upper? –  David Carraher Feb 6 at 4:13
1  
Uncle Scrooze, I hate you. You should at least leave some money for your nephews. –  Abhijit Feb 6 at 8:38
1  
@DavidCarraher: No you can't. It would be impossible to differentiate between the variable j and the imaginary unit j –  Abhijit Feb 6 at 8:53
    
Didn't you say it was supposed to output twice the distance? when trying with UUUUDRRRL i'm getting 3.606 with this function instead of 7.21. –  plannapus Feb 6 at 8:59
3  
You can save 2 more characters, by multiplying the constants by 2 instead of multiplying the final result. –  Abhijit Feb 6 at 9:16
show 1 more comment

Mathematica 92 49

Calle deserves full credit for streamlining the code.

f@l_:=2 N@Norm[Tr[l/.{"r"→1,"l"→-1,"u"→I,"d"→-I}]]

Example

f[{"u", "u", "u", "u", "d", "r", "r", "r", "l"}]

7.2111

share|improve this answer
1  
You're doing a lot of work that isn't required by the OP, f@l_ := 2 N@Norm[Tr[l /. {"r" -> 1, "l" -> -1, "u" -> I, "d" -> -I}]] will suffice. –  Calle Feb 6 at 17:25
    
I get 2 Norm[(2. + 2. I) + "U" + "X"] as the output for your code. –  David Carraher Feb 6 at 17:38
1  
Yes, but the OP says it's OK to fail with such input. That is how I and everyone else interpret it. I can't read these other languages, but you will see that they often hardcode for u, r, l and d. –  Calle Feb 6 at 17:40
    
Ok. Got it. Thanks for pointing that out. –  David Carraher Feb 6 at 17:41
    
If you replace two remaining pairs of parentheses with @s you get another two characters less. –  shrx Feb 7 at 0:50
show 1 more comment

perl6: 44 chars

2*abs [+] i <<**>>%(<U R D L>Z ^4){get.comb}
  • get.comb gets one line of input and splits into characters
  • <U R L D> is a list of words, chars in this case
  • (1,2,3) Z (4,5,6) == (1,2), (2,5), (3,6), so it zips 2 lists into each other, making a list of parcels that %() turns into a hash
  • <<**>> does pairwise **, extending the shorter list to fit the longer. Shorter list happens to only be i
  • [+] sums all elements of a list, abs takes the modulus for complex numbers

Yes, I removed all possible spaces.

share|improve this answer
add comment

Julia, 45

f(l)=2*abs(sum([im^(c=='d'?3:c) for c in l]))

Stole the i to powers trick. Also all the characters except d have values that work as acceptable powers for i.

share|improve this answer
add comment

J, 29 characters

+:+&.*:/-/_2[\#/.~/:~'ruld'i.

Only works with lower case directions and any characters other than r, u, l, and d will cause it to give a wrong answer.

Usage:

   +:+&.*:/-/_2[\#/.~/:~'ruld'i.'uuuudrrrl'
7.2111

Explanation:

'ruld'i.'uuuudrrrl' The dyadic form of i. finds the index of items from the right argument in the left argument. In this case:

   'ruld'i.'uuuudrrrl'
1 1 1 1 3 0 0 0 2

/:~ sorts this list into ascending order:

   /:~'ruld'i.'uuuudrrrl'
0 0 0 1 1 1 1 2 3

#/.~ counts the number of occurrences of each number:

   #/.~/:~'ruld'i.'uuuudrrrl'
3 4 1 1

_2[\ chops it into 2 rows:

   _2[\#/.~/:~'ruld'i.'uuuudrrrl'
3 4
1 1

-/ subtracts the bottom from the top

   -/_2[\#/.~/:~'ruld'i.'uuuudrrrl'
2 3

+&.*: borrows a trick from another J answer I saw this morning, and squares the items, then sums them, then performs a square root. See under &. documentation:

   +&.*:/-/_2[\#/.~/:~'ruld'i.'uuuudrrrl'
3.60555

+: doubles the result:

   +:+&.*:/-/_2[\#/.~/:~'ruld'i.'uuuudrrrl'
7.2111
share|improve this answer
add comment

R, 86 74 56 characters

Ok it's actually way shorter with imaginary numbers indeed:

2*Mod(sum(sapply(scan(,""),switch,u=1i,d=-1i,l=-1,r=1)))

Usage:

> 2*Mod(sum(sapply(scan(,""),switch,u=1i,d=-1i,l=-1,r=1)))
1: u u u u d r r r l
10: 
Read 9 items
[1] 7.211103

Old solution at 74 characters with xy coords:

2*sqrt(sum(rowSums(sapply(scan(,""),switch,u=0:1,d=0:-1,l=-1:0,r=1:0))^2))

Usage:

> 2*sqrt(sum(rowSums(sapply(scan(,""),switch,u=0:1,d=0:-1,l=-1:0,r=1:0))^2))
1: u u u u d r r r l
10: 
Read 9 items
[1] 7.211103

Takes input as stdin, need to be lower-case and space-separated. Use x-y coordinates starting from (0,0).

share|improve this answer
add comment

k (50 49)

{2*sqrt x$x:0 0f+/("udlr"!(1 0;-1 0;0 -1;0 1))@x}

Example

{2*sqrt x$x:0 0f+/("udlr"!(1 0;-1 0;0 -1;0 1))@x}"uuuudrrrl"
7.211103
share|improve this answer
add comment

Java, 185, 203, 204, 217, 226

class A{public static void main(String[] a){int x=0,y=0;for(int i=0;i<a[0].length();i++) switch(a[0].charAt(i)){case'U':y++;break;case'D':y--;break;case'L':x++;break;case'R':x--;}System.out.print(Math.hypot(x,y)*2);}}

I did assume that each "U" was "1 up", so two units up would be "UU"

Edit: swapped out switch for ifs

class A{public static void main(String[]a){int x=0,y=0;for(int i=0;i<a[0].length();i++){int c=a[0].charAt(i);if(c=='U')y++;if(c=='D')y--;if(c=='L')x++;if(c=='R')x--;}System.out.print(Math.hypot(x,y)*2);}}

Moved for iterator

class A{public static void main(String[]a){int x=0,y=0;for(int i=0;i<a[0].length();){int c=a[0].charAt(i++);if(c=='U')y++;if(c=='D')y--;if(c=='L')x++;if(c=='R')x--;}System.out.print(Math.hypot(x,y)*2);}}

No longer takes input as string, rather array of directions

class A{public static void main(String[]a){int x=0,y=0;for(String s:a){char c=s.charAt(0);if(c=='U')y++;if(c=='D')y--;if(c=='L')x++;if(c=='R')x--;}System.out.print(Math.hypot(x,y)*2);}}
share|improve this answer
    
My understanding of the brief was that you only need a function, not a whole program. –  Boann Feb 6 at 18:32
add comment

PHP, 67

function f($a){foreach($a as$d)@$$d++;return 2*hypot($U-$D,$L-$R);}

Example:

<?php
var_dump(f(array('U', 'U', 'U', 'U', 'D', 'R', 'R', 'R', 'L')));

>float(7.211102550928)
share|improve this answer
add comment

T-SQL, 158

IF PATINDEX('%[^UDLR]%', @s)=0 select 2*sqrt(power(LEN(REPLACE(@s,'U',''))-LEN(REPLACE(@s,'D','')),2)+power(LEN(REPLACE(@s,'L',''))-LEN(REPLACE(@s,'R','')),2))

The @s is the input string of varchar(max) type

share|improve this answer
add comment

VB.net (Non-Golfed)

Dim g = From c In "UDLR"
        Group Join d In directions
        On c Equals d
        Into q=Group
        Select q.Count 
Dim f = 2*Math.Sqrt((g(0)-g(1))^2 + (g(2)-g(3))^2)
share|improve this answer
    
If we were allowed to use Let before the From it would be a single line. –  Adam Speight Feb 7 at 18:12
add comment

ES6, 77 69

Definition:

f=s=>{u=d=l=r=0;for(c of s)eval(c+'++');return 2*Math.hypot(u-d,l-r)}

Usage:

>>> f('uuuudrrrl')
7.211102550927979
>>> f( 'uuuudrrrl'.split('') )
7.211102550927979
  • Accepts string OR array (lowercase)
  • Doesn't use imaginary numbers
  • Would not have been possible just 3 days before OP posted the question; that is, it only runs in Firefox 27+ (and maybe also Chrome with experimental stuff enabled, haven't tested :)!!

(Inspired partially by Boann's answer.)

share|improve this answer
    
I really wanna do something tricky to get rid of the return, like turn the whole thing into a boolean expression that just gets evaluated and returned automagically, but I'm not sure there's a way to do this unless I can replace the for statement with some expression (an arrow function body containing statements require the brackets and the explicit return, bodies that are just expressions don't).. –  Noyo Feb 7 at 17:54
add comment

C# - 90 characters

Fresh from LINQPad.

int x=0,y=0;input.Max(i=>i==85?y++:i==82?x++:i==68?y--:x--);(Math.Sqrt(x*x+y*y)*2).Dump();

Where input is a valid string.

string input = "LULUURRRRURD";

8.48528137423857

share|improve this answer
add comment

JavaScript - 142 characters - no eval()

function r(a){return Math.sqrt(Math.pow(a.match(/u/g).length-a.match(/d/g).length,2)+Math.pow(a.match(/l/g).length-a.match(/r/g).length,2))*2}

where a is a string like 'uudrrl'

use like this -

a='uudrrl'
r(a)

Test in browser console.

var x = "luluurrrrurd"
r(x)
8.48528137423857
share|improve this answer
add comment

Befunge-93 (65)

It has 65 non-whitespace characters (217 with whitespace, though that can be reduced by a more compact layout (for 69/176 chars)). It takes some liberality with the output format, but is undeniably accurate. Doesn't seem worth the effort to implement/steal a square root implementation.

v                  >$:*\:*+88*4*5-2.,.@
               >3-:|
           >6-:|
       >8-:|
>~"D"-:|
       $   $   $   $
           \   \
       1   1   1   1
       -   -   +   +
           \   \
^      <   <   <   <

echo 'UUDLLUU' | ./befungee.py ../man outputs 2√13 (actually implementation seems to have issue with the extended ASCII though).

share|improve this answer
add comment

Matlab, 51 characters

My Matlab submission, works only with captial letters. This was a fun one! The hardest part was converting the string into an array of complex numbers to be summed.

Function:

f=@(s)abs(sum(fix((s-76.5)/8.5)+((s-79)*i/3).^-99))

Usage:

>> f=@(s)abs(sum(fix((s-76.5)/8.5)+((s-79)*i/3).^-99))
>> f('UURDL')
ans =

     1
>>
share|improve this answer
add comment

Javascript, 136

function z(a){var x=a.split('u').length-a.split('d').length;var y=a.split('r').length-a.split('l').length;return Math.sqrt(x*x+y*y)*2;};
document.write(z('uuuudrrrwl'));
7.211102550927978
share|improve this answer
add comment

JavaScript, 89

function f(a){U=D=L=R=0;for(d in a)eval(a[d]+'++');return 2*Math.sqrt((U-=D)*U+(L-=R)*L)}

Example:

<script>
document.write(f(['U', 'U', 'U', 'U', 'D', 'R', 'R', 'R', 'L']));
</script>

>7.211102550927978
share|improve this answer
add comment

C, 120

float d(char *p){int v=0,h=0;while(*p){v+=*p=='U'?1:*p=='D'?-1:0,h+=*p=='R'?1:*p=='L'?-1:0,++p;}return 2*sqrt(v*v+h*h);}

d("LULUURRRRURD") -> 8.485281

share|improve this answer
add comment

JavaScript (no ES6, no eval) - 131

f=function(h){for(i=0,a=[0,,0,0,0];i<h.length;++i)++a[(h.charCodeAt(i)>>2)-25];x=a[0]-a[4];y=a[2]-a[3];return Math.sqrt(x*x+y*y)*2}

Test:

console.log(f('uuuudrrrl'));     // 7.211102550927978 
console.log(f('luluurrrrurd'));  // 8.48528137423857
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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