Combination Lock

[Jason Menard]

I used to post a bunch of these when this forum first opened, and it's been awhile since my last one, so....

This diversion is pretty simple, along the lines of something you might get in a lower-level computer science class. It does however demonstrate an important concept in computer science.

What you must do is implement a combination lock MyComboLock, using the supplied ComboLock interface and ComboLockDriver driver class. The user sets the lock positioning one "number" at a time. The lock must open when the last sequence of inputs it receives corresponds to the lock's combination.

The combination may be of any length and there is really no limit to what each component of the combination may consist of. A couple examplez of valid combinations are "23 36 84 72" and "aaa dfdf ww vx sdfd wwe gfg". Your implementation should be able to handle pretty much any type of combination.

HINT: Given the combination "23 36 84 72", while of course the lock should open immediaetly after simply entering just the combination in sequence (23,36,84,72), your lock should also open immediately after entering something like the following series of inputs: 23,36,23,36,84,72. I recommend using the above sequence to test that your lock works correctly.

ComboLock.java

package jr.combolock;
 
/**
 * An interface for a combination lock.  The lock consists of two states: 
 * locked and unlocked.  The lock must remain in the locked state until the 
 * correct sequence of positions is set corresponding to the lock's combination.
 */
public interface ComboLock {   
    /**
     * Determine if the lock is currently locked.  The lock will remain locked
     * until setPosition() has been called with the correct sequence 
     * corresponding to this lock's combination.  The lock's initial state 
     * must be locked.
     * @return boolean true if locked, false if unlocked
     */
    public boolean isLocked();
 
    /**
     * Set the combination used to unlock this lock.  Each position of 
     * the combination must be separated by a space.
     * @param combo String the combination used to unlock this lock
     */
    public void setCombo(String combo);
 
    /**
     * Set the current position of the combination.  In order to unlock the 
     * lock, the position must be set in the correct sequence corresponding 
     * to the lock's combination.
     * @param position String the current position of the combination
     */
    public void setPosition(String position);
}

ComboLockDriver.java

package jr.combolock;
 
import java.io.*;
 
public class ComboLockDriver {
    public static void main(String[] args) {
        ComboLock lock = new MyComboLock();
        lock.setCombo("23 36 84 72");
        while (lock.isLocked()) {
            System.out.print("Set Lock Position To: ");
            lock.setPosition(getKeyboard());
        }
        System.out.println("Lock is now unlocked");
    }
    
    private static String getKeyboard() {
        String keyboardIn;
        try {
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            keyboardIn = br.readLine();
        }
        catch (IOException e) {
            keyboardIn = "";
        }
        return keyboardIn;
    }
}

Post your implementation of MyComboLock here. Don't forget to enclose your code in UBB CODE tags, and remember to disable smilies.
[ July 06, 2004: Message edited by: Jason Menard ]

[Ernest Friedman-Hill]

This is not the most elegant solution imaginable, but it does the job. There's nothing in the spec about what to do on various error conditions, so in general this class just does what it can.

package jr.combolock;
import java.util.StringTokenizer;
import java.util.ArrayList;
 
class MyComboLock implements ComboLock {
    private boolean m_isLocked = true;
    private String[] m_combo;
    private int m_ptr;
 
    public boolean isLocked() {
        return m_isLocked;
    }
 
    public void setCombo(String combo) {
        StringTokenizer tokenizer = new StringTokenizer(combo, " ");
        ArrayList tokens = new ArrayList();
        while (tokenizer.hasMoreTokens())
            tokens.add(tokenizer.nextToken());
        int size = tokens.size();
        if (size > 0) {
            m_combo = (String[]) tokens.toArray(new String[size]);
        } else {
            m_combo = null;
        }
        m_ptr = 0;
    }
 
    public void setPosition(String position) {
        if (m_combo == null)
            return;        
 
        else if (m_combo[m_ptr].equals(position)) {
            ++m_ptr;
            if (m_ptr == m_combo.length)
                m_isLocked = false;
 
        } else if (position.equals(m_combo[0]))
            m_ptr = 1;
 
        else
            m_ptr = 0;
    }
}

[ EJFH: Made "m_ptr" private. ]
[ July 06, 2004: Message edited by: Ernest Friedman-Hill ]

[Jason Menard]

Your solution is nearly identical to mine, which I'll post tomorrow. There are only a few minor differences.
[ July 06, 2004: Message edited by: Jason Menard ]

[Philippe Maquet]

A little shorter just for the fun...

package jr.combolock;
 
import java.util.StringTokenizer;
 
public class MyComboLock implements ComboLock {
 
    private String[] comboTokens;
    private int foundPositions;
 
    public boolean isLocked() {
        return comboTokens != null;
    }
 
    public void setCombo(String combo) {
        foundPositions = 0;
        StringTokenizer tokenizer = new StringTokenizer(combo, " ");
        int nTokens = tokenizer.countTokens();
        if (nTokens == 0) {
            comboTokens = null;
        } else {
            comboTokens = new String[nTokens];
            for (int i = 0; i < comboTokens.length; i++) {
                comboTokens[i] = tokenizer.nextToken();
            }
        }
    }
 
    public void setPosition(String position) {
        if (comboTokens != null && comboTokens[foundPositions].equals(position)) {
            if (++foundPositions == comboTokens.length) {
                comboTokens = null;
            }
        }
    }
}

Phil.
[ July 06, 2004: Message edited by: Philippe Maquet ]

[Lasse Koskela]

You call that short?

public class MyComboLock implements ComboLock {
 
private String combo;
 
private StringBuffer sequence = new StringBuffer();
 
public boolean isLocked() {
return !sequence.toString().endsWith(combo);
}
 
public void setCombo(String combo) {
this.combo = combo;
}
 
public void setPosition(String position) {
sequence.append(position);
}
}

(hey, nobody mentioned that the implementation shouldn't be a memory hog...)

[Philippe Maquet]

hey, nobody mentioned that the implementation shouldn't be a memory hog...

Yeah, neither that is must work according to the spec...

your lock should also open immediately after entering something like the following series of inputs: 23,36,23,36,84,72

Phil
[ July 07, 2004: Message edited by: Philippe Maquet ]

[David O'Meara]

Question: can a combination contain repeated values? eg "a b a c"

[Ernest Friedman-Hill]

Originally posted by Philippe Maquet:
A little shorter just for the fun...

 
    public void setPosition(String position) {
        if (comboTokens != null && comboTokens[foundPositions].equals(position)) {
            if (++foundPositions == comboTokens.length) {
                comboTokens = null;
            }
        }
    }

Did you only test on Jason's input? Try another sequence like

23,666,36,666,84,666, 72

You'll find that it (erroneously) unlocks, because nothing resets foundPositions after a non-match.

[Jason Menard]

Here's mine...

MyComboLock.java

package jr.combolock;
 
public class MyComboLock implements ComboLock{
    private String[] comboArray;
    private int currentPos;
 
    public boolean isLocked() {
        if (currentPos == comboArray.length) {
            return false;
        }
        return true;
    }
 
    public void setCombo(String combo) {
        comboArray = combo.split(" ");
    }
 
    public void setPosition(String position) {
        if (comboArray[currentPos].equals(position)) {
            currentPos++;
        } else if (comboArray[0].equals(position)) {
            currentPos = 1;
        } else {
            currentPos = 0;
        }
    }
}

[Ernest Friedman-Hill]

Originally posted by Jason Menard:

    public void setCombo(String combo) {
        comboArray = combo.split(" ");
    }
 

Showoff! I've yet to work a real project that didn't need to maintain JDK 1.3 compatibility.

[Jason Menard]

Originally posted by David O'Meara:
Question: can a combination contain repeated values? eg "a b a c"

Yep.

[Jason Menard]

Originally posted by Ernest Friedman-Hill:
Showoff! I've yet to work a real project that didn't need to maintain JDK 1.3 compatibility.

I however have not been so unfortunate! I would have to point out that as written, your setPosition() is more correct than mine in that you unlock yours there without the chance of an IndexOutOfBoundsException. I don't account for that like I should have. Of course, I also don't use that silly hungarian notation, but I won't hold that against you.

[Ernest Friedman-Hill]

Originally posted by Jason Menard:
I also don't use that silly hungarian notation, but I won't hold that against you.

I've dictated that "m_" wart on my projects for many years; I like to be able to tell at a glance if a variable is a member or not. But come to think of it, it's now been -- well, two years since I used Emacs for programming, and IntelliJ IDEA (/me goes off to look quickly to make sure) knows how to hilight members a different color than non-members, so in fact, I could actually get out of that habit, now.

[Philippe Maquet]

Hi Ernest,

Did you only test on Jason's input? Try another sequence like
23,666,36,666,84,666, 72
You'll find that it (erroneously) unlocks, because nothing resets foundPositions after a non-match.

Well, I didn't try that exact sequence, but well similar ones and ... it works. Here is the output for yours:

Set Lock Position To: 23
Set Lock Position To: 666
Set Lock Position To: 36
Set Lock Position To: 666
Set Lock Position To: 84
Set Lock Position To: 666
Set Lock Position To: 72
Lock is now unlocked

Regards,

Phil.

[Jason Menard]

Doh! Ernest is right, Philippe. I just tried it and it doesn't look like it's working correctly. Given Ernest's input, it should remain locked.
[ July 07, 2004: Message edited by: Jason Menard ]

[Ernest Friedman-Hill]

Hmmm. Phillipe, I don't want to have a big old fight or anything, but I've just tested both versions with this sequence, and yours unlocks, and mine doesn't, given the sequence with the "666"s in it. Are you sure?
[ July 07, 2004: Message edited by: Ernest Friedman-Hill ]

[Philippe Maquet]

Hi Jason and Ernest,

Now I'm with you!

Ernest:
23,666,36,666,84,666, 72

You'll find that it (erroneously) unlocks, because nothing resets foundPositions after a non-match.

I just stopped reading you carefully enough after your "erroneously", that I simply translated by "doesn't work as expected". So I (too) quickly retested my code, which still worked as *I* expected of course...

HINT: Given the combination "23 36 84 72", while of course the lock should open immediaetly after simply entering just the combination in sequence (23,36,84,72), your lock should also open immediately after entering something like the following series of inputs: 23,36,23,36,84,72. I recommend using the above sequence to test that your lock works correctly.

I just misunderstood the specs: in my mind, the "something like" was just an example. In other words, "23 36 anything 84 72" had to unlock. I stand corrected.

Now BTW as we're talking about bugs...

Ernest: only 1, AFAIK:
- set the combo, unlock the lock, reset the combo and ... it will stay unlocked for ever.

Jason: 2 (or 4 - depending on how you count them):
- If you don't call setCombo() before, both setPosition() and isLocked() throw a NullPointerException.
- If you reset the lock (a call to setCombo()) after the first unlock, both isLocked() and setPosition() behaviours become random (because currentPos is not reset).

What I find interesting in such a game - and funny as well - is that from so simple specs, we all come with 4 rather different algorithms and coding styles. Besides I've learned from reading you.

What's next?

Bets regards,

Phil.
[ July 07, 2004: Message edited by: Philippe Maquet ]

[Jason Menard]

Originally posted by Philippe Maquet:
Jason: 2 (or 4 - depending on how you count them):
- If you don't call setCombo() before, both setPosition() and isLocked() throw a NullPointerException.
- If you reset the lock (a call to setCombo()) after the first unlock, both isLocked() and setPosition() behaviours become random (because currentPos is not reset).

You are correct of course. Although I left some wiggle room because the spec stated that it had to work with the ComboLockDriver class, in which case I can be sloppy secure in my knowledge that such a scenario will never arise.

Basically the combination lock is an example of a finite state machine. I used the sequence 23,36,23,36,84,72 as a hint because a common mistake would crop up with that sequence if the programmer didn't take it into account. The common mistake being to reset the position pointer to 0 instead of resetting it to 1 when setPosition("23") was called the second time.

For those who are at least somewhat familiar with automata, here's my poor attempt at an ascii drawing of it with the sample combination.

      ______________________________________
     |       |              |               |
     |       |!("23","36")  |!("23","84")   |!("23","72")
     V       |              |               |
   ->0-"23"->1-----"36"---->2------"84"---->3-----"72"------>4
  |  |       A              |               |
  |__|!"23"  |______________|_______________|
                       "23"            "23"

[ July 07, 2004: Message edited by: Jason Menard ]

[Stefan Wagner]

That's the reason why it matches the Pattern-Matcher pattern:

class MyComboLock implements ComboLock
{
private String position = "", combo= "";
public void setCombo (String c) { combo = c; };
public void setPosition (String p){ position += p; };
 
public boolean isLocked ()
{
String test = ".*\\b" + combo + "\\b.*";
return ! (Pattern.matches (test, position));
};
}

I made the assumption that you have to input the delimiter ' ' as well.
The code would get more easy without it.

I get a performance problem on long sequences of mismatches, but I don't believe you find somebody who will proof it by inserting the sequences by hand.
[ July 09, 2004: Message edited by: Stefan Wagner ]