King - Bitesize Brilliance. Kingsize Talents. Supersize Opportunities. King makes great games for social and mobile platforms that offer fun, bitesize entertainment experiences for everyone to enjoy.

close

Codes

Error correcting codes are used in a wide variety of applications ranging from satellite communication to music CDs. The idea is to encode a binary string of length k as a binary string of length n>k, called a codeword such that even if some bit(s) of the encoding are corrupted (if you scratch on your CD for instance), the original k-bit string can still be recovered. There are three important parameters associated with an error correcting code: the length of codewords (n), the dimension (k) which is the length of the unencoded strings, and finally the minimum distance (d) of the code.

Distance between two codewords is measured as hamming distance, i.e., the number of positions in which the codewords differ: 0010 and 0100 are at distance 2. The minimum distance of the code is the distance between the two different codewords that are closest to each other.

Linear codes are a simple type of error correcting codes with several nice properties. One of them being that the minmum distance is the smallest distance any non-zero codeword has to the zero codeword (the codeword consisting of n zeros always belongs to a linear code of length n).

Another nice property of linear codes of length n and dimension k is that they can be described by an n×k generator matrix of zeros and ones. Encoding a k-bit string is done by viewing it as a column vector and multiplying it by the generator matrix. The example below shows a generator matrix and how the string 1001 is encoded.

Quest docs > graph.png

Matrix multiplication is done as usual except that additon is done modulo 2 (i.e., 0+1=1+0=1 and 0+0=1+1=0). The set of codewords of this code is then simply all vectors that can be obtained by encoding all k-bit strings in this way.

Write a program to calculate the minimum distance for several linear error correcting codes of length at most 30 and dimension at most 15. Each code will be given as a generator matrix.

Input

You will be given several generator matrices as input. The first line contains an integer T indicating the number of test cases. The first line of each test case gives the parameters n and k where 1≤n≤30, 1≤k≤15 and n > k, as two integers separated by a single space. The following n lines describe a generator matrix. Each line is a row of the matrix and has k space separated entries that are 0 or 1.

Output

For each generator matrix output a single line with the minimum distance of the corresponding linear code.

Sample Input 1

Sample Output 1

2
7 4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
0 1 1 1
1 0 1 1
1 1 0 1
3 2
1 1
0 0
1 1
3
0


Submit your response

You can solve the quests in Java or c++. Input is read from stdin.

To submit your quest solution, send an email including your source code files as attachments to quests@king.com

Use the quest name in the subject line, and include your full name. Then sit back and wait for the response. It should only take a minute or so.

close

Get Shorty

Nils and Mikael are intergalaxial fighters as well as life long enemies. Now Nils has managed to capture the poor Mikael in his dark dungeons, and it is up to you to help Mikael escape with as much of his pride intact as possible.

The dungeons can be viewed as a set of corridors and intersections. Each corridor joins two intersections. There are no guards, traps, or locked doors in Nils’ dungeon. However, there is one obstacle which makes escaping from the dungeon a perilious project: in each corridor there is a sentry, armed with a factor weapon. (As is commonly known, a factor weapon with factor f reduces the size of its target to a factor f of its original size, e.g. if Mikael is 8 gobs large and is hit by a factor weapon with factor f=0.25 his size will be reduced to 2 gobs.)

Mikael will not be able to pass through a corridor without being hit by the factor weapon (but luckily enough, reloading the factor weapon takes enough time that the sentry will only have time to shoot him once as he passes through). It seems inevitable that Mikael will come out of this adventure a smaller man, but since the sentries have different factors in their factor weapons, his final size depends very much on the route he takes to the exit of the dungeons. Naturally, he would like to lose as little size as possible, and has asked you to help him accomplish that.

Input

Input consists of a series of test cases (at most 20). Each test case begins with a line consisting of two integers n,m separated by a single space, where 2≤n≤10000 is the number of intersections and 1≤m≤15000 is the number of corridors in Nils’ dungeon. Then follow m lines, each containing two integers x, y and a real number f (with at most four decimals), indicating that there is a corridor between intersections x and y, and that the factor weapon of the sentry in that corridor has factor 0≤f≤1. Intersections are numbered from 0 to n−1. Mikael always starts in intersection 0, and the exit is located in intersection n−1.

The last case will be followed by a case where n=m=0, which should not be processed.

Output

For each test case, output a single line containing a real number (with exactly four decimals) indicating how big a fraction of Mikael will be left when he reaches the exit, assuming he chooses the best possible route through the dungeon. You may assume that it is always possible for Mikael to reach the exit.

Sample Input 1

Sample Output 1

3 3
0 1 0.9
1 2 0.9
0 2 0.8
2 1
1 0 1
0 0
0.8100
1.0000


Submit your response

You can solve the quests in Java or c++. Input is read from stdin.

To submit your quest solution, send an email including your source code files as attachments to quests@king.com

Use the quest name in the subject line, and include your full name. Then sit back and wait for the response. It should only take a minute or so.

Are you ready for an engineering career at King?

watch video apply now

A little bit more about us

King makes great games that offer fun, bitesize entertainment experiences for everyone to enjoy. We put everything we have into creating snackable entertainment that is packed with excitement and energy, adding moments of magic every day. Our hits include Candy Crush Saga, Pet Rescue Saga, Bubble Witch Saga and Pyramid Solitaire Saga.

Sweden is the place to be

Whether it’s at the office, as part of a Dream Hack or over a friendly beer, the development community never stops pushing its members to go one better, which is probably why this corner of Scandinavia is becoming a by-word for forward-thinking engineering and game design. On top of that, it’s just a really cool place to live.

Stockholm is one of the world's most unique and beautiful capital cities. Built over 14 islands, it’s easy to get around and there’s a whole bunch of outdoor space to enjoy. In fact, depending on the time of year, you’ll be able to ski, ice-skate or swim right in the middle of the city. Our office is located in Vasastan, famous for its good restaurants, hip bars and interesting small boutiques - we think it’s the best spot in town.

Malmö is famous for its Turning Torso skyscraper. You can also find everything from awesome seascapes to underground art galleries, large stadium concerts by international stars to all the fun of Eurovision 2013. It’s all within walking distance of our beautiful office in the centre of the city. And because Malmö is only 20 minutes away from Copenhagen, you can go and visit The Little Mermaid any time you like.

Close

Which country are you in?

How did you hear about us?

Where do you fit in?

We’re looking for talented developers, whether you’re a mobile superstar with some serious C++ moves or a Flash whizkid, Stockholm and Malmö are the perfect spots to grow your expertise.

Behind the scenes at King it’s all about Hadoop clusters, immense scalability, agile teams, fast shipment, short projects and instant feedback. Above all, it’s about working together and having fun as part of a team that’s growing at an awesome rate.

If you think you’ve got what it takes to make the next hit game apply now!

img-slideshow1 img-slideshow2 img-slideshow3 img-slideshow4

Let's have some fun

We've got a couple of tricky quests here that we think should put your development skills to the test. If tackling problems like these is your kind of fun, then you’ll love it here. Succeeding in a quest will help you stand out if you want to join us.

Quest 01: Codes

Try your hand at writing a programme to calculate the minimum distance for several linear error correcting codes.

Quest 02: Get shorty

An intergalaxial jailbreak all comes down to your ability with factors (f). Can you plot a route to help Mikael escape?

And it gets better.....

TOYS AND TECH

From Big Data techniques to game-changing developments, we’re always working on something pioneering and exciting. And we’ll make sure you have all the tech goodies you need to forge ahead. We’ll even let you work on your hardware of choice, with whatever operating system you fancy. Mac, PC or Linux – it’s up to you.

PEOPLE AND PERKS

We believe anyone can have a great idea, so an open, friendly atmosphere is important to us. It’s probably a big part of why we achieve such high employee engagement scores and our people say they love working here. Little things like open plan offices, games rooms and free food and drink help too. As does working in small, agile teams and getting together for regular hackathons, games jams and international, office-wide away days.

LEARNING AND DEVELOPMENT

We take personal growth seriously. So as well as getting to grips with lots of awesome learning experiences, including access to training and well-stocked office libraries, you’ll find that ours is a culture of non-stop coaching. And when it comes to sharing expertise and knowledge, we’re about as open as it gets.

REWARDS AND RELOCATION

We’re big on healthy, happy employees and that approach starts before you even get the job. If we invite you to interview, we’ll fly you and your partner to Sweden to decide whether it’s the place for you. Once you’re on board, we’ll do what we can to make you feel at home. As well as a thorough induction, a competitive pay packet and great benefits, you’ll enjoy a generous relocation package that covers every last detail, from schools to housing assistance. We’ll also contribute to things like gym membership and set you up with insurance and pension consultations.

Thanks for your interest in careers at King.

Unfortunately you can't complete this job application on your mobile device. However, the good news is that we can send you a link to this site so that you can apply the next time you're on a desktop computer.

Please enter your email address below and we'll send you the link:

Mobile email

*Required Field

If you don't receive an email from us within a few minutes, please check your Spam or Bulk E-Mail folder.

Keep browsing on mobile