Google’s Foo.bar: Distract the Guards

Distract the Guards
===================

The time for the mass escape has come, and you need to distract the guards so that the bunny prisoners can make it out! Unfortunately for you, they’re watching the bunnies closely. Fortunately, this means they haven’t realized yet that the space station is about to explode due to the destruction of the LAMBCHOP doomsday device. Also fortunately, all that time you spent working as first a minion and then a henchman means that you know the guards are fond of bananas. And gambling. And thumb wrestling.

The guards, being bored, readily accept your suggestion to play the Banana Games.

You will set up simultaneous thumb wrestling matches. In each match, two guards will pair off to thumb wrestle. The guard with fewer bananas will bet all their bananas, and the other guard will match the bet. The winner will receive all of the bet bananas. You don’t pair off guards with the same number of bananas (you will see why, shortly). You know enough guard psychology to know that the one who has more bananas always gets over-confident and loses. Once a match begins, the pair of guards will continue to thumb wrestle and exchange bananas, until both of them have the same number of bananas. Once that happens, both of them will lose interest and go back to guarding the prisoners, and you don’t want THAT to happen!

For example, if the two guards that were paired started with 3 and 5 bananas, after the first round of thumb wrestling they will have 6 and 2 (the one with 3 bananas wins and gets 3 bananas from the loser). After the second round, they will have 4 and 4 (the one with 6 bananas loses 2 bananas). At that point they stop and get back to guarding.

How is all this useful to distract the guards? Notice that if the guards had started with 1 and 4 bananas, then they keep thumb wrestling! 1, 4 -> 2, 3 -> 4, 1 -> 3, 2 -> 1, 4 and so on.

Now your plan is clear. You must pair up the guards in such a way that the maximum number of guards go into an infinite thumb wrestling loop!

Write a function answer(banana_list) which, given a list of positive integers depicting the amount of bananas the each guard starts with, returns the fewest possible number of guards that will be left to watch the prisoners. Element i of the list will be the number of bananas that guard i (counting from 0) starts with.

The number of guards will be at least 1 and not more than 100, and the number of bananas each guard starts with will be a positive integer no more than 1073741823 (i.e. 2^30 -1). Some of them stockpile a LOT of bananas.

Languages
=========

To provide a Python solution, edit solution.py
To provide a Java solution, edit solution.java

Test cases
==========

Inputs:
(int list) banana_list = [1, 1]
Output:
(int) 2

Inputs:
(int list) banana_list = [1, 7, 3, 21, 13, 19]
Output:
(int) 0

Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

You are not authorised to read all content in this post.

Please login…

Google’s Foo.bar: Doomsday Fuel

I tried a simple way in my very first solution, only two test cases passed. Then I google’d other ppl’s test cases, and found this.

This challenge is about mathematics, not traditional algorithms. Thanks to this, I learned Markov Chains and Absorbing Markov Chains. Thanks to @patrickJMT for his videos on youtube.

All test cases, someone posted on pastebin.com

You are not authorised to read all content in this post.

Please login…

另类方法劫持手机流量

实际上看,CharlesProxy并不能100%地“劫持”到手机的https流量,说“劫持”可能不太合适,因为CharlesProxy根本都不把这个443端口的请求在请求列表里显示出来。

这次玩的是GameLoft的Asphalt Xtreme,从google play store下载下来玩后,发现游戏的免费门槛太高了,随便玩玩不消费就进行不下去。
之前玩GameLoft的游戏改数据,都是iPhone下备份数据,修改存档,因为那些游戏有存档。但是这次主要用了Android,且没有root。试过iOS的版本,文档里没看到明文数据(txt/bin都没有)。本来想找个游戏修改器试试,后来没继续下去。

具体选型上,我是在EdgeRouter Lite上跑了个redsocks。因为是临时方案,所以不考虑使用EdgeOS/VyOS的配置语法,而直接使用了iptables。
协议分析和数据劫持,使用了CharlesProxy,因为CharlesProxy支持socks代理,还自带”Rewrite”功能,可以做简单字符串替换和正则替换。

环境:
路由 EdgeRouter Lite 固件1.9.1,IP 192.168.1.1,基于debian wheezy
Redsocks,0.4+dfsg-1,下载地址 https://packages.debian.org/wheezy/redsocks

电脑 MacBook Pro macOS 12 + CharlesProxy 4.x, IP 192.168.1.20,HTTP端口8888,Socks端口8889

手机 Mate 9,IP 192.168.1.40;

路由端

ERL是mips/mips64,从debian官网下载mips版的deb,直接 dpkg -i 安装即可。如果路由上没有libevent,还得下载装一下。
安装好redsocks后,修改 /etc/default/redsocks,修改START=yes。
直接基于 /etc/redsocks.conf 修改

改local_ip的原因是因为我iptables偷懒了。反正用完就关,无所谓。

使用 /etc/init.d/redsocks start启动服务。

iptables
只劫持了来自 192.168.1.40 的tcp 443的流量,修改到了12345端口。

开启CharlesProxy的Socks服务
Proxy菜单 -> Proxy Settings… -> Proxies
勾选“Enable SOCKS proxy”,Port“8889”,勾选“Enable HTTP proxying over SOCKS”和“Include default HTTP ports(80,443,8080,8443)”。

由于默认状态下,CharlesProxy列表里出现的都是IP,没有域名,所以简单粗暴地对所有的443端口开启SSL proxy。
Proxy菜单 -> SSL Proxy Settings… -> SSL Proxying
直接Add一个 Host=*,Port=443的项目,并启用。用完就关掉。

接下来就是Rewrite的了,在看到流量之前就不用考虑了。
工具在 Tools菜单里就能看到。

TCPDUMP Capture Netlink Packets

I’m writing a Wireshark Dissector for IPSET’s protocol. Commands below are to capture netlink packets using tcpdump.