Sicherheitsbits

CDW · Nov 16, 2008

Die Firma EyBiM hat ein neues Sicherheitssystem entwickelt - vereinfacht gesagt handelt es sich um einen Chip mit X "Sicherheitsbits".
Bsp: [1,1,1,1,1,1]
Sofern alle Bits gesetzt sind, wird ein OK Signal gesendet (und dadurch ein Schloss aufgemacht bzw. eine Tür geöffnet).

Regeln zum Setzen der Bits:
das höchste Bit (links) kann beliebig gesetzt oder gelöscht werden.
sonst: ein Bit kann nur dann gesetzt oder gelöscht werden, wenn das nächsthöhere Bit gelöscht und die anderen höherwertigen Bits gesetzt sind.
D.h das "nächstlinkere" Bit muss 0 sein und die anderen "linkeren" Bits (sofern vorhanden) 1 entsprechen.
Formaler ausgedrückt:
Sei A ein Array mit Bits =[a1,a2,a3,...,an]
Das i-te Bit kann nur dann gesetzt/gelöscht werden, wenn:
a)es das erste Bit ist <=> i=1
b)wenn das Bit i-1=0 ist und alle anderen Bits von 1 bis i-2=1 sind.
Bsp:
x,0,0,0,0,0 <- x kann beliebig sein.
0,x,0,0,0,0 <- x kann beliebig sein.
1,0,x,0,0,0 <- x kann beliebig sein.
1,1,0,x,0,0, <- x kann beliebig sein.

Die Sicherheitsprüfung besteht nun darin, mit einem biometrsichen Scanner einige Daten auszulesen, daraus einen Startzustand für den Chip zu bilden (z.B 1,1,0,1,0,0). Nach diesem Schritt führt der User seine persönliche Security-Card ein. Auf dieser Karte ist einfach eine Abfolge an Schritten gespeichert, so dass der Chip aus dem Startzustand in den [1,1,1,1,1,1] Zustand kommt.
Damit bleibt ein Diebstahl/Verlust der Karte unproblematisch.

Ganz zufälligerweise ist der Startzustand des Chips für Dich gleich den ersten 6 Bits Deiner Habo-Userid.
Berechne nun eine (für Dich gültige) Abfolge von Schritten.
Bsp: von [0,0,0] nach [1,1,1]

[[0,0,0],[1,0,0],[1,0,1],[0,0,1],[0,1,1],[1,1,1]]

von [1,0,0] nach [1,1,1]

[[1,0,0],[1,0,1],[0,0,1],[0,1,1],[1,1,1]]

Optimalerweise sollte Dein Programm die Abfolge von jedem angegebenen Startzustand berechnen können.

Wenn Du Dich an das Ausgabeformat in diesem Beispiel hälst, bekommst Du einen Bonus

Edit: hab mal die Schwierigkeit etwas höher gesetzt.

Spyx · Nov 16, 2008

Ich hab jetzt einfach mal einen Online-Converter benutzt, um meine HaBo-User-ID ins Binärsystem zu übertragen (Link).

Meine User-ID ist: 16711
Umgerechnet ins Binärsystem: 100000101000111
Davon die ersten 6 Bits: 100000

Stimmt das so?
Wenn ja, dann hat es Qkiller ziemlich einfach

.

CDW · Nov 16, 2008

1)ein gesetztes Bit ist =1

, Ziel ist also [1,1,1,1,1,1]
2)die ersten 6 Bits sind bei Dir 000111 (ist zumindest imho üblich, von rechts nach links zu gehen, wegen der zweierpotenzen ->2^5+2^4+2^3+2^2+2^1+ 2^0)
das wären 4 Zwischenschritte.
Natürlich kannst Du bei der [1,0,0,0,0,0] Version bleiben - wären mindestens 42 Zwischenschritte

Oi!Alex · Nov 17, 2008

Bin.: 11000000001010

[0,0,1,0,1,0], [1,0,1,0,1,0], [1,0,1,0,0,0], [1,0,1,0,0,1], [1,0,1,0,1,1], [1,0,0,0,1,1], [1,0,0,1,1,1], [1,0,1,1,1,1], [0,0,1,1,1,1], [0,1,1,1,1,1], [1,1,1,1,1,1]

Wäre das richtig? Bin mir nicht ganz sicher ob ich es richtig verstanden habe.

CDW · Nov 17, 2008

Original von Oi!Alex
Wäre das richtig? Bin mir nicht ganz sicher ob ich es richtig verstanden habe.

Nee, leider nicht. Habe noch eine formalere Definition im ersten Post hinzugefügt.
Man kann ein Bit ändern, wenn es das erste (von links) ist oder wenn
das linke "Nachbarbit"=0 und die anderen linkeren Nachbarn (sofern vorhanden) =1 sind.

Code:

[0,0,1,0,1,0], [1,0,1,0,1,0], [1,0,1,0,0,0], [1,0,1,0,0,1]
                                              ^ ^ ^ ^ ^=0=>ok
					      | | |  =0 ->nicht ok
					        =0 ->nicht ok

Währen bei Dir eher:

Code:

[0,0,1,0,1,0],[0,1,1,0,1,0],[1,1,1,0,1,0],[1,1,1,0,0,0],[0,1,1,0,0,0]...

90nop · Nov 17, 2008

Mir war, als hätte ich kürzlich einen permutations-Algo gesehen, der genau nach diesem Schema vorgegegangen ist. Mal schauen ob ich den wieder finde...

Oi!Alex · Nov 18, 2008

Original von CDW
Nee, leider nicht. Habe noch eine formalere Definition im ersten Post hinzugefügt.
Man kann ein Bit ändern, wenn es das erste (von links) ist oder wenn
das linke "Nachbarbit"=0 und die anderen linkeren Nachbarn (sofern vorhanden) =1 sind.

Ah okay habs verstanden, muss mal schauen wann ich Zeit habe, da setzt ich mich da mal ran.

lagalopex · Nov 18, 2008

Hab mich mal dran gesetzt. Der erste Ansatz hat sogar funktioniert (dem entsprechend kurz ist auch das Programm...)

Denke ich zumindest mal:

Code:

[[1,0,0,1,0,0],[1,0,1,1,0,0],[0,0,1,1,0,0],[0,1,1,1,0,0],[1,1,1,1,0,0],[1,1,1,1,0,1],[0,1,1,1,0,1],[0,0,1,1,0,1],[1,0,1,1,0,1],[1,0,0,1,0,1],[0,0,0,1,0,1],[0,1,0,1,0,1],[1,1,0,1,0,1],[1,1,0,0,0,1],[0,1,0,0,0,1],[0,0,0,0,0,1],[1,0,0,0,0,1],[1,0,1,0,0,1],[0,0,1,0,0,1],[0,1,1,0,0,1],[1,1,1,0,0,1],[1,1,1,0,1,1],[0,1,1,0,1,1],[0,0,1,0,1,1],[1,0,1,0,1,1],[1,0,0,0,1,1],[0,0,0,0,1,1],[0,1,0,0,1,1],[1,1,0,0,1,1],[1,1,0,1,1,1],[0,1,0,1,1,1],[0,0,0,1,1,1],[1,0,0,1,1,1],[1,0,1,1,1,1],[0,0,1,1,1,1],[0,1,1,1,1,1],[1,1,1,1,1,1]]

Source folgt dann in ein paar Tagen

CDW · Nov 18, 2008

Original von lagalopex

Code:

[[1,0,0,1,0,0],[1,0,1,1,0,0],[0,0,1,1,0,0],[0,1,1,1,0,0],[1,1,1,1,0,0],[1,1,1,1,0,1],[0,1,1,1,0,1],[0,0,1,1,0,1],[1,0,1,1,0,1],[1,0,0,1,0,1],[0,0,0,1,0,1],[0,1,0,1,0,1],[1,1,0,1,0,1],[1,1,0,0,0,1],[0,1,0,0,0,1],[0,0,0,0,0,1],[1,0,0,0,0,1],[1,0,1,0,0,1],[0,0,1,0,0,1],[0,1,1,0,0,1],[1,1,1,0,0,1],[1,1,1,0,1,1],[0,1,1,0,1,1],[0,0,1,0,1,1],[1,0,1,0,1,1],[1,0,0,0,1,1],[0,0,0,0,1,1],[0,1,0,0,1,1],[1,1,0,0,1,1],[1,1,0,1,1,1],[0,1,0,1,1,1],[0,0,0,1,1,1],[1,0,0,1,1,1],[1,0,1,1,1,1],[0,0,1,1,1,1],[0,1,1,1,1,1],[1,1,1,1,1,1]]

in diesem Format kann ich es durch den Validierer jagen

Code:

| ?- Lagalopexloesung=[[1,0,0,1,0,0],[1,0,1,1,0,0],[0,0,1,1,0,0],[0,1,1,1,0,0],[1,1,1,1,0,0],[1,1,1,1,0,1],[0,1,1,1,0,1],[0,0,1,1,0,1],[1,0,1,1,0,1],[1,0,0,1,0,1],[0,0,0,1,0,1],[0,1,0,1,0,1],[1,1,0,1,0,1],[1,1,0,0,0,1],[0,1,0,0,0,1],[0,0,0,0,0,1],[1,0,0,0,0,1],[1,0,1,0,0,1],[0,0,1,0,0,1],[0,1,1,0,0,1],[1,1,1,0,0,1],[1,1,1,0,1,1],[0,1,1,0,1,1],[0,0,1,0,1,1],[1,0,1,0,1,1],[1,0,0,0,1,1],[0,0,0,0,1,1],[0,1,0,0,1,1],[1,1,0,0,1,1],[1,1,0,1,1,1],[0,1,0,1,1,1],[0,0,0,1,1,1],[1,0,0,1,1,1],[1,0,1,1,1,1],[0,0,1,1,1,1],[0,1,1,1,1,1],[1,1,1,1,1,1]],
     valid(Lagalopexloesung).
yes
| ?-

MontyPerl · Nov 20, 2008

Code:

#!/usr/bin/env perl
use strict;
use warnings;
use Data::Dumper;
local $Data::Dumper::Indent = 0;

my $HaBoUID  = shift || 18149;    # My (MontyPerl's) UID is the default.
my $bits     = $HaBoUID & 63;     # 2**6 - 1
my @solution = fillBits($bits);

my $outArray = [];
for (@solution) {
    push @$outArray, [map { $_ ? 1 : 0 } split(//, sprintf("%06b", $_))];
}
my $dumped = Dumper $outArray;
$dumped =~ s/^\$VAR\d+ = //;
$dumped =~ s/;$//;
print $dumped, "\n";

sub fillBits {
    my ($bits, @way) = @_;
    if ($bits == 63) {
        # warm... warmer.. disco.
        return @way, $bits;
    }
    elsif (grep { $bits == $_ } @way) {
        # we had this number already.
        return;
    }
    for my $n (0 .. 5) {
        if (canSwitch($bits, $n)) {
            my @sol = fillBits($bits ^ (2**$n), @way, $bits);
            return @sol if @sol;
        }
    }
    return;
}

sub canSwitch {
    my ($bits, $bit) = @_;
    if (!((2**($bit + 1)) & $bits)) {
        for my $n (($bit + 2) .. 5) {
            if (!((2**$n) & $bits)) {
                return 0;
            }
        }
        return 1;
    }
    else {
        return 0;
    }
}

Ein Fünftel des Codes ist nur die Vorbereitung für die Darstellung der validierbaren Ausgabe und ich hab n Bisschen viele Klammern benutzt, weil ich mir bei der prescendence von logischem NOT, bitweisen Operatoren und Potenz-Operator nicht sicher war, aber nunja.
Mein Lösung für meine UID (18149):

Code:

[[1,0,0,1,0,1],[0,0,0,1,0,1],[0,1,0,1,0,1],[1,1,0,1,0,1],[1,1,0,0,0,1],[0,1,0,0,0,1],[0,0,0,0,0,1],[1,0,0,0,0,1],[1,0,1,0,0,1],[0,0,1,0,0,1],[0,1,1,0,0,1],[1,1,1,0,0,1],[1,1,1,0,1,1],[0,1,1,0,1,1],[0,0,1,0,1,1],[1,0,1,0,1,1],[1,0,0,0,1,1],[0,0,0,0,1,1],[0,1,0,0,1,1],[1,1,0,0,1,1],[1,1,0,1,1,1],[0,1,0,1,1,1],[0,0,0,1,1,1],[1,0,0,1,1,1],[1,0,1,1,1,1],[0,0,1,1,1,1],[0,1,1,1,1,1],[1,1,1,1,1,1]]

CDW · Nov 21, 2008

@MontyPerl:

Code:

valid([[1,0,0,1,0,1],[0,0,0,1,0,1],[0,1,0,1,0,1],[1,1,0,1,0,1],[1,1,0,0,0,1],[0,1,0,0,0,1],[0,0,0,0,0,1],[1,0,0,0,0,1],[1,0,1,0,0,1],[0,0,1,0,0,1],[0,1,1,0,0,1],[1,1,1,0,0,1],[1,1,1,0,1,1],[0,1,1,0,1,1],[0,0,1,0,1,1],[1,0,1,0,1,1],[1,0,0,0,1,1],[0,0,0,0,1,1],[0,1,0,0,1,1],[1,1,0,0,1,1],[1,1,0,1,1,1],[0,1,0,1,1,1],[0,0,0,1,1,1],[1,0,0,1,1,1],[1,0,1,1,1,1],[0,0,1,1,1,1],[0,1,1,1,1,1],[1,1,1,1,1,1]]).
true.

Sonst:

Code:

trans(X,X).                         
trans([0|T],[1|T]).                 
trans([1|T],[0|T]).                 
step([0|T1],[0|T2]) :- trans(T1,T2).  
step([1|T1],[1|T2]) :- step(T1,T2).  
                                    
valid([_]).                         
valid([X,Y|Z]) :- (trans(X,Y);step(X,Y)),        
        valid([Y|Z]),!; write(('Uebergang:',X->Y)).

Code:

trans(X,X).                          %Uebergang korrekt, wenn beide Zustaende gleich sind    
trans([0|T],[1|T]).                  %0 -> 1 ist zulaessig, Rest muss gleich sein
trans([1|T],[0|T]).                  %1 -> 0 genauso
step([0|T1],[0|T2]):-trans(T1,T2).   %auf eine 0 folgt ein Uebergang
step([1|T1],[1|T2]):- step(T1,T2).   %auf eine 1 kann nur der nächste Schritt folgen
                                     %Uebergang mit nur einem (Rest)Element 
valid([_]).                          %ist irgendwie immer korrekt ;)  
valid([X,Y|Z]):-(trans(X,Y);         %X->Y ein korrekter Uebergang oder
                 step(X,Y)),         %X->Y Schritt ist korrekt
        valid([Y|Z]),!;              %Y->Z sollte auch korrekt sein ->dann stimmt X->Z  
	write(('Uebergang:',X->Y)).  %sonst gib den unkorrekten Uebergang aus

Ausführbar mit Sicstus/SWI/GNU Prolog oder JLog (kann als Applet gestartet werden).
http://jlogic.sourceforge.net/download.html

Eingabe:
"valid([[0,1,0],[0,0,0],...])." <--- den "." am Ende nicht vergessen

bei einer unkorrekten Schrittfolge wird der Schritt X->Y ausgegeben (bei einer korrekten nur yes/true).

Lesco · Nov 23, 2008

Hier eine Haskell-Lösung, hätte man ein bisschen lesbarer schreiben können, funktioniert aber auch so.
Man kann einen Startzustand in beliebige Endzustände überführen(findPathExt). Zum Finden einer Lösung ist findPath <startzustand> aufzurufen.

Code:

import Control.Monad.State
import Control.Monad.Writer

canBeChanged :: [Int] -> Int -> Bool
canBeChanged _ 0 = True
canBeChanged xs n = all (==1) (take (n-1) xs) && (xs !! (n-1)) == 0

flipBit lst n = (take n lst) ++ [if (lst !! n) == 0 then 1 else 0] ++ (drop (n+1) lst)

getTransTo' :: Int -> Int -> [Int] -> StateT [Int] (Writer [[Int]]) ()
getTransTo' i n lst
    | lst !! i == n = return ()
    | canBeChanged lst i = put (flipBit lst i) >> get >>= tell . (:[])
    -- if we can't set it directly, set all bits left of it to their required values:
    | otherwise = sequence_ $ [getTransTo (i-1) 0] ++ [getTransTo x 1 | x <- reverse [0..i-2]] ++ [getTransTo i n]

getTransTo :: Int -> Int -> StateT [Int] (Writer [[Int]]) ()
getTransTo i n = get >>= getTransTo' i n

findPathExt :: [Int] -> [Int] -> [[Int]]
findPathExt lst pattern = [lst] ++ (execWriter $ execStateT solve lst)
    where solve = mapM_ (uncurry getTransTo) . reverse $ zip [0..length lst-1] pattern

findPath :: [Int] -> [[Int]]
findPath lst = findPathExt lst [1,1..]

Beispiel für meine User-Id(11149):

Code:

[[0,0,1,1,0,1],[1,0,1,1,0,1],[1,0,0,1,0,1],[0,0,0,1,0,1],[0,1,0,1,0,1],[1,1,0,1,0,1],[1,1,0,0,0,1],[0,1,0,0,0,1],[0,0,0,0,0,1],[1,0,0,0,0,1],[1,0,1,0,0,1],[0,0,1,0,0,1],[0,1,1,0,0,1],[1,1,1,0,0,1],[1,1,1,0,1,1],[0,1,1,0,1,1],[0,0,1,0,1,1],[1,0,1,0,1,1],[1,0,0,0,1,1],[0,0,0,0,1,1],[0,1,0,0,1,1],[1,1,0,0,1,1],[1,1,0,1,1,1],[0,1,0,1,1,1],[0,0,0,1,1,1],[1,0,0,1,1,1],[1,0,1,1,1,1],[0,0,1,1,1,1],[0,1,1,1,1,1],[1,1,1,1,1,1]]

Edit: Leicht verbesserte Version eingefügt.

lagalopex · Nov 23, 2008

So... dann will ich auch mal meine C++ Lösung posten

Code:

#include <iostream>

using namespace std;

void bin(int i, bool sep = true)
{
	cout << ((sep)? "," : "") << "[";
	for (int n = 5; n >= 0; --n)
		cout << ((i>>n)&1) << ((n > 0)? "," : "");
	cout << "]";
}

void setbit(int &v, int p, int val = 1)
{
	if (((v >> p) & 1) == !!val)
		return;
	if (p < 5) {
		setbit(v, p + 1, 0);
		for (int pos = p + 2; pos < 6; ++pos)
			setbit(v, pos);
	}
	v ^= (1 << p);
	bin(v);
}

int main()
{
	int id;
	cout << "HaBo-UserId: " << flush;
	cin >> id;
	id &= 0x2f;
	cout << "Die Sechs-Bit-Zahl: " << id << endl;

	cout << "[";
	bin(id, false);

	int pos;
	for (pos = 0; pos < 6; ++pos)
		setbit(id, pos);
	cout << "]" << endl;
}

t3rr0r.bYt3 · Nov 24, 2008

Ich hab leider grad gar keine Zeit, das zu vervollständigen, daher hier nur mal die flip-Operationen in SML zusammengehackt. Wer mag, erweitert die Funktionen einfach um einen weiteren Parameter (Liste), an die jeder Schritt angehängt wird. hd2 und tl2 sind einfach ein Umbau von head und tail (beides auf leeren Listen nicht definiert). An isOne_, set _ und clear _ sollte eigentlich ne Exception fliegen, da hab ich aber die Syntax nicht mehr im Kopf

Code:

fun	tl2 []			= []
|	tl2 (xs)		= tl(xs)

fun	hd2 []			= [] 
|	hd2 (xs)		= hd(xs)::[]

fun	isOne []		= true
|	isOne (0::xs)		= false
|	isOne (1::xs)		= isOne(xs) 
|	isOne _			= false

fun	set []			= []
|	set (1::xs)		= 1::(set(xs))
|	set (0::(0::xs))	= if isOne(xs) then set(1::(0::xs)) else set(0::(0::(set(xs))))
|	set (0::(1::xs))	= set (0::(hd2(clear(1::xs)))@(set(tl2(clear(1::xs)))))
|	set (0::xs)		= 1::[]
|	set _			= []

and	clear []		= []
|	clear (0::xs)		= 0::xs
|	clear (1::(0::xs))	= if isOne(xs) then 0::(0::xs) else clear(1::(0::(set(xs))))
|	clear (1::xs)		= 0::((hd2(clear(xs))))@(set(tl2(clear(xs))))
|	clear _			= []

Ook! · Dez 1, 2008

Hallo!

Code:

def doIt(id, fr=True):
    if "".join(id) == "1"*len(id): return
    if fr: result.append("["+ ",".join(id) +"]")
    
    for i in range(0, len(id)):        
        if fr and id[i] == "1": continue
        if validFlip(id, i):
            id[i] = str(int(not int(id[i])))
            result.append("["+ ",".join(id) +"]")
    doIt(id, False)
        
def validFlip(id, i):
    if (i==0) or (id[i-1] == "0" and False not in [ bool(int(id[x])) for x in range(0,i-1) ]): return True
    elif i-2 == -1: return id[i-1] == "0" 
    else: return False

if __name__ == '__main__':
    result = [ ]
    doIt(list("001100"))
    print "["+ ",".join(result) +"]"

Prüfung mit JLog:

Code:

valid([[0,0,1,1,0,0],[1,0,1,1,0,0],[0,0,1,1,0,0],[0,1,1,1,0,0],[1,1,1,1,0,0],[1,1,1,1,0,1],[0,1,1,1,0,1],[0,0,1,1,0,1],[1,0,1,1,0,1],[1,0,0,1,0,1],[0,0,0,1,0,1],[0,1,0,1,0,1],[1,1,0,1,0,1],[1,1,0,0,0,1],[0,1,0,0,0,1],[0,0,0,0,0,1],[1,0,0,0,0,1],[1,0,1,0,0,1],[0,0,1,0,0,1],[0,1,1,0,0,1],[1,1,1,0,0,1],[1,1,1,0,1,1],[0,1,1,0,1,1],[0,0,1,0,1,1],[1,0,1,0,1,1],[1,0,0,0,1,1],[0,0,0,0,1,1],[0,1,0,0,1,1],[1,1,0,0,1,1],[1,1,0,1,1,1],[0,1,0,1,1,1],[0,0,0,1,1,1],[1,0,0,1,1,1],[1,0,1,1,1,1],[0,0,1,1,1,1],[0,1,1,1,1,1],[1,1,1,1,1,1]])
yes

Gruß
Felix

Painii · Dez 12, 2008

Meine Lösung in Java

Code:

public class Sicherheit {
	private String ablauf;	//Speicher für den Ablauf der Änderungen
	private boolean first;	//Für ordentliche Auflistung in ablauf
	private int[] bits;	//Das Array mit der ID die geändert wird
	public Sicherheit(int[] a){
		this.ablauf="[";
		this.first=true;
		this.bits=a;
		ablauf();
	}
	
	private void ablauf(){	//Schreibt die Änderungen auf damit sie in den Validierer passen
		if(!first)ablauf=ablauf+",";
		ablauf=ablauf+"[";
		for(int i=0;i<this.bits.length;i++){
			if(i==0)ablauf=ablauf+this.bits[i];
			else ablauf=ablauf+","+this.bits[i];
		}
		ablauf=ablauf+"]";
		first=false;
	
	}
	private void machEins(int pos){
		if(this.bits[pos]==1)return;	//Zahl ist schon 1
		if(pos==0){						//Erste Zahl kann einfach geändert werden
			this.bits[pos]=1;
			this.ablauf();				//Schreibt die Änderung auf
			return;
		}
		else{							
			machNull(pos-1);			//Änder die Zahl links in eine 0
			for(int i=pos-2;i>=0;i--)machEins(i);	//Mach alle Zahlen links von der 0 zu 1
			this.bits[pos]=1;		//Jetzt darf ich ändern
			this.ablauf();			//Schreibt die Änderung auf
		}
	}
	private void machNull(int pos){
		if(this.bits[pos]==0)return;	//Zahl ist schon 0
		if(pos==0){	//Erste Zahl kann einfach geändert werden
			this.bits[pos]=0;
			this.ablauf();	//Schreibt die Änderung auf
			return;
		}
		else{
			machNull(pos-1);	//Änder die Zahl links in eine 0
			for(int i=pos-2;i>=0;i--)machEins(i);	//Mach alle Zahlen links von der 0 zu 1
			this.bits[pos]=0;	//Jetzt darf ich ändern
			this.ablauf();	//Schreibt die Änderung auf
		}
	}
	public void loesen(){	//Startet die Loesung
		for(int i=this.bits.length-1;i>=0;i--){
			this.machEins(i);	//Geht von rechts nach links durch das array und macht alles zu 1
		}
		this.ablauf=this.ablauf+"]";	//Abschluss des Verlaufs
	}
	
	public static void main(String[] args){
		int[] d1={1,1,1,0,1,1};	//Meine ID
		Sicherheit a=new Sicherheit(d1);
		a.loesen();
		System.out.println(a.ablauf);	//Ausgabe des Lösungswegs
	}
}

Code:

valid([[1,1,1,0,1,1],[0,1,1,0,1,1],[0,0,1,0,1,1],[1,0,1,0,1,1],[1,0,0,0,1,1],[0,0,0,0,1,1],[0,1,0,0,1,1],[1,1,0,0,1,1],[1,1,0,1,1,1],[0,1,0,1,1,1],[0,0,0,1,1,1],[1,0,0,1,1,1],[1,0,1,1,1,1],[0,0,1,1,1,1],[0,1,1,1,1,1],[1,1,1,1,1,1]]).
true.

Lesco · Dez 12, 2008

Original von Painii

Code:

private void machEins(int pos){
		if(this.bits[pos]==1)return;	//Zahl ist schon 1
		if(pos==0){						//Erste Zahl kann einfach geändert werden
			this.bits[pos]=1;
			this.ablauf();				//Schreibt die Änderung auf
			return;
		}
		else{							
			machNull(pos-1);			//Änder die Zahl links in eine 0
			for(int i=pos-2;i>=0;i--)machEins(i);	//Mach alle Zahlen links von der 0 zu 1
			this.bits[pos]=1;		//Jetzt darf ich ändern
			this.ablauf();			//Schreibt die Änderung auf
		}
	}
	private void machNull(int pos){
		if(this.bits[pos]==0)return;	//Zahl ist schon 0
		if(pos==0){	//Erste Zahl kann einfach geändert werden
			this.bits[pos]=0;
			this.ablauf();	//Schreibt die Änderung auf
			return;
		}
		else{
			machNull(pos-1);	//Änder die Zahl links in eine 0
			for(int i=pos-2;i>=0;i--)machEins(i);	//Mach alle Zahlen links von der 0 zu 1
			this.bits[pos]=0;	//Jetzt darf ich ändern
			this.ablauf();	//Schreibt die Änderung auf
		}
	}

Kleine Anregung zur Verbesserung: Fallen dir irgendwelche Gemeinsamkeiten bei den beiden Funktionen auf, die sich evtl. zusammenfassen ließen?

Painii · Dez 12, 2008

Ja, ich könnte einen 2. Parameter nehmen (z.b. boolean), und daraus eine Funktion machen die beide Werte setzen kann (false->0, true->1)...

Was ich auch zusammenfassen könnte ist der Teil wo ich die Werte vorher auf 1 bzw. 0 setze, da ich da eh nur kopiert habe:

Code:

	private void machEins(int pos){
		if(this.bits[pos]==1)return;	//Zahl ist schon 1
		if(pos==0){						//Erste Zahl kann einfach geändert werden
			this.bits[pos]=1;
			this.ablauf();				//Schreibt die Änderung auf
			return;
		}
		else{							
			machTauschbar(pos);
			this.bits[pos]=1;		//Jetzt darf ich ändern
			this.ablauf();			//Schreibt die Änderung auf
		}
	}
	private void machNull(int pos){
		if(this.bits[pos]==0)return;	//Zahl ist schon 0
		if(pos==0){	//Erste Zahl kann einfach geändert werden
			this.bits[pos]=0;
			this.ablauf();	//Schreibt die Änderung auf
			return;
		}
		else{
			machTauschbar(pos);
			this.bits[pos]=0;	//Jetzt darf ich ändern
			this.ablauf();	//Schreibt die Änderung auf
		}
	}
	private void machTauschbar(int pos){
		machNull(pos-1);
		for(int i=pos-2;i>=0;i--)machEins(i);
	}

Aber ich mag sowas nicht so gerne und hab lieber zwei "eindeutige" Funktionen wo jeder auf einen Blick weiss was die machen

Lesco · Dez 12, 2008

Das führt aber zu doppeltem Code, was bei Änderungen an diesem Codeabschnitt sehr schnell sehr nervig wird und setzeBit(int pos, int wert) oder so halte ich für ziemlich eindeutig. Außerdem machen derartige Wiederholungen den Code meines Erachtens schlechter les- und wartbar.