Code Golf: Ghost Leg

Question

The challenge

The shortest code by character count that will output the numeric solution, given a number and a valid string pattern, using the Ghost Leg method.

Examples

Input: 3,
"| | | | | | | |
 |-| |=| | | | |
 |-| | |-| |=| |
 | |-| |-| | |-|"

Output: 2

Input: 2,
"| | |=| |
 |-| |-| |
 | |-| | |"

Output: 1

Clarifications

1. Do not bother with input. Consider the values as given somewhere else.
2. Both input values are valid: the column number corresponds to an existing column and the pattern only contains the symbols |, -, = (and [space], [LF]). Also, two adjacent columns cannot both contain dashes (in the same line).
3. The dimensions of the pattern are unknown (min 1x1).

Clarifications #2

1. There are two invalid patterns: |-|-| and |=|=| which create ambiguity. The given input string will never contain those.
2. The input variables are the same for all; a numeric value and a string representing the pattern.
3. Entrants must produce a function.

Test case

Given pattern:
"|-| |=|-|=|LF| |-| | |-|LF|=| |-| | |LF| | |-|=|-|"

|-| |=|-|=|
| |-| | |-|
|=| |-| | |
| | |-|=|-|

Given value : Expected result
 1 : 6
 2 : 1 
 3 : 3
 4 : 5
 5 : 4
 6 : 2

Edit: corrected expected results

Mythomania

What do you mean by "two adjacent columns cannot both contain dashes"? – Softhearted

@meagar: You will never be given a pattern like this: |-|-| (because it creates ambiguity). I believe I should probably add "... in the same line". You're right – Mythomania

Can two adjacent columns contain a dash an equal sign? – Softhearted

@Anax: does that mean that input like |=|-| doesn't exist as well? – Iridescent

Full program, just a method, or just a peice of code? Do we assume "=" represents two lines? – Chivalric

Invalid patterns: |-|-| and |=|=|. Everything else is valid and has no ambiguity. The point is that we need to know every time how to turn (left or right). In the case of |=|-|, the first column leads us to the third, the second leads to the same column and the third column leads to the first. – Mythomania

@Charles: a method/function will do. And yes, = represents two lines. – Mythomania

Must the input be assumed to be a single string? (Plus the column number) – Chivalric

@Charles: The input is two arguments: an integer and a string – Rocco

@Ates: just want to confirm for certain, since any flexibility in the input could be used to an advantage (e.g. an array of strings). – Chivalric

I believe it's fair to assume the same input for all languages. – Mythomania

I think this is the longest I've seen a CG without any answers. – Gurango

These example strings have extra spaces at the beginning, which (I assume) should not be there. – Camouflage

@Nick, indeed. Have a look at the test case for a real example of a given pattern – Mythomania

@Anax: In the test case, shouldn't it be 4->5 and 5->4? – Exactly

@Daniel: yes, was already corrected. – Mythomania

I think there are shorter answers than the javascript by character count. – Opine

Indeed; but all answers are based on Daniel's (Javascript) answer, that's why the Javascript won in my opinion. – Mythomania

Answer 1

JavaScript: 169 158 148 141 127 125 123 122 Characters

Minified and Golfed:

function g(n,s){for(l=s.split('\n'),n*=2;k=l.shift();)for(j=3;j;)n+=k[n-3]==(c=--j-1?'=':'-')?-2:k[n-1]==c?2:0;return n/2}

Readable Version:

function g(n, str) {
   var c, i, j;
   var lines = str.split('\n');
   n = (n * 2) - 2;

   for (i = 0; i < lines.length; i++) {
      for (j = 0; j < 3; j++) {
         c = (j == 1) ? '-' : '=';

         if (lines[i].charAt(n-1) == c) n-=2;          // Move left
         else if (lines[i].charAt(n+1) == c) n+=2;     // Move right
      }
   }

   return 1+n/2;
}

Explanation:

1. str is split into an array of lines.
2. n is scaled to cover the number of characters in each line, starting from 0.
3. Iterate three times over each line: one time for each layer. Imagine each line is divided into 3 layers: The top and bottom layers are where the legs of the of the = sign are attached. The middle layer is for the legs of the - signs.
4. Move n either left or right according to the adjacent signs. There is only one possible move for every layer of each line. Therefore n could move up to 3 times in a line.
5. Return n, normalized to start from 1 to the number of vertical lines.

Test Cases:

var ghostLegs = [];

ghostLegs[0] = "|-| |=|-|=|\n" +
               "| |-| | |-|\n" +
               "|=| |-| | |\n" +
               "| | |-|=|-|";

ghostLegs[1] = "| | | | | | | |\n" +
               "|-| |=| | | | |\n" +
               "|-| | |-| |=| |\n" +
               "| |-| |-| | |-|";

ghostLegs[2] = "| | |=| |\n" +
               "|-| |-| |\n" +
               "| |-| | |";

ghostLegs[3] = "|=|-|";

for (var m = 0; m < ghostLegs.length; m++) {
   console.log('\nTest: ' + (m + 1) + '\n');

   for (var n = 1; n <= (ghostLegs[m].split('\n')[0].length / 2) + 1; n++) {
      console.log(n + ':' + g(n, ghostLegs[m]));
   }
}

Results:

Test: 1
1:6
2:1
3:3
4:5
5:4
6:2

Test: 2
1:1
2:3
3:2
4:4
5:5
6:6
7:8
8:7

Test: 3
1:3
2:1
3:4
4:2
5:5

Test: 4
1:3
2:2
3:1

Exactly

+1 for first correct answer and understanding the "layers" problem – Mythomania

+1 This is so elegant, I'm too embarrassed to post my solution now. – Chivalric

I just shortened it to 140 characters by using shift() and inlining the assignment to c. – Handhold

I just shortened it to 126 characters by replacing charAt(n) with [n] – Handhold

@David: Nice job! I'm going to shave an extra couple of chars by tweaking the for(j=0;j<3;) loop. – Exactly

@David, is your character count off by 1, or is it mine? – Exactly

someone should try to utilize the new javascript 1.8 stuff (expression closures, reduce, etc). – Handhold

I still have NO idea what the function is doing or what the question is asking. haha. – Handhold

@David: lol!... excellent golfing!... isn't that 123 chars however? – Exactly

And off with another character! 121 characters! – Handhold

@Daniel: console.log("function g(n,s){for(l=s.split('\n'),n*=2;k=l.shift();)for(j=3;j;)n+=k[n-3]==(c=--j-1?'=':'-')?-2:k[n-1]==c?2:0;return n/2}".length) === 121 – Handhold

@David: The problem with that method is \n is being counted as 1 char, and I guess it counts as two in golfing :) – Exactly

hm, very tricky! all of my counts have been off my 1 then. sorry! should be fixed now. – Handhold

No probs... You stripped 18% of the chars with those tweaks! That's great golfing :) – Exactly

Answer 2

AWK - 68 77 79 chars

Pretty much a translation of Daniel's solution (we love ya man ;)

{for(i=0;i<3;){s=++i-2?"=":"-";if(s==$x)x--;else if(s!=$++x)x--}}END{print x}

But we can do away with if/else and replace it with ?:

{for(i=0;i<3;){s=++i-2?"=":"-";s==$x?x--:s!=$++x?x--:x}}END{print x}

Run it with the starting position defined as the x variable:

$ for x in `seq 6`; do echo $x\ ;awk -F\| -vx=$x -f ghost.awk<<__EOF__
|-| |=|-|=|
| |-| | |-|
|=| |-| | |
| | |-|=|-|
__EOF__
done

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

Matherne

+1 That's a pretty good translation :) ... I'm going to try the ?: as well, but I still doubt that the verbosity of JS will allow me to break the 160 char barrier! ... EDIT: It did eventually :) – Exactly

Answer 3

Ruby - 66 95 92 83 chars

(Alternating rows idea from Daniel's answer)

def f s,m
m.each_line{|r|%w{= - =}.map{|i|s+=i==r[2*s-3]?-1:i==r[2*s-1]?1:0}}
s
end

92 chars

def f s,m
  s=s*2-2
  m.each_line{|r|%w{= - =}.each{|i|s+=i==r[s-1]?-2:i==r[s+1]?2:0}}
  1+s/2
end

Usage

map="|-| |=|-|=|
| |-| | |-|
|=| |-| | |
| | |-|=|-|"

1.upto(6) do |i|
    p f(i, map)
end

Output

6
1
3
5
4
2

Westing

This only works in Ruby 1.9, not in 1.8. And only with these malformed test cases which have an extra space at the front for all but the first row. – Camouflage

+1 for the credit :) ... My JavaScript solution can never get close to 95 chars! – Exactly

Answer 4

Perl, 92 91 chars

sub g{for$s(pop=~/.+/g){map$_[0]-=1-abs(index substr(" $s",$_[0]*2-2,3),$_),qw[= - =]}pop}

Another approach, 98 97 95 94 93 92 chars

sub g{map{for$s(qw[= - =]){pos=$_[0]*2-2;$_[0]+=/\G((?<=$s)|.$s)/&&$&cmp$"}}pop=~/.+/g;pop}

Test suite

$s=<<'__PATTERN__';
|-| |=|-|=|
| |-| | |-|
|=| |-| | |
| | |-|=|-|
__PATTERN__

for $n (1..6) {
    print g($n,$s);
}

Ladida

Answer 5

Daniel's answer in C# - 173 chars

After seeing Daniel Vassallo's solution, I was too ashamed of mine to post it. But here's Daniel's answer ported to C# for the heck of it. One major drawback in C# was having to do bounds checking, which cost 20 characters.

int G(string s,int n){var l=s.Split('\n');n*=2;for(int i=0,j,c;i<l.Length;i++)
for(j=0;j<3;n+=n>2&&l[i][n-3]==c?-2:n<l[i].Length&&l[i][n-1]==c?2:0)c=j++==1?45
:61;return n/2;}

Formatted:

int G(string s, int n)
{
    var l = s.Split('\n');
    n *= 2;

    for (int i = 0, j, c; i < l.Length; i++)
        for (j = 0; j < 3; n += n > 2 && l[i][n - 3] == c ? -2 : n < l[i].Length && l[i][n - 1] == c ? 2 : 0)
            c = j++ == 1 ? 45 : 61;

    return n / 2;
}

Chivalric

Answer 6

VB.Net: 290 chars (320 bytes)

Requires Option Strict Off, Option Explicit Off

Function G(i,P)
i=i*2-1
F=0
M="-"
Q="="
Z=P.Split(Chr(10))
While E<Z.Length
L=(" "& Z(E))(i-1)
R=(Z(E)&" ")(i)
J=L & R=" "&" "
E-=(F=2Or J)
i+=If(F=1,2*((L=M)-(R=M)),If(F=2,2*((L=Q)-(R=Q)),If(J,0,2+4*(L=Q Or(L=M And R<>Q)))))
F=If(F=1,2,If(F=2,0,If(J,F,2+(L=Q Or R=Q))))
End While
G=(i-1)\2+1
End Function

Readable form:

Function G(ByVal i As Integer, ByVal P As String) As Integer

    i = i * 2 - 1
    Dim F As Integer = 0
    Const M As String = "-"
    Const Q As String = "="
    Dim Z As String() = P.Split(Chr(10))
    Dim E As Integer = 0

    While E < Z.Length
        Dim L As Char = (" " & Z(E))(i - 1)
        Dim R As Char = (Z(E) & " ")(i)
        Dim J As Boolean = L & R = " " & " "

        E -= (F = 2 Or J)
        i += If(F = 1, 2 * ((L = M) - (R = M)), _
                If(F = 2, 2 * ((L = Q) - (R = Q)), _
                If(J, 0, 2 + 4 * (L = Q Or (L = M And R <> Q)))))

        F = If(F = 1, 2, If(F = 2, 0, If(J, F, 2 + (L = Q Or R = Q))))

    End While

    G = (i - 1) \ 2 + 1

End Function

Test cases

Sub Main()

    Dim sb As New StringBuilder
    Dim LF As Char = ControlChars.Lf
    sb.Append("|-| |=|-|=|")
    sb.Append(LF)
    sb.Append("| |-| | |-|")
    sb.Append(LF)
    sb.Append("|=| |-| | |")
    sb.Append(LF)
    sb.Append("| | |-|=|-|")

    Dim pattern As String = sb.ToString

    For w As Integer = 1 To pattern.Split(LF)(0).Length \ 2 + 1
        Console.WriteLine(w.ToString & " : " & G(w, pattern).ToString)

    Next

    Console.ReadKey()

End Sub

Edit:

(for those still reading this)

I tried a different approach. My idea was to map the different patterns expected and act accordingly. We first need to decide if we'll turn left or right and then determine the number of columns our little Amidar monkey will move (reversing the string if needed).

Presenting the full solution first:

Function GhostLeg(ByVal i As Integer, ByVal p As String) As Integer

    i = i * 2 - 2

    Dim LeftOrRight As New Dictionary(Of String, Integer)
    LeftOrRight(" | ") = 0
    LeftOrRight("-| ") = -1
    LeftOrRight("=| ") = -1
    LeftOrRight("=|-") = -1
    LeftOrRight(" |-") = 1
    LeftOrRight(" |=") = 1
    LeftOrRight("-|=") = 1

    Dim ColumnAdd As New Dictionary(Of String, Integer)
    ColumnAdd("| | | ") = 0
    ColumnAdd("| | |-") = 0
    ColumnAdd("| |-| ") = 0
    ColumnAdd("| | |=") = 0
    ColumnAdd("| |=| ") = 0
    ColumnAdd("| |-|=") = 0
    ColumnAdd("| |=|-") = 0

    ColumnAdd("|=| | ") = 0
    ColumnAdd("|=| |-") = 0
    ColumnAdd("|=| |=") = 0
    ColumnAdd("|-| |-") = 1
    ColumnAdd("|-| | ") = 1
    ColumnAdd("|-| |=") = 1
    ColumnAdd("|-|=|-") = 2
    ColumnAdd("|-|=| ") = 2
    ColumnAdd("|=|-| ") = 2
    ColumnAdd("|=|-|=") = 3

    Const TRIPLESPACE As String = " | | "
    Dim direction As Integer

    For Each line As String In p.Split(Chr(10))
        line = TRIPLESPACE & line & TRIPLESPACE

        direction = LeftOrRight(line.Substring(i + 4, 3))
        If direction = 1 Then
            line = line.Substring(i + 5, 6)
            i += 2 * direction * ColumnAdd(line)

        ElseIf direction = -1 Then
            line = StrReverse(line.Substring(i, 6))
            i += 2 * direction * ColumnAdd(line)

        End If

    Next

    Return 1 + i \ 2

End Function

By removing the character-wise expensive Dictionary, as well as the unecessary |'s and after some more 'minification' we end up with:

Function G(i,p)
D="- 0= 0=-0 -2 =2-=2"
A="- -1-  1- =1-=-2-= 2=- 2=-=3"
For Each l In p.Replace("|","").Split(Chr(10))
l="   "& l &"   "
w=InStr(D,Mid(l,i+2,2))
If w Then
w=Val(D(w+1))-1
s=InStr(A,If(w=1,Mid(l,i+3,3),StrReverse(Mid(l,i,3))))
i+=If(s,w*Val(A(s+2)),0)
End If
Next
G=i
End Function

Not much of a gain, compared to my previous effort (282 chars, 308 bytes), but maybe this approach will prove useful to others using a different programming language.

Mythomania

Interesting approach, and quite compact for VB! MY dumb C# solution was about the same length. – Chivalric

Thanks. My VB port of Daniel's solution was 189 byes long (or 178 characters w/o LF). Not bad for VB. – Mythomania