Flipping bits game

From Rosetta Code
Jump to: navigation, search
Task
Flipping bits game
You are encouraged to solve this task according to the task description, using any language you may know.
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.

  1. The game should create an original random target configuration and a starting configuration.
  2. Ensure that the starting position is never the target position.
  3. 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).
  4. 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.

Contents

[edit] Ada

This solution determines the size of the playground from the command line.

with Ada.Text_IO, Ada.Command_Line, Ada.Numerics.Discrete_Random;
 
procedure Flip_Bits is
 
subtype Letter is Character range 'a' .. 'z';
 
Last_Col: constant letter := Ada.Command_Line.Argument(1)(1);
Last_Row: constant Positive := Positive'Value(Ada.Command_Line.Argument(2));
 
package Boolean_Rand is new Ada.Numerics.Discrete_Random(Boolean);
Gen: Boolean_Rand.Generator;
 
type Matrix is array
(Letter range 'a' .. Last_Col, Positive range 1 .. Last_Row) of Boolean;
 
function Rand_Mat return Matrix is
M: Matrix;
begin
for I in M'Range(1) loop
for J in M'Range(2) loop
M(I,J) := Boolean_Rand.Random(Gen);
end loop;
end loop;
return M;
end Rand_Mat;
 
function Rand_Mat(Start: Matrix) return Matrix is
M: Matrix := Start;
begin
for I in M'Range(1) loop
if Boolean_Rand.Random(Gen) then
for J in M'Range(2) loop
M(I,J) := not M(I, J);
end loop;
end if;
end loop;
for I in M'Range(2) loop
if Boolean_Rand.Random(Gen) then
for J in M'Range(1) loop
M(J,I) := not M(J, I);
end loop;
end if;
end loop;
return M;
end Rand_Mat;
 
procedure Print(Message: String; Mat: Matrix) is
package NIO is new Ada.Text_IO.Integer_IO(Natural);
begin
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line(Message);
Ada.Text_IO.Put(" ");
for Ch in Matrix'Range(1) loop
Ada.Text_IO.Put(" " & Ch);
end loop;
Ada.Text_IO.New_Line;
for I in Matrix'Range(2) loop
NIO.Put(I, Width => 3);
for Ch in Matrix'Range(1) loop
Ada.Text_IO.Put(if Mat(Ch, I) then " 1" else " 0");
end loop;
Ada.Text_IO.New_Line;
end loop;
end Print;
 
Current, Target: Matrix;
Moves: Natural := 0;
 
begin
-- choose random Target and start ("Current") matrices
Boolean_Rand.Reset(Gen);
Target := Rand_Mat;
loop
Current := Rand_Mat(Target);
exit when Current /= Target;
end loop;
Print("Target:", Target);
 
-- print and modify Current matrix, until it is identical to Target
while Current /= Target loop
Moves := Moves + 1;
Print("Current move #" & Natural'Image(Moves), Current);
Ada.Text_IO.Put_Line("Flip row 1 .." & Positive'Image(Last_Row) &
" or column 'a' .. '" & Last_Col & "'");
declare
S: String := Ada.Text_IO.Get_Line;
function Let(S: String) return Character is (S(S'First));
function Val(Str: String) return Positive is (Positive'Value(Str));
begin
if Let(S) in 'a' .. Last_Col then
for I in Current'Range(2) loop
Current(Let(S), I) := not Current(Let(S), I);
end loop;
else
for I in Current'Range(1) loop
Current(I, Val(S)) := not Current(I, Val(S));
end loop;
end if;
end;
end loop;
 
-- summarize the outcome
Ada.Text_IO.Put_Line("Done after" & Natural'Image(Moves) & " Moves.");
end Flip_Bits;
Output:

For a 3*3-Matrix, the command line input is "c 3".

>./flip_bits c 3

Target:
    a b c
  1 1 0 1
  2 1 0 0
  3 1 0 0

Current move # 1
    a b c
  1 1 0 0
  2 1 0 1
  3 0 1 0
Flip row 1 .. 3 or column 'a' .. 'c'
3

Current move # 2
    a b c
  1 1 0 0
  2 1 0 1
  3 1 0 1
Flip row 1 .. 3 or column 'a' .. 'c'
c
Done after 2 Moves.

[edit] AutoHotkey

Uploads are currently disabled, so since a GUI is used, I can't show an example.

size := 3 ; max 26
Gui, Add, Button, , O
Loop, %size%
{
x := chr(A_Index+64)
If x = A
Loop, %size%
Gui, Add, Button, y+4 gFlip, % A_Index
Gui, Add, Button, ym gFlip, % x
Loop, %size%
{
y := A_Index
Random, %x%%y%, 0, 1
Gui, Add, Edit, v%x%%y% ReadOnly, % %x%%y%
}
}
Gui, Add, Text, ym, Moves:`nTarget:
Loop, %size%
{
x := chr(A_Index+64)
Loop, %size%
{
y := A_Index
Gui, Add, Edit, % y=1 ? x="A" ? "xp+0 ym+30" : "x+14 ym+30" : "" . "ReadOnly vt" x y, % t%x%%y% := %x%%y%
}
}Gui, Add, Text, xp-18 ym w30 Right vMoves, % Moves:=1
 
; randomize
While (i < size)
{
Random, z, 1, %size%
Random, x, 0, 1
z := x ? chr(z+64) : z
Solution .= z ; to cheat
If Flip(z, size)
i := 0 ; ensure we are not at the solution
Else
i++ ; count
}
Gui, Show, NA
Return
 
Flip(z, size) {
Loop, %size%
{
If z is alpha
GuiControl, , %z%%A_Index%, % %z%%A_Index% := !%z%%A_Index%
Else
{
AIndex := chr(A_Index+64)
GuiControl, , %AIndex%%z%, % %AIndex%%z% := !%AIndex%%z%
}
}
Loop, %size%
{
x := chr(A_Index+64)
Loop, %size%
{
y := A_Index
If (%x%%y% != t%x%%y%)
Return 0
}
}
Return 1
}
 
Flip:
GuiControl, , Moves, % Moves++
If Flip(A_GuiControl, size)
{
Msgbox Success in %Moves% moves!
Reload
}
Return
 
ButtonO:
Reload
Return
 
GuiEscape:
GuiClose:
ExitApp
Return

[edit] C++

 
#include <time.h>
#include <iostream>
#include <string>
 
typedef unsigned char byte;
using namespace std;
 
class flip
{
public:
flip() { field = 0; target = 0; }
void play( int w, int h ) { wid = w; hei = h; createField(); gameLoop(); }
 
private:
void gameLoop()
{
int moves = 0;
while( !solved() )
{
display(); string r; cout << "Enter rows letters and/or column numbers: "; cin >> r;
for( string::iterator i = r.begin(); i != r.end(); i++ )
{
byte ii = ( *i );
if( ii - 1 >= '0' && ii - 1 <= '9' ) { flipCol( ii - '1' ); moves++; }
else if( ii >= 'a' && ii <= 'z' ) { flipRow( ii - 'a' ); moves++; }
}
}
cout << endl << endl << "** Well done! **" << endl << "Used " << moves << " moves." << endl << endl;
}
 
void display()
{ system( "cls" ); output( "TARGET:", target ); output( "YOU:", field ); }
 
void output( string t, byte* f )
{
cout << t << endl;
cout << " "; for( int x = 0; x < wid; x++ ) cout << " " << static_cast<char>( x + '1' ); cout << endl;
for( int y = 0; y < hei; y++ )
{
cout << static_cast<char>( y + 'a' ) << " ";
for( int x = 0; x < wid; x++ )
cout << static_cast<char>( f[x + y * wid] + 48 ) << " ";
cout << endl;
}
cout << endl << endl;
}
 
bool solved()
{
for( int y = 0; y < hei; y++ )
for( int x = 0; x < wid; x++ )
if( target[x + y * wid] != field[x + y * wid] ) return false;
return true;
}
 
void createTarget()
{
for( int y = 0; y < hei; y++ )
for( int x = 0; x < wid; x++ )
if( frnd() < .5f ) target[x + y * wid] = 1;
else target[x + y * wid] = 0;
memcpy( field, target, wid * hei );
}
 
void flipCol( int c )
{ for( int x = 0; x < hei; x++ ) field[c + x * wid] = !field[c + x * wid]; }
 
void flipRow( int r )
{ for( int x = 0; x < wid; x++ ) field[x + r * wid] = !field[x + r * wid]; }
 
void calcStartPos()
{
int flips = ( rand() % wid + wid + rand() % hei + hei ) >> 1;
for( int x = 0; x < flips; x++ )
{ if( frnd() < .5f ) flipCol( rand() % wid ); else flipRow( rand() % hei ); }
}
 
void createField()
{
if( field ){ delete [] field; delete [] target; }
int t = wid * hei; field = new byte[t]; target = new byte[t];
memset( field, 0, t ); memset( target, 0, t ); createTarget();
while( true ) { calcStartPos(); if( !solved() ) break; }
}
 
float frnd() { return static_cast<float>( rand() ) / static_cast<float>( RAND_MAX ); }
 
byte* field, *target; int wid, hei;
};
 
int main( int argc, char* argv[] )
{ srand( time( NULL ) ); flip g; g.play( 5, 5 ); return system( "pause" ); }
 
Output:
TARGET:
1 2 3 4 5
a 1 0 0 0 0
b 1 0 1 1 1
c 1 1 0 0 0
d 0 0 0 0 0
e 0 1 1 0 0


YOU:
1 2 3 4 5
a 0 1 1 1 1
b 0 1 0 0 0
c 0 0 1 1 1
d 0 0 0 0 0
e 1 0 0 1 1


Enter rows letters and/or column numbers: abce


** Well done! **
Used 4 moves.

[edit] D

Translation of: Python
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, $)][uniform(0, $)] ^= 1;
}
 
void notRow(ref Board board, in size_t i) pure nothrow {
board[i][] ^= 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)
[&notRow, &notColumn][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() {
"T prints the target, and Q exits.\n".writeln;
// 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") {
return "Game stopped.".writeln;
} else
writefln(" Wrong input '%s'. Try again.\n", ans.take(9));
}
 
"\nWell done!".writeln;
}
Output:
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!

[edit] J

Using J's command line as the game ui:

start=:3 :0
Moves=:0
N=:i.y
Board=: ?2$~,~y
'fr fc'=. (2,y)$}.#:(+?&.<:@<:)2x^2*y
End=: fr~:fc~:"1 Board
Board;End
)
 
abc=:'abcdefghij'
move=:3 :0
fc=. N e.abc i. y ([-.-.)abc
fr=. N e._-.~_ "."0 abc-.~":y
Board=: fr~:fc~:"1 Board
smoutput (":Moves=:Moves++/fr,fc),' moves'
if. Board-:End do.
'yes'
else.
Board;End
end.
)

Example:

   start 3
┌─────┬─────┐
1 1 11 0 1
1 1 00 1 1
1 0 00 0 1
└─────┴─────┘
move 'b2'
2 moves
┌─────┬─────┐
1 0 11 0 1
1 0 00 1 1
0 0 10 0 1
└─────┴─────┘
move '1'
3 moves
yes

Note that any size game may be generated but this version only recognizes column flips for the first ten columns.


[edit] MATLAB

Size can be passed in as an argument or entered after a prompt.

function FlippingBitsGame(n)
% Play the flipping bits game on an n x n array
 
% Generate random target array
fprintf('Welcome to the Flipping Bits Game!\n')
if nargin < 1
n = input('What dimension array should we use? ');
end
Tar = logical(randi([0 1], n));
 
% Generate starting array by randomly flipping rows or columns
Cur = Tar;
while all(Cur(:) == Tar(:))
nFlips = randi([3*n max(10*n, 100)]);
randDim = randi([0 1], nFlips, 1);
randIdx = randi([1 n], nFlips, 1);
for k = 1:nFlips
if randDim(k)
Cur(randIdx(k), :) = ~Cur(randIdx(k), :);
else
Cur(:, randIdx(k)) = ~Cur(:, randIdx(k));
end
end
end
 
% Print rules
fprintf('Given a %d x %d logical array,\n', n, n)
fprintf('and a target array configuration,\n')
fprintf('attempt to transform the array to the target\n')
fprintf('by inverting the bits in a whole row or column\n')
fprintf('at once in as few moves as possible.\n')
fprintf('Enter the corresponding letter to invert a column,\n')
fprintf('or the corresponding number to invert a row.\n')
fprintf('0 will reprint the target array, and no entry quits.\n\n')
fprintf('Target:\n')
PrintArray(Tar)
 
% Play until player wins or quits
move = true;
nMoves = 0;
while ~isempty(move) && any(Cur(:) ~= Tar(:))
fprintf('Move %d:\n', nMoves)
PrintArray(Cur)
move = lower(input('Enter move: ', 's'));
if length(move) > 1
fprintf('Invalid move, try again\n')
elseif move
r = str2double(move);
if isnan(r)
c = move-96;
if c > n || c < 1
fprintf('Invalid move, try again\n')
else
Cur(:, c) = ~Cur(:, c);
nMoves = nMoves+1;
end
else
if r > n || r < 0
fprintf('Invalid move, try again\n')
elseif r == 0
fprintf('Target:\n')
PrintArray(Tar)
else
Cur(r, :) = ~Cur(r, :);
nMoves = nMoves+1;
end
end
end
end
 
if all(Cur(:) == Tar(:))
fprintf('You win in %d moves! Try not to flip out!\n', nMoves)
else
fprintf('Quitting? The challenge a bit much for you?\n')
end
end
 
function PrintArray(A)
[nRows, nCols] = size(A);
fprintf(' ')
fprintf(' %c', (1:nCols)+96)
fprintf('\n')
for r = 1:nRows
fprintf('%8d%s\n', r, sprintf(' %d', A(r, :)))
end
fprintf('\n')
end
Output:

Normal play and winning:

Welcome to the Flipping Bits Game!
What dimension array should we use? 3
Given a 3 x 3 logical array,
and a target array configuration,
attempt to transform the array to the target
by inverting the bits in a whole row or column
at once in as few moves as possible.
Enter the corresponding letter to invert a column,
or the corresponding number to invert a row.
0 will reprint the target array, and no entry quits.

Target:
         a b c
       1 0 0 0
       2 0 1 0
       3 0 0 0

Move 0:
         a b c
       1 1 1 1
       2 1 0 1
       3 1 1 1

Enter move: a
Move 1:
         a b c
       1 0 1 1
       2 0 0 1
       3 0 1 1

Enter move: b
Move 2:
         a b c
       1 0 0 1
       2 0 1 1
       3 0 0 1

Enter move: c
You win in 3 moves! Try not to flip out!

Bad input, reprinting target, and quitting:

Welcome to the Flipping Bits Game!
What dimension array should we use? 3
Given a 3 x 3 logical array,
and a target array configuration,
attempt to transform the array to the target
by inverting the bits in a whole row or column
at once in as few moves as possible.
Enter the corresponding letter to invert a column,
or the corresponding number to invert a row.
0 will reprint the target array, and no entry quits.

Target:
         a b c
       1 0 0 1
       2 1 0 0
       3 1 0 0

Move 0:
         a b c
       1 0 0 0
       2 0 1 0
       3 0 1 0

Enter move: a
Move 1:
         a b c
       1 1 0 0
       2 1 1 0
       3 1 1 0

Enter move: b
Move 2:
         a b c
       1 1 1 0
       2 1 0 0
       3 1 0 0

Enter move: 0
Target:
         a b c
       1 0 0 1
       2 1 0 0
       3 1 0 0

Move 2:
         a b c
       1 1 1 0
       2 1 0 0
       3 1 0 0

Enter move: hello
Invalid move, try again
Move 2:
         a b c
       1 1 1 0
       2 1 0 0
       3 1 0 0

Enter move: d
Invalid move, try again
Move 2:
         a b c
       1 1 1 0
       2 1 0 0
       3 1 0 0

Enter move: 4
Invalid move, try again
Move 2:
         a b c
       1 1 1 0
       2 1 0 0
       3 1 0 0

Enter move: 
Quitting? The challenge a bit much for you?


[edit] 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.

#!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";
 
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.

[edit] 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.

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 );
}

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.

[edit] PL/I

(subscriptrange, stringrange, stringsize):
flip: procedure options (main);
declare n fixed binary;
 
put skip list ('This is the bit-flipping game. What size of board do you want?');
get list (n);
put skip list
('Your task is to change your board so as match the board on the right (the objective)');
 
begin;
declare initial(n,n) bit (1), objective(n,n) bit (1);
declare (i, j, k, move) fixed binary;
declare ch character(1);
declare alphabet character (26) initial ('abcdefghijklmnopqrstuvwxyz');
 
on subrg
begin; put skip list ('Your row or column ' || trim(ch) || ' is out of range'); stop; end;
 
initial, objective = iand(random()*99, 1) = 1;
 
/* Set up the objective array: */
do i = 1 to n-1;
j = random()*n+1; objective(j,*) = ^objective(j,*);
j = random()*n+1; objective(*,j) = ^objective(*,j);
end;
 
do move = 0 by 1;
put skip edit ( center('You', n*3), center('The objective', 3*n+4) ) (x(3), a);
put skip edit ( (substr(alphabet, i, 1) do i = 1 to n) ) (x(5), (n) a(3));
put edit ( (substr(alphabet, i, 1) do i = 1 to n) ) (x(3), (n) a(3));
do i = 1 to n;
put skip edit (i, initial(i,*), objective(i,*)) ((n+1) f(3), x(3), (n) F(3));
end;
 
if all(initial = objective) then leave;
 
put skip(2) list
('Please type a row number or column letter whose bits you want to flip: ');
get edit (ch) (L); put edit (ch) (a);
k = index(alphabet, ch);
if k > 0 then
initial(*, k) = ^initial(*,k); /* Flip column k */
else
initial(ch,*) = ^initial(ch,*); /* Flip row ch */
end;
put skip(2) list ('Congratulations. You solved it in ' || trim(move) || ' moves.');
end;
 
end flip;

Output:

This is the bit-flipping game.  What size of board do you want? 

Your task is to change your board so as match the board on the right (the objective) 
      You      The objective
     a  b  c     a  b  c  
  1  1  1  1     0  1  1
  2  0  0  0     1  0  0
  3  1  1  1     1  0  0

Please type a row number or column letter whose bits you want to flip:  
3
      You      The objective
     a  b  c     a  b  c  
  1  1  1  1     0  1  1
  2  0  0  0     1  0  0
  3  0  0  0     1  0  0

Please type a row number or column letter whose bits you want to flip:  
a
      You      The objective
     a  b  c     a  b  c  
  1  0  1  1     0  1  1
  2  1  0  0     1  0  0
  3  1  0  0     1  0  0

Congratulations. You solved it in 2 moves.

[edit] 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.')
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

[edit] Racket

#lang racket
(define (flip-row! pzzl r)
(define N (integer-sqrt (bytes-length pzzl)))
(for* ((c (in-range N)))
(define idx (+ c (* N r)))
(bytes-set! pzzl idx (- 1 (bytes-ref pzzl idx)))))
 
(define (flip-col! pzzl c)
(define N (integer-sqrt (bytes-length pzzl)))
(for* ((r (in-range N)))
(define idx (+ c (* N r)))
(bytes-set! pzzl idx (- 1 (bytes-ref pzzl idx)))))
 
(define (new-game N (flips 10))
(define N2 (sqr N))
(define targ (list->bytes (for/list ((_ N2)) (random 2))))
(define strt (bytes-copy targ))
(for ((_ flips))
(case (random 2)
((0) (flip-col! strt (random N)))
((1) (flip-row! strt (random N)))))
(if (equal? strt targ) (new-game N) (values targ strt)))
 
(define (show-games #:sep (pzl-sep " | ") . pzzls)
(define N (integer-sqrt (bytes-length (first pzzls))))
(define caption (string-join (for/list ((c (in-range N))) (~a (add1 c))) ""))
(define ruler (string-join (for/list ((c (in-range N))) "-") ""))
 
(define ((pzzle-row r) p)
(string-join (for/list ((c (in-range N))) (~a (bytes-ref p (+ c (* N r))))) ""))
 
(displayln
(string-join
(list*
(format " ~a" (string-join (for/list ((_ pzzls)) caption) pzl-sep))
(format " ~a" (string-join (for/list ((_ pzzls)) ruler) pzl-sep))
(for/list ((r (in-range N)) (R (in-naturals (char->integer #\a))))
(format "~a ~a" (integer->char R) (string-join (map (pzzle-row r) pzzls) pzl-sep))))
"\n")))
 
(define (play N)
(define-values (end start) (new-game N))
(define (turn n (show? #t))
(cond
[(equal? end start) (printf "you won on turn #~a~%" n)]
[else
(when show? ;; don't show after whitespace
(printf "turn #~a~%" n)
(show-games start end))
(match (read-char)
[(? eof-object?) (printf "sad to see you go :-(~%")]
[(? char-whitespace?) (turn n #f)]
[(? char-numeric? c)
(define cnum (- (char->integer c) (char->integer #\1)))
(cond [(< -1 cnum N)
(printf "flipping col ~a~%" (add1 cnum))
(flip-col! start cnum)
(turn (add1 n))]
[else (printf "column number out of range ~a > ~a~%" (add1 cnum) N)
(turn n)])]
[(? char-lower-case? c)
(define rnum (- (char->integer c) (char->integer #\a)))
(cond [(< -1 rnum N)
(printf "flipping row ~a~%" (add1 rnum))
(flip-row! start rnum)
(turn (add1 n))]
[else (printf "row number out of range ~a > ~a~%" (add1 rnum) (sub1 N))
(turn n)])]
[else (printf "unrecognised character in input: ~s~%" else)
(turn n)])]))
(turn 0))
Output:
(play 3)
turn #0
  123 | 123
  --- | ---
a 001 | 101
b 110 | 101
c 100 | 000
1
flipping col 1
turn #1
  123 | 123
  --- | ---
a 101 | 101
b 010 | 101
c 000 | 000
b
flipping row 2
you won on turn #2

[edit] 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]
/*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

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.

[edit] Tcl

Works with: Tcl version 8.6
package require Tcl 8.6
 
oo::class create Flip {
variable board target s
constructor {size} {
set s $size
set target [my RandomConfiguration]
set board $target
while {$board eq $target} {
for {set i 0} {$i < $s} {incr i} {
if {rand()<.5} {
my SwapRow $i
}
if {rand()<.5} {
my SwapColumn $i
}
}
}
}
 
method RandomConfiguration {{p 0.5}} {
for {set row 0} {$row < $s} {incr row} {
set r {}
for {set col 0} {$col < $s} {incr col} {
lappend r [expr {rand() < $p}]
}
lappend result $r
}
return $result
}
 
method SwapRow {rowId} {
for {set i 0} {$i < $s} {incr i} {
lset board $rowId $i [expr {![lindex $board $rowId $i]}]
}
}
method SwapColumn {columnId} {
for {set i 0} {$i < $s} {incr i} {
lset board $i $columnId [expr {![lindex $board $i $columnId]}]
}
}
 
method Render {configuration {prefixes {}}} {
join [lmap r $configuration p $prefixes {
format %s%s $p [join [lmap c $r {string index ".X" $c}] ""]
}] "\n"
}
method GetInput {prompt} {
puts -nonewline "${prompt}: "
flush stdout
gets stdin
}
 
method play {} {
set p0 {}
set p {}
set top [format "%*s " [string length $s] ""]
for {set i 1;set j 97} {$i<=$s} {incr i;incr j} {
append top [format %c $j]
lappend p [format "%*d " [string length $s] $i]
lappend p0 [format "%*s " [string length $s] ""]
}
 
set moves 0
puts "You are trying to get to:\n[my Render $target $p0]\n"
while true {
puts "Current configuration (#$moves):\n$top\n[my Render $board $p]"
 
# Test for if we've won
if {$board eq $target} break
 
# Ask the user for a move
set i [my GetInput "Pick a column (letter) or row (number) to flip"]
 
# Parse the move and apply it
if {[string is lower -strict $i] && [set c [expr {[scan $i "%c"] - 97}]]<$s} {
my SwapColumn $c
incr moves
} elseif {[string is integer -strict $i] && $i>0 && $i<=$s} {
my SwapRow [expr {$i - 1}]
incr moves
} else {
puts "Error: bad selection"
}
puts ""
}
puts "\nYou win! (You took $moves moves.)"
}
}
 
Flip create flip 3
flip play
 
Example game:
You are trying to get to:
  .XX
  XXX
  X.X

Current configuration (#0):
  abc
1 .X.
2 ..X
3 X..
Pick a column (letter) or row (number) to flip: 2

Current configuration (#1):
  abc
1 .X.
2 XX.
3 X..
Pick a column (letter) or row (number) to flip: c

Current configuration (#2):
  abc
1 .XX
2 XXX
3 X.X

You win! (You took 2 moves.)
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox