THE REINSURANCE ACTUARY
  • Blog
  • Project Euler
  • Category Theory
  • Disclaimer

Solving the 2015 GCHQ Christmas Puzzle part 1

3/1/2016

 

This year GCHQ released a Christmas Puzzle, in this post I'll show you how to solve the series of puzzles, and also, the thought process that I used to get to the solutions.

If you would like to attempt to solve the puzzle yourself then here is the link to the first part of the puzzle. The solution to the first part will then lead to the second part of the puzzle. In total there are five parts.
http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx

From the GCHQ website:

"In this type of grid-shading puzzle, each square is either black or white. Some of the black squares have already been filled in for you.

Each row or column is labelled with a string of numbers. The numbers indicate the length of all consecutive runs of black squares, and are displayed in the order that the runs appear in that line. For example, a label "2 1 6" indicates sets of two, one and six black squares, each of which will have at least one white square separating them."
Picture
I decided to solve this puzzle in excel. The main reason for this was that I wanted to be able to fill in squares automatically rather than shading them by hand. I've posted a link to an excel file below which matches the start of the puzzle. In my version if you press Ctrl+a then the selected cell will turn black, and if you press ctrl+d then the selected cell will turn blue. I'll explain the use of blue cells later.
gchq_qr.xlsm
File Size: 19 kb
File Type: xlsm
Download File

 The first step to solving this puzzle is to count the number of rows and columns in the grid. In this case we have a 25 by 25 grid. In excel I then calculated the minimum number of cells required for each row and column. For example, the third column is listed as 1,3,1,3,1,3,1,3,1. Since there must be a blank space in between each block of black cells, this combination must take up a minimum of 25 cells but since there are only 25 cells in the column we now know which cells in this column need to be coloured black. We can now go ahead and fill in this column. We also know that the spaces in between the blocks of black cells need to be blank, to signify this we can colour these cells blue. Repeating this process allows us to complete 3 columns and 2 rows.

The next step is to look at rows and columns which have high minimum values but which are less than 25 but still high. For example, looking at the first row, it is listed as 7,3,1,1,7 with a minimum of 23. Since the first two blocks on either side are 7 long, cells 17:23 must be coloured in as a minimum, but as a maximum cells 19:25 must be filled in. Since there is an overlap between these two we can colour in the cells in the overlap. Here is an image demonstrating this. There are three copies of the first row, the first row contains the minimum cells and the second row contains the maximum cells. I have then coloured the overlap on the blocks of seven in black.
Picture
Filling in the first cell in a row is also useful as it lets us immediately use the information about that column. For example we know that the third cell in the first row is black, looking at the listing for this column we see that the first block of blacks is a 1, therefore the cell below it in the second column must be blank and can be filled in blue. Using this these techniques we eventually complete the grid. Giving the following image.
Picture
You may recognise this kind of pattern as a QR code. A QR Code is a 2 dimensional bar code. I downloaded a QR reader to my phone and scanned the image which takes you to the following url:
http://www.gchq.gov.uk/puzz/Pages/index.aspx

Your comment will be posted after it is approved.


Leave a Reply.

    Author

    ​​I work as an actuary and underwriter at a global reinsurer in London.

    I mainly write about Maths, Finance, and Technology.
    ​
    If you would like to get in touch, then feel free to send me an email at:

    ​LewisWalshActuary@gmail.com

      Sign up to get updates when new posts are added​

    Subscribe

    RSS Feed

    Categories

    All
    Actuarial Careers/Exams
    Actuarial Modelling
    Bitcoin/Blockchain
    Book Reviews
    Economics
    Finance
    Forecasting
    Insurance
    Law
    Machine Learning
    Maths
    Misc
    Physics/Chemistry
    Poker
    Puzzles/Problems
    Statistics
    VBA

    Archives

    March 2023
    February 2023
    October 2022
    July 2022
    June 2022
    May 2022
    April 2022
    March 2022
    October 2021
    September 2021
    August 2021
    July 2021
    April 2021
    March 2021
    February 2021
    January 2021
    December 2020
    November 2020
    October 2020
    September 2020
    August 2020
    May 2020
    March 2020
    February 2020
    January 2020
    December 2019
    November 2019
    October 2019
    September 2019
    April 2019
    March 2019
    August 2018
    July 2018
    June 2018
    March 2018
    February 2018
    January 2018
    December 2017
    November 2017
    October 2017
    September 2017
    June 2017
    May 2017
    April 2017
    March 2017
    February 2017
    December 2016
    November 2016
    October 2016
    September 2016
    August 2016
    July 2016
    June 2016
    April 2016
    January 2016

  • Blog
  • Project Euler
  • Category Theory
  • Disclaimer