Two Spies

If N is 3|s1-s2| = 1 It seems like there is some kind of pattern here.
If N is 4 |s1-s2| = 3
If N is 5 |s1-s2| = 2
If N is 6 |s1-s2| = 4
If N is 7 |s1-s2| = 3
If N is 8 |s1-s2| = 3
If N is 9 |s1-s2| = 6
If N is 10 |s1-s2| = 6
If N is 11 |s1-s2| = 5
If N is 12 |s1-s2| = 5
If N is 13 |s1-s2| = 5
If N is 14 |s1-s2| = 9
If N is 15 |s1-s2| = 9
If N is 16 |s1-s2| = 7
If N is 17 |s1-s2| = 7
If N is 18 |s1-s2| = 7
If N is 19 |s1-s2| = 7
If N is 20 |s1-s2| = 7
If N is 21 |s1-s2| = 15
If N is 22 |s1-s2| = 14
If N is 23 |s1-s2| = 14
If N is 24 |s1-s2| = 10
If N is 25 |s1-s2| = 10
If N is 26 |s1-s2| = 10
If N is 27 |s1-s2| = 10
If N is 28 |s1-s2| = 10
If N is 29 |s1-s2| = 10
If N is 30 |s1-s2| = 10

Hmm, surely sometimes S1 is Bigger than S2 and Sometimes its the other way round, so sometimes the difference should be negative and sometimes positive?

Originally posted by iamatiger
Hmm, surely sometimes S1 is Bigger than S2 and Sometimes its the other way round, so sometimes the difference should be negative and sometimes positive?

Originally posted by tomtom232
Couldn't we just graph the positions of each spy for ever number and then use the graph to create two formula's for each "spy line?"

ex x is the amount of people in the group and y is the position of each spy.
8| s(4,8) S(7,8)
7|
6|s(1,6) S(5,6)
5| s(2,5)S(4,5)
4|s(1,4) S(4,4)
3|s(1,3)S(2,3)
2|
1|
0|------------------ ...[text shortened]... l people in the group?
Maybe there is a pattern in the amount of people between each spy.

Hmmmm
If you look at the number of people (N) where a spy steps backwards some number (rather than forwards by 3) these numbers of people are:

reset num1 reset2 reset
154
276
3119
41614
52421
63631
75447
88170
9122105
10183158
11274237
12411355

Spy 1 reset points are very nearly equal to 3.1677195 * 1.5^X where X is the reset number

Spy 2s reset points are very nearly equal to 2.7361081 & 1.5^x

It suspicious that they are both so proportional to 1.5^x

On each move, the spy shuffles forward 3, and two are moved off the end. The chain is now N+1 long, and the spy is 2 positions closer to the end.
So, on each move the spy gets 2 positions closer to the end. If his distance to the end is odd, it will always be odd, and if it is even it will always be even (on this run)

So, distance from spy at end on Switch = N-S (S is the spy position at the switch)

If this distance is even, then the spy will end up in last position (0 from the end).
If this distance is odd, the spy will end up second from last position (1 from the end)

The even spy will be in last position after (N-S)/2 moves when the chain is (3N-S)/2 long

The odd spy will be in second to last position after (N-S-1)/2 moves when the chain is (3N - S - 1)/2 long

On the next move after this:
The even spy will be at position 2, with a chain (3N-S)/2 + 1 long
The odd spy will be at position 1 with a chain (3N-S-1)/2 + 1 long

Have to go to work now, but that's how I'm thinking at the mo.

Talzamir - Do you know if this has a solution for any N?

(other than some program like)

Solution for 3 = "12X" (1 = pos of spy 1, 2 = pos of spy 2)

Solution for N+1 = right(sol_n,2)&"X"&left(sol_n,len(sol_n)-2)

You get a very interesting pattern if you write down the pattern twice on each line, starting 3 spaces further back each time:

using A for spy 1, B for spy 2, X for martyr, and S as a spacer to keep everthing in line

SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSABXABX
SSSSSSSSSSSSSSSSSSSSSSSSSSSBXXABXXA
SSSSSSSSSSSSSSSSSSSSSSSSXAXBXXAXBX
SSSSSSSSSSSSSSSSSSSSSBXXXAXBXXXAX
SSSSSSSSSSSSSSSSSSAXXBXXXAXXBXXX
SSSSSSSSSSSSSSSXXXAXXBXXXXAXXBX
SSSSSSSSSSSSBXXXXXAXXBXXXXXAXX
SSSSSSSSSXXXBXXXXXAXXXBXXXXXA
SSSSSSXAXXXXBXXXXXAXXXXBXXXX
SSSXXXXAXXXXBXXXXXXAXXXXBXX
XXXXXXXAXXXXBXXXXXXXAXXXXB

Originally posted by iamatiger
On each move, the spy shuffles forward 3, and two are moved off the end. The chain is now N+1 long, and the spy is 2 positions closer to the end.
So, on each move the spy gets 2 positions closer to the end. If his distance to the end is odd, it will always be odd, and if it is even it will always be even (on this run)

So, distance from spy at end on S ...[text shortened]... a chain (3N-S-1)/2 + 1 long

Have to go to work now, but that's how I'm thinking at the mo.

The first 83 switch states for spy one, up to the point where my spreadsheet can't represent the numbers precisely, with him in position 2 of a chain 871897780498214
men long (about 125,000 times the population of the world) are:

ABABCCCCADBCABADDBCCABADBCCCCCABCADDBCADBCADDDBADBADDDDBCABCCABCABABABADDBCABCADBAB

I can see no sign at all of any ordering, therefore I am starting to think that writing a non-recursive formula for the spy position at any position is impossible, although we can get to the nearest switch state and skip forward the right amount with a fairly short program.

Here is a program implementing the recursive mod method and my switch states method:


use strict;
use warnings;
use Time::HiRes qw( gettimeofday tv_interval);


while () {
print "Input number of resistance fighters, '0' to exit \n";
chomp (my $num_fighters = <> ) ;
last unless $num_fighters;

my @start_time = gettimeofday;
my ($spy_1_pos, $spy_2_pos) = recursive_modulus($num_fighters);
my $elapsed_time = tv_interval(\@start_time);

print "Recursive Modulus got $spy_1_pos and $spy_2_pos in $elapsed_time seconds\n";

@start_time = gettimeofday;
($spy_1_pos, $spy_2_pos) = switch_states_method($num_fighters);
$elapsed_time = tv_interval(\@start_time);
print "Switch States Method got $spy_1_pos and $spy_2_pos in $elapsed_time seconds\n";
}

sub recursive_modulus {
my $N = shift;
my @answers;
foreach my $spy_start_pos (1,2) {
my $spy_pos = $spy_start_pos;
foreach my $n_people (4 .. $N) {
$spy_pos += 3;
$spy_pos = $spy_pos % $n_people; #spy_pos mod n_people
$spy_pos = $n_people if $spy_pos == 0;
}
push @answers, $spy_pos;
}
return @answers;
}

sub switch_states_method {
my $N = shift;
my @answers;
foreach my $spy_start_pos (1..2) {
my ($spy_pos, $last_spy_pos) = ($spy_start_pos, $spy_start_pos);
my ($chain_length, $last_chain_length) = (3,3);
while ($chain_length <= $N) {
$last_chain_length = $chain_length;
$last_spy_pos = $spy_pos;
my $odd_num_in_chain = $chain_length % 2; #0 if even, 1 if odd
if ($odd_num_in_chain) {
if ($spy_pos == 1) {
#odd num in chain and spy pos is 1
$spy_pos = 2;
$chain_length = 1.5*$chain_length + 0.5;
}else{
#odd num in chain and spy pos is 2
$spy_pos = 1;
$chain_length = 1.5*$chain_length - 0.5;
}
}else {
$chain_length = 1.5*$chain_length;
#spy position does not change;
}
}
my $num_left = $N - $last_chain_length;
push @answers, $last_spy_pos + 3*$num_left;
}
return @answers;

And here are the results from some runs:
It's pretty clear that the switch states method is scaling with log(n_people) whereas recursive modulus scales with n_people

I'm stopping thinking about this now, it seems I've gone as far as I can go.

Input number of resistance fighters, '0' to exit
3
Recursive Modulus got 1 and 2 in 0 seconds
Switch States Method got 1 and 2 in 4.5e-005 seconds
Input number of resistance fighters, '0' to exit
4
Recursive Modulus got 4 and 1 in 5.1e-005 seconds
Switch States Method got 4 and 1 in 4.8e-005 seconds
Input number of resistance fighters, '0' to exit
10
Recursive Modulus got 10 and 4 in 5.7e-005 seconds
Switch States Method got 10 and 4 in 5.5e-005 seconds
Input number of resistance fighters, '0' to exit
100
Recursive Modulus got 58 and 91 in 0.000148 seconds
Switch States Method got 58 and 91 in 7.1e-005 seconds
Input number of resistance fighters, '0' to exit
1000
Recursive Modulus got 226 and 604 in 0.00104 seconds
Switch States Method got 226 and 604 in 9.1e-005 seconds
Input number of resistance fighters, '0' to exit
10000
Recursive Modulus got 8923 and 2692 in 0.01 seconds
Switch States Method got 8923 and 2692 in 0.000107 seconds
Input number of resistance fighters, '0' to exit
100000
Recursive Modulus got 59905 and 92620 in 0.061135 seconds
Switch States Method got 59905 and 92620 in 4.8e-005 seconds
Input number of resistance fighters, '0' to exit
1000000
Recursive Modulus got 265157 and 637798 in 0.393022 seconds
Switch States Method got 265157 and 637798 in 5.8e-005 seconds
Input number of resistance fighters, '0' to exit
10000000
Recursive Modulus got 9232277 and 3093025 in 3.718212 seconds
Switch States Method got 9232277 and 3093025 in 6.5e-005 seconds
Input number of resistance fighters, '0' to exit
100000000
Recursive Modulus got 63442642 and 95675152 in 37.114123 seconds
Switch States Method got 63442642 and 95675152 in 7.7e-005 seconds
Input number of resistance fighters, '0' to exit
1000000000
Recursive Modulus got 305463824 and 672612260 in 371.391242 seconds
Switch States Method got 305463824 and 672612260 in 0.000103 seconds
Input number of resistance fighters, '0' to exit

Originally posted by iamatiger
I can see no sign at all of any ordering, therefore I am starting to think that writing a non-recursive formula for the spy position at any position is impossible..

Yep, on a local level it is predictable - position moves 3 forward each go, but on a long distance level the recursive modulus makes it random and unpredictable. Luckily, because each regular part is 1.5 times longer than the last, it is possible to pre-compute compute the regular parts, and only work out the non regular parts explicitly, which gives the technique solving it in log(n) time.

Here a the shorter but somewhat more obfucticated version of the perl log(n) solution:

foreach my $spy_start_pos (0..1) {
my ($spy_pos, $last_spy_pos, $chain_length, $last_chain_length) = ($spy_start_pos, $spy_start_pos, 3, 3);
while ($chain_length < $N) {
my $odd_chain = $chain_length % 2;
chain_length *= 1.5;
$chain_length += 0.5 - $spy_pos if $odd_chain;
$spy_pos = !$spy_pos if $odd_chain;
($last_chain_length, $last_spy_pos) = ($chain_length, $spy_pos) if $chain_length <= $N;
}
push @answers, $last_spy_pos + 1 + 3*($N - $last_chain_length);
}

Originally posted by iamatiger
Yep, on a local level it is predictable - position moves 3 forward each go, but on a long distance level the recursive modulus makes it random and unpredictable. Luckily, because each regular part is 1.5 times longer than the last, it is possible to pre-compute compute the regular parts, and only work out the non regular parts explicitly, which gives the t ...[text shortened]... $N;
}
push @answers, $last_spy_pos + 1 + 3*($N - $last_chain_length);
}