Reachability measure in Conway's Soldiers

Question

Background

Conway's Soldiers is a version of peg solitaire played on an infinite checkerboard. The board is initially full of pegs below an infinite horizontal line, and empty above it. Following the ordinary peg solitaire rules (move a peg by jumping over another one horizontally or vertically, removing the one that was jumped over), the objective is to move a peg as far above the horizontal line as possible.

Wikipedia page has the solutions for 1 to 4 units above the line: (A and B denote two possible alternatives.)

In ASCII notation (using alternative B):

                         X
               X         .
        X      .         .
_X_   __._   __.__   ____.____
 O    OOO    OOOOO   OOOOOOOOO
 O      O      OOO     OOOO
                      OOOOO
                        OO

Conway proved that it is impossible to reach 5 units above the line with finite number of moves. To prove it, he assigned a value to each peg: if a peg is \$n\$ units away from the target position in terms of Manhattan distance, it is assigned the value of \$\varphi^n\$, where

$$ \varphi = \frac{\sqrt5 - 1}{2} $$

(The value is the golden ratio minus 1.)

This value was carefully chosen to ensure that every possible move keeps the total value constant when a move is towards X, and decreasing when a move is away from it. Also, the final state must have a peg precisely at the target position, giving the value of \$\varphi^0 = 1\$, so the target position is unreachable if the initial configuration has the value sum less than 1.

For the target position at 5 units above the line, the configuration looks like this:

     X
     .
     .
     .
_____._____
OOOCBABCOOO
OOOOCBCOOOO
OOOOOCOOOOO
    ...

The peg at the position A is given \$\varphi^5\$, the ones at B are \$\varphi^6\$ each, and so on. Then he showed that the sum for the infinite number of pegs is exactly 1, and therefore the value sum of any finite subset is less than 1, concluding the proof of non-reachability.

Task

Now, let's apply this measure to an arbitrary configuration, not just for the original problem, e.g. the pegs may surround the target position:

OOOOO
O...O
O.X.O
O...O
OOOOO

Given such a configuration, calculate Conway's measure on it and output truthy if the measure is at least 1, falsey otherwise. (Note that the truthy output does not guarantee that the target is actually reachable, while the falsey output does say that the target is too far away from the pegs to reach it.)

The calculated measure should be within 1e-6 margin. A program that produces wrong answers when the computed one falls within \$\pm10^{-6}\$ from the true measure is acceptable. You can use (sqrt(5)-1)/2 or 0.618034, but not 0.61803 or 0.61804.

You can choose any three distinct symbols (characters, numbers, or any other kind of values) to indicate a peg, an empty space, and the target position respectively. You can take the grid as a matrix, a list of strings (or lists of symbols), or a single string (or a list of symbols) with a delimiter of your choice. You can assume that the input has exactly one target position, and it is not already occupied by a peg.

Test cases

In the test cases below, O is a peg, X is the target position, and . is a blank.

True

measure = 1 (0.61803 will fail all of the measure=1 cases)
OOX
--------------
measure = 1
OO.X
.O..
.O..
--------------
measure = 1
..X..
.....
.....
OOOOO
..OOO
--------------
measure = 1
....X....
.........
.........
.........
OOOOOOOOO
..OOOO...
.OOOOO...
...OO....
--------------
measure = 4
OOOOO
O...O
O.X.O
O...O
OOOOO
--------------
measure ~ 1.00813
X....OOOO
....OOOO.
...OOOO..
..OOOO...
.OOOO....

False

measure ~ 0.618
OO.X
--------------
measure ~ 0.999975 (0.61804 will fail)
OOOOOOOOOOOOOOOOOOOOOO.X
--------------
measure ~ 0.9868
X....OOO
....OOOO
...OOOO.
..OOOO..
.OOOO...
--------------
measure = 0
.....
.....
..X..
.....
.....

Answer 1

Python 3.8, 109 bytes

lambda s,i=-1:sum(c%2*.618034**(abs((i:=i+1)//(n:=(h:=s.index)(0)+1)-(x:=h(2))//n)+abs(i%n-x%n))for c in s)>1

Try it online!

Input is a list of integers, created by concatenating all rows of the grid. Each row is terminated by the number 0. Use the numbers 1, 2, 4 to represents "O", "X", ".".

---

Python 3.8, 108 bytes

lambda s,i=-1:sum(c%2*.618034**(abs((i:=i+1)//(n:=s.find(0)+1)-(x:=s.find(2))//n)+abs(i%n-x%n))for c in s)>1

Try it online!

Pushing the input format a little bit here by using unprintable characters. Input is a single byte string of concatenated rows, where each row is terminated by a NULL character (code point 0).
Replace X with the character SOT (code point 2).

Byte string is essentially an integer list of code points. The reason I'm not using list of integer is because list doesn't have find method. The code points of the row terminator and X are chosen to be single digit.

---

How:

The length of each row (including the terminator) can be simply calculated as:

n:=s.find(0)+1  # terminator is represented as 0

Similarly, the target position is

x:=s.find(2)    # X is represented as 2

We can then do some modular tricks to figure out the Manhattan distance between a position i and the target x:

abs(i//n + x//n) + abs(i%n + x%n)

All of these are shoved into a single expression by abusing walrus operator.

Answer 2

Python 2, 111 110 bytes

Thanks to @xnor for suggesting to use numbers as input, rather than a list of strings

g=input()
f=g.index;l=f(5)+1
c=i=0
for r in g:c+=r/9*.618034**(abs(f(2)/l-i/l)+abs(f(2)%l-i%l));i+=1
print c>1

Try it online!

Input is a single list of numbers. Uses 9 for pegs, 0 for blanks, 2 for the target, and 5 as a line terminator.

---

Python 2, 118 bytes

Solution provided by @Surculose Sputum

g=input()
f=g.find;l=f(',')+1;m=f('X')
c=i=0
for r in g:c+=(r<',')*.618034**(abs(m/l-i/l)+abs(m%l-i%l));i+=1
print c>1

Try it online!

Uses + instead of O to represent a peg. Input is a single string where rows are terminated by commas (,).

---

Original solution, 128 bytes

g=input();l=len(g[0]);g=''.join(g)
m=g.find('X')
c=i=0
for r in g:c+=(r<'-')*.618034**(abs(m/l-i/l)+abs(m%l-i%l));i+=1
print c>1

Try it online!

Uses + instead of O to represent a peg. Input is a list of strings representing the rows

Answer 3

J, 46 bytes

$(1<:1#.0.618034^1&#.)@(|@-"1{.)/@(#:I.)1 2=/,

Try it online!

Answer 4

Charcoal, 86 84 bytes

ＷＳ⊞υι≔⌕Ｅυ№ιX¹θ≔⟦⟧ζＦＬυＦ⁻⌕Ａ§υιO⌕§υθX⊞ζ⁺↔⁻ιθ↔κ≔Ｅ²ιδＦ⌈ζ⊞δ↨…⮌δ²±¹Ｉ⊘⁺ΣＥζ⁺§δ⊖ι§δ⊕ι×₂⁵ΣＥζ§δι

Try it online! Link is to verbose version of code. Uses exact surd arithmetic, and then converts the final surd to floating-point using \$ \sqrt 5 \$. Explanation:

ＷＳ⊞υι

Input the configuration.

≔⌕Ｅυ№ιX¹θ

Find the row that contains the X.

≔⟦⟧ζ

Start a list of O distances.

ＦＬυ

Loop through each row.

Ｆ⁻⌕Ａ§υιO⌕§υθX

Loop through each column that contains an O, and calculate the relative column offset from the X.

⊞ζ⁺↔⁻ιθ↔κ

For each relative column offset, add its absolute value to the absolute value of the relative row offset, and push that to the list of O distances.

(I would prefer to write the above as Ｆ⁺↔⁻ιθ↔⁻⌕Ａ§υιO⌕§υθX⊞ζκ which is slightly more efficient but Charcoal can't take the absolute value of an empty list.)

≔Ｅ²ιδ

Now start generating negative Fibonacci numbers starting with \$ F_0, F_{-1} \$ and working down.

Ｆ⌈ζ⊞δ↨…⮌δ²±¹

Get the maximum distance and add that many more negative Fibonacci numbers.

Ｉ⊘⁺ΣＥζ⁺§δ⊖ι§δ⊕ι×₂⁵ΣＥζ§δι

Calculate the total distance using the formula \$ \sum \phi^{-n} = \frac 1 2 \left ( \sum L_{-n} + \sqrt 5 \sum F_{-n} \right ) \$ where \$ L_n = F_{n-1} + F_{n+1} \$.

Answer 5

Jelly, 25 bytes

ŒĠḊạ€Ɲ§µ5½’H*SS<1¬
SS>3aÇ

Try it Online!

All testcases This should yield 6 truthy then 5 falsey outputs (I added the extra cases OX and X, which cause special problems with this algorithm). See the calculated value sums if interested.

Takes input as a rectangular array, where .OX corresponds to 012 (empty, peg, target).

How it works

ŒĠḊạ€Ɲ§µ5½’H*SS<1¬  # Is the value sum at least 1?
ŒĠ                    # Get an tuple of (coords of all 0 entries, coords of all 1 entries, coords of all 2 entries)
                      # If the matrix does not contain one of these, then that element of the tuple is left out, necessitating the SS>3 check
  Ḋ                   # Dequeue: remove the irrelevant coords of all 0 entries
   ạ€Ɲ                # Get the absolute (x,y) offset of all 1 entries from the 2 entry
      §               # Sum for Manhattan distance
       µ              # We are left with the Manhattan distances of each 1 from the 2
        5½’H          # (sqrt(5)-1)/2
            *         # to the power of
             S        # Each distance (S is sum, why is this an identity?)
              S       # Sum these powers to get the value sum
               <1¬    # Is this not less than 1? (Jelly has no <= operator)
                      # As a side note, ‘ÆC counts the number of primes <= z+1
                      # This is the same number of bytes as <1¬ and also returns a nonnegative value iff z is at least 1

SS>3aÇ               # Main link
SS>3                  # Is the sum of all entries > 3? (this is necessary to deal with having no pegs or no blanks, which messes with ŒĠ)
    a                 # and
     Ç                # the value sum is at least one

Extras

Another 25-byte solution:

;0ŒĠḊạ€Ɲ§µ5½’H*SS<1¬
ḢLaÇ

21 bytes if [[2]] (target but no pegs) is not included as a testcase;

;0ŒĠḊạ€Ɲ§µ5½’H*SS

Answer 6

Pyth, 37 bytes

!>1s.e*/b9^t.n3+a/KxQ2JhxQ5/kJa%KJ%kJ

Try it online! (You can copy-paste formatted test cases from my Python answer)

Port of my Python answer. Input is a single list of numbers. Uses 9 for pegs, 0 for blanks, 2 for the target, and 5 as a line terminator.

!>1s.e*/b9^t.n3+a/KxQ2JhxQ5/kJa%KJ%kJ
                  KxQ2       Initialize K to be the index of 2 in the input
                      JhxQ5  Initialize J to be the index of 5, plus 1
    .e                       Enumerated Map over the input, with b as the value, k as the index
            .n3              pre-initialized constant: phi (~1.6180339)
           t                  minus 1
          ^                  raised to the exponent:
                a/KJ/kJ       absolute difference between K/J and (index)/J
               +               plus
                a%KJ%kJ       absolute difference between K%J and (index)%J
                             (this gives us the manhattan distance between the current point and the target)
      *                      Multiply by
       /b9                    divide b by 9, yields 1 if b is a peg, 0 otherwise
   s                    Sum the mapped values
!>1                     Return true if greater than or equal to 1, false otherwise
                       (We can't use "less than" because the first test case yields 1.0 exactly)