Problem of the Day -- Bank Password

Bank Password

Today's problem comes from a thread over on /r/theydidthemath.

The problem goes like this. A user is asked to create a password that is 7 digits where none of the numbers can repeat. In addition to this requirement none of the numbers can be in a direct sequence (6 and 7, 7 and 6, or 9 and 0). Create a program to generate a random password for this bank that fits their rule set.

Permalink: http://problemotd.com/problem/bank-password/

Comments:

Emre Ozdemir - 10 years, 7 months ago

I'm guessing 7 and 7 or 5 and 5 is allowed. This is my solution in C++.

#include <iostream> 
#include <ctime>
using namespace std; 

int main(){

    srand(time(NULL));
    int k[7];
    int i;

    for(i=0;i<=6;i++)
    {
            k[i]=rand()%9+1;
            if(k[i]-1==k[i-1] || k[i]+1==k[i-1])
                k[i]=rand()%9+1;

            cout<<k[i];
    }

    getchar();
    getchar();
}

reply permalink

Opetion - 10 years, 7 months ago
Not that I have solved it. but I don't think your solution will work. you are using only once the random so it might get exactly the same number. and it wont satisfy the " a password that is 7 digits where none of the numbers can repeat. " :)

reply permalink

Emre Ozdemir - 10 years, 7 months ago

Yes, I must have missed that. I also realized I didn't include 0. So this is updated version.

#include <iostream> 
#include <ctime>
#include <cmath>
using namespace std; 

int main(){

    srand(time(NULL));
    int k[7];
    int i, x, y;

    for(i=0;i<7;i++)
    {
        k[i]=rand()%10;

        for(x=0;x<i;x++)
        {
LOOP:       
            y=k[i]-k[i-1];
            if(k[i]==k[x] || abs(y)==1)
            {
                x=0;
                k[i]=rand()%10;
                goto LOOP;
            }
        }           
            cout<<k[i];
    }
    getchar();
    getchar();
}

reply permalink

Andreas - 10 years, 7 months ago

first time commenting, hope the formatting works out alright. this is written in scala

object ProblemOTD extends App {

  case class Number(value: Int) {
    def hasValidSuccessor(that: Number) : Boolean = {
      (value + 1) % 10       != that.value &&
     ((value - 1) + 10) % 10 != that.value
    }
  }

  def getPassword : String = {
    var numbers = (0 to 9) map Number

    val random = new java.util.Random

    val firstNumber = numbers(random.nextInt(10))
    var lastNumber = firstNumber

    numbers = numbers filter (_ != firstNumber)

    var resList = firstNumber :: Nil

    while (resList.size < 7) {
      val nextNumber = numbers(random.nextInt(numbers.size))

      if (lastNumber.hasValidSuccessor(nextNumber)) {
        resList = nextNumber :: resList
        numbers = numbers filter (_ != nextNumber)
        lastNumber = nextNumber
      }
    }

    resList.reverse.foldLeft("")(_ + _.value.toString)
  }

  println(getPassword)
}

reply permalink

Max Burstein - 10 years, 7 months ago

Awesome! Thanks for commenting

reply permalink

duddles - 10 years, 7 months ago

It gives me an error when I try to login... here is my python attempt:

def bank_password():
    password_length = 7
    l = range(10)
    password = []
    last_digit = 99

    while len(password) < 7:
        available = list(l)
        if last_digit - 1 in available:
            available.remove(last_digit-1)
        if last_digit + 1 in available:
            available.remove(last_digit+1)
        if last_digit == 0 and 9 in available:
            available.remove(9)
        if last_digit == 9 and 0 in available:
            available.remove(0)
        last_digit = random.choice(available)
        l.remove(last_digit)
        password.append(str(last_digit))
    print ''.join(password)

reply permalink

Max Burstein - 10 years, 7 months ago

I think I know what the issue is. I will look in to getting this fixed when I get home later tonight. Sorry for the inconvenience.

reply permalink
Max Burstein - 10 years, 7 months ago

Should be good to go

reply permalink

Ethan Glover - 10 years, 7 months ago

I'm not sure why I'm not getting consistent passwords. I'll run the program 10 times and there's always a couple with either two of the same number or a sequence. Help is appreciated. :) (Java)

public static void newPass() {
    int[] pass = new int[7];
    Random rand = new Random();

    // Fill original password
    for(int i = 0; i < pass.length; i++)
        pass[i] = rand.nextInt(9);

    // Compare each element to rest of list
    for(int i = 0; i < pass.length; i++)
        pass = compare(i, pass);

    // Print pass
    for(int i = 0; i < pass.length; i++)
        System.out.print(pass[i] + " ");
}

public static int[] compare(int n, int[] list) {
    // Compare list w/ n
    Random rand = new Random();

    int i = 0;
    while(i < list.length) {
        // Check if list[n] == list[i], skip if same element
        if(list[i] == list[n] && i != n) {
            list[i] = rand.nextInt(10);
            i = 0;
        // Check for sequence
        } else if(list[i] == list[i] + 1 || list[i] == list[i] - 1) {
            list[i] = rand.nextInt(10);
            i = 0;
        // Increment if both good
        } else {
            i++;
        }
    }

    return list;
}

reply permalink

Max Burstein - 10 years, 7 months ago

In the first if of the compare function you don't check if the newly generated number has already been used or not. I think one approach that may be helpful is to have a list 0-9 and then randomly select from there. Once you use a number remove it from the list.

reply permalink
Ethan - 10 years, 7 months ago
Sounds like a good idea. :) Thanks!

reply permalink

Pearce Keesling - 10 years, 7 months ago

Normally I do these in C, but I felt like doing this one in ruby. If I feel inspired I'll probably rewrite in C.

#!/usr/bin/env ruby

pass = [rand(9)]
6.times do
    allowed = (1..9).to_a - [pass, (pass.last+1)].flatten
    buff = allowed[rand(allowed.size)]
    pass << buff
end
puts pass.join

reply permalink

Pearce Keesling - 10 years, 7 months ago

I guess I was able to find the motivation :)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int contains(int pass[7], int num)
{
    for(int i= 0;i < 7;i++)
        if(num==pass[i])return 0;
    return 1;
}

int main()
{
    srand(time(NULL));
    int pass[7] = {rand()%9 + 1};
    for(int* digit = pass; digit < pass+7;digit++)
    {
        int allowed[7]={0};
        int* a = allowed;
        for(int i =0 ; i < 9;i++)
        {
            if(!contains(pass, i))continue;
            if(*(digit-1)+1!=i)*(a++)=i;
        }
        *digit = allowed[rand()%(a-allowed)];
    }
    for(int i = 0; i < 7;i++)
        printf("%i",pass[i]);
    puts("");

    return 0;
}

reply permalink

Nick Krichevsky - 10 years, 7 months ago

A bit late ... but meh.

from random import randint
password=""
for i in range(7):
    while True:
        num=randint(0,9)
        if len(password) is 0:
            password+=str(num)
        if str(num) not in password:
            prevNum=password[-1]
            if (prevNum is not num-1 and prevNum is not num+1) and (num is not 0 and prevNum is not 9) and (num is not 9 and prevNum is not 0):
                password+=str(num)
                break
print password

reply permalink

Anonymous - 10 years, 7 months ago

A complete solution in Clojure.

(defn remove-neighbours [digits n]
  (if (nil? n)
    digits
    (remove #{(mod (dec n) 10) (mod (inc n) 10)} digits)))

(defn bank-password []
  (loop [ret [] digits (range 10) i 7]
    (if (zero? i)
      (apply str ret)
      (let [choices (remove-neighbours digits (last ret))
            digit (nth choices (rand-int (count choices)))]
        (recur (conj ret digit) (remove #{digit} digits) (dec i))))))

(bank-password)  ; => "2508174"

reply permalink

Anonymous - 10 years, 6 months ago

#python 2.7
import random
password = [random.randint(0,9)]
i = 0

choices = range(0,10)
while i < 6:
    exclusions = password + [(password[i] - 1)] + [(password[i] + 1)]
    nextnumberchoices = [x for x in choices if x not in exclusions]
    next = random.choice(nextnumberchoices)
    password.append(next)
    i = i + 1

print "".join(str(x) for x in password)

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

Bank Password

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri