Flipping bits game
- The game
Given an N by N square array of zeroes or ones in an initial configuration, and a target configuration of zeroes and ones The task is to transform one to the other in as few moves as possible by inverting whole numbered rows or whole lettered columns at once, as one move.
In an inversion any 1 becomes 0, and any 0 becomes 1 for that whole row or column.
- The Task
The task is to create a program to score for the Flipping bits game.
- The game should create an original random target configuration and a starting configuration.
- Ensure that the starting position is never the target position.
- The target position must be guaranteed as reachable from the starting position. (One possible way to do this is to generate the start position by legal flips from a random target position. The flips will always be reversible back to the target from the given start position).
- The number of moves taken so far should be shown.
Show an example of a short game here, on this page, for a 3 by 3 array of bits.
D
<lang d>import std.stdio, std.random, std.ascii, std.string, std.range,
std.algorithm, std.conv;
enum N = 3; // Board side. static assert(N <= lowercase.length); enum columnIDs = lowercase[0 .. N]; alias Board = ubyte[N][N];
void flipBits(ref Board board, in size_t count=1) {
foreach (immutable _; 0 .. count)
board[uniform(0, N)][uniform(0, N)] ^= 1;
}
void notRow(ref Board board, in size_t i) pure nothrow {
foreach (ref b; board[i])
b ^= 1;
}
void notColumn(ref Board board, in size_t i) pure nothrow {
foreach (ref row; board)
row[i] ^= 1;
}
Board generateGameBoard(in ref Board target) {
// board is generated with many flips, to keep parity unchanged.
Board board = target;
while (board == target)
foreach (immutable _; 0 .. 2 * N)
[¬Row, ¬Column][uniform(0, 2)](board, uniform(0, N));
return board;
}
void show(in ref Board board, in string comment) {
comment.writeln;
writefln(" %-(%c %)", columnIDs);
foreach (immutable j, const row; board)
writefln(" %2d %-(%d %)", j + 1, row);
}
void main() {
writefln("
Given a %d by %d square array of zeroes or ones in an initial configuration, and a target configuration of zeroes and ones. The task is to transform one to the other in as few moves as possible by inverting whole numbered rows or whole lettered columns at once. In an inversion any 1 becomes 0 and any 0 becomes 1 for that whole row or column. T prints the target, and Q exits.\n", N, N);
// Create target and flip some of its bits randomly. Board target; flipBits(target, uniform(0, N) + 1); show(target, "Target configuration is:");
auto board = generateGameBoard(target);
immutable prompt = format(" 1-%d / %s-%s to flip, or T, Q: ",
N, columnIDs[0], columnIDs.back);
uint move = 1;
while (board != target) {
show(board, format("\nMove %d:", move));
prompt.write;
immutable ans = readln.strip;
if (ans.length == 1 && columnIDs.canFind(ans)) {
board.notColumn(columnIDs.countUntil(ans));
move++;
} else if (iota(1, N + 1).map!text.canFind(ans)) {
board.notRow(ans.to!uint - 1);
move++;
} else if (ans == "T") {
show(target, "Target configuration is:");
} else if (ans == "Q") {
"Game stopped.".writeln;
return;
} else
writefln(" Wrong input '%s'. Try again.\n", ans.take(9));
}
"\nWell done!".writeln;
}</lang>
- Output:
Given a 3 by 3 square array of zeroes or ones in an initial
configuration, and a target configuration of zeroes and ones.
The task is to transform one to the other in as few moves as
possible by inverting whole numbered rows or whole lettered
columns at once. In an inversion any 1 becomes 0 and any 0
becomes 1 for that whole row or column.
T prints the target, and Q exits.
Target configuration is:
a b c
1 1 1 1
2 0 0 0
3 0 0 0
Move 1:
a b c
1 1 0 0
2 1 0 0
3 1 0 0
1-3 / a-c to flip, or T, Q: a
Move 2:
a b c
1 0 0 0
2 0 0 0
3 0 0 0
1-3 / a-c to flip, or T, Q: 1
Well done!
Perl
Pass the size of the puzzle on the command line. It defaults to 4. You can play any size game between 2 and 26. While playing, the game accepts anything which looks like valid rows or columns, and disregards any irrelevant text in between.
<lang perl>#!perl use strict; use warnings qw(FATAL all);
my $n = shift(@ARGV) || 4; if( $n < 2 or $n > 26 ) { die "You can't play a size $n game\n"; }
my $n2 = $n*$n;
my (@rows, @cols); for my $i ( 0 .. $n-1 ) { my $row = my $col = "\x00" x $n2; vec($row, $i * $n + $_, 8) ^= 1 for 0 .. $n-1; vec($col, $i + $_ * $n, 8) ^= 1 for 0 .. $n-1; push @rows, $row; push @cols, $col; }
my $goal = "0" x $n2; int(rand(2)) or (vec($goal, $_, 8) ^= 1) for 0 .. $n2-1; my $start = $goal; { for(@rows, @cols) { $start ^= $_ if int rand 2; } redo if $start eq $goal; }
my @letters = ('a'..'z')[0..$n-1]; sub to_strings { my $board = shift; my @result = join(" ", " ", @letters); for( 0 .. $n-1 ) { my $res = sprintf("%2d ",$_+1); $res .= join " ", split //, substr $board, $_*$n, $n; push @result, $res; } \@result; }
my $fmt; my ($stext, $etext) = ("Starting board", "Ending board"); my $re = join "|", reverse 1 .. $n, @letters; my $moves_so_far = 0; while( 1 ) { my ($from, $to) = (to_strings($start), to_strings($goal)); unless( $fmt ) { my $len = length $from->[0]; $len = length($stext) if $len < length $stext; $fmt = join($len, "%", "s%", "s\n"); } printf $fmt, $stext, $etext; printf $fmt, $from->[$_], $to->[$_] for 0 .. $n; last if $start eq $goal; INPUT_LOOP: { printf "Move #%s: Type one or more row numbers and/or column letters: ", $moves_so_far+1; my $input = <>; die unless defined $input; my $did_one; for( $input =~ /($re)/gi ) { $did_one = 1; if( /\d/ ) { $start ^= $rows[$_-1]; } else { $_ = ord(lc) - ord('a'); $start ^= $cols[$_]; } ++$moves_so_far; } redo INPUT_LOOP unless $did_one; } } print "You won after $moves_so_far moves.\n"; </lang>
- Output:
PS C:\Documents and Settings\Ben\RosettaCode> perl FlippingBitsGame.pl 5
Starting board Ending board
a b c d e a b c d e
1 0 0 1 0 1 1 1 0 1 1 0
2 1 1 1 0 0 2 0 1 1 1 1
3 1 1 1 0 1 3 1 0 0 0 1
4 1 0 1 1 0 4 0 0 1 0 1
5 0 1 0 0 0 5 0 0 1 0 0
Move #1: Type one or more row numbers and/or column letters: ad
Starting board Ending board
a b c d e a b c d e
1 1 0 1 1 1 1 1 0 1 1 0
2 0 1 1 1 0 2 0 1 1 1 1
3 0 1 1 1 1 3 1 0 0 0 1
4 0 0 1 0 0 4 0 0 1 0 1
5 1 1 0 1 0 5 0 0 1 0 0
Move #3: Type one or more row numbers and/or column letters: e35
Starting board Ending board
a b c d e a b c d e
1 1 0 1 1 0 1 1 0 1 1 0
2 0 1 1 1 1 2 0 1 1 1 1
3 1 0 0 0 1 3 1 0 0 0 1
4 0 0 1 0 1 4 0 0 1 0 1
5 0 0 1 0 0 5 0 0 1 0 0
You won after 5 moves.
The same game could have been won after typing a d e 3 5 in any order, even on one line.
Perl 6
Pass in a parameter to set the square size for the puzzle. (Defaults to 4.) Arbitrarily limited to between 1 and 26. Yes, you can choose to solve a 1 element square puzzle, but it won't be very challenging. Accepts upper or lower case letters for columns. Disregards any out-of-range indices. Enter a blank or 0 (zero) to exit.
<lang perl6>sub MAIN ($square = 4) {
say "{$square}? Seriously?" and exit if $square < 1 or $square > 26;
my %bits = map { $_ => %( map { $_ => 0 }, ('A' .. *)[^ $square] ) },
(1 .. *)[^ $square];
scramble %bits;
my $target = build %bits;
scramble %bits until build(%bits) ne $target;
display($target, %bits);
my $turns = 0;
while my $flip = prompt "Turn {++$turns}: Flip which row / column? " {
flip $flip.match(/\w/).uc, %bits;
if display($target, %bits) {
say "Hurray! You solved it in $turns turns.";
last;
}
}
}
sub display($goal, %hash) {
shell('clear');
say "Goal\n$goal\nYou";
my $this = build %hash;
say $this;
return ($goal eq $this);
}
sub flip ($a, %hash) {
given $a {
when any(keys %hash) {
%hash{$a}{$_} = %hash{$a}{$_} +^ 1 for %hash{$a}.keys
};
when any(keys %hash{'1'}) {
%hash{$_}{$a} = %hash{$_}{$a} +^ 1 for %hash.keys
};
}
}
sub build (%hash) {
my $string = ' ';
$string ~= sprintf "%2s ", $_ for sort keys %hash{'1'};
$string ~= "\n";
for sort keys %hash -> $key {
$string ~= sprintf "%2s ", $key;
$string ~= sprintf "%2s ", %hash{$key}{$_} for sort keys %hash{$key};
$string ~= "\n";
};
$string
}
sub scramble(%hash) {
my @keys = keys %hash;
@keys ,= keys %hash{'1'};
flip $_, %hash for @keys.pick( @keys/2 );
}</lang> A sample 3 x 3 game might look like this:
Goal
A B C
1 1 1 0
2 0 0 1
3 1 1 0
You
A B C
1 0 0 0
2 1 1 1
3 1 1 1
Turn 1: Flip which row / column? 2
Goal
A B C
1 1 1 0
2 0 0 1
3 1 1 0
You
A B C
1 0 0 0
2 0 0 0
3 1 1 1
Turn 2: Flip which row / column? 1
Goal
A B C
1 1 1 0
2 0 0 1
3 1 1 0
You
A B C
1 1 1 1
2 0 0 0
3 1 1 1
Turn 3: Flip which row / column? c
Goal
A B C
1 1 1 0
2 0 0 1
3 1 1 0
You
A B C
1 1 1 0
2 0 0 1
3 1 1 0
Hurray! You solved it in 3 turns.
Python
<lang python>""" Given a %i by %i sqare array of zeroes or ones in an initial configuration, and a target configuration of zeroes and ones The task is to transform one to the other in as few moves as possible by inverting whole numbered rows or whole lettered columns at once. In an inversion any 1 becomes 0 and any 0 becomes 1 for that whole row or column.
"""
from random import randrange from copy import deepcopy from string import ascii_lowercase
try: # 2to3 fix
input = raw_input
except:
pass
N = 3 # N x N Square arrray
board = [[0]* N for i in range(N)]
def setbits(board, count=1):
for i in range(count):
board[randrange(N)][randrange(N)] ^= 1
def shuffle(board, count=1):
for i in range(count):
if randrange(0, 2):
fliprow(randrange(N))
else:
flipcol(randrange(N))
def pr(board, comment=):
print(str(comment))
print(' ' + ' '.join(ascii_lowercase[i] for i in range(N)))
print(' ' + '\n '.join(' '.join(['%2s' % j] + [str(i) for i in line])
for j, line in enumerate(board, 1)))
def init(board):
setbits(board, count=randrange(N)+1)
target = deepcopy(board)
while board == target:
shuffle(board, count=2 * N)
prompt = ' X, T, or 1-%i / %s-%s to flip: ' % (N, ascii_lowercase[0],
ascii_lowercase[N-1])
return target, prompt
def fliprow(i):
board[i-1][:] = [x ^ 1 for x in board[i-1] ]
def flipcol(i):
for row in board:
row[i] ^= 1
if __name__ == '__main__':
print(__doc__ % (N, N))
target, prompt = init(board)
pr(target, 'Target configuration is:')
print()
turns = 0
while board != target:
turns += 1
pr(board, '%i:' % turns)
ans = input(prompt).strip()
if (len(ans) == 1
and ans in ascii_lowercase and ascii_lowercase.index(ans) < N):
flipcol(ascii_lowercase.index(ans))
elif ans and all(ch in '0123456789' for ch in ans) and 1 <= int(ans) <= N:
fliprow(int(ans))
elif ans == 'T':
pr(target, 'Target configuration is:')
turns -= 1
elif ans == 'X':
break
else:
print(" I don't understand %r... Try again. "
"(X to exit or T to show target)\n" % ans[:9])
turns -= 1
else:
print('\nWell done!\nBye.')</lang>
- Output:
Given a 3 by 3 sqare array of zeroes or ones in an initial
configuration, and a target configuration of zeroes and ones
The task is to transform one to the other in as few moves as
possible by inverting whole numbered rows or whole lettered
columns at once.
In an inversion any 1 becomes 0 and any 0 becomes 1 for that
whole row or column.
Target configuration is:
a b c
1 0 1 0
2 0 0 0
3 0 0 0
1:
a b c
1 1 0 0
2 0 0 1
3 0 0 1
X, T, or 1-3 / a-c to flip: 1
2:
a b c
1 0 1 1
2 0 0 1
3 0 0 1
X, T, or 1-3 / a-c to flip: c
Well done!
Bye.
- Showing bad/other inputs
Target configuration is:
a b c
1 0 0 0
2 0 0 0
3 0 0 1
1:
a b c
1 1 0 1
2 0 1 0
3 0 1 1
X, T, or 1-3 / a-c to flip: 3
2:
a b c
1 1 0 1
2 0 1 0
3 1 0 0
X, T, or 1-3 / a-c to flip: 4
I don't understand '4'... Try again. (X to exit or T to show target)
2:
a b c
1 1 0 1
2 0 1 0
3 1 0 0
X, T, or 1-3 / a-c to flip: c
3:
a b c
1 1 0 0
2 0 1 1
3 1 0 1
X, T, or 1-3 / a-c to flip: d
I don't understand 'd'... Try again. (X to exit or T to show target)
3:
a b c
1 1 0 0
2 0 1 1
3 1 0 1
X, T, or 1-3 / a-c to flip: T
Target configuration is:
a b c
1 0 0 0
2 0 0 0
3 0 0 1
3:
a b c
1 1 0 0
2 0 1 1
3 1 0 1
X, T, or 1-3 / a-c to flip: X
REXX
This REXX version allows the specification for:
- the size of the array (grid) [default is 3]
- the number of bits (for the target) to be set [default is 3]
- the characters which are used for the on and off [defaults are 1 and 0]
<lang rexx>/*REXX program presents a "flipping bit" puzzle to the user at the C.L. */ parse arg N u on off .; tries=0 /*get optional arguments. */ if N== | N==',' then N=3 /*Size given? Then use default.*/ if u== | u==',' then u=3 /*number of bits initialized ON.*/ if on== then on=1 /*character used for "on". */ if off== then off=0 /*character used for "off". */ @.=off /*set the array to "off" chars.*/
do while it()<u /* [↓] turn "on" U elements.*/
r=random(1,N); c=random(1,N); @.r.c=on /*set row,column to ON*/
end /*while*/ /* [↑] keep going 'til U bits set*/
oz=z /*remember the original array str*/ call it 20, ' ◄───target' /*show target for user to attain.*/ do random(1,2); call flip 'R',random(1,N); call flip 'C',random(1,N); end if z==oz then call flip 'R',random(1,N) /*ensure it's not the original*/
do until z==oz /*prompt until they get it right.*/
if tries\==0 then say '─────────bit array after move: ' tries
call it 1 /*display the array to the screen*/
call prompt /*get a row or column # from C.L.*/
call flip left(?,1),substr(?,2) /*flip a user selected row or col*/
call it /*get image of the updated array.*/
end /*forever*/
say; say '─────────Congrats! You did it in' tries "tries." exit tries /*stick a fork in it, we're done.*/ /*──────────────────────────────────FLIP subroutine─────────────────────*/ flip: parse arg x,# /*x is R or C, # is which one*/ if x=='R' then do c=1 for N; if @.#.c==on then @.#.c=off;else @.#.c=on;end
else do r=1 for N; if @.r.#==on then @.r.#=off;else @.r.#=on;end
return /*──────────────────────────────────IT subroutine───────────────────────*/ it: z=; $=0; _=; parse arg tell,tx; if tell\== then say
do r=1 for N
do c=1 for N; z=z||@.r.c; _=_ @.r.c; $=$+(@.r.c==on); end
if tell\== then say left(,tell) _ tx; _= /*show array?*/
end /*r*/
return $ /*──────────────────────────────────PROMPTER subroutine─────────────────*/ prompt: p='─────────Please enter a row or col number (as r1 or c3), or Quit:'
do forever; ok=1; say; say p; parse upper pull ?; ?=space(?,0)
parse var ? what 2 num; if abbrev('QUIT',?,1) then exit 0
if what\=='R' & what\=='C' then call terr 'first char not R or C'
if \datatype(num,W) then call terr 'row or col not numeric'
else num=num/1 /*normalize the #*/
if num<1 | num>N then call terr 'row or col out of range'
if \ok then iterate /*had any errors?*/
tries=tries+1; return ? /*bump counter. */
end /*forever*/
/*──────────────────────────────────TERR subroutine─────────────────────*/
terr: if ok then say '***error!***:' arg(1); ok=0; return</lang>
output when using the default inputs:
Note that the user's input is also show (the r1, c3, and c1 user responses).
1 0 0 ◄───target
0 0 0 ◄───target
1 1 0 ◄───target
0 0 0
0 1 1
1 0 1
─────────Please enter a row or col number (as r1 or c3), or Quit:
r1
─────────bit array after move: 1
1 1 1
0 1 1
1 0 1
─────────Please enter a row or col number (as r1 or c3), or Quit:
c3
─────────bit array after move: 2
1 1 0
0 1 0
1 0 0
─────────Please enter a row or col number (as r1 or c3), or Quit:
c2
─────────Congrats! You did it in 3 tries.