Monthly Archives: January 2022

Google Hash Code 2022 – Practice Problem 1

18 January 2022 in Google / Hash Code tagged competition / google / hash / hash code / programming / Programming Competition by Tux

One Pizza

Problem

A picture of menu with six ingredients to choose from and a 'What do you like on pizza?' text.

You are opening a small pizzeria. In fact, your pizzeria is so small that you decided to offer only one type of pizza. Now you need to decide what ingredients to include (peppers? tomatoes? both?).

Everyone has their pizza preferences. Each of your potential clients has some ingredients they like and maybe some ingredients they dislike. Each client will come to your pizzeria if both conditions are true:

all the ingredients they like are on the pizza, and
none of the ingredients they dislike are on the pizza

Each client is OK with additional ingredients they neither like nor dislike being present on the pizza. Your task is to choose which ingredients to put on your only pizza type to maximize the number of clients that will visit your pizzeria.

Input

The first line contains one integer 1≤C≤10⁵ the number of potential clients.
The following 2×C lines describe the clients’ preferences in the following format:
- First line contains integer 1≤L≤5, followed by L names of ingredients a client likes, delimited by spaces.
- Second line contains integer 0≤D≤5, followed by D names of ingredients a client dislikes, delimited by spaces.

Each ingredient name consists of between 1 and 15 ASCII characters. Each character is one of the lowercase letters (a-z) or a digit (0-9).

Input Data

Full Input (zipped)Download

Submission

The submission should consist of one line consisting of a single number 0≤N followed by a list of N ingredients to put on the only pizza available in the pizzeria, separated by spaces. The list of ingredients should contain only the ingredients mentioned by at least one client, without duplicates.

Scoring

A solution scores one point for each client that will come to your pizzeria. A client will come to your pizzeria if all the ingredients they like are on the pizza and none of the ingredients they dislike are on the pizza.

Sample

Sample Input

3
2 cheese peppers
0
1 basil
1 pineapple
2 mushrooms tomatoes
1 basil

Sample Output

4 cheese mushrooms tomatoes peppers

In the Sample Input, there are 3 potential clients:

The first client likes 2 ingredients, cheese and peppers, and does not dislike anything.
The second client likes only basil and dislikes only pineapple.
The third client likes mushrooms and tomatoes and dislikes only basil

The picture below shows the preferences of 3 potential clients.

Three 'Vote for your pizza' cards with some ingredients marked as likes and some marked with dislikes.

In this particular Sample Output, we choose to use 4 ingredients in the pizza: cheese, mushrooms, tomatoes, and peppers.

The pizza corresponding to the sample output. It contains cheese, mushrooms, tomatoes, and peppers.

The first client likes the pizza because it contains both cheese and peppers, which they like.
The second client does not like the pizza: it does not contain basil which they like.
The third client likes the pizza because it contains mushrooms and tomatoes, which they like, and does not contain basil which they do not like.

This means submission of this output would score 2 points for this case because two clients (the first and third ones) would like this pizza.

—

Past editions

— From https://codingcompetitions.withgoogle.com/hashcode/archive

Hash Code started in 2014 with just 200 participants from France. In 2020, more than 100,000 participants from across Europe, the Middle East, and Africa took part in the competition. You can take a look at the problems and winning teams from past editions of Hash Code below.

Past problem statements

Software engineering at scale

Hash Code 2021, Final Round
[download id=”10690″]
Google stores the vast majority of its code in one monolithic codebase, holding billions of lines of code. As of 2016, more than 25,000 software engineers were contributing to it, improving existing services and adding cool new features to meet the demands of their users.

Traffic Signaling

Hash Code 2021, Online Qualification Round
[download id=”6058″]
Given the description of a city plan and planned paths for all cars in that city, optimize the schedule of traffic lights to minimize the total amount of time spent in traffic and help as many cars as possible reach their destination before a given deadline.

Assembling smartphones

Hash Code 2020, Final Round
[download id=”5932″]
In this problem statement, we will explore the idea of operating an automated assembly line for smartphones.
Building a smartphone is a complex process that involves assembling numerous components, including the screen, multiple cameras, microphones, speakers, a processing unit, and a storage unit.
To automate the building of a smartphone, we will be using robotic arms that can move around the assembly workspace, performing all necessary tasks.

Book scanning

Hash Code 2020, Online Qualification Round
[download id=”5929″]
Books allow us to discover fantasy worlds and better understand the world we live in. They enable us to learn about everything from photography to compilers… and of course, a good book is a great way to relax!
Google Books is a project that embraces the value books bring to our daily lives. It aspires to bring the world’s books online and make them accessible to everyone. In the last 15 years, Google Books has collected digital copies of 40 million books in more than 400 languages, partly by scanning books from libraries and publishers all around the world.
In this competition problem, we will explore the challenges of setting up a scanning process for millions of books stored in libraries around the world and having them scanned at a scanning facility.

Compiling Google

Hash Code 2019, Final Round
[download id=”5927″]
Google has a large codebase, containing billions of lines of code across millions of source files. From these source files, many more compiled files are produced, and some compiled files are then used to produce further compiled files, and so on.
Given then huge number of files, compiling them on a single server would take a long time. To speed it up, Google distributes the compilation steps across multiple servers.
In this problem, we will explore how to effectively use multiple compilation servers to optimize compilation time.

Photo slideshow

Hash Code 2019, Online Qualification Round
[download id=”5925″]
As the saying goes, “a picture is worth a thousand words.” We agree – photos are an important part of contemporary digital and cultural life. Approximately 2.5 billion people around the world carry a camera – in the form of a smart phone – in their pocket every day. We tend to make good use of it, too, taking more photos than ever (back in 2017, Google Photos announced it was backing up more than 1.2 billion photos and videos per day).
The rise of digital photography creates an interesting challenge: what should we do with all of these photos? In this competition problem, we will explore the idea of composing a slideshow out of a photo collection.

City Plan

Hash Code 2018, Final Round
[download id=”5921″]
The population of the world is growing and becoming increasingly concentrated in cities. According to the World Bank, global urbanization (the percentage of the world’s population that lives in cities) crossed 50% in 2008 and reached 54% in 2016.
The growth of urban areas creates interesting architectural challenges. How can city planners make efficient use of urban space? How should residential needs be balanced with access to public utilities, such as schools and parks?

Self-driving rides

Hash Code 2018, Online Qualification Round
[download id=”5917″]
Millions of people commute by car every day; for example, to school or to their workplace.
Self-driving vehicles are an exciting development for transportation. They aim to make traveling by car safer and more available while also saving commuters time.
In this competition problem, we’ll be looking at how a fleet of self-driving vehicles can efficiently get commuters to their destinations in a simulated city.

Router placement

Hash Code 2017, Final Round
[download id=”4175″]
Who doesn’t love wireless Internet? Millions of people rely on it for productivity and fun in countless cafes, railway stations and public areas of all sorts. For many institutions, ensuring wireless Internet access is now almost as important a feature of building facilities as the access to water and electricity. Typically, buildings are connected to the Internet using a fiber backbone. In order to provide wireless Internet access, wireless routers are placed around the building and connected using fiber cables to the backbone. The larger and more complex the building, the harder it is to pick router locations and decide how to lay down the connecting cables.

Streaming videos

Hash Code 2017, Online Qualification Round
[download id=”4178″]
Have you ever wondered what happens behind the scenes when you watch a YouTube video? As more and more people watch online videos (and as the size of these videos increases), it is critical that video-serving infrastructure is optimized to handle requests reliably and quickly. This typically involves putting in place cache servers, which store copies of popular videos. When a user request for a particular video arrives, it can be handled by a cache server close to the user, rather than by a remote data center thousands of kilometers away. Given a description of cache servers, network endpoints and videos, along with predicted requests for individual videos, decide which videos to put in which cache server in order to minimize the average waiting time for all requests.

Schedule Satellite Operations

Hash Code 2016, Final Round
[download id= “2596”]A satellite equipped with a high-resolution camera can be an excellent source of geo imagery. While harder to deploy than a plane or a Street View car, a satellite — once launched — provides a continuous stream of fresh data. Terra Bella is a division within Google that deploys and manages high-resolution imaging satellites in order to capture rapidly-updated imagery and analyze them for commercial customers. With a growing constellation of satellites and a constant need for fresh imagery, distributing the work between the satellites is a major challenge. Given a set of imaging satellites and a list of image collections ordered by customers, schedule satellite operations so that the total value of delivered image collections is as high as possible.

Optimize Drone Deliveries

Hash Code 2016, Online Qualification Round
[download id=”2595″]
The Internet has profoundly changed the way we buy things, but the online shopping of today is likely not the end of that change; after each purchase we still need to wait multiple days for physical goods to be carried to our doorstep. Given a fleet of drones, a list of customer orders and availability of the individual products in warehouses, schedule the drone operations so that the orders are completed as soon as possible.

Route Loon Balloons

Hash Code 2015, Final Round
[download id=”2594″]
Project Loon aims to bring universal Internet access using a fleet of high altitude balloons equipped with LTE transmitters. Circulating around the world, Loon balloons deliver Internet access in areas that lack conventional means of Internet connectivity. Given the wind data at different altitudes, plan altitude adjustments for a fleet of balloons to provide Internet coverage to select locations.

Optimize a Data Center

Hash Code 2015, Online Qualification Round
[download id=”2593″]
For over ten years, Google has been building data centers of its own design, deploying thousands of machines in locations around the globe. In each of these of locations, batteries of servers are at work around the clock, running services we use every day, from Google Search and YouTube to the Judge System of Hash Code. Given a schema of a data center and a list of available servers, your task is to optimize the layout of the data center to maximize its availability.

Street View Routing

Hash Code 2014, Final Round
[download id=”2592″]
The Street View imagery available in Google Maps is captured using specialized vehicles called Street View cars. These cars carry multiple cameras capturing pictures as the car moves around a city. Capturing the imagery of a city poses an optimization problem: the fleet of cars is available for a limited amount of time and we want to cover as much of the city streets as possible.

Google Hash Code 2022 Nicosia Cyprus – Call for participation

12 January 2022 in Google / Hash Code tagged code / cyprus / google / hash / hash code by Tux

We’ll be hosting a hub at the University of Cyprus for the Online Qualification Round of Hash Code, a team-based programming competition created by Google for university students and industry professionals. The Online Qualification Round takes place on the 24th of February at 19:30 EET and registered teams from Cyprus are invited to participate from our hub, which will take place at the Computer Science Department. Top scoring teams from the Online Qualification Round will then be invited to Google’s office to compete in the Final Round of the competition in April.

If you’re interested in joining our hub, find a team (two to four people) and register at g.co/hashcode. Make sure to select the University of Cyprus from the list of hubs in the Judge System.

Address:

Rooms: 101, 102, 103
Department of Computer Science,
Pure and Applied Sciences (FST-01)
University of Cyprus
1 University Avenue
2109 Aglantzia, CYPRUS

Date and Time:

24th February 2022
From: 19:30 EET
To: 23:30 EET

Free Amenities Offered

High speed Internet access
Wi-Fi access to the Internet for your mobile devices (personal computers and smart phones)
Lab computers will be available for use by the participants
Food in the form of snacks and beverages will be available outside the labs

Symfony 5 skeleton project on Ubuntu

7 January 2022 in PHP tagged asset / check:req / composer / curl / Encore / flex / git / gzip / mb_strlen / npm / php / php-cli / php-intl / php-mbstring / php-mysql / php-xml / PhpStorm / serve / server / symfony / twig / ubuntu / Webpack / Webpack Encore / yarn by Tux

This guide will present the steps we followed on a GNU/Linux Ubuntu 20.04LTS to create a new project out of the Symfony 5 website skeleton.

Install core dependecies

First of all, we need to install all dependencies that we will need for sure.

sudo apt install curl gzip git php-cli php-xml php-mbstring php-intl php-mysql p7zip-full;

We chose to install the php-cli package instead of the php as we do not need to install all the additional dependencies php has, like apache2. Since we are working on a development computer, we can skip the required packages for deployment.

We decided to use MySQL in our project, so we installed the php-mysql package that provides the PDO for that database technology.

php-intl and php-mbstring were installed to suppress the following warnings:

Optional recommendations to improve your setup
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 * mb_strlen() should be available
   > Install and enable the mbstring extension.

 * intl extension should be available
   > Install and enable the intl extension (used for validators).

Downloading and installing symfony

Since Symfony version 5, there is a new support application for the development of Symfony projects. Using the following commands:

we downloaded it from the official website,
installed it to our home folder,
and then moved it to /user/local/bin/symfony to be accessible from any terminal without changing the path each time.

wget https://get.symfony.com/cli/installer -O - | bash;
sudo mv ~/.symfony/bin/symfony /usr/local/bin/symfony;

In case you do not want to move the binary to /usr/local/bin you can either use it as a local file:

~/.symfony/bin/symfony;

or add it to your $PATH variable:

export PATH="$HOME/.symfony/bin:$PATH";

Creating a new project and making sure dependencies are met

After the above steps are done, we can clone the Symfony 5 skeleton and then use the symfony support application to check that our system has all the needed features.

symfony new symfony_project;
cd symfony_project;
symfony check:req;

If everything is OK, you should get a message similar to the one below:

$ symfony check:req

Symfony Requirements Checker
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

> PHP is using the following php.ini file:
/etc/php/7.4/cli/php.ini

> Checking Symfony requirements:

...................................

                                              
 [OK]                                         
 Your system is ready to run Symfony projects 
                                              

Note  The command console can use a different php.ini file
~~~~  than the one used by your web server.
      Please check that both the console and the web server
      are using the same PHP version and configuration.

Starting a minimal web server to see the skeleton application

Using PHP’s built-in server, we can execute the skeleton application and see the result in our browser:

php -S 127.0.0.1:8000 -t public/;

Starting the Symfony minimal web server to see the skeleton application

Another option to check out your application is using the Symfony built-in web server, which is richer in features than the PHP server but lighter than Apache or Nginx. Below we present how to start it as an application in a terminal and how to start it as a detached service (leaving your terminal free for other operations).

#If you start it as it as an application, you will need to press Ctrl + C to kill it.
symfony serve;

Starting Symfony server as a detached service:

symfony serve -d;
#To stop it, use the following
symfony server:stop;
#Please note that the command contains the word server and not serve like before.

Adding more features to our project

To make our project more dynamic and versatile, we need to install a few packages using composer. Composer is a PHP utility for managing dependencies. It allows you to indicate the libraries your project relies on, and it will take care of installing and updating them. To fast install it, open a terminal and type the following command:

curl -Ss getcomposer.org/installer | php;
# Moving the composer into the /usr/local/bin/ folder will allow us to access it from any folder later on as that folder is in the default PATH variable. You could again avoid this step but it makes the process more user friendly.
sudo mv composer.phar /usr/local/bin/composer;

Allowing code annotations in our PHP code

After the composer is successfully installed, we can install the annotations package, which among other features, will allow us to define routes inside our PHP controller files.

composer require annotations;

A code example of that is the following:

<?php


namespace App\Controller;

use Symfony\Bundle\FrameworkBundle\Controller\AbstractController;
use Symfony\Component\HttpFoundation\Response;
use Symfony\Component\Routing\Annotation\Route;

class QuestionController extends AbstractController
{
    /**
     * @Route("/", name="app_homepage")
     */
    public function homepage()
    {
        return new Response('Done');
    }

    /**
     * @Route("/questions/{slug}", name="app_question_show")
     */
    public function show($slug)
    {
        $answers = [
            'a',
            'b',
            'c'
        ];
        dump($this);

        return $this->render('question/show.html.twig', [
            'question' => ucwords(str_replace('-', ' ', $slug)),
            'answers' => $answers
        ]);
        #return new Response(sprintf("The question: %s", $slug));
    }
}

Installing the twig package that allows us to work better with HTML templates

To avoid embedding HTML code in our PHP code, we can install twig, which provides a framework of templates to build several sites quickly.

composer require template;

Enriching the development experience

To debug in a better way our applications, we install the following two groups of packages that provide several debugging features, including a logging mechanism.

composer require profiler --dev;
composer require debug;

Avoid hardcoding assets in the HTML DOM

To avoid hardcoding items in your DOM (and forcing yourself to remember to edit them depending on the deployment options you are using), you can use the asset package that will handle most of those issues.

composer require symfony/asset;

Serializing more items and objects to JSON and XML

To enrich the power of API calls that return JSON or XML objects (like the code below)

return $this->json(/*...*/);

we can install the following serializer:

composer require symfony/serializer;

and be used as follows:

$serializer->serialize(
  $myObject,
  'json'
);

Develop using HTTPS / SSL for free

Although we are not super happy about installing local Certificate Authorities on our machines, we used the following commands to install the Symfony Certifying Authority certificate and enable HTTPS/SSL development without accepting a non-verified certificate in the browser each time.

sudo apt install libnss3-tools;
symfony server:ca:install;

If you do not install libnss3-tools, you will get the following warning:

$ symfony server:ca:install
You might have to enter your root password to install the local Certificate Authority certificate
Sudo password:
The local CA is now installed in the system trust store!
WARNING "certutil" is not available, so the CA can't be automatically installed in Firefox and/or Chrome/Chromium!
Install "certutil" with "apt install libnss3-tools" and re-run the command
                                                                                                        
 [OK] The local Certificate Authority is installed and trusted

After you install it, the message will change as follows:

$ symfony server:ca:install
The local CA is now installed in the Firefox and/or Chrome/Chromium trust store (requires browser restart)!
                                                                                                        
 [OK] The local Certificate Authority is installed and trusted

Install Webpack Encore for the assets

To install Webpack encore, we need yarn. To get yarn, we need npm. So we need the following installation steps:

sudo apt install npm;
sudo npm install --global yarn;

After these steps are successful, in the project folder, execute the following commands to allow the yarn to perform all necessary installations and then use encore to monitor the assets and rebuild its cache. The settings are depended on the file webpack.config.js.

yarn install;
yarn encore dev --watch;

Below, we present an example file of webpack.config.js.

var Encore = require('@symfony/webpack-encore');

// Manually configure the runtime environment if not already configured yet by the "encore" command.
// It's useful when you use tools that rely on webpack.config.js file.
if (!Encore.isRuntimeEnvironmentConfigured()) {
    Encore.configureRuntimeEnvironment(process.env.NODE_ENV || 'dev');
}

Encore
    // directory where compiled assets will be stored
    .setOutputPath('public/build/')
    // public path used by the web server to access the output path
    .setPublicPath('/build')
    // only needed for CDN's or sub-directory deploy
    //.setManifestKeyPrefix('build/')

    /*
     * ENTRY CONFIG
     *
     * Add 1 entry for each "page" of your app
     * (including one that's included on every page - e.g. "app")
     *
     * Each entry will result in one JavaScript file (e.g. app.js)
     * and one CSS file (e.g. app.css) if your JavaScript imports CSS.
     */
    .addEntry('app', './assets/js/app.js')
    //.addEntry('page1', './assets/js/page1.js')
    //.addEntry('page2', './assets/js/page2.js')

    // When enabled, Webpack "splits" your files into smaller pieces for greater optimization.
    .splitEntryChunks()

    // will require an extra script tag for runtime.js
    // but, you probably want this, unless you're building a single-page app
    .enableSingleRuntimeChunk()

    /*
     * FEATURE CONFIG
     *
     * Enable & configure other features below. For a full
     * list of features, see:
     * https://symfony.com/doc/current/frontend.html#adding-more-features
     */
    .cleanupOutputBeforeBuild()
    .enableBuildNotifications()
    .enableSourceMaps(!Encore.isProduction())
    // enables hashed filenames (e.g. app.abc123.css)
    .enableVersioning(Encore.isProduction())

    // enables @babel/preset-env polyfills
    .configureBabelPresetEnv((config) => {
        config.useBuiltIns = 'usage';
        config.corejs = 3;
    })

    // enables Sass/SCSS support
    //.enableSassLoader()

    // uncomment if you use TypeScript
    //.enableTypeScriptLoader()

    // uncomment to get integrity="..." attributes on your script & link tags
    // requires WebpackEncoreBundle 1.4 or higher
    //.enableIntegrityHashes(Encore.isProduction())

    // uncomment if you're having problems with a jQuery plugin
    //.autoProvidejQuery()

    // uncomment if you use API Platform Admin (composer req api-admin)
    //.enableReactPreset()
    //.addEntry('admin', './assets/js/admin.js')
;

module.exports = Encore.getWebpackConfig();

Some settings for PHPStorm by JetBrains

Since the IDE we are using for PHP development is PHPStorm, we installed the recommended plugins for Symfony to it. In the following image, we list the three plugins that we installed.

Specifically, we installed:

Symfony Support
PHP Annotations
PHP Toolbox

After installing the three plugins, we navigated to the Symfony Plugin settings (which you can find either using the search functionality or under the menu: Languages & Frameworks > PHP > Symfony).

From there, we clicked on the Enable Plugin for this Project and then changed the Web Directory from web to public.

FFmpeg tiny cheat sheet

6 January 2022 in Applications tagged audio / concat / copy / export / ffmpeg / ffprobe / fps / frame rate / frames / hstack / libmp3lame / libx264 / merge by Tux

We assume that the user has set the video filename to the variable named $video in the following commands.

FFmpeg export audio from any video to mp3

ffmpeg -i "$video" -vn -c:a libmp3lame -y "$audio";

FFmpeg export frames from video to images

ffmpeg -i "$video" "$frames_folder/%08d.ppm";

Retrieve the frame rate from the input video

#To view it on screen
ffprobe -v 0 -of csv=p=0 -select_streams v:0 -show_entries stream=r_frame_rate "$video";
#To assign it to a variable use the following
frame_rate=`ffprobe -v 0 -of csv=p=0 -select_streams v:0 -show_entries stream=r_frame_rate "$video"`;

To create a video out of a folder with frames/images and an audio file.

ffmpeg -framerate "$frame_rate" -i "$frames_folder/%08d.ppm" -i "$audio" -pix_fmt yuv420p -acodec copy -y "$output_video";
#To set a custom starting index for the frames you can use the -start_number argument
ffmpeg -start_number 62 -framerate "$frame_rate" -i "$frames_folder/%08d.ppm" -i "$audio" -pix_fmt yuv420p -acodec copy -y "$output_video";
#To use the MP4 coded use -vcodec libx264
ffmpeg -framerate "$frame_rate" -i "$frames_folder/%08d.ppm" -i "$audio" -vcodec libx264 -pix_fmt yuv420p -acodec copy -y "$output_video";

To merge an audio less video with an audio file

ffmpeg -i "$no_audio_video" -i "$audio" -shortest -vcodec copy -acodec copy "$output_video";

To change the frame rate of a video

ffmpeg -i "$video" -filter:v fps=20 "$output_video";

To merge two videos side by side

ffmpeg -i "$left_video" -i "$right_video" -filter_complex hstack "$output_video";

Concatenate multiple videos into one

The easiest way without writing huge commands is the following: First, create a file named parts.txt and add content similar to what we list below:

#Lines starting with # will be ignored
file 'part00-03.mp4'
file 'part04.mp4'
file 'part05-07.mp4'
file 'part08-09.mp4'
file 'part10.mp4'
file 'part11-13.mp4'

Then execute the following command to concatenate all those videos into one:

ffmpeg -f concat -safe 0 -i parts.txt -c copy "$output_video";

Speed up a video

Using the following command, you can speed up a video by dropping excess frames:

ffmpeg -i "$video" -filter:v "setpts=0.5*PTS" "$output_video";

The above example will double the speed (the value 0.5 controls it.)

To speed the video up without losing frames, you can increase the FPS value of the output video. To retrieve the frame rate, please see the command that was posted earlier.

ffmpeg -i "$video" -r 80 -filter:v "setpts=0.25*PTS" "$output_video";

In the second example, we assumed that the input video had 20 frames per second. Using the 0.25 value, we decided to speed the video up by a factor of 4. To preserve the input frames, we increased the frame rate from 20 to 80 using the parameter -r.