Thursday, October 29, 2015

How To See Characteristics of File Systems on Linux or Unix

http://www.cyberciti.biz/faq/linux-unix-display-characteristics-of-file-systems-command

How do I display the characteristics of file systems such as inodes, blocks, block size, file system name, state, lifetime writes, fsck status and more on Linux or Unix-like operating system?

You can use any one of the following command as per your Linux or Unix variant:
=> tune2fs command
=> lsfs command
=> fstyp command
=> df command

Linux show file system characteristics

Pass the -l option to list the contents of the filesystem superblock, including the current values of the parameters that can be set via tune2fs command. Type the following command:
# tune2fs -l /path/to/device | more
# tune2fs -l /dev/sda2 | grep
# tune2fs -l /dev/cciss/c1d1p1
# tune2fs -l /dev/mapper/data

Sample outputs:
Fig.01: tune2fs command in action
Fig.01: tune2fs command in action

You can use grep command to filter out information. For example, to see lifetime writes on ext4 filesystem, enter:
# tune2fs -l /dev/md0 | grep 'writes'
Sample outputs:
Lifetime writes:          90 GB

A note about HP-UX specific command

The fstyp command allows the user to determine the file system type of a mounted or unmounted file system. You need to pass special a device special file such as /dev/dsk/c1t6d0 and -v option to see information about the file system's superblock.
# fstyp -v /dev/vg02/lvol2
# fstyp -v /dev/dsk/c1t6d0 | more
# df -g /dev/vg02/lvol2

The 'df -g' command the entire structure of the file system.

A note about Solaris Unix to see the file system characteristics

Type the following command:
# fstyp -v /dev/md/dsk/d200
# fstyp -v /dev/md/dsk/d200 | more
# df -g /dev/md/dsk/d200

A note about AIX unix specific command

The lsfs command displays characteristics of file systems, such as mount points, automatic mounts, permissions, and file system size. The FileSystem parameter reports on a specific file system:
# lsfs -q /dev/hd10admin
# lsfs -q / | more

Linux Read CPU Temperature Sensor Chip Data Including Voltage and Fan Speed With lm-sensors

http://www.cyberciti.biz/faq/howto-linux-get-sensors-information

I wanted to monitor the temperature of my CPU and fan speed. How do I read CPU core temperature data including fan speed from a shell prompt under a Linux operating system? How do I monitor my Linux server cpu hardware and all sensor chips data using a command prompt on a Debian or Ubuntu?

You can use Linux hardware monitoring tool called lm_sensor. This tool provides some essential command line utilities for monitoring the hardware health of Linux systems containing hardware health monitoring hardware such as the LM78, LM75 and more.
This tool use the System Management Bus (SMBus or SMB), which is a simple two-wire bus, derived from I²C and used for communication with low-bandwidth devices on a motherboard, especially power related chips such as a laptop's rechargeable battery subsystem. Other devices might include temperature, fan, or voltage sensors; and lid switches. PCI add-in cards may connect to an SMBus segment.

Installation

The lm_sensors (also known as "sensors" or "lm-sensors") package may or may not be installed on your server or laptop:

Install lm_sensors on a CentOS / RHEL

Type the following yum command to install software on CentOS / RHEL / Fedora Linux (older version):
$ sudo yum install lm_sensors
Fig.01: Install lm_sensors using yum
Fig.01: Install lm_sensors using yum

Install lm_sensors on a Fedora

Type the following dnf command:
$ sudo dnf install lm_sensors
Fig.02: Install lm_sensors using dnf
Fig.02: Install lm_sensors using dnf

Install lm-sensors on a Debian / Ubuntu

Type the following apt-get command:
$ sudo apt-get install lm-sensors
Fig.03: Install lm-sensors using apt-get
Fig.03: Install lm-sensors using apt-get

Install lm-sensors on a OpenSuse/Suse

Type the following zypper command:
# zypper in sensors

Configure lm_sensors

To detect hardware monitoring chips, type the following command as the root user:
# sensors-detect
OR
$ sudo sensors-detect
Sample output:
# sensors-detect revision 4609 (2007-07-14 09:28:39 -0700)

This program will help you determine which kernel modules you need
to load to use lm_sensors most effectively. It is generally safe
and recommended to accept the default answers to all questions,
unless you know what you're doing.

We can start with probing for (PCI) I2C or SMBus adapters.
Do you want to probe now? (YES/no):
Probing for PCI bus adapters...
Use driver `i2c-i801' for device 0000:00:1f.3: Intel 82801G ICH7

We will now try to load each adapter module in turn.
Module `i2c-i801' already loaded.
If you have undetectable or unsupported adapters, you can have them
scanned by manually loading the modules before running this script.

To continue, we need module `i2c-dev' to be loaded.
Do you want to load `i2c-dev' now? (YES/no):
Module loaded successfully.

We are now going to do the I2C/SMBus adapter probings. Some chips may
be double detected; we choose the one with the highest confidence
value in that case.
If you found that the adapter hung after probing a certain address,
you can specify that address to remain unprobed.

Next adapter: saa7133[0] (i2c-0)
Do you want to scan it? (YES/no/selectively):
Client found at address 0x47
Handled by driver `ir-kbd-i2c' (already loaded), chip type `Pinnacle PCTV'
    (note: this is probably NOT a sensor chip!)
Client found at address 0x4b
Handled by driver `tuner' (already loaded), chip type `tda8290+75a'
    (note: this is probably NOT a sensor chip!)
Client found at address 0x50
Probing for `Analog Devices ADM1033'...                     No
Probing for `Analog Devices ADM1034'...                     No
Probing for `SPD EEPROM'...                                 No
Probing for `EDID EEPROM'...                                No

Next adapter: SMBus I801 adapter at 4000 (i2c-1)
Do you want to scan it? (YES/no/selectively):
Client found at address 0x2e
Probing for `Myson MTP008'...                               No
Probing for `National Semiconductor LM78'...                No
Probing for `National Semiconductor LM78-J'...              No
Probing for `National Semiconductor LM79'...                No
Probing for `National Semiconductor LM80'...                No
Probing for `National Semiconductor LM85 or LM96000'...     No
Probing for `Analog Devices ADM1027, ADT7460 or ADT7463'... No
Probing for `SMSC EMC6D100, EMC6D101 or EMC6D102'...        No
Probing for `Analog Devices ADT7462'...                     No
Probing for `Analog Devices ADT7467 or ADT7468'...          No
Probing for `Analog Devices ADT7470'...                     No
Probing for `Analog Devices ADT7473'...                     No
Probing for `Analog Devices ADT7475'...                     No
Probing for `Analog Devices ADT7476'...                     No
Probing for `Andigilog aSC7611'...                          No
Probing for `Andigilog aSC7621'...                          Success!
    (confidence 5, driver `to-be-written')
Probing for `National Semiconductor LM87'...                No
Probing for `National Semiconductor LM93'...                No
Probing for `Winbond W83781D'...                            No
Probing for `Winbond W83782D'...                            No
Probing for `Winbond W83792D'...                            No
Probing for `Winbond W83793R/G'...                          No
Probing for `Winbond W83791SD'...                           No
Probing for `Winbond W83627HF'...                           No
Probing for `Winbond W83627EHF'...                          No
Probing for `Winbond W83627DHG'...                          No
Probing for `Asus AS99127F (rev.1)'...                      No
Probing for `Asus AS99127F (rev.2)'...                      No
Probing for `Asus ASB100 Bach'...                           No
Probing for `Winbond W83L785TS-S'...                        No
Probing for `Analog Devices ADM9240'...                     No
Probing for `Dallas Semiconductor DS1780'...                No
Probing for `National Semiconductor LM81'...                No
Probing for `Analog Devices ADM1026'...                     No
Probing for `Analog Devices ADM1025'...                     No
Probing for `Analog Devices ADM1024'...                     No
Probing for `Analog Devices ADM1029'...                     No
Probing for `Analog Devices ADM1030'...                     No
Probing for `Analog Devices ADM1031'...                     No
Probing for `Analog Devices ADM1022'...                     No
Probing for `Texas Instruments THMC50'...                   No
Probing for `Analog Devices ADM1028'...                     No
Probing for `ITE IT8712F'...                                No
Probing for `SMSC DME1737'...                               No
Probing for `Fintek F75373S/SG'...                          No
Probing for `Fintek F75375S/SP'...                          No
Probing for `Fintek F75387SG/RG'...                         No
Probing for `Winbond W83791D'...                            No
Client found at address 0x44
Probing for `Maxim MAX6633/MAX6634/MAX6635'...              No
Client found at address 0x50
Probing for `Analog Devices ADM1033'...                     No
Probing for `Analog Devices ADM1034'...                     No
Probing for `SPD EEPROM'...                                 Yes
    (confidence 8, not a hardware monitoring chip)
Probing for `EDID EEPROM'...                                No

Some chips are also accessible through the ISA I/O ports. We have to
write to arbitrary I/O ports to probe them. This is usually safe though.
Yes, you do have ISA I/O ports even if you do not have any ISA slots!
Do you want to scan the ISA I/O ports? (YES/no):
Probing for `National Semiconductor LM78' at 0x290...       No
Probing for `National Semiconductor LM78-J' at 0x290...     No
Probing for `National Semiconductor LM79' at 0x290...       No
Probing for `Winbond W83781D' at 0x290...                   No
Probing for `Winbond W83782D' at 0x290...                   No
Probing for `Silicon Integrated Systems SIS5595'...         No
Probing for `VIA VT82C686 Integrated Sensors'...            No
Probing for `VIA VT8231 Integrated Sensors'...              No
Probing for `IPMI BMC KCS' at 0xca0...                      No
Probing for `IPMI BMC SMIC' at 0xca8...                     No

Some Super I/O chips may also contain sensors. We have to write to
standard I/O ports to probe them. This is usually safe.
Do you want to scan for Super I/O sensors? (YES/no):
Probing for Super-I/O at 0x2e/0x2f
Trying family `National Semiconductor'...                   No
Trying family `SMSC'...                                     Yes
Found `SMSC LPC47M182 Super IO Fan Sensors'
    (but not activated)
Probing for Super-I/O at 0x4e/0x4f
Trying family `National Semiconductor'...                   No
Trying family `SMSC'...                                     No
Trying family `VIA/Winbond/Fintek'...                       No
Trying family `ITE'...                                      No

Some CPUs or memory controllers may also contain embedded sensors.
Do you want to scan for them? (YES/no):
AMD K8 thermal sensors...                                   No
Intel Core family thermal sensor...                         Success!
    (driver `coretemp')
Intel AMB FB-DIMM thermal sensor...                         No

Now follows a summary of the probes I have just done.
Just press ENTER to continue: 

Driver `to-be-written' (should be inserted):
  Detects correctly:
  * Bus `SMBus I801 adapter at 4000'
    Busdriver `i2c-i801', I2C address 0x2e
    Chip `Andigilog aSC7621' (confidence: 5)

Driver `coretemp' (should be inserted):
  Detects correctly:
  * Chip `Intel Core family thermal sensor' (confidence: 9)

I will now generate the commands needed to load the required modules.
Just press ENTER to continue: 

To make the sensors modules behave correctly, add these lines to
/etc/modules:

#----cut here----
# I2C adapter drivers
i2c-i801
# Chip drivers
# no driver for Andigilog aSC7621 yet
coretemp
#----cut here----
Do you want to add these lines to /etc/modules automatically? (yes/NO)
This is an interactive program that will walk you through the process of scanning your system for various hardware monitoring chips, or sensors, supported by libsensors, or more generally by the lm_sensors tool suite. For my system coretemp and i2c-i801 driver need to loaded in order to see sensors data. Type 'YES" to update /etc/modules files. Now you need to reboot the box. Alternatively, you can load all drivers using modprobe command:
# modprobe coretemp
# modprobe i2c-i801

How do I read sensors chip data such as temperature and fan speed?

Type the following command at shell prompt:
$ sensors
Sample output:
coretemp-isa-0000
Adapter: ISA adapter
Core 0:      +59°C  (high =  +100°C)                   
 
coretemp-isa-0001
Adapter: ISA adapter
Core 1:      +59°C  (high =  +100°C)                   
 
coretemp-isa-0002
Adapter: ISA adapter
Core 2:      +55°C  (high =  +100°C)                   
 
coretemp-isa-0003
Adapter: ISA adapter
Core 3:      +56°C  (high =  +100°C)
Here is another output from Intel xeon server box:
w83627hf-i2c-0-2d
Adapter: SMBus I801 adapter at 1100
VCore 1:   +4.08 V  (min =  +1.34 V, max =  +1.49 V)       ALARM
VCore 2:   +4.08 V  (min =  +1.34 V, max =  +1.49 V)       ALARM
+3.3V:     +4.08 V  (min =  +3.14 V, max =  +3.46 V)       ALARM
+5V:       +5.11 V  (min =  +4.73 V, max =  +5.24 V)
+12V:     +11.73 V  (min = +10.82 V, max = +13.19 V)
-12V:      +1.21 V  (min = -13.18 V, max = -10.88 V)       ALARM
-5V:       +2.24 V  (min =  -5.25 V, max =  -4.75 V)       ALARM
V5SB:      +5.51 V  (min =  +4.73 V, max =  +5.24 V)       ALARM
VBat:      +0.54 V  (min =  +2.40 V, max =  +3.60 V)       ALARM
fan1:        0 RPM  (min =    0 RPM, div = 2)
fan2:        0 RPM  (min = 2689 RPM, div = 2)              ALARM
fan3:        0 RPM  (min = 6553 RPM, div = 2)              ALARM
temp1:       -48°C  (high =    -1°C, hyst =   -25°C)   sensor = thermistor
temp2:     -48.0°C  (high =   +80°C, hyst =   +75°C)   sensor = thermistor
temp3:     -48.0°C  (high =   +80°C, hyst =   +75°C)   sensor = thermistor
vid:      +1.419 V  (VRM Version 11.0)
alarms:
beep_enable:
          Sound alarm enabled
w83627hf-isa-0290
Adapter: ISA adapter
VCore 1:   +4.08 V  (min =  +1.34 V, max =  +1.49 V)       ALARM
VCore 2:   +4.08 V  (min =  +1.34 V, max =  +1.49 V)       ALARM
+3.3V:     +4.08 V  (min =  +3.14 V, max =  +3.46 V)       ALARM
+5V:       +5.11 V  (min =  +4.73 V, max =  +5.24 V)
+12V:     +11.73 V  (min = +10.82 V, max = +13.19 V)
-12V:      +1.29 V  (min = -13.18 V, max = -10.88 V)       ALARM
-5V:       +2.24 V  (min =  -5.25 V, max =  -4.75 V)       ALARM
V5SB:      +5.48 V  (min =  +4.73 V, max =  +5.24 V)       ALARM
VBat:      +0.54 V  (min =  +2.40 V, max =  +3.60 V)       ALARM
fan1:        0 RPM  (min =    0 RPM, div = 2)
fan2:        0 RPM  (min = 2689 RPM, div = 2)              ALARM
fan3:        0 RPM  (min = 6553 RPM, div = 2)              ALARM
temp1:       -48°C  (high =    -1°C, hyst =   -25°C)   sensor = thermistor
temp2:     -48.0°C  (high =   +80°C, hyst =   +75°C)   sensor = thermistor
temp3:     -48.0°C  (high =   +80°C, hyst =   +75°C)   sensor = thermistor
vid:      +1.419 V  (VRM Version 11.0)
alarms:
beep_enable:
          Sound alarm enabled

Tip: Watch your sensors data in real time

Type the following NA command:
# watch sensors
OR
# watch -d sensors
Sample outputs:
Gif 01: Sensors in action
Gif 01: Sensors in action

Further recommended readings:

Updated for accuracy.

An Introduction to Tabled Logic Programming with Picat

http://www.linuxjournal.com/content/introduction-tabled-logic-programming-picat

Picat is a new logic-based programming language. In many ways, Picat is similar to Prolog, especially B-Prolog, but it has functions in addition to predicates, pattern-matching instead of unification in predicate heads, list comprehensions and optional destructive assignment. Knowing some Prolog helps when learning Picat but is by no means required.
According to the authors of the language, Picat is an acronym for:
  • Pattern-matching.
  • Imperative.
  • Constraints.
  • Actors.
  • Tabling.
Picat has a lot of interesting features, such as constraint logic programming support and interfaces to various solvers. In this article, I focus on one aspect of Picat: tabling and a tabling-based planner module.
First, let's install and learn some basics of Picat. Installing Picat is easy; you can download precompiled binaries for 32- and 64-bit Linux systems, as well as binaries for other platforms. If you want to compile it yourself, C source code is available under the Mozilla Public License. The examples here use Picat version 1.2, but newer or slightly older versions also should work.
After the installation, you can run picat from a command line and see Picat's prompt:

Picat 1.2, (C) picat-lang.org, 2013-2015.
Picat>
You can run commands (queries) interactively with this interface.
Let's start with the mandatory "Hello, World":

Picat> println("Hello, World!").
Hello, World!
yes
No real surprises here. The yes at the end means that Picat successfully executed the query.
For the next example, let's assign 2 to a variable:

Picat> X = 2.
X = 2
yes
Note the uppercase letter for the variable name; all variable names must start with a capital letter or an underscore (the same as in Prolog).
Next, assign symbols to the X variable (symbols are enclosed in single quotes; for many symbols, quotes are optional, and double-quoted strings, like the "Hello, World!" above, are lists of symbols):

Picat> X = a.
X = a
yes
Picat> X = 'a'.
X = a
yes
For capital-letter symbols, single quotes are mandatory (otherwise it will be treated as a variable name):

Picat> X = A.
A = X
yes
Picat> X = 'A'.
X = 'A'
yes
Note that the variable X in different queries (separated by a full stop) are completely independent different variables.

Lists

Next, let's work with lists:

Picat> X = [1, 2, 3, a].
X = [1,2,3,a]
yes
Lists are heterogeneous in Picat, so you can have numbers as the first three list elements and a symbol as the last element.
You can calculate the results of arithmetic expressions like this:

Picat> X = 2 + 2.
X = 4
yes
Picat> X = [1, a, 2 + 2].
X = [1,a,4]
yes

Picat> X = 2, X = X + 1.
no
This probably is pretty surprising for you if your background is in mainstream imperative languages. But from the logic point of view, it makes prefect sense: X can't be equal to X + 1.
Using := instead of = produces a more expected answer:

Picat> X = 2, X := X + 1.
X = 3
yes
The destructive assignment operator := allows you to override Picat's usual single-assignment "write once" policy for variables. It works in a way you'd expect from an imperative language.
You can use the [|] notation to get a "head" (the first element) and a "tail" (the rest of the elements) of a list:

Picat> X = [1, 2, 3], [Tail | Head] = X.
X = [1,2,3]
Tail = 1
Head = [2,3]
yes
You can use the same notation to add an element to the beginning of a list:

Picat> X = [1, 2, 3], Y = [0 | X].
X = [1,2,3]
Y = [0,1,2,3]
yes
Picat> X = [1, 2, 3], X := [0 | X].
X = [0,1,2,3]
yes
The first example creates a new variable Y, and the second example reuses X with the assignment operator.

TPK Algorithm

Although it's handy to be able to run small queries interactively to try different things, for larger programs, you probably will want to write the code to a file and run it as a script.
To learn some of Picat's syntactical features, let's create a program (script) for a TPK algorithm. TPK is an algorithm proposed by D. Knuth and L. Pardo to show the basic syntax of a programming language beyond the "Hello, World!" program. The algorithm asks a user to enter 11 real numbers (a0...a10). After that, for i = 10...0 (in that order), the algorithm computes the value of an arithmetic function y = f(ai), and outputs a pair (i, y), if y <= 400 or (i, TOO LARGE) otherwise.

Listing 1. TPK


f(T) = sqrt(abs(T)) + 5 * T**3.
main =>
    N = 11,
    As = to_array([read_real() : I in 1..N]),
    foreach (I in N..-1..1)
        Y = f(As[I]),
        if Y > 400 then
            printf("%w TOO LARGE\n", I)
        else
            printf("%w %w\n", I, Y)
        end
    end.
First, the code defines a function to calculate the value of f (a function in Picat is a special kind of a predicate that always succeeds with a return value). The main predicate follows (main is a default name for the predicate that will be run during script execution). The code uses list comprehension (similar to what you have in Python, for example) to read the 11 space-separated real numbers into an array As. The foreach loop iterates over the numbers in the array; I goes from 11 to 1 with the step -1 (in Picat, array indices are 1-based). The loop body calculates the value of y for every iteration and prints the result using an "if-then-else" construct. printf is similar to the corresponding C language function; %w can be seen as a "wild card" control sequence to output values of different types.
You can save this program to a file with the .pi extension (let's call it tpk.pi), and then run it using the command picat tpk.pi. Input 11 space-separated numbers and press Enter.

Tabling

Now that you have some familiarity with the Picat syntax and how to run the scripts, let's proceed directly to tabling. Tabling is a form of automatic caching or memoization—results of previous computations can be stored to avoid unnecessary recomputation.
You can see the benefits of tabling by comparing two versions of a program that calculates Fibonacci numbers with and without tabling.
Listing 2 shows a naive recursive Fibonacci implementation in Picat.

Listing 2. Naive Fibonacci


fib(0) = 1.
fib(1) = 1.
fib(N) = F =>
  N > 1,
  F = fib(N - 1) + fib(N - 2).

main =>
  N = read_int(),
  println(fib(N)).
This naive implementation works, but it has an exponential running time. Computing the 37th Fibonacci number takes more than two seconds on my machine:

$ time echo 37 | picat fib_naive.pi
39088169
real 0m2.604s
Computing the 100th Fibonacci number would take this program forever!
But, you can add just one line (table) at the beginning of the program to see a dramatic improvement in running time.
Now you can get not only 37th Fibonacci number instantly, but even the 1,337th (and the answer will not suffer from overflow, because Picat supports arbitrary-length integers).
Effectively, with tabling, you can change the asymptotic running time from exponential to linear.
An even more useful feature is "mode-directed" tabling. Using it you can instruct Picat to store the minimal or the maximal of all possible answers for a non-deterministic goal. This feature is very handy when implementing dynamic programming algorithms. However, that topic is beyond the scope of this article; see Picat's official documentation to learn more about mode-directed tabling.

The planner Module

Picat also has a tabling-based planner module, which can be used to solve artificial intelligence planning problems. This module provides a higher level of abstraction and declarativity.
To use the module, an application programmer has to specify action and final predicates.
The final predicate, in its simplest form, has only one parameter—the current state—and succeeds if the state is final.
The action predicate usually has several clauses—one for each possible action or group of related actions. This predicate has four parameters: current state, new state, action name and action cost.
Let's build a maze-solver using the planner module. The maze-solving program will read a maze map from the standard input and output the best sequence of steps to get to the exit. Here is an example map:

5 5
@.#..
=.#..
.##..
.#X..
.|...
The first line contains the dimensions of the maze: the number of rows R and columns C.
Next, R lines describe the rows of the maze. Here is the description of the map symbols:
  • @ — initial hero position.
  • . — an empty cell.
  • # — a permanent wall.
  • = — a key.
  • | — a closed door.
  • X — the exit.
The hero can move up, down, left and right (no diagonals) to any open cell (a cell without a wall or a closed door). The hero can pick up keys and open doors. Opening a door and moving into a newly open cell is considered one action. To open a door, the hero must have a key.
Because this is a magic maze, the key disappears after it opens a door. All keys are identical, so opening a door basically just decreases the number of keys the hero has by one.
The goal is to reach the exit using the minimum amount of energy. Moving to an open cell costs one energy unit, picking up a key costs one energy unit, and opening a door and moving to the cell previously occupied by that door costs two energy units.
Let's represent a state for this problem as a tuple (R, C, (ExitI, ExitJ), Walls, Doors, Keys, K, (HeroI, HeroJ)):
  • R and C are the number of rows and columns in the maze.
  • (ExitI, ExitJ) are the coordinates of the exit.
  • Walls is a list of the positions of all walls.
  • Doors is a list of the positions of all closed doors.
  • Keys is a list of the positions of not-yet-picked-up keys.
  • K is the number of keys the hero has.
  • (HeroI, HeroJ) are coordinates of the hero's position.
Let's first do some boring work of translating a textual representation of a maze to an initial state in the format defined before.
The main predicate is an imperative procedure in constructing an initial state from a textual representation of a maze: you read the input line by line, symbol by symbol, and then construct the lists of walls, doors and keys, as well as record the coordinates of the hero and the exit.

Listing 3. Read the Maze Description


main =>
  R = read_int(), C = read_int(),
  Walls = [], Doors = [], Keys = [],
  (ExitI, ExitJ) = (_, _),
  (HeroI, HeroJ) = (_, _),
  foreach (I in 1..R)
    Line = read_line(),
    foreach (J in 1..C)
      Char = Line[J],
      if Char == '@' then
        HeroI := I, HeroJ := J
      end,
      if Char == 'X' then
        ExitI := I, ExitJ := J
      end,
      if Char == '#' then
        Walls := [(I, J) | Walls]
      end,
      if Char == '|' then
        Doors := [(I, J) | Doors]
      end,
      if Char == '=' then
        Keys := [(I, J) | Keys]
      end
    end
  end,
  InitState = (R, C, (ExitI, ExitJ),
               Walls, Doors, Keys,
               0, (HeroI, HeroJ)),
  println(InitState).
Let's save this program to maze_read.pi, the maze description from above to maze.txt, and run the program (the output is split into several lines for clarity):

$ picat maze_read.pi < maze.txt
5,5,
(4,3),
[(4,2),(3,3),(3,2),(2,3),(1,3)],
[(5,2)],
[(2,1)],
0,1,1
So, you have the dimensions of the maze (5 by 5), the coordinates of the exit (4, 3), the list of the coordinates of all five walls, a one-element list of the closed doors and a one-element list of the keys available for picking up. The hero has 0 keys and starts in cell (1, 1).
Now that you have your state, you can define some predicates to solve the problem. First, the final predicate for the planner module:

final((_, _, (I, J), _, _, _, _, (I, J))) =>
  true.
The state is final when the hero is in the cell with the same coordinates as the exit cell. Variables with name _ are throw-away, "don't care" variables that are not required to have any specific value (Picat invents a different name for each _ behind the scenes, so they don't have to be equal either).
Next, describe the action to take a key if the hero is in a cell with one:

action(State, NewState, Action, Cost) ?=>
  (R, C, (ExitI, ExitJ), Walls, Doors, Keys,
    K, (HeroI, HeroJ)) = State,
    select((HeroI, HeroJ), Keys, NewKeys),
    Action = $take_key(HeroI, HeroJ),
    Cost = 1,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, Doors, NewKeys,
                K + 1, (HeroI, HeroJ)).
First you decompose the state into components, and then you try to select a key with the current coordinates of the hero from the Keys list. If there is such a key, this will succeed, and the rest of the keys will be assigned to "NewKeys"; otherwise, select fails, and Picat will break the execution of this action clause.
The name of the action is take_key, with the coordinates of the event in the parentheses (the $ instructs Picat to treat it literally, like a string, and not to try to execute as a function), and the cost is one energy unit.
The new state is almost the same as the old state, except that the number of keys the hero has is increased by one, and the current key no longer is available to pick up.
Besides picking up keys, there are two more possible actions: moving to an empty cell and moving to a cell with a door after opening it. It's a good idea to combine both these actions into one clause, because they share a lot of code used to select a new hero position and check whether it's within the maze boundary:

action(State, NewState, Action, Cost) =>
  (R, C, (ExitI, ExitJ), Walls, Doors, Keys,
    K, (HeroI, HeroJ)) = State,
  (
    Di = 0, Dj = 1
  ;
    Di = 0, Dj = -1
  ;
    Di = 1, Dj = 0
  ;
    Di = -1, Dj = 0
  ),
  NewHeroI = HeroI + Di,
  NewHeroJ = HeroJ + Dj,
  NewHeroI >= 1, NewHeroI <= R,
  NewHeroJ >= 1, NewHeroJ <= C,
  (
    % move to open cell
    not membchk((NewHeroI, NewHeroJ), Walls),
    not membchk((NewHeroI, NewHeroJ), Doors),
    Action = $move(NewHeroI, NewHeroJ),
    Cost = 1,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, Doors, Keys,
                K, (NewHeroI, NewHeroJ))
  ;
    % open a door and move to that cell
    K > 0,
    select((NewHeroI, NewHeroJ), Doors, NewDoors),
    Action = $open(NewHeroI, NewHeroJ),
    Cost = 2,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, NewDoors, Keys,
                K - 1, (NewHeroI, NewHeroJ))
  ).
Again, first you decompose the state into the components. Next, you try all possible new positions for the hero with non-deterministic disjunction: ;.
A position must be within the maze boundaries: I must be from 1 to R, and J must be from 1 to C. After that, there are two possibilities: move to an open cell, or open a door and move to that cell.
Moving to an open cell is possible only if there isn't a wall or a closed door at the desired position. Two not membchk lines verify this condition. If the condition is met, the action name is move, and the cost is one energy unit. The only change in the state is the hero's position.
Opening an door is possible if there is a door at the position and the hero has at least one key. The select line here is similar to the line for the take action, but now you select a door instead of a key. If the conditions are met, the action name is open, and the cost is two energy units. The new state is almost the same as the old state, but the door is removed from the list of doors, the number of keys the hero has is decreased by one, and the hero has moved to a new position.
To use the defined final and action predicates and find the plan, you need to change println(InitState) to best_plan_unbounded(InitState, Plan), println(Plan) in the main from the maze_read.pi program. (Note: best_plan_unbounded is one of the predicates of the planner module for finding best plans. This particular version uses memory to avoid re-exploring states, converting tree search in the space of all possible plans to graph search.)
Listing 4 shows the complete maze program.

Listing 4. Full Maze Program


import planner.

action(State, NewState, Action, Cost) ?=>
  (R, C, (ExitI, ExitJ), Walls, Doors, Keys,
    K, (HeroI, HeroJ)) = State,
    select((HeroI, HeroJ), Keys, NewKeys),
    Action = $take_key(HeroI, HeroJ),
    Cost = 1,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, Doors, NewKeys,
                K + 1, (HeroI, HeroJ)).

action(State, NewState, Action, Cost) =>
  (R, C, (ExitI, ExitJ), Walls, Doors, Keys,
    K, (HeroI, HeroJ)) = State,
  (
    Di = 0, Dj = 1
  ;
    Di = 0, Dj = -1
  ;
    Di = 1, Dj = 0
  ;
    Di = -1, Dj = 0
  ),

  NewHeroI = HeroI + Di,
  NewHeroJ = HeroJ + Dj,
  NewHeroI >= 1, NewHeroI <= R,
  NewHeroJ >= 1, NewHeroJ <= C,

  (
    % move to open cell
    not membchk((NewHeroI, NewHeroJ), Walls),
    not membchk((NewHeroI, NewHeroJ), Doors),
    Action = $move(NewHeroI, NewHeroJ),
    Cost = 1,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, Doors, Keys,
                K, (NewHeroI, NewHeroJ))
  ;
    % open a door and move to that cell
    K > 0,
    select((NewHeroI, NewHeroJ), Doors, NewDoors),
    Action = $open(NewHeroI, NewHeroJ),
    Cost = 2,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, NewDoors, Keys,
                K - 1, (NewHeroI, NewHeroJ))
  ).

final((_, _, (I, J), _, _, _, _, (I, J))) =>
  true.

main =>
  R = read_int(), C = read_int(),
  Walls = [], Doors = [], Keys = [],
  (ExitI, ExitJ) = (_, _),
  (HeroI, HeroJ) = (_, _),
  foreach (I in 1..R)
    Line = read_line(),
    foreach (J in 1..C)
      Char = Line[J],
      if Char == '@' then
        HeroI := I, HeroJ := J
      end,
      if Char == 'X' then
        ExitI := I, ExitJ := J
      end,
      if Char == '#' then
        Walls := [(I, J) | Walls]
      end,
      if Char == '|' then
        Doors := [(I, J) | Doors]
      end,
      if Char == '=' then
        Keys := [(I, J) | Keys]
      end
    end
  end,
  InitState = (R, C, (ExitI, ExitJ),
               Walls, Doors, Keys,
               0, (HeroI, HeroJ)),
  best_plan_unbounded(InitState, Plan),
  println(Plan).
After running it for the maze used above, you get an optimal plan (list of actions) to solve the maze (the output is split into several lines for clarity):

$ picat maze.pi < maze.txt
[
 move(2,1),
 take_key(2,1),
 move(3,1),
 move(4,1),
 move(5,1),
 open(5,2),
 move(5,3),move(4,3)
]
You can try to run this program with inputs of various sizes and with different features. For example, this input requires the hero to take a key to the right, then go left to get more keys, and then go right again to the exit:

1 10 ==|=|@=||X
Of course, you can improve the maze program in many different ways:
  • Better user interface: currently, the output is not very easy to read, and the program exits with an error if the maze is not solvable.
  • Sets or hash tables instead of lists: looking for a key or wall in a list requires linear time, while with a more appropriate data structure, it will be constant.
  • Adding a heuristic: the search could be improved with a heuristic to make it a variant of an IDA* algorithm.
  • New maze features: you could implement different kinds of keys, weapons, treasure and monsters.
Overall, Picat looks like a really good starting point for a journey into the realm of logic-based programming languages. It provides many of the goodies Prolog has, such as non-determinism and built-in depths-first search with backtracking, and at the same time, Picat allows you to fall back to convenient imperative concepts like destructive assignments and loops. Higher-level features, like tabling and the planner module, provide ways to write concise, declarative and efficient programs.

Resources

Picat: http://picat-lang.org
"Artificial intelligence planning with Picat" by Sergii Dymchenko: http://sdymchenko.com/blog/2015/01/31/ai-planning-picat
Hakan Kjellerstrand's Picat Page: http://www.hakank.org/picat
"Declaratively solving Google Code Jam problems with Picat" by Sergii Dymchenko and Mariia Mykhailova: http://arxiv.org/abs/1504.00977
"Combinatorial Search with Picat" by Neng-Fa Zhou: http://arxiv.org/abs/1405.2538

Wednesday, October 28, 2015

Extracting and Organizing with Bash

http://freedompenguin.com/articles/how-to/extracting-and-organizing-with-bash

Long week? Yeah, me too. I have my heavy metal Linux band in the motel room and no customers to attend to at the moment…let’s do some Bash scripting! Remember the “thumbnailing” script I did a few weeks ago? This is the script I use before doing thumbnails. It’s actually a bit more trippy and uses another script which I’ll cover in the next installment.
I begin by getting a temporary file setup:
  • #!/bin/bash
  • set -e
  • DateFile="/tmp/image-dates.$$"
  • [ -z "$DateFile" ] && echo "no datefile, bye." && exit 1
  • [ -f "$DateFile" ] && rm -f $DateFile
  • touch "$DateFile"
We have a guard: did we screw up our file name? That’s almost irrationally cautious, so you might feel justified in deleting that guard. The $$ symbol is a quick way to get your process ID (PID). You can use this for many things, but it is reasonably unique with low-frequency usage (that is, a few times a day).
65535Process
You can only have 65535 process IDs, and there are 86400 seconds a day, so if you approach one process a second, you’ll get repeats. If we find an identical date file, let’s delete it anyhow and create a new one. (POP QUIZ: tell me a one-liner that does this.)
Turn that metal up! We’re about to “headbang” through a crazy lead solo of string manipulation:
  • ls *.jpg *.dng *.bmp *.tiff *.jpeg \
  • *.JPG *.DNG *.BMP *.TIFF *.JPEG 2>/dev/null \
  • | while read F
  • do
  • G=$( echo -n "$F" | perl -pe 'y/[A-Z]/[a-z]/' )
  • cmd="mv -v $F $G"
  • $cmd
  • done
Yeah! Let’s crush some upper-case file names! Why the 2>/dev/null though? Have you ever done an “ls * .txt” command just to get everything in your directory listed and followed by a warning: .txt: file not found ? Yeah. That error message, or those TIFF or JPEG files you probably won’t have will all give you that message. It’s a safe message to discard into /dev/null.
devnull
We’re taking each file name F, and piping it into perl and feeding it into the Sarlacc jaws of the y/// translator. This y/// operator is the perl equivalent to the ‘tr’ command: it translates one character pattern to another character pattern. We’re forcing all upper-case alphabetic characters into lower case characters. Why? Type in caps much? (The bassist does, the bastard.) Extra credit: give me the shell command that replaces that perl command.
Now G is the transformed name, and we just move the file from the original F value to the new G value. (POP QUIZ: Why, oh why would I assemble a string of this command? Could this be evidence of an erased echo statement?) Extra Credit: make this command safer for filenames with spaces in them.
Drum solo! We’re going to rattle out some dates with another wee utility called ImgDate.sh:
  • ls *.{jpg,dng,bmp,tiff,jpeg,gif,png} 2>/dev/null \
  • | while read F
  • do
  • echo -n "$F " >> $DateFile
  • ~/bin/ImgDate.sh $F >> $DateFile
  • done
imagelist
Remember that the >> operator appends to files and echo -n prints stuff without a newline. Pay attention to spaces. We’re immediately going to use this output in a loop:
  • cat $DateFile | sort | uniq \
  • | while read D
  • do
  • echo "D $D"
  • imgfile=`echo "$D" | awk '{print $1}'`
  • imgdir=`echo "$D" | awk '{print $NF}'`
  • if [ ! -d "$imgdir" ]
  • then
  • mkdir -v $imgdir
  • fi
  • mv -v $imgfile $imgdir
  • done
What, another external program…awk? Isn’t that the sound your drummer makes after the fifth shot of Jagermeister? Hell yeah. Awk loves to toss out column values, so $1 is anything in the first column. What did we put in the first column of DateFile? Oh yeah…the drummer, no, the image file name. The last column is always $NF. Pop Quiz: Why not $2 in the second column? Warning: Don’t ask where why the drummer is called NF, he’s shy. Extra Credit #2: what if the file name has spaces in it?
tree
Now we need to clean the floor of our motel room: /tmp. Let’s wipe up $DateFile.
  • rm -f $DateFile
I’m going to drag the drummer off to the tour bus, but I’m going to leave you with one more puzzler: If I delete $DateFile at the end of this party, why do I bother deleting it at the start of the party as well? Think about it…