Daily Challenge #144 - Box Office Clerk

You work as a clerk at a cinema box office and a new movie has been released. There are a lot of people standing in a line waiting to buy a ticket with either 25, 50, or 100 dollar bill. Each ticket for the new movie costs 25 dollars.

If you start with no money in the register, can you sell a ticket to every person in line and give change? You must attend to everyone in order, it would be unfair to sell tickets out of order.

Return YES, if you can sell a ticket to every person and give change.
Otherwise, return NO.

Examples
tickets([25, 25, 50]) => YES
tickets([25, 100]) => NO You will not have enough money to give change to 100 dollars
tickets([25, 25, 50, 50, 100]) => NO You will not have the right bills to give 75 dollars of change (you can't make two bills of 25 from one of 50)

Tests
tickets([25, 25, 50, 50])
tickets([25, 50, 25, 100])

Good luck!

---

This challenge comes from AlexIsHappy on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[Hao]

Using JavaScript:

const changes = {
    25: 0,
    50: 0
};

const procedure = cash => {
    switch (cash) {
        case 25:
            changes[25]++;
            return true;
        case 50:
            if (changes[25] > 0) {
                changes[50]++;
                changes[25]--;
                return true;
            } else {
                return false;
            }
        case 100:
            if (changes[50] > 0 && changes[25] > 0) {
                changes[50]--;
                changes[25]--;
                return true;
            } else if (changes[25] > 2) {
                changes[25] -= 3;
                return true;
            } else {
                return false;
            }
    }
};

const tickets = queue => queue.every(procedure) ? 'YES' : 'NO';

console.log(tickets([25, 25, 50, 50, 100]));    // NO
console.log(tickets([25, 25, 50, 50]));         // YES
console.log(tickets([25, 50, 25, 100]));        // YES

[Avalander]

Scala

object BoxOffice {
  sealed trait Answer
  object Yes extends Answer
  object No extends Answer

  type Register = Map[Int, Int]

  @tailrec
  def tickets (xs: Seq[Int], register: Register = Map()): Answer =
    xs match {
      case Nil => Yes
      case x :: rest =>
        x match {
          case 25  => tickets(rest, register add 25)
          case 50  =>
            if (register.hasItem(25)) tickets(rest, register remove 25 add 50)
            else No
          case 100 =>
            if (register.hasItem(50) && register.hasItem(25))
              tickets(rest, register remove 50 remove 25 add 100)
            else if (register.hasItem(25, 3))
              tickets(rest, register.remove(25, 3) add 100)
            else No
          case x   => throw new MatchError(s"Can't handle currency $x")
        }
    }

  implicit class ExtRegister(r: Register) {
    def hasItem (key: Int, amount: Int = 1): Boolean =
      (r get key) match {
        case None        => false
        case Some(value) => value >= amount
      }

    def add (item: Int, amount: Int = 1): Register = {
      val prev = r.getOrElse(item, 0)
      r.updated(item, prev + amount)
    }

    def remove(item: Int, amount: Int = 1): Register = {
      val prev = r.getOrElse(item, 0)
      r.updated(item, prev - amount)
    }
  }
}

And the tests:

class BoxOfficeTest extends FunSuite {
  test("tickets") {
    assert(tickets(List(25, 25, 50)) == Yes)
    assert(tickets(List(25, 100)) == No)
    assert(tickets(List(25, 25, 50, 50, 100)) == No)
    assert(tickets(List(25, 25, 50, 50)) == Yes)
    assert(tickets(List(25, 50, 25, 100)) == Yes)
  }
}

[Idan Arye]

Rust:

fn tickets(bills: &[usize]) -> Result<bool, String> {
    let mut change_25 = 0usize;
    let mut change_50 = 0usize;

    for bill in bills {
        match bill {
            25 => {
                change_25 += 1;
            }
            50 => {
                if 1 <= change_25 {
                    change_25 -= 1;
                    change_50 += 1;
                } else {
                    return Ok(false);
                }
            }
            100 => {
                if 1 <= change_25 && 1 <= change_50 {
                    change_25 -= 1;
                    change_50 -= 1;
                } else if 3 <= change_25 {
                    change_25 -= 3;
                } else {
                    return Ok(false);
                }
            }
            _ => {
                return Err(format!("Expected a 25, 50 or 100 bill - got {}", bill));
            }
        }
    }

    Ok(true)
}

fn main() {
    assert!(tickets(&[25, 25, 50]) == Ok(true));
    assert!(tickets(&[25, 100]) == Ok(false));
    assert!(tickets(&[25, 25, 50, 50, 100]) == Ok(false));
    assert!(tickets(&[25, 25, 50, 50]) == Ok(true));
    assert!(tickets(&[25, 50, 25, 100]) == Ok(true));
}

[Sabin Pandelovitch]

Another JS approach

const tickets = bills => {
  let status = "YES";

  const register = bills.reduce(
    (acc, val) => {
      acc[val] += 1;
      return acc;
    },
    { 25: 0, 50: 0, 100: 0 }
  );

  const removeFromRegister = bills =>
    bills.forEach(bill => (register[bill] -= 1));

  bills.forEach(bill => {
    if (bill === 100) removeFromRegister([50, 25]);
    if (bill === 50) removeFromRegister([25]);
  });

  Object.values(register).forEach(item => {
    if (item < 0) status = "NO";
  });

  return status;
};

console.log(tickets([25, 25, 50, 50, 100])); //NO

CondeSandbox

[Rafael Acioly]

Python solution 🐍

from typing import List

TICKET_VALUE = 25

def tickets(values: List[int]) -> str:
  register = 0

  for amount in values:
    change = amount - TICKET_VALUE
    if register < change:
      return "NO"
    register += TICKET_VALUE

  return "YES"

[Siddharth Venkatesan]

using Ruby:

def tickets(queue)
  tillbox = []
  can_process = true
  change = { 25 => [], 50 => [25],  100 => [25,50] } 

  queue.each do |bill|
    # if tillbox has the change required
    if (tillbox & change[bill] == change[bill])
      tillbox << bill
      change[bill].each { |b| tillbox.delete_at(tillbox.index(b)) }
    else 
      can_process = false
      break
    end
  end
  can_process
end

puts tickets([25, 25, 50, 50]) #true
puts tickets([25, 50, 25, 100]) #false

[Craig McIlwrath]

Haskell:

import Control.Monad (foldM) 
import Data.Maybe (isJust)

data CashBox = CashBox { v25 :: Int, v50 :: Int }

emptyBox :: CashBox
emptyBox = CashBox 0 0

add25s :: Int -> CashBox -> CashBox 
add25s n (CashBox x y) = CashBox (x + n) y 
add25 :: CashBox -> CashBox
add25 = add25s 1
take25s :: Int -> CashBox -> CashBox 
take25s n = add25s (-n)
take25 :: CashBox -> CashBox 
take25 = take25s 1
add50s :: Int -> CashBox -> CashBox 
add50s n (CashBox x y) = CashBox x (y + 1)
add50 :: CashBox -> CashBox
add50 = add50s 1
take50s :: Int -> CashBox -> CashBox 
take50s n = add50s (-n)
take50 :: CashBox -> CashBox 
take50 = take50s 1

makeChange :: Int -> CashBox -> Maybe CashBox
makeChange 25  c = Just $ add25 c
makeChange 50  c = if v25 c > 0
                   then Just $ add50 $ take25 c
                   else Nothing
makeChange 100 c = case v50 c of
                     0 -> if v25 c > 2 then Just (take25s 3 c) else Nothing
                     _ -> if v25 c > 0 then Just (take25 (take50 c)) else Nothing
makeChange _   _ = Nothing

tickets :: [Int] -> Bool
tickets = isJust . foldM (flip makeChange) emptyBox

I think all my utility add and take kinda obscure the code a bit. Oh well. Also I'm flipping makeChange because I realized after that foldM applies the arguments in the other order, and I was too lazy to rewrite :P

[erezwanderman]

Typescript:

const tickets = (bills: number[]) => {
  return bills.reduce(
    (prev, curr) => {
      if (curr == 25) return [[prev[0][0] + 1, prev[0][1]], prev[1]];
      if (curr == 50 && prev[0][0] === 0) return [prev[0], 'NO'];
      if (curr == 50) return [[prev[0][0] - 1, prev[0][1] + 1], prev[1]];
      if (prev[0][1] >= 1 && prev[0][0] >= 1) return [[prev[0][0] - 1, prev[0][1] - 1], prev[1]];
      if (prev[0][1] >= 3) return [[prev[0][0] - 3, prev[0][1]], prev[1]];
      return [prev[0], 'NO'];
    },
    <[[number, number], string]>[[0, 0], 'YES']
  )[1];
}

const testCases = [
  [25, 25, 50],
  [25, 100],
  [25, 25, 50, 50, 100],
  [25, 25, 50, 50],
  [25, 50, 25, 100]
];
for (const testCase of testCases) {
  console.log(testCase, '=>', tickets(testCase))
}