Google Code Jam 2016 Round 1A Problem C in J language

You are a teacher at the brand new Little Coders kindergarten. You have N kids in your class, and each one has a different student ID number from 1 through N. Every kid in your class has a single best friend forever (BFF), and you know who that BFF is for each kid. BFFs are not necessarily reciprocal -- that is, B being A's BFF does not imply that A is B's BFF.

Your lesson plan for tomorrow includes an activity in which the participants must sit in a circle. You want to make the activity as successful as possible by building the largest possible circle of kids such that each kid in the circle is sitting directly next to their BFF, either to the left or to the right. Any kids not in the circle will watch the activity without participating.

What is the greatest number of kids that can be in the circle?

继续阅读Google Code Jam 2016 Round 1A Problem C in J language

Google Code Jam 2016 Round 1A Problem B in J language

When Sergeant Argus's army assembles for drilling, they stand in the shape of an N by square grid, with exactly one soldier in each cell. Each soldier has a certain height.

Argus believes that it is important to keep an eye on all of his soldiers at all times. Since he likes to look at the grid from the upper left, he requires that:

  • Within every row of the grid, the soldiers' heights must be in strictly increasing order, from left to right.
  • Within every column of the grid, the soldiers' heights must be in strictly increasing order, from top to bottom.

Although no two soldiers in the same row or column may have the same height, it is possible for multiple soldiers in the grid to have the same height.

Since soldiers sometimes train separately with their row or their column, Argus has asked you to make a report consisting of 2*N lists of the soldiers' heights: one representing each row (in left-to-right order) and column (in top-to-bottom order). As you surveyed the soldiers, you only had small pieces of paper to write on, so you wrote each list on a separate piece of paper. However, on your way back to your office, you were startled by a loud bugle blast and you dropped all of the pieces of paper, and the wind blew one away before you could recover it! The other pieces of paper are now in no particular order, and you can't even remember which lists represent rows and which represent columns, since you didn't write that down.

You know that Argus will make you do hundreds of push-ups if you give him an incomplete report. Can you figure out what the missing list is?

继续阅读Google Code Jam 2016 Round 1A Problem B in J language

A rather marvelous means to send data anonymously via fake DNS query

前几天freebuf上出现了一篇文章,黑暗幽灵(DCM)木马详细分析,这个木马为了防止被直接找出服务器地址,在上传用户数据时伪装成了DNS查询,然后在关键节点捕获带有特定标识的网络包后进行转发。

抛开一切,不得不说这样的想法还是很好玩。于是就来写了个demo实验了一下。

假定我们伪装成查询www.google.com的IPv4地址,实际发送的数据是nise DNS query

继续阅读A rather marvelous means to send data anonymously via fake DNS query

Google Code Jam 2016 Round 1A Problem A in J language

On the game show The Last Word, the host begins a round by showing the contestant a string S of uppercase English letters. The contestant has a whiteboard which is initially blank. The host will then present the contestant with the letters of S, one by one, in the order in which they appear in S. When the host presents the first letter, the contestant writes it on the whiteboard; this counts as the first word in the game (even though it is only one letter long). After that, each time the host presents a letter, the contestant must write it at the beginning or the end of the word on the whiteboard before the host moves on to the next letter (or to the end of the game, if there are no more letters).


For example, for S = CAB, after writing the word Con the whiteboard, the contestant could make one of the following four sets of choices:

  • put the A before C to form AC, then put the B before AC to form BAC
  • put the A before C to form AC, then put the B after AC to form ACB
  • put the A after C to form CA, then put the B before CA to form BCA
  • put the A after C to form CA, then put the B after CA to form CAB

继续阅读Google Code Jam 2016 Round 1A Problem A in J language

Quinary Search Tree

update (2016-04-05):
    Ternary Search Tree (improved)的实现有误,将稍后更正。

There is always a topic that how to store a set of strings. Throughout the years, many kinds of data structure had been proposed and applied, for instance, hash tables, binary search tree, digital search tree, ternary search tree and so on and so forth.

如何存储一组字符串总是一个经久不衰的话题。在这些年间,有许多种不同的数据结构不断被提出和应用,例如哈希表、二分搜索树、数字查找树、三元搜索树等等。

Let's begin with ternary search tree which is proposed by Jon and Robert at Pricenton[1]. There is one more pointer in the node compared with binary search tree, and it's the exactly minor change that not only makes it combine the time efficiency of digital tries with the space efficiency of binary search trees, but also provides more features like prefix search and fuzz search.

让我们从三元搜索树开始,它是由Jon和Robert在Pricenton[1]提出的。和二分搜索树相比起来,它的每个节点中多了一个指针,也正是这么一个小小的改动,不仅使它结合了数字查找树的时间效率和二分搜索树的空间效率,还使得它提供了诸如前缀搜索和模糊搜索这样的特性。

But can we make it more efficient in time with a tolerable space increment? We need to analyse the algorithm and the data structure of ternary search tree.

但是我们能在可容忍的空间使用增加上,进一步提高它的时间效率吗?我们需要分析三元搜素树的算法与结构。

继续阅读Quinary Search Tree