# Question
Title: Create self-extractor script (relaxed rules)
This is the target language-relaxed version of Generate a self-extractor application

Create a program in *any* language, that takes an arbitrary binary input, and generates a valid program (also in *any* language), which when compiled and run (or interpreted) will print this binary input.

So you could do this:

```
$ cat file.dat | python program.py > gen.rb
$ ruby gen.rb > file.dat.new
$ diff file.dat file.dat.new
$ echo $?
0

```

The scoring depends on the byte count of the original code (**O**), and the square of the byte count of the generated codes for the following inputs:

* **A**: The whole lyrics of Never gonna give you up
* **B**: The uncompressed grayscale 32x32 BMP version of Lena Söderberg
* **C**: The original source code (the generator, **O**)
* **D**: The generated source code for the **A** input

Score is **O** \+ max(**A**, **O**)^2 + max(**B**, **O**)^2 + max(**C**, **O**)^2 + max(**D**, **O**)^2.

Score explained:

1. The values for the generated variants are squared to encourage optimizing the size of the generated code (and the size of the original code is reflected in **C** as well).
2. Also to encourage minimizing the length of the generator code (as opposed to the generated code), if the generated code is smaller than the generator, then the size of the generator will be used instead.

Lowest score wins.

Clarification of the rules:

* You can use the standard libraries of the chosen language(s), except for libraries that are designed (or can be used *directly*) for compression and/or decompression (like zlib, bz2, etc.). Using other kinds of libraries, like `base64` are fine, but they have to be part of the standard library of the chosen language(s).
* The generated code has to be able to print the original data without any external help, like network connections or pipes, etc. (e.g. if you move the `gen.exe` to another, isolated computer it should be able to generate the output there as well). You also have to assume that the generated code (if you are using an interpreted target language) will be run the following way: `$ langint script.scr > output` where `langint` is the interpreter of your chosen language.
* The code generator should also work for any other input (generates code that regenerates the original input), but compression performance for them is not measured in the score (this means that optimizing the generator only for the test inputs are okay). However if there is (or anyone finds) at least one input with a maximum size of 65535 for which the code generator does not work, then the score of the submission is *infinite*.
* The input files are supplied in base64 to make sure everyone will run the app on the same inputs. Please note that the lyrics have windows style line endings. Base64 decoding of the input is not part of the challenge, it can be done separately (eg the `file.dat` on the example is already the base64 decoded file).

File inputs *in base 64*:

**Never gonna give you up**

```
V2UncmUgbm8gc3RyYW5nZXJzIHRvIGxvdmUNCllvdSBrbm93IHRoZSBydWxlcyBhbmQgc28gZG8g
SQ0KQSBmdWxsIGNvbW1pdG1lbnQncyB3aGF0IEknbSB0aGlua2luZyBvZg0KWW91IHdvdWxkbid0
IGdldCB0aGlzIGZyb20gYW55IG90aGVyIGd1eQ0KSSBqdXN0IHdhbm5hIHRlbGwgeW91IGhvdyBJ
J20gZmVlbGluZw0KR290dGEgbWFrZSB5b3UgdW5kZXJzdGFuZA0KDQpOZXZlciBnb25uYSBnaXZl
IHlvdSB1cA0KTmV2ZXIgZ29ubmEgbGV0IHlvdSBkb3duDQpOZXZlciBnb25uYSBydW4gYXJvdW5k
IGFuZCBkZXNlcnQgeW91DQpOZXZlciBnb25uYSBtYWtlIHlvdSBjcnkNCk5ldmVyIGdvbm5hIHNh
eSBnb29kYnllDQpOZXZlciBnb25uYSB0ZWxsIGEgbGllIGFuZCBodXJ0IHlvdQ0KDQpXZSd2ZSBr
bm93biBlYWNoIG90aGVyIGZvciBzbyBsb25nDQpZb3VyIGhlYXJ0J3MgYmVlbiBhY2hpbmcgYnV0
DQpZb3UncmUgdG9vIHNoeSB0byBzYXkgaXQNCkluc2lkZSB3ZSBib3RoIGtub3cgd2hhdCdzIGJl
ZW4gZ29pbmcgb24NCldlIGtub3cgdGhlIGdhbWUgYW5kIHdlJ3JlIGdvbm5hIHBsYXkgaXQNCkFu
ZCBpZiB5b3UgYXNrIG1lIGhvdyBJJ20gZmVlbGluZw0KRG9uJ3QgdGVsbCBtZSB5b3UncmUgdG9v
IGJsaW5kIHRvIHNlZQ0KDQpOZXZlciBnb25uYSBnaXZlIHlvdSB1cA0KTmV2ZXIgZ29ubmEgbGV0
IHlvdSBkb3duDQpOZXZlciBnb25uYSBydW4gYXJvdW5kIGFuZCBkZXNlcnQgeW91DQpOZXZlciBn
b25uYSBtYWtlIHlvdSBjcnkNCk5ldmVyIGdvbm5hIHNheSBnb29kYnllDQpOZXZlciBnb25uYSB0
ZWxsIGEgbGllIGFuZCBodXJ0IHlvdQ0KDQpOZXZlciBnb25uYSBnaXZlIHlvdSB1cA0KTmV2ZXIg
Z29ubmEgbGV0IHlvdSBkb3duDQpOZXZlciBnb25uYSBydW4gYXJvdW5kIGFuZCBkZXNlcnQgeW91
DQpOZXZlciBnb25uYSBtYWtlIHlvdSBjcnkNCk5ldmVyIGdvbm5hIHNheSBnb29kYnllDQpOZXZl
ciBnb25uYSB0ZWxsIGEgbGllIGFuZCBodXJ0IHlvdQ0KDQooT29oLCBnaXZlIHlvdSB1cCkNCihP
b2gsIGdpdmUgeW91IHVwKQ0KKE9vaCkNCk5ldmVyIGdvbm5hIGdpdmUsIG5ldmVyIGdvbm5hIGdp
dmUNCihHaXZlIHlvdSB1cCkNCihPb2gpDQpOZXZlciBnb25uYSBnaXZlLCBuZXZlciBnb25uYSBn
aXZlDQooR2l2ZSB5b3UgdXApDQoNCldlJ3ZlIGtub3cgZWFjaCBvdGhlciBmb3Igc28gbG9uZw0K
WW91ciBoZWFydCdzIGJlZW4gYWNoaW5nIGJ1dA0KWW91J3JlIHRvbyBzaHkgdG8gc2F5IGl0DQpJ
bnNpZGUgd2UgYm90aCBrbm93IHdoYXQncyBiZWVuIGdvaW5nIG9uDQpXZSBrbm93IHRoZSBnYW1l
IGFuZCB3ZSdyZSBnb25uYSBwbGF5IGl0DQoNCkkganVzdCB3YW5uYSB0ZWxsIHlvdSBob3cgSSdt
IGZlZWxpbmcNCkdvdHRhIG1ha2UgeW91IHVuZGVyc3RhbmQNCg0KTmV2ZXIgZ29ubmEgZ2l2ZSB5
b3UgdXANCk5ldmVyIGdvbm5hIGxldCB5b3UgZG93bg0KTmV2ZXIgZ29ubmEgcnVuIGFyb3VuZCBh
bmQgZGVzZXJ0IHlvdQ0KTmV2ZXIgZ29ubmEgbWFrZSB5b3UgY3J5DQpOZXZlciBnb25uYSBzYXkg
Z29vZGJ5ZQ0KTmV2ZXIgZ29ubmEgdGVsbCBhIGxpZSBhbmQgaHVydCB5b3UNCg0KTmV2ZXIgZ29u
bmEgZ2l2ZSB5b3UgdXANCk5ldmVyIGdvbm5hIGxldCB5b3UgZG93bg0KTmV2ZXIgZ29ubmEgcnVu
IGFyb3VuZCBhbmQgZGVzZXJ0IHlvdQ0KTmV2ZXIgZ29ubmEgbWFrZSB5b3UgY3J5DQpOZXZlciBn
b25uYSBzYXkgZ29vZGJ5ZQ0KTmV2ZXIgZ29ubmEgdGVsbCBhIGxpZSBhbmQgaHVydCB5b3UNCg0K
TmV2ZXIgZ29ubmEgZ2l2ZSB5b3UgdXANCk5ldmVyIGdvbm5hIGxldCB5b3UgZG93bg0KTmV2ZXIg
Z29ubmEgcnVuIGFyb3VuZCBhbmQgZGVzZXJ0IHlvdQ0KTmV2ZXIgZ29ubmEgbWFrZSB5b3UgY3J5
DQpOZXZlciBnb25uYSBzYXkgZ29vZGJ5ZQ0KTmV2ZXIgZ29ubmEgdGVsbCBhIGxpZSBhbmQgaHVy
dCB5b3U=

```

**Lena**

```
Qk02CAAAAAAAADYEAAAoAAAAIAAAACAAAAABAAgAAAAAAAAEAAB1CgAAdQoAAAABAAAAAAAAAAAA
AAEBAQACAgIAAwMDAAQEBAAFBQUABgYGAAcHBwAICAgACQkJAAoKCgALCwsADAwMAA0NDQAODg4A
Dw8PABAQEAAREREAEhISABMTEwAUFBQAFRUVABYWFgAXFxcAGBgYABkZGQAaGhoAGxsbABwcHAAd
HR0AHh4eAB8fHwAgICAAISEhACIiIgAjIyMAJCQkACUlJQAmJiYAJycnACgoKAApKSkAKioqACsr
KwAsLCwALS0tAC4uLgAvLy8AMDAwADExMQAyMjIAMzMzADQ0NAA1NTUANjY2ADc3NwA4ODgAOTk5
ADo6OgA7OzsAPDw8AD09PQA+Pj4APz8/AEBAQABBQUEAQkJCAENDQwBEREQARUVFAEZGRgBHR0cA
SEhIAElJSQBKSkoAS0tLAExMTABNTU0ATk5OAE9PTwBQUFAAUVFRAFJSUgBTU1MAVFRUAFVVVQBW
VlYAV1dXAFhYWABZWVkAWlpaAFtbWwBcXFwAXV1dAF5eXgBfX18AYGBgAGFhYQBiYmIAY2NjAGRk
ZABlZWUAZmZmAGdnZwBoaGgAaWlpAGpqagBra2sAbGxsAG1tbQBubm4Ab29vAHBwcABxcXEAcnJy
AHNzcwB0dHQAdXV1AHZ2dgB3d3cAeHh4AHl5eQB6enoAe3t7AHx8fAB9fX0Afn5+AH9/fwCAgIAA
gYGBAIKCggCDg4MAhISEAIWFhQCGhoYAh4eHAIiIiACJiYkAioqKAIuLiwCMjIwAjY2NAI6OjgCP
j48AkJCQAJGRkQCSkpIAk5OTAJSUlACVlZUAlpaWAJeXlwCYmJgAmZmZAJqamgCbm5sAnJycAJ2d
nQCenp4An5+fAKCgoAChoaEAoqKiAKOjowCkpKQApaWlAKampgCnp6cAqKioAKmpqQCqqqoAq6ur
AKysrACtra0Arq6uAK+vrwCwsLAAsbGxALKysgCzs7MAtLS0ALW1tQC2trYAt7e3ALi4uAC5ubkA
urq6ALu7uwC8vLwAvb29AL6+vgC/v78AwMDAAMHBwQDCwsIAw8PDAMTExADFxcUAxsbGAMfHxwDI
yMgAycnJAMrKygDLy8sAzMzMAM3NzQDOzs4Az8/PANDQ0ADR0dEA0tLSANPT0wDU1NQA1dXVANbW
1gDX19cA2NjYANnZ2QDa2toA29vbANzc3ADd3d0A3t7eAN/f3wDg4OAA4eHhAOLi4gDj4+MA5OTk
AOXl5QDm5uYA5+fnAOjo6ADp6ekA6urqAOvr6wDs7OwA7e3tAO7u7gDv7+8A8PDwAPHx8QDy8vIA
8/PzAPT09AD19fUA9vb2APf39wD4+PgA+fn5APr6+gD7+/sA/Pz8AP39/QD+/v4A////AEmnoKA4
OUVOT0tDSHCAhIiNkpOUnrDNtmJ3dWBUZFk/aJSbp0MwOkU9W0IpUGSCi4+QjJKiu9ieXliNaExV
ZUVZiZerTS45ND1jSyhDY2qNj4uNmazH2H9SS5i1WFZhTlB8l6tMMTk1QVtcOzRkaYSOiZKgt8/K
foCJj8eRWWBbXHaZqkcwRDM8a3RSOkxneYuMmKi/26B8lYeO2bNjZWJycpqsTi5CO0twc0ozPVVz
i5Cer8fcZG6WjIKt0nBhZn5TmqxaNUhNV3ZqPzU7RXKJjaLEzok/c5SEcXbQnktZOU+kpWI9QWBu
dU06MjU9ZIGUpJlbOk9whX1+e8bXi0UuY6qhXEk/aXJ4PTU0OkJjh5qmYShASW+dmZaFvdzWujZe
raRoVUNpYJV1MDZCYoOKfo2HPDhDaaGalYi02tXWQF6soWZdQlJgbJJRLkp6i4uIm6hlNEFjmZiT
i6rT0tVKV6igYV9MXV09U3xHRXyNmpeHqI09PmSGnJWOoczQ0klKpZ1lalRhQjdWWH5AeJWll3ur
oVU9YGahmJGRvszQT1GooF94WlNGPFw3e3tzobKjh7ejZERcSJqalYugxsheW6uhX29zWUlTWCo/
pI+IkZ+GsotURl81ip2Zlo2ftWBkqp1ZX3OTU0pMNi9rwGxMbYGyZz5GWy5woZqbmZCMY2uqm1hk
aoFyY0U5Nz2Rs4l2oMG5cUlRMVScop+ZlY5ka6qaWWVrdYZ/UjY3P0+bs6mvxtuHUUQ2OouhnJmZ
mWdtqZlVYWZwp317WD1FOkqYuKy+xmZwQjEvZp+ko6CcZ3OqllZhYX2zf36AZEQ7RVmku7i4doeP
QipGmaehnZtjdqyVVmJcmKl5f4SIdVhpUFCkxMPFpoiCPy58pZ+bml5yq5VXYl6YoHWCh46Ukpea
lp6yv8fPw590JlKcoJ2dYHCqlFhjYJOKan2Mk6Crrq61uLK2wsrQxbE2L3mjn5xhb6aQVmRli3hs
eYKYq7GyucG/yMemnr3W1U4pQ5WhnFlqpIxUYmh+e218goeluL3DycvZoo+BSKvQRjAuYZ6hV2yk
jFdjanZ5b3eFiIquw8nM1r1nlYczd5tZLTM0eKNpaKeLV2RpdXpzc3uIjqe8ydbJamSZgmKTko89
LTBCg5Rupo1VY2p0e313foaUr77GtH9ncJWNjJKPlI08LzE9pY+ijlplbXl+gIKCjZ6wsp18eXRy
jpeYk42S1nUpMy2ipaSMX2dsen6AgYKBgoWBfX+Ad3WTnp2bkLm7dVgwMZ2hp41haG17gYKDg4N/
f4ODgIB3dZyinpigzIJ2glsun5yokmJqbnyDhIWFhoSDhYOBgnSCnp2bmMKob3t9gWU=

```

# Answer
> 1 votes
# PHP - 141.047.262 45.922.273 13.895.520 13.779.516

My code applies a handcrafted huffmann encoding to the input, see below for an uncompressed and commented version.

* O: 1145
* A: 1901 (42 bytes smaller)
* B: 2180 (78 bytes larger)
* C: 1223 (78 bytes larger)
* D: 1979

Demo:

```
[timwolla@~/workspace/php]cat lena.txt |php huffmann.php |php|md5sum && md5sum lena.txt
ebcc2e2a501121b37dcbac3e438be58b  -
ebcc2e2a501121b37dcbac3e438be58b  lena.txt
[timwolla@~/workspace/php]cat rick.txt |php huffmann.php |php|md5sum && md5sum rick.txt
549d9635795ef37857e0b3dc02e52e53  -
549d9635795ef37857e0b3dc02e52e53  rick.txt

```

Minified version:

```
<?php
$q=file_get_contents('php://stdin');$_='str_split';$i=$_($q);$t=[];$c=array_count_values($i);foreach($c as$k=>$v)$t[]=['c'=>$v,'v'=>$k];do{usort($t,function($a,$b){return$a['c']-$b['c'];});$a=array_shift($t);$b=array_shift($t);$t[]=['c'=>$a['c']+$b['c'],'l'=>$a,'r'=>$b];}while(count($t)>1);$r=[];function t($t,&$r,$j=''){if(isset($t['v']))$r[$t['v']]=$j;else{t($t['l'],$r,$j.'1');t($t['r'],$r,$j.'0');}}t($t[0],$r);uksort($r,function($a,$b){return$a<$b;});$z=$_(array_reduce($i,function($a,$b)use($r){return $a.$r[$b];},""),8);$z[]=str_pad(array_pop($z),8,0);$s="";for($i=0;$i<256;$i++)$s.=isset($r[chr($i)])?$r[chr($i)].';':';';$w='<?php
$_=<<<\'EOT\'
'.array_reduce($z,function($a,$b){return $a.chr(bindec($b));},"").'
EOT;
$s=explode(";","'.$s.'");$r=[];foreach($s as$k=>$v)$v?$r[chr($k)]=$v:1;$o=implode("",array_map(function($a){return str_pad(decbin(ord($a)),8,0,0);},'.$_.'($_)));for(;$l=strlen($o);){for($i=1;$i<$l;$i++){$p=substr($o,0,$i);if(($k=array_search($p,$r,true))!==false){echo$k;$o=substr($o,$i);continue 2;}}die;}';
do{$x=md5(mt_rand());}while(strpos($q,$x));
$q="<?=<<<'x$x'
$q
x$x;
";echo strlen($w)<strlen($q)?$w:$q;

```

Uncompressed and commented version: (Note that it will surely spit out the unencoded version, because of the comment)

```
<?php
$q=file_get_contents('php://stdin'); // read input
$_='str_split'; // shorter name (saves some bytes in the end)
$i=$_($q); // convert input into array of chars
$c=$t=[];
$c=array_count_values($i); // calculate frequency table
foreach($c as$k=>$v){
    // build bottom of huffmann tree
    $t[]=[
        'c'=>$v, // count
        'v'=>$k // value (= the character)
    ];
}
do{
    usort($t,function($a,$b){return$a['c']-$b['c'];}); // sort elements of the tree-to-be
    $a=array_shift($t); // lowest count
    $b=array_shift($t); // 2nd lowest count

    // and merge them
    $t[]=[
        'c'=>$a['c']+$b['c'], // cumulated cost of this part of the tree
        'l'=>$a, // left
        'r'=>$b // right
    ];
}
while(count($t)>1);
$r=[];
// recursive tree traverser to build the bits of the encoding
function t($t,&$r,$j='') {
    if(isset($t['v'])) {
        // abort once we found a value
        $r[$t['v']]=$j;
    }
    else {
        // going left = 1
        t($t['l'],$r,$j.'1');
        // going right = 0
        t($t['r'],$r,$j.'0');
    }
}
t($t[0],$r);
// sort the bit-mapping by ascii value of the key
uksort($r,function($a,$b){return$a<$b;});

// encode the input by concatenating the bits and split the result into chunks of 8 bits
$z=$_(array_reduce($i,function($a,$b)use($r){return $a.$r[$b];},""),8);
// ensure the last part is 8 bit long
$z[]=str_pad(array_pop($z),8,0);

// encode the mapping into a semicolon separated string, unmapped characters are empty (that's why I sorted the mapping above)
$s="";
for($i=0;$i<256;$i++) {
    $s.=isset($r[chr($i)])?$r[chr($i)].';':';';
}

// build the decoder
$w='<?php
$_=<<<\'EOT\'
'.array_reduce($z,function($a,$b){return $a.chr(bindec($b));},"" /* // convert the 8-bit chunks into characters */).'
EOT;

// split the encoded map at the semicolons
$s=explode(";","'.$s.'");
$r=[];
foreach($s as$k=>$v) {
    $v?$r[chr($k)]=$v:1; // if there are some bits save them into the map
}
// convert the encoded characters back into a long string of 0 and 1
$o=implode("",array_map(function($a){return str_pad(decbin(ord($a)),8,0,0);},'.$_.'($_)));

for(;$l=strlen($o);){
    // search the whole string for an character in the map
    for($i=1;$i<$l;$i++){
        $p=substr($o,0,$i);
        if(($k=array_search($p,$r,true))!==false){
            // character found, spit it out
            echo$k;
            // and remove the bits
            $o=substr($o,$i);
            continue 2;
        }
    }
    // nothing found, we are finished, the remaining characters are a result of the padding to multiples of 8
    die;
}';
// search a NOWDOC delimiter that does not occur in the input
do{
    $x=md5(mt_rand());
}
while(strpos($q,$x));

// build a program that simply spits out the input unchanged
$q="<?=<<<'x$x'
$q
x$x;
";

// check which one is shorter :-)
echo strlen($w)<strlen($q)?$w:$q;

```

---
Tags: code-golf, compression, code-generation
---


title: Brainf*ckish directions

text:
# Question
Title: Brainf*ckish directions
Your task – should you choose to accept it – is to build a program that parses and evaluates a string (from left to right and of arbitrary length) of tokens that give directions – either left or right. Here are the four possible tokens and their meanings:

```
>  go right one single step
<  go left one single step
-> go right the total amount of single steps that you've gone right, plus one,
   before you previously encountered this token and reset this counter to zero
<- go left the total amount of single steps that you've gone left, plus one,
   before you previously encountered this token and reset this counter to zero

```

There's a catch though – the tokens of directions your program should be able to parse will be presented in this form:

```
<<->-><<->->>->>->

```

... in other words, they are concatenated, and it is your program's task to figure out the correct precedence of directions and amount of steps to take (by looking ahead). The order of precedence is as follows (from highest to lowest precedence):

1. `->`
2. `<-`
3. `>`
4. `<`

If you encounter `<-` when no steps to the left had previously been made since either the start or since the last reset, take one single step to the left. Same rule applies to `->`, but then for going to the right.

**Your program should start at 0 and its result should be a signed integer representing the final end position.**

You may expect the input to always be valid (so, nothing like `<--->>--<`, for instance).

Example input:

```
><->><-<-><-<>>->

```

Steps in this example:

```
 step | token | amount | end position
------+-------+--------+--------------
   1. |   >   |     +1 |           1
   2. |   <   |     -1 |           0
   3. |  ->   |     +2 |           2
   4. |   >   |     +1 |           3
   5. |   <-  |     -2 |           1
   6. |   <   |     -1 |           0
   7. |  ->   |     +2 |           2
   8. |   <-  |     -2 |           0
   9. |   <   |     -1 |          -1
  10. |   >   |     +1 |           0
  11. |   >   |     +1 |           1
  12. |  ->   |     +3 |           4

```

For clarification: the output of the program should only be the final end position as a signed integer. The table above is just there to illustrate the steps my example took. No need to output such a table, table row, or even just the steps' end positions. Only the final end position, as a signed integer, is required.

Shortest code, after one week, wins.

# Answer
# GolfScript, 46 chars

```
'->'/')'*.'<-'-.')'/);+,\'>)'-.'<-'/);\'-'-+,-

```

This is one of the most linear GolfScript programs I've ever written — there's not a single loop, conditional or variable assignment in it. Everything is done using string manipulation:

* First, I replace every occurrence of `->` by `)`. Since the input is guaranteed to be valid, this ensures that any remaining occurrence of `-` must be a part of `<-`.
* Next, I make two copies of the string. From the first copy, I remove the characters `<` and `-`, leaving only `>` and `)`. I then duplicate the result, remove all the `)`s and every `>` following the last `)` from the second copy, concatenate them and count the characters. Thus, in effect, I'm counting:

+ +1 for each `)`,
    + +1 for each `>` after the last `)`, and
    + +2 for each `>` before the last `)`.
* Next, I do the same for the other copy, except this time counting `<` and `<-` instead of `>` and `)`, and removing the `-`s before the final character count. Thus, I count:

+ +1 for each `<-`,
    + +1 for each `<` after the last `<-`, and
    + +2 for each `<` before the last `<-`.
* Finally, I subtract the second count from the first one, and output the result.
> 6 votes

# Answer
# Python 2.7 - 154 147 134 128 bytes

```
l=r=p=0
exec"exec raw_input('%s->','p+=r+1;r=0%s<-','p-=l+1;l=0%s>','r+=1;p+=1%s<','l+=1;p-=1;')"%((";').replace('",)*4)
print p

```

*Serious changes have been made to the way this program works. I've removed the old explanation, which can still be found in this answer's edit history.*

This one's gross.

It works pretty much the same way as other answers for this question, replacing the characters in the input with valid statements in that language and executing them. There's one major difference, though: `replace` is a long word. Screw that.

@ProgrammerDan in chat came up with the idea of using a tuple with the string `;').replace('` in it 4 times, to use the pre-`str.format()` method of formatting text. Four instances of `%s` are in the string on the second line, each one taking its value from the associated element of the tuple at the end. Since they're all the same, each `%s` is replaced with `;').replace('`. When you perform the operations, you get this string:

```
exec raw_input(';').replace('->','p+=r+1;r=0;').replace('<-','p-=l+1;l=0;').replace('>','r+=1;p+=1;').replace('<','l+=1;p-=1;')

```

This is now valid python code that can be executed with `exec`. That's right, baby: *Nested `exec`s let me use string operations on code that needs to perform string operations on code*. Someone please kill me.

The rest of it is pretty straightforward: Each command is replaced with code that keeps track of three variables: The current position, the number of rights since the last `->`, and the same for lefts and `<-`. The whole thing is run and the position is printed.

You'll notice that I do `raw_input(';')`, using ';' as a prompt, rather than `raw_input()` which has no prompt. This saves characters in an unintuitive way: If I did `raw_input()`, I'd have to have the tuple filled with `).replace('`, and every instance of `%s` would have ';\\'' before it *except the first one*. Having a prompt creates more redundancy so I can save more characters overall.
> 6 votes

# Answer
# Perl, 134 131 ... 99 95 bytes

```
sub f{$p+=$d;$&=~/-/?($p+=$s,$s=0):($s+=$d)}$_=<>;$d=1;s/-?>/f/eg;$s=0;$d=-1;s/<-?/f/eg;print$p

```

Takes input as a single line on stdin, eg:

```
ski@anito:~$ perl -le 'sub f{$p+=$d;$&=~/-/?($p+=$s,$s=0):($s+=$d)}$_=<>;$d=1;s/-?>/f/eg;$s=0;$d=-1;s/<-?/f/eg;print$p'
><->><-<-><-<>>->
4

```

or:

```
ski@anito:~$ echo "><->><-<-><-<>>->" | perl -le 'sub f{$p+=$d;$&=~/-/?($p+=$s,$s=0):($s+=$d)}$_=<>;$d=1;s/-?>/f/eg;$s=0;$d=-1;s/<-?/f/eg;print$p'
4

```

I split the instructions into the "right" operators ("\>" and "-\>") and "left" operators ("\<" and "\<-"). The advantages of this are that it's easier to exploit the parallelism between left and right operators, and we don't have to do anything fancy to tokenize the string. Each "direction" is dealt with as a substitution operation where we adjust the running total by the number of steps taken in that direction, ignoring the reverse direction which is taken care of by the other substitution operation. Here's a less-golfed ancestor of this code as a sort of documentation:

```
sub f {
  $dir=shift;
  if($1 =~ /-/) {
    $pos+=$side+$dir;
    $side=0;
  } else {
    $pos+=$dir;
    $side+=$dir;
  }
}

$_=<>;

s/(-?>)/f(1)/eg;
$side=0;
s/(<-?)/f(-1)/eg;

print $pos

```

In a prior iteration of this code, the substitutions were all done in one pass. This had the advantage of keeping a direct mapping between $p/$pos and the position that would be returned at any given point in time, but took more bytes of code.

If you want to use() 5.10.0, you can s/print/say/ to shave another 2 characters off the count, but that's not really my style.
> 5 votes

# Answer
## Perl, 88 77 bytes

```
$_=<>;print s/->/F/g+2*s/>(?=.*F)//g+s/>//g-(s/<-/B/g+2*s/<(?=.*B)//g+s/<//g)

```

Input is expected via STDIN, for example:

```
echo '><->><-<-><-<>>->'|perl -e '$_=<>;print s/->/F/g+2*s/>(?=.*F)//g+s/>//g-(s/<-/B/g+2*s/<(?=.*B)//g+s/<//g)'
4

```

## Update

There is no need to convert the string to a summation, because `s//` is already counting. :-)

## First version

```
$_=<>;s/->/+1/g;s/>(?=.*1)/+2/g;s/>/+1/g;s/<-/-1/g;s/<(?=.*-)/-2/g;s/</-1/g;print eval

```

Input is expected via STDIN, example:

```
echo '><->><-<-><-<>>->'|perl -e '$_=<>;s/->/+1/g;s/>(?=.*1)/+2/g;s/>/+1/g;s/<-/-1/g;s/<(?=.*-)/-2/g;s/</-1/g;print eval'
4

```

## Explanation:

The idea is to convert the direction string into a summation so that the result is output by a simple `print eval`.

`>` before any `->` takes two steps, one at once and the other at the next `->`. It does not matter, which of the `->` while it follows at least one of them. The internal counter is reset after the next `->`, thus `>` does not cause further steps, the maximum is two steps. Then `->` adds one step for itself and so do any remaining `>` after the last `->`.

The same holds for the backwards direction with negative instead of positive step counts.

E.g.: `><->><-<-><-<>>->`

`s/->/+1/`: Start with forward direction, because `->` has highest precedence.
E.g.: `><**+1**><-<**+1**<-<>>**+1**`

`s/>(?=.*1)/+2/g`: The look-ahead pattern assures that only the `>` before any `->` are converted.
E.g.: `**+2**<+1**+2**<-<+1<-<**+2+2**+1`

`s/>/+1/g`: Now the remaining `>` are covered.
E.g.: `+2<+1+2<-<+1<-<+2+2+1`

`s/<-/-1/g`: Analog the backwards direction.
E.g.: `+2<+1+2**-1**<+1**-1**<+2+2+1`

`s/<(?=.*-)/-2/g`: In the look-ahead pattern the full `-1` of the former `<-` is not needed, because there are no `-` of the direction symbols left.
E.g.: `+2**-2**+1+2-1**-2**+1-1<+2+2+1`

`s/</-1/g`: The remaining `<` after the last `<-` are converted.
E.g.: `+2-2+1+2-1-2+1-1**-1**+2+2+1`

`print eval`: Calculate and output the result.
E.g.: **`4`**
> 4 votes

# Answer
## Ruby, 141 bytes

```
l=1;r=1;o=0
gets.gsub('->',?R).gsub('<-',?L).chars{|c|case c
when'<';o-=1;l+=1
when'>';o+=1;r+=1
when'L';o-=l;l=1
when'R';o+=r;r=1
end}
$><<o

```

Ungolfed:

```
parsed = gets.gsub('->', 'R')
             .gsub('<-', 'L')
countL = 1
countR = 1
result = 0
parsed.each_char do |c|
    case c
    when '<'
        result -= 1
        countL += 1
    when '>'
        result += 1
        countR += 1
    when 'L'
        result -= countL
        countL = 1
    when 'R'
        result += countR
        countR = 1
    end
end
puts result

```
> 2 votes

# Answer
## D - 243

**Golfed**:

```
import std.regex,std.stdio;void main(string[]a){int s,c,v;auto t=a[1].matchAll("->|<-(?!>)|>|<".regex);foreach(m;t){auto r=m.hit;if(r=="->"){s+=c+1;c=0;}else if(r=="<-"){s-=v+1;v=0;}else if(r==">"){++s;++c;}else if(r=="<"){--s;++v;}}s.write;}}

```

**Un-golfed**:

```
import std.regex, std.stdio;

void main( string[] a )
{
    int s, c, v;
    auto t = a[1].matchAll( "->|<-(?!>)|>|<".regex );

    foreach( m; t )
    {
        auto r = m.hit;

        if( r == "->" )
        {
            s += c + 1;
            c = 0;
        }
        else if( r == "<-" )
        {
            s -= v + 1;
            v = 0;
        }
        else if( r == ">" )
        {
            ++s;
            ++c;
        }
        else if( r == "<" )
        {
            --s;
            ++v;
        }
    }

    s.write;
}

```
> 1 votes

# Answer
## Javascript (116, ~~122~~, ~~130~~)

116:

```
for(l=r=p=i=0;c='<>-0'.indexOf(a.replace(/->/g,0)[i++])+1;p--)c-4?c-3?c-2?l++:(r++,p+=2):(p-=l-2,l=0):(p+=r+2,r=0);p

```

122:

```
for(l=r=p=i=0,a=a.replace(/->/g,0);c='<>-0'.indexOf(a[i])+1;i++,p--)c-4?c-3?c-2?l++:(r++,p+=2):(p-=l-2,l=0):(p+=r+2,r=0);p

```

130:

```
for(l=r=p=i=0;c='<>-'.indexOf(a[i])+1;i++,p--)c-3?c-1?(r++,p+=2):a[i+1]=='-'?a[i+2]=='>'?l++:(p-=l,l=0,i++):l++:(p+=r+2,r=0,i++);p

```
> 1 votes

# Answer
# JavaScript, 136

```
z=0;l=r=1;c=["--z;++l;",/</g,"++z;++r;",/>/g,"z-=l;l=1;",/<-/g,"z+=r;r=1;",/->/g];for(a=8;a--;s=s.replace(c[a--],c[a]));eval(s);alert(z)

```

Unminified:

```
s="><->><-<-><-<>>->";
z=0;
l=r=1;
c=[
    "--z;++l;", /</g,
    "++z;++r;", />/g,
    "z-=l;l=1;", /<-/g,
    "z+=r;r=1;", /->/g
];
for(a=8;a--;s=s.replace(c[a--],c[a]));
eval(s);
alert(z) // Output (4)

```

## How it works

Given a string input as `s` like so:

```
s="><->><-<-><-<>>->";

```

It uses a Regex to replace each command with a set of instructions which modify `z` (the end position), `l` (stored left movements) and `r` stored right movements. Each Regex is performed in order of precedence.

For the input above this converts `s` to:

```
"++z;++r;--z;++l;z+=r;r=1;++z;++r;z-=l;l=1;--z;++l;z+=r;r=1;z-=l;l=1;--z;++l;++z;++r;++z;++r;z+=r;r=1;"

```

Pretty, ain't it.

Finally we `eval(s)` to perform the instructions and alert `z` which contains the end position.
> 1 votes

# Answer
# C, ~~148~~ ~~141~~ 140

140:

```
r,l,o;main(char *x,char **v){for(x=v[1];*x;x++)(*x^45)?(*x^60)?(r++,o++):(*(x+1)==45)?(x++,o-=l+2,l=0):(o--,l++):(o+=r+1,r=0,x++);return o;}

```

141:

```
r,l,o;main(char *x,char **v){for(x=v[1];*x;x++)(*x^45)?(*x^60)?(r++,o++):(*(x+1)==45)?(x++,o=o-l-2,l=0):(o--,l++):(o+=r+1,r=0,x++);return o;}

```

148:

```
r,l,o;main(char *x,char **v){for(x=v[1];*x;x++){if(*x^45){if(*x^60)r++,o++;else{o--,l++;if(*(x+1)==45)x++,o-=l,l=0;}}else o+=r+1,r=0,x++;}return o;}

```

With whitespace:

```
r,l,o;
main(char *x,char **v)
{
    for(x=v[1];*x;x++)
    (*x^45) ?
        (*x^60) ?
            (r++,o++)
            :
            (*(x+1)==45) ?
                (x++,o-=l+2,l=0)
            :(o--,l++)
        :(o+=r+1,r=0,x++);
    return o;
}

```

Probably a lot more room to golf this. I mostly gave up on trying to manipulate 4 variables in ternaries that captured lvalues (it kept coming out longer and getting later), but not a bad first pass. Pretty straight-forward array pass. Takes input as a command-line argument, outputs via the return value.

You'll need the `-std=c99` flag to compile it with gcc.

**EDIT:** Yep, it's late - missed some obvious stuff.
> 1 votes

# Answer
# PHP, 284 282

No regex.

```
$i=fgets(STDIN);$c=$a=0;$s=str_split($i);while($c<count($s)){switch($s[$c]){case"<":if($s[$c+1]=="-"){if($s[$c+2]==">"){$c+=3;$a+=$rr;$rr=0;$ll++;}else{$c+=2;$a+=-($ll+1);$ll=0;}}else{$c++;$a--;$ll++;}break;case">":$c++;$a++;$rr++;break;case"-":$c+=2;$a+=$rr+1;$rr=0;break;}}echo$a;

```

**Ungolfed:**

```
$i=fgets(STDIN);
$c=$a=0;
$s=str_split($i);
while($c<count($s)){
    switch($s[$c]){
    case "<":
        if($s[$c+1]=="-"){
            if($s[$c+2]==">"){
                $c+=3;$a+=$rr;$rr=0;$ll++;
            }
            else{
                $c+=2;$a+=-($ll+1);$ll=0;
            }
        }
        else{
            $c++;$a--;$ll++;
        }
    break;
    case ">":
        $c++;$a++;$rr++;
        break;
    case "-":
        $c+=2;$a+=$rr+1;$rr=0;
        break;
    }
}
echo $a;

```
> 0 votes

# Answer
## JavaScript \[217 bytes\]

```
prompt(x=l=r=0,z='replace',f='$1 $2 ')[z](/(>.*?)(->)/g,f)[z](/(<.*?)(<-)/g,f)[z](/(<|>)(<|>)/g,f)[z](/<-?|-?>/g,function(c){c=='>'&&(x++,r++),c=='<'&&(x--,l++),c=='->'&&(x+=++r,r*=0),c=='<-'&&(x-=++l,l*=0)}),alert(x)

```

Probably it may be shortened a bit more...
> 0 votes

# Answer
## Another perl solution, 113 chars

There are already two answers that beat this, it's just for giggles. It uses an approach based on Ilmari's observation about the value of tokens:

```
$_=<>;chomp;s/->/#/g;s/<-/%/g;s/>(?=.*#)/?/g;s/<(?=.*%)/;/g;s/#/>/g;s/%/</g;$t+=ord for split//;print$t-61*length

```

Exploded a bit:

```
$_=<>;
chomp;
s/->/#/g;
s/<-/%/g;
s/>(?=.*#)/?/g;
s/<(?=.*%)/;/g;
s/#/>/g;
s/%/</g;
$t+=ord for split//;
print$t-61*length

```
> 0 votes

---
Tags: code-golf, parsing
---


title: Solve a reverse arrow maze

text:
# Question
Title: Solve a reverse arrow maze
This is an "arrow maze":

```
  v      <
>     v
      >  ^
>         v
^ <       *

```

The `*` marks the spot where you will finish. Your goal is to find where the maze **starts** (hence, reverse maze). In this case, it's the first `>` on the second line.

```
  v------<
S-+---v  |
  |   >--^
>-+-------v
^ <       *

```

Note that all arrows must be used. Also note that you can assume the lines will be padded with spaces to equal length.

Your program must input the maze in any reasonable way (stdin, from a file, message box, etc.), however the maze **must** be completely intact. For example, you can't input the lines separated by commas; the input must be exactly the maze.

You must output the start of the maze in any reasonable way. For example, you could

* output the coordinates of the start
* output the entire maze with the start arrow replaced with an `S`
* output the entire maze with all arrows except the start arrow removed (whitespace intact!)
* etc.

As long as you can tell by your output which arrow is the start arrow, then it's okay. For example, an output of

```
"0"
"2"

```

is alright, regardless of the newlines and quotes, because you can still tell where the start was.

This is , so the shortest code in bytes will win.

# Answer
# GolfScript, 55 bytes

```
:&,,{&=42>},.{.&="><^v"?[1-1&n?~.~)]=:d;{d+.&=32=}do}%-

```

Online demo

Assumes that all input lines are padded with spaces to the same length and separated by newlines. Outputs the byte offset of the starting arrow from the start of the input string (e.g. `12` for the example maze in the challenge).

Specifically, this program finds the byte offsets of all arrows that have no other arrow pointing to them (assuming that all arrows do point to an arrow or a goal; strange behavior may occur if this is not true). By default, if there are several such arrows (which, per spec, should not be possible in valid input), their offsets will simply be concatenated in the output. If you want, you can append `n*` to the program to have them separated by newlines instead.

De-golfed version with comments:

```
:&                     # save a copy of the input string in the variable "&"
,, { &= 42> },         # make a list of the byte offsets of all arrows
.                      # duplicate the list and apply the following loop to it:
{
  .                    # make a copy of the original offset...
  &=                   # ...and get the corresponding character in the input
  "><^v" ?             # map the arrow character to integers 0 to 3, and...
  [ 1 -1 &n?~ .~) ]=   # ...map these to +1, -1, -len-1 or +len+1, where len is the...
  :d;                  # ...length of the first input line, and save result as "d"
  { d+ . &= 32= } do   # add d to the byte offset until another non-space is found
} %
-                      # subtract the resulting list of target offsets from the
                       # original list of arrow offsets; this should leave exactly
                       # one offset, which is left on the stack for output

```
> 4 votes

# Answer
## GolfScript (101 100 bytes)

```
n/:g,,{:&g=:r,,{&1$r='^v<>*'?70429 3base 2/=++}/}%{,4=},.{2<}%:&\{2/~\{[~2$~@+(@@+(\]&1$?)!}do\;}%^`

```

Output is in the form `[[x y]]` where the co-ordinates are both 0-based.

Online demo

Processing is in two phases: the first phase turns the maze into an array of `[x y dx dy]` tuples; the second phase maps each arrow / asterisk to the arrow / asterisk it points to. (Asterisks are considered to point to themselves). By the definition of the problem, there is exactly one arrow which isn't in the result of this map, and that is the solution.
> 5 votes

# Answer
# Mathematica ~~491~~ 323

**Ungolfed** with comments

The procedure begins from the finish ("\*"), finds the arrow that points to it, and so forth until reaching the start.

The function, f\[maze\].

```
(* positions of the arrowheads *)
aHeads[a_]:=Position[m,#]&/@{"^","v",">","<"}

(* position of the final labyrinth exit*)
final[a_]:=Position[a,"*"][[1]];

(* find arrowheads that point to the current location at {r,c} *)
aboveMe[{r_,c_},a_]:=Cases[aHeads[a][[2]],{r1_,c}/;r1<r]
belowMe[{r_,c_},a_]:=Cases[aHeads[a][[1]],{r1_,c}/;r1>r]
rightOfMe[{r_,c_},a_]:=Cases[aHeads[a][[4]],{r,c1_}/;c1>c]
leftOfMe[{r_,c_},a_]:=Cases[aHeads[a][[3]],{r,c1_}/;c1<c]

(*find the precursor arrowhead*)
precursor[{loc_,a_,list_:{}}]:=

(* end the search when the precursor has already been traversed or when there is no precursor *)
Which[MemberQ[list,loc],list,
loc=={},list,True,

(* otherwise find the next precursor *)

```

precursor\[{Flatten\[{aboveMe\[loc,a\],belowMe\[loc,a\],rightOfMe\[loc,a\],leftOfMe\[loc,a\]},2\],a, Prepend\[list,loc\]}\]\]

```
(* return the path through the maze from start to finish *)
f[maze_]:= precursor[{final[maze[[1]]],maze[[1]]}]

```

---

**Golfed**

```
f@z_:=Module[{p,h,m=z[[1]]},h@a_:=Position[a,#]&/@{"^","v",">","<","*"};
  p[{v_,a_,j_:{}}]:=Module[{r,c,x=Cases},{r,c}=v;
  Which[MemberQ[j,v],j,v=={},j,True,
  p[{Flatten[{x[h[a][[2]],{r1_,c}/;r1<r],x[h[a][[1]],{r1_,c}/;r1>r],
  x[h[a][[4]],{r,c1_}/;c1>c],x[h[a][[3]],{r,c1_}/;c1<c]},2],a,Prepend[j,v]}]]];
  p[{Position[m,"*"][[1]],m}]]

```

## Example

The maze. Each ordered pair contains the row and column of a cell. E.g. {2, 3} denotes the cell at row 2, column 3.

```
maze=Grid[Normal@ SparseArray[{{5, 5} -> "*",{1, 2} -> "v", {1, 5} -> "<",{2, 1} -> ">",
   {2, 3} -> "v",{3, 3} -> ">", {3, 5} -> "^",{4, 1} -> ">", {4, 5} -> "v",{5, 1} -> "^",
   {5, 2} -> "<",{_, _} -> " "}]]

```

---

**Input**

```
f[maze]

```

---

**Output**: The path from start to finish.

> {{2, 1}, {2, 3}, {3, 3}, {3, 5}, {1, 5}, {1, 2}, {5, 2}, {5, 1}, {4, 1}, {4, 5}, {5, 5}}
> 2 votes

# Answer
I think I found a good way to solve this, but I happened to suck at golfing it. I guess this could be WAY shorter, so I'm going to explain my idea so others can use it if they find it good.

**If every arrow must be used, then all the arrows will be pointed by another arrow, except one, that is our solution.**

This means we don't actually have to play the maze backwards, but, starting from the upper-left one, we just need to check the nearest pointable arrow for each one. This is a real painsaver for larger mazes (since you don't have to check all four directions, but just one).

Here's my solution:

# PHP, 622 bytes

```
$h=fopen("a.txt","r");$b=0;while(($z=fgets($h))!==false){$l[$b]=str_split($z,1);$b++;}$v=array("^","<","v",">");$s=array();for($i=0;$i<count($l);$i++){for($j=0;$j<count($l[0]);$j++){if(in_array($l[$i][$j],$v)){switch($l[$i][$j]){case"^":$c=$i-1;while($l[$c][$j]==" ")$c--;$s[]=$c.",".$j;break;case"v":$c=$i+1;while($l[$c][$j]==" ")$c++;$s[]=$c.",".$j;break;case"<":$c=$j-1;while($l[$i][$c]==" ")$c--;$s[]=$i.",".$c;break;case">":$c=$j+1;while($l[$i][$c]==" ")$c++;$s[]=$i.",".$c;break;}}}}for($i=0;$i<count($l);$i++){for($j=0;$j<count($l[0]);$j++){if(in_array($l[$i][$j],$v)){if(!in_array($i.",".$j,$s)){echo$i.",".$j;}}}}

```

**Ungolfed:**

```
$h=fopen("a.txt","r");
$b=0;
while(($z=fgets($h))!==false) {
    $l[$b]=str_split($z,1);
    $b++;
}
//Input ends here
$v = array("^","<","v",">");
$s = array();
//Here i check every arrow, and save every pointed one in $s
for($i=0;$i<count($l);$i++){
    for($j=0;$j<count($l[0]);$j++){
        if(in_array($l[$i][$j],$v)){
            switch($l[$i][$j]) {
                case "^":
                    $c=$i-1;
                    while ($l[$c][$j]==" ")
                        $c--;
                    $s[]=$c.",".$j;
                    break;
                case "v":
                    $c=$i+1;
                    while ($l[$c][$j]==" ")
                        $c++;
                    $s[]=$c.",".$j;
                    break;
                case "<":
                    $c=$j-1;
                    while ($l[$i][$c]==" ")
                        $c--;
                    $s[]=$i.",".$c;
                    break;
                case">":
                    $c=$j+1;
                    while ($l[$i][$c]==" ")
                        $c++;
                    $s[]=$i.",".$c;
                    break;
            }
        }
    }
}
//I check if the arrow is in $s. If not, we have a solution.
for($i=0;$i<count($l);$i++){
    for($j=0;$j<count($l[0]);$j++){
        if (in_array($l[$i][$j],$v)){
            if (!in_array($i.",".$j,$s)){
                echo$i.",".$j;
            }
        }
    }
}

```
> 1 votes

# Answer
**PHP** \- 492 bytes

```
$r=split("\n",$m);$h=count($r);foreach($r as &$k)$k=str_split($k);$l=count($r[0]);$e=strpos($m,"*")+1-$h;$a=$x=$e%$l;$b=$y=floor(($e-$x)/$l);do{$c=0;for(;--$a>=0;){if($r[$b][$a]==">"){$x=$a;$c++;}if($r[$b][$a]!=" ")break;}$a=$x;for(;--$b>=0;){if($r[$b][$a]=="v"){$y=$b;$c++;}if($r[$b][$a]!=" ")break;}$b=$y;for(;++$a<$l;){if($r[$b][$a]=="<"){$x=$a;$c++;}if($r[$b][$a]!=" ")break;}$a=$x;for(;++$b<$h;){if($r[$b][$a]=="^"){$y=$b;$c++;}if($r[$b][$a]!=" ")break;}$b=$y;}while($c>0);echo "$x-$y";

```

This solution supposes that the map can be found in local variable `$m`. The shortest method I have for passing that is via `$_GET`: `$m=$_GET['m'];` at 14 bytes. An ungolfed version with map in variable is provided below for clarity of reading.

```
$m=<<<EOT
  v      <
>     v
      >  ^
>         v
^ <       *
EOT;

$r=split("\n",$m);
$h=count($r);
foreach($r as &$k)
    $k=str_split($k);
$l=count($r[0]);

$e=strpos($m,"*")+1-$h;

$a=$x=$e%$l;
$b=$y=floor(($e-$x)/$l);
do{
$c=0;
for(;--$a>=0;)
    {
        if($r[$b][$a]==">"){$x=$a;$c++;}
        if($r[$b][$a]!=" ")break;
    }
$a=$x;
for(;--$b>=0;)
    {
        if($r[$b][$a]=="v")
            {
                $y=$b;
                $c++;
            }
        if($r[$b][$a]!=" ")break;

    }
$b=$y;
for(;++$a<$l;)
    {
        if($r[$b][$a]=="<")
            {
                $x=$a;
                $c++;
            }
        if($r[$b][$a]!=" ")break;
    }
$a=$x;
for(;++$b<$h;)
    {
        if($r[$b][$a]=="^")
            {
                $y=$b;
                $c++;
            }
        if($r[$b][$a]!=" ")break;
    }
$b=$y;
}while($c>0);
echo "$x-$y";

```
> 1 votes

# Answer
# K, 281 277 258

```
{{$[&/x in*:'{{~"*"=x 1}{(s;k . s;k;s:*1_w@&(k ./:w:{{x@&x in y}[(*:'{(x[1]@x 0;x 1)}\[x;(z;y)]);i]}[(h!b,b,a,a:#k:x 2)m;(h!(0 1+;0 -1+;1 0+;-1 0+))m:x 1;x 0])in"*",h:"><v^")}\(x;y;z;x)}[*x;y .*x;y];*x;.z.s[1_x]y]}[i@&~(x ./:i::,/(!#x),/:\:!b::#*x)in" *";x]}

```

Here's an earlier, ungolfed version

```
solve:{[x]
    //j - indices of all possible starting points
    //i - every index
    j::i@&~(x ./:i::,/(!a:#x),/:\:!b:#*x) in " *";

    h::">v<^";

    //d - dictionary mapping each directional character to
    //    increment/decerement it needs to apply to the x/y axis
    d::h!((::;1+);(1+;::);(::;-1+);(-1+;::));

    //e - dictionary mapping each directional character to
    //    the maximum number of moves it should make in a
    //    given direction
    e::h!b,a,b,a;

    //f - function to produce the indices of each point that is
    //    passed once we move in a certain direction from a
    //    certain index
    f::{{x@&x in y}[(last'{(x[0];x[0]@'x 1)}\[x;(y;z)]);i]};

    //g - function that, given a starting and a direction,
    //    moves in that direction until hitting another directional
    //    character. It then moves in the new direction etc. until
    //    it reaches the end point -- *
    g::{[x;y;z]
        {[x]
            q:x 0;m:x 1; k:x 2;
            w:f[e m;d m;q];
            s:*1_w@&(k ./:w)in h,"*";
            m:k . s;
            (s;m;k;s)}\[{~"*"=x 1};(x;y;z;x)]};

    // recursive function that starts at the first possible starting point
    // and plots its way to the end. If all other potential starting points
    // have been touched in this path, then this is the correct starting point.
    // else, recursively call the function with the next possible starting point
    :{$[min "b"$j in last'g[*x;y . *x;y];*x;.z.s[1_x;y]]}[j;x]
  }

```

Returns the starting point as `x y` with 0 based indices.

```
k)maze
"  v      < "
">     v    "
"      >  ^ "
">         v"
"^ <       *"
k)solve maze
1 0

```
> 1 votes

# Answer
## Python 422

```
with open("m.txt","r") as f:m=f.read().split("\n")
p=[(v.find("*"),p) for p,v in enumerate(m) if "*" in v][0]
g=[]
def f(a):
    x,y=b,c=a
    for p,i in enumerate((lambda x:[l[x] for l in m])(x)):
        if i in "^>v<" and((p<y and i=="v")or(p>y and i=="^")):return b,p
    for p,i in enumerate(m[y]):
        if i in "^>v<" and((p<x and i==">")or(p>x and i=="<")):return p,c
while True:
    z=f(p)
    if z in g:break
    else:g.append(z);p=z
print p

```

The input is in a file called `m.txt`. The output is `(x, y)` but if you change the last print statement to `print g`, the output will be a list like `[(x, y), (x, y), ...]` with all the steps to get from the end to the start.
> 1 votes

---
Tags: code-golf, ascii-art, path-finding
---