Search Posts

Counting Google sheep in Oracle PL/SQL

It’s 2 AM and I can’t sleep. Might be related to the fact that yesterday I celebrated International Cofee Day a bit.. too much 🙂

I guess it’s time to count sheep. Back in 2016, Google thought we need help on this matter so they raised a “Problem A. Counting Sheep” on one of that year’s Code Jam Qualification Round.

I think it’s fun to solve it via Oracle PL/SQL since they get along so well and might get the job done eventually (the sleep job that is).

Below is the problem details, as it can be found linked here as well:

Bleatrix Trotter the sheep has devised a strategy that helps her fall asleep faster. First, she picks a number N. Then she starts naming N, 2 × N, 3 × N, and so on. Whenever she names a number, she thinks about all of the digits in that number. She keeps track of which digits (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) she has seen at least once so far as part of any number she has named. Once she has seen each of the ten digits at least once, she will fall asleep.

Bleatrix must start with N and must always name (i + 1) × N directly after i × N. For example, suppose that Bleatrix picks N = 1692. She would count as follows:

  • N = 1692. Now she has seen the digits 1, 2, 6, and 9.
  • 2N = 3384. Now she has seen the digits 1, 2, 3, 4, 6, 8, and 9.
  • 3N = 5076. Now she has seen all ten digits, and falls asleep.

What is the last number that she will name before falling asleep? If she will count forever, print INSOMNIA instead.

Input

The first line of the input gives the number of test cases, TT test cases follow. Each consists of one line with a single integer N, the number Bleatrix has chosen.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the last number that Bleatrix will name before falling asleep, according to the rules described in the statement.

Limits

1 ≤ T ≤ 100.

Small dataset

0 ≤ N ≤ 200.

Large dataset

0 ≤ N ≤ 106.

Here is how I did it via PL/SQL

What do I need?

  • A new directory (created one directly on my D drive, CountSheep)
  • A mechanism to read the input files (test cases numbers): A-small-practice.in or A-large-practice.in – these can be found here
  • A table to temporary hold the “working” numbers as we move along
  • A cursor for iterating through the numbers
  • More looping – loop-inception
  • Output to file

Getting hands dirty

The below code / solution plus the input and output files are also available on GitHub at this location.

set serveroutput on;
-- drop table hr.test_cases;

-- creating a table to hold the input test cases numbers
create table hr.test_cases (
  idx number(4) primary key,
  in_n number(12)
);

-- select * from hr.test_cases;

-- drop sequence hr.tc_idx_seq  

-- in order to fave full control over the ordering of the numbers present in the file 
-- let's create a sequence that will populate the PK (idx) column
-- very important: first line of the input file gives the number of tests so in the input files this is 100 

create sequence hr.tc_idx_seq  
minvalue 0
start with 0
increment by 1;

-- creating support for loading the input file and reading it later
create or replace directory MY_DIR AS 'D:\CountSheep'; 
-- we are just playing here
grant read on directory MY_DIR TO PUBLIC;

-- clean up table (added for several iterations of debugging script)
truncate table hr.test_cases;

-- 1. Read input file and insert its content into the working table
declare
  in_n number(12);
  input_file UTL_FILE.FILE_TYPE; 
begin
  -- storin' the file
  input_file := UTL_FILE.FOPEN('MY_DIR','A-small-practice.in','R'); 
  loop
    begin
      UTL_FILE.GET_LINE(input_file,in_n); 
      -- make sure tests table is clean
      insert into HR.TEST_CASES(idx, in_n) values (hr.tc_idx_seq.nextval, in_n);
      
      exception when No_Data_Found then exit; 
    end;
  end loop;

  -- closing the file from memory, after a quick check
  if UTL_FILE.IS_OPEN(input_file) then
    dbms_output.put_line('File is Open! Closing it soon..');
  end if;

  UTL_FILE.FCLOSE(input_file); 
end; 
/
-- set serveroutput off;
-- select * from hr.test_cases;
-- 2. Get number of tests from the first line of the input file.

declare
  tests_number number; 
  cursor c_numbers is 
        select idx, in_n 
        from hr.test_cases
        where idx != (select min(idx) from hr.test_cases);    
  idx number := 0;      
  crt_idx number;
  curr_number number; 
  last_seen_number number(20);
  zero2nine varchar2(10);
  output_file UTL_FILE.FILE_TYPE;
  output_filename varchar2(30) := 'A-small-practice.out';
  
begin
  DBMS_OUTPUT.ENABLE (buffer_size => NULL);
  output_file := UTL_FILE.FOPEN('MY_DIR', output_filename, 'W');

  select tc.in_n into tests_number
  from hr.test_cases tc
  where tc.idx = (select min(idx) from hr.test_cases);
  
  -- check if T (number of test cases is in the renge 1 <= T <= 100)
  if (tests_number < 0 or tests_number > 100) then  
    dbms_output.put_line('Number of test cases (' || to_char(tests_number) || ') is not in the required range 1 ? T ? 100. Exiting.. ');
    return;
  end if;
  dbms_output.put_line('Number of tests in the input file is: ' || to_char(tests_number));

  open c_numbers;
  loop   
    fetch c_numbers into crt_idx, curr_number;
    exit when c_numbers%notfound;
      -- loop for N, N*2, N*3.. and check if all numbers are there
      zero2nine := '0123456789'; -- order of string elements not relly important
      idx :=  idx + 1;
      --dbms_output.put_line(curr_number);
      for i in 1..99999
      loop
        -- dbms_output.put_line('i is :' || to_char(i)); 
        last_seen_number := curr_number*i;
        -- dbms_output.put_line('last_seen_number is :' || to_char(last_seen_number));
        -- if the input number is either zero or last entry in the file then exit --> INSOMNIA
        if (coalesce(last_seen_number, 0) = 0) then
          --dbms_output.put_line('Case #' || to_char(idx) || ': INSOMNIA');
          utl_file.put_line(output_file, 'Case #' || to_char(idx) || ': INSOMNIA');
          exit;
        end if;  
        
        for j in 0..9 
        loop
          -- dbms_output.put_line('zero2nine is :' || to_char(zero2nine)); 
          -- if the current digit is in the zero2nine variable then trim this
          if (instr(to_char(last_seen_number), to_char(j)) > 0) then
            zero2nine := REPLACE(zero2nine,to_char(j),'');
          end if;
        end loop;
        if (length(zero2nine) is null) then
          --dbms_output.put_line('Case #' || to_char(idx) || ': ' || to_char(last_seen_number));
          utl_file.put_line(output_file, 'Case #' || to_char(idx) || ': ' || to_char(last_seen_number));
          exit;
        end if;
      end loop;    
  end loop;
  close c_numbers;
  utl_file.fclose(output_file);
end;
/

Output of the files of the files look as expected. Sample below

count sheep output

 

Zzzzzzz..

Leave a Reply

Your email address will not be published. Required fields are marked *